In the last post we constructed a graph structure using the Structure_Graph Pear library. But building a graph is not enough; we also need the ability to search through it. To make it easier to build search algorithms, it is useful if we can represent the graph and its connections in a different way; adjacency matrix being one such representation.

An adjacency matrix is a means of representing which vertices (or nodes) of a graph are adjacent to which other vertices. An adjacency matrix is a two dimensional array in which the elements indicate whether an edge is present between two vertices. An edge between two vertices is indicated with a 1; while the absence of a edge is indicated by a 0. A example graph and its adjacency matrix is shown above. For example in the above figure vertex ‘2’ is adjacent to vertices 1,3 and 5.

The following is the code to build a adjacency matrix for the graph structure constructed in the last post. Refer to the previous post to get a context for the variables ‘$nonDirectedGraph’ and ‘$nodes_names’. Note that in the example in the last post we have saved the node names using the ‘setData()’ method.

/* Get a list of all the nodes in our graph */ $array_nodes = $nonDirectedGraph->getNodes(); /* This is where will save the adj. matrix */ $adj_matrix = array(); /* Reset the matrix to all '0's */ foreach($nodes_names as $row){ foreach($nodes_names as $col){ $adj_matrix[$row][$col] = 0; } } /* Now build the adj. matrix */ foreach($array_nodes as $nd) { $row = $nd->getData(); $neighbours = $nd->getNeighbours(); foreach($neighbours as $neighbour) { $col = $neighbour->getData(); $adj_matrix[$row][$col] = 1; } } |

Once we have run the above code, the ‘$adj_matrix’ array will hold the adjacency matrix representation of our graph.

The adjacency matrix for figure 1. above is shown below.

a b c d e a 0 1 0 0 0 b 1 0 1 1 0 c 0 1 0 1 1 d 0 1 1 0 1 e 0 0 1 1 0 |

The adjacency matrix for figure 2, which is a directed graph is different, as shown below.

a b c d e a 0 1 0 0 0 b 0 0 1 1 0 c 0 0 0 0 1 d 0 0 1 0 0 e 0 0 0 1 0 |

Below is a ad hoc code to print the ‘$adj_matrix’ array to the console.

/* Print the adj. matrix */ echo " "; foreach($nodes_names as $name) { echo $name . " "; } echo "\n"; foreach($nodes_names as $row){ echo $row . " "; foreach($nodes_names as $col){ echo $adj_matrix[$row][$col] . " "; } echo "\n"; } |

In future posts we will look into graph search algorithms.

I have created the graph from your previous post and when I create the matrix , it only displays 0.

I’m trying to solve it though, but if you found the error please let me know.

I found the problem:

$col = $neighbour->getData();

The nodes don’t have anything set.

You are missing the:

$nodes[‘a’]->setData(‘a’);

..

etc..

The post is supposed to work in tandem with the previous post in which we create the graph nodes.

Yeah, but i the previous post you didn’t set value to the nodes so this part won’t work:

$col = $neighbour->getData();

$adj_matrix[$row][$col] = 1;

Thank you though, it was helpful.

Question: Do you know any search algorithm that i can implement to the adjacency matrix?, and I’m looking for a framework to display the graph in an image like a real graph.

Sedgewick’s ‘Algorithms’, provides a nice overview of Graph algorithms:

http://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/032157351X/