PHPを使ってグラフを描画する方法と、グラフを使うアルゴリズムを実行する方法について調べました
PHPにおけるグラフ描画とアルゴリズム (CodeZine)
グラフの描画にはImage_GraphVizを、アルゴリズムの実行にはStructures_Graphを使います。Image_GraphVizは、Graphvizを使うだけあってかなりのことができますが、Structures_Graphはまだまだ発展途上な感じです
本格的なアルゴリズムが必要な場合はMathematicaが便利です。それで性能が足りないときにはBoost Graph Libraryを使うといいでしょう