Building a Graph data structure in PHP

undirected graphGraphs are one of the most frequently used data structures,along with linked lists and trees. In a recent PHP project I needed to build a Graph structure to analyze some interlinked urls. The problem was of a simple nature, so rather than writing my own code, I went with the one available in the Pear repository.

The Pear Structures_Graph package allows creating and manipulating graph data structures. It allows building of either directed or undirected graphs, with data and metadata stored in nodes. The library provides functions for graph traversing as well as for characteristic extraction from the graph topology.

Installing Structures_Graph

Installation of the library is simple. Structures_Graph being a Pear package we will use the Pear installer. Or you can manually download the package from Pear.

pear install Structures_Graph

Primary class methods

The Graph library relies on four main functions to create a graph structure.

/* 
   Create a new empty Graph Structure. 
   Note: Here we are creating a simple non-directed graph. If you want a 
   directed graph, pass 'true' to the 'Structures_Graph'
   constructor below. 
 */
 
$nonDirectedGraph = new Structures_Graph(false);
/* Create a new empty Node Structure */
$node1 = new Structures_Graph_Node();
/* Add the new node to the Graph Structure */
$nonDirectedGraph ->addNode($node1);
/* Connect one node to another */
$node1->connectTo($node2);

A complete example

In this post we will look into a small Graph example, and using the library to build the structure and query it. The graph we are going to work with is shown below.

directed and undirected graph

In the following example, we will construct a directed graph pictured above in Fig. 1, and look into various other graph query functions.

Using the above given main methods, we can build a directed Graph structure for the above Fig.2 as below.

require_once 'Structures/Graph.php';
require_once 'Structures/Graph/Node.php';
 
$nonDirectedGraph = new Structures_Graph(false);
 
$nodeA = new Structures_Graph_Node();
$nodeB = new Structures_Graph_Node();
$nodeC = new Structures_Graph_Node();
$nodeD = new Structures_Graph_Node();
$nodeE = new Structures_Graph_Node();
 
$nonDirectedGraph ->addNode($nodeA);
$nonDirectedGraph ->addNode($nodeB);
$nonDirectedGraph ->addNode($nodeC);
$nonDirectedGraph ->addNode($nodeD);
$nonDirectedGraph ->addNode($nodeE);
 
$nodeA->connectTo($nodeB);
$nodeB->connectTo($nodeC);
$nodeB->connectTo($nodeD);
$nodeD->connectTo($nodeC);
$nodeC->connectTo($nodeE);
$nodeE->connectTo($nodeD);

Another version of the above code, which uses an array to store nodes is shown below. Although the first version looks clean, the below version reduces the number of lines of code once the total number of nodes increases.

Whichever version you prefer, once the above code is done, we have ourselves a nice Graph structure to work with.

<?php
 
require_once 'Structures/Graph.php';
require_once 'Structures/Graph/Node.php';
 
$nonDirectedGraph = new Structures_Graph(false);
 
$nodes_names = array('a', 'b', 'c' ,'d', 'e');
$nodes = array();
 
foreach($nodes_names as $node) {
    /* Create a new node / vertex */
    $nodes[$node] = new Structures_Graph_Node();
 
    /* Add the node to the Graph structure */
    $nonDirectedGraph ->addNode($nodes[$node]);
}
 
/**
  * Specify connections between different nodes.
  * For example in the following array, 'a-b'
  * specifies that node 'a' is connected to node 'b'.
  * Also refer to the figure above.
  */
 
$vertices = array('a-b', 'b-c', 'b-d', 'd-c', 'c-e', 'e-d');
 
foreach($vertices as $vertex) {
    $data = preg_split("/-/",$vertex);
    $nodes[$data[0]]->connectTo($nodes[$data[1]]);
}

Associating Data with a node

Each node can also has the ability to hold some data. For example you could add a city name, or a link to a particular node; or you could create a graph of your Facebook friends and add their names and image links to the node.

$nodes['b']->setData("http://www.google.com");

You can retrieve the node data with the following.

echo $nodes['b']->getData();

Along with the data we can also associate metadata with the nodes. This can be useful if you would like to assign weights to the edges of the graph, which you can store as a metadata. The metadata is stored as a key value pair.

/* Store edge weight as a metadata */
$nodes['a']->setMetadata('node weight', 56);
/* Now get the metadata */
echo $nodes['a']->getMetadata('node weight'); // returns 56

Querying the Graph structure

Building a Graph structure is not enough, it can only be useful if one can query it to reveal its structure and properties. This is what we will do in this section.

After running the above example the ‘$directedGraph’ object will hold the structure of the graph shown in the figure above. You can now query the graph with various methods.

First we will query the indegree and outdegree of a particular node. So if our node is called ‘b’, then the indegree is the number of other nodes connecting to ‘b’, and the outdegree is the number of nodes ‘b’ is connecting to. Since this is a non-directed graph, both are equal.

echo $nodes['b']->inDegree(); // returns 3
echo $nodes['b']->outDegree(); // returns 3

To find out the number of nodes connected to any particular node, you can use the following. Note that this is a non-directed graph, so the number of neighbors is the total nodes connected to ‘b’. If it was an directed graph as in Fig. 2 above, the total number of neighbors is the outdegree of ‘b’.

$connected_nodes = $nodes['b']->getNeighbours();
echo count($connected_nodes); // returns 3

You can also get a list of all the nodes of the graph, in no particular order, by using the ‘getNodes()’ method. This can be useful for enumerating all the nodes of the graph.

$gNodes = $nonDirectedGraph ->getNodes();
 
foreach($gNodes as $node) {
    echo $node->getData();
}

Acyclic test

We can also test whether a graph is acyclic using the following. For that you will also need to include the Graph Manipulator class. Note that the definition of an acyclic graph used in this manipulator is that of a DAG. The graph must be directed, or else it is considered cyclic, even when there are no arcs.

require_once 'Structures/Graph/Manipulator/AcyclicTest.php';
 
$t = new Structures_Graph_Manipulator_AcyclicTest();
echo $t->isAcyclic($directedGraph ); // returns 'false' for Fig. 1

Checking connectivity between nodes is simple enough. We can check if a particular node is connected to another node using the ‘connectsTo()’ method.

echo $nodes['a']->connectsTo($nodes['b']); // true
echo $nodes['b']->connectsTo($nodes['a']); // true
echo $nodes['b']->connectsTo($nodes['d']); // true
echo $nodes['e']->connectsTo($nodes['a']); // true

All return ‘true’, because we can traverse from any node to any other. If this would have been a directed graph as in Fig.2, we would get the following instead.

echo $nodes['a']->connectsTo($nodes['b']); // true
echo $nodes['b']->connectsTo($nodes['a']); // false
echo $nodes['b']->connectsTo($nodes['d']); // true
echo $nodes['e']->connectsTo($nodes['a']); // false

For a non-directed graph as in the above figure, you would get the following.

echo $nodes['a']->connectsTo($nodes['b']); // true
echo $nodes['b']->connectsTo($nodes['a']); // true
echo $nodes['b']->connectsTo($nodes['d']); // false
echo $nodes['e']->connectsTo($nodes['a']); // false

Topological sorting

The Structures_Graph also includes a ‘Topological Sorter’, which is able to return the set of nodes in a graph, sorted by topological order. A graph may only be sorted topologically if-and-only-if it’s a DAG. You can test it with the Structures_Graph_Manipulator_AcyclicTest. To use the sort feature you will need to include the Graph Topological Sorter class.

require_once 'Structures/Graph/Manipulator/AcyclicTest.php';
require_once 'Structures/Graph/Manipulator/TopologicalSorter.php';
 
if($t->isAcyclic($directedGraph)) {
 
    $t = new Structures_Graph_Manipulator_TopologicalSorter();
    $data = $t->sort($directedGraph);
 
    foreach($data as $d) {
        echo($d[0]->getData());
    }
}

The above code will return :

a b c d e

Graphs in general have many more properties then given here, and many other search algorithms. Maybe in future posts I’ll go into some other details of Graphs using the current Pear library.



6 thoughts on “Building a Graph data structure in PHP

  1. Thanks a lot for such a great article. It helped me a lot. Please, keep posting more stuff concerning graph manipulation with PHP (using Pear), like graph searching algorithms.

  2. I can’t get the matrix to be shown as you posted here, it always ends up with all zeros. Could you please paste the actual code used to create the graph, into the matrix, and into a text output please?

Comments are closed.