Building a adjacency matrix of a graph


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.

directed and undirected 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.

This site is a digital habitat of Sameer Borate, a freelance web developer working in PHP, MySQL and WordPress. I also provide web scraping services, website design and development and integration of various Open Source API's. Contact me at metapix[at]gmail.com for any new project requirements and price quotes.

7 Responses

1

Sameer Borat-Blog: Der Aufbau einer Adjazenzmatrix eines Graphen | PHP Boutique

February 18th, 2012 at 1:45 pm

[...] Grafik-Tutorial in seinem letzten Beitrag Sameer weiter auf der Suche auf Grafiken in PHP mit Diese neuen Beitrag zeigt, wie eine “Agentur Matrix” von einem derzeit gebaut erstellen graph. Der Aufbau [...]

2

Sameer Borate’s Blog: Building a adjacency matrix of a graph « We are php

February 20th, 2012 at 9:41 pm

[...] on the graphing tutorial in his last post Sameer continues on looking at graphs in PHP with this new post showing how to create an “agency matrix” of a currently built graph. Building a graph [...]

3

Antonio Martinez

September 27th, 2012 at 12:48 pm

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.

4

Antonio Martinez

September 27th, 2012 at 11:45 pm

I found the problem:

$col = $neighbour->getData();

The nodes don’t have anything set.

You are missing the:

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

sameer

September 28th, 2012 at 5:22 am

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

6

Antonio Martinez

September 30th, 2012 at 2:23 pm

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.

sameer

September 30th, 2012 at 9:46 pm

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

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

Your thoughts