Graph theory tutorial in PHP

Question

Do you know a good online tutorial detailing solving graph problems using PHP, I'm also very interested in optimal graph data type representation in PHP (I assume that would be multidimensional arrays)?

I'm talking about mathematical graph theory (yes, vertices and edges). Google spits out loads of stuff, just not the PHP implementation of the basic theory. I'm interested in the data types of choice, methods to walk the graph and solve graph problems. I need to apply it mainly for hierarchic data (as trees) and interrelation definitions between entities (such as web user communities).

I have started developing my own scripts looking at code in other languages. Still, all your suggestions are more than welcome.

Answer 1

The way I did this in Java for a few basic algorithms (Dijkstra, Prim, Kruskal) was to have classes for Vertex (= Node), Edge and DirectedEdge. A vertex has an array of directed edges. An edge has references to two vertices it connects (actual object references). A directed edge has an edge but gives the vertices meaning (v1 = origin, v2 = target). I had a Graph class that has an array of vertices and an array of edges. This allows to use either the vertices or the edges as starting point for traversal. For some of the algorithms I also created Tree and Forest data structures. A tree contains a list of edges, a forest contains a list of trees.

In case you're interested, I've put the source of the java app on GitHub.

I would probably do it the same way in PHP.

Answer 2

A few examples:

• Depth-first tree search in PHP
• Hierarchical Data - data from a database manipulated by a PHP tree
• Dijkstra's algorithm in PHP (site not always available) - shortest path for a directed graph with non-negative weighted edges
• Floyd–Warshall in PHP - another shortest path algorithm
• An artificial neural network in PHP - a very specialized graph but potentially interesting.
• A* search in PHP - very specialized again, but interesting

Don't shy away from resources in other languages or pseudo-code. Once you get a feel for the building blocks, you'll artificially limit yourself if you insist on PHP-only resources.