Adjacency Matrix Using Python Programming

AdjacencyMatrixFeaturedImage

An adjacency matrix is a very important concept in Graph Theory. Adjacency Matrix represents a graph in a mathematical format using Matrices. Let’s say the Graph has a ‘V’ number of Vertices. Adjacency Matrix is a Square Matrix of dimensions V*V. It represents the Edges of the Graph.

Let us understand how the adjacency matrix is created using this formula,

AdjM={

    A[i][j]=0 if [i,j] is not an edge in the Graph
    A[i][j]=1 if [i,j] is an edge in the Graph

where i,j <V
}

An example will clarify the above adjacency matrix formula. A graph is represented below:

Example Graph 1
Example Graph 1
Adjacency Matrix For The Above Given Graph
Adjacency Matrix For The Above Given Graph

The second Image shows the Adjacency Matrix for the Example Graph. It should be noted that as the Graph is Undirected and therefore the elements at positions [i,j] and [j,i] in the Adjacency Matrix are 1, where [i,j] is an edge in the Graph. As there is an edge between the vertices 2 and 0 in the Graph, the values at positions (2,0) and (0,2) in the Adjacency Matrix are 1. It can be seen for other edges as well. As there is no edge between vertices 4 and 1 in the Graph, values at positions (4,1) and (1,4) are 0. It can be seen for other vertices, which do not have an edge in between, as well.

For More Information: Implementing a Graph in Python

How To Create Adjacency Matrix in Python?

The networkx module of Python helps the user in the Visualization of Graphs. It will be used to explain the Graphs and Adjacency Matrices formed. It can be installed using the following command in Command Shell:

>>> pip install networkx

This article will go through two different methods. The first method is creating an adjacency Matrix from a list of vertices and edges provided as input. The second method is creating a Graph (a collection of vertices and edges) from the adjacency matrix given as an input. The entire article focuses only on undirected graphs.

Creating Adjacency Matrix From Graph Vertices and Edges

This function would have two inputs: a list of vertices and edges. The edges would be given as a list of lists. Each of the inner lists consists of two elements: the first element is the starting vertex of the edge, and the second element is the ending vertex of the edge. It returns an adjacency matrix as its output and draws the corresponding graph in the function. It is demonstrated in the code below:

def createAdjacencyMatrix(vertices,edges):
  noofvertices=len(vertices)
  adjM=[]
  while(len(adjM)<noofvertices):
    temp=[]
    for i in range(noofvertices):
      temp.append(0)
    adjM.append(temp)
  for edge in edges:
    i=edge[0]
    j=edge[1]
    if i>=noofvertices or j>=noofvertices or i<0 or j<0:
      print(f"Not a Proper Input in Edge {i},{j}")
    else:
      adjM[i][j]=1
      adjM[j][i]=1
  G=nx.Graph()
  G.add_edges_from(edges)
  nx.draw_networkx(G)
  plt.show()
  return adjM

The above code snippet creates an adjacency matrix stored in the variable called adjM. It has the same dimensions row-wise and column-wise as the number of vertices in the Graph. The adjacency matrix is initialized with all its initial values as 0. All the inner lists of the edges list are traversed, and the first element is assigned as the starting node, while the second element is assigned as the ending node. It can also be seen on Line 12 a check condition is also implemented. The program will print an error message for vertex values out of range. The out-of-range is defined as either a vertex having a value greater than the maximum number of vertices or having a value smaller than 0. After that, the values at positions [i,j] and [j,i] in the adjacency matrix are converted to 1.

The other portion of the function draws a Graph based on the inputs given. The function returns the created adjacency matrix. The functioning of the networkx module is well defined in the article provided below:

Also Read: NetworkX Package – Python Graph Library

When executed, the function will produce an adjacency matrix and draw the corresponding graph. The vertices and edges for the input graph are as shown below:

vertices=[0,1,2,3,4,5]
edges=[[1,2],[2,4],[1,5],[3,5],[4,5],[1,3],[0,3],[0,2],[5,3],[5,1]]

When the above-given values are given as an input to the function createAdjacencyMatrix(), it produces the following output:

Graph Output Of CreateAdjacencyMatrix Function
Graph Output Of CreateAdjacencyMatrix() Function
[[0, 0, 1, 1, 0, 0],
 [0, 0, 1, 1, 0, 1],
 [1, 1, 0, 0, 1, 0],
 [1, 1, 0, 0, 0, 1],
 [0, 0, 1, 0, 0, 1],
 [0, 1, 0, 1, 1, 0]]

The second function creates a Graph from the adjacency matrix. It takes input as Adjacency Matrix and provides output as a collection of vertices and edges.

Creating Graph From Adjacency Matrix

In the second function, the adjacency matrix is provided as input. It will also visualize the graph, and return values will be vertices and edges. The adjacency matrix is a list of lists wherein the length of each of the inner lists is the same as the length of the entire outer list. This ensures a square matrix is provided as an input. It is demonstrated in the code below:

def createGraph(adjM):
  edges=[]
  noofvertices=len(adjM)
  for mat in adjM:
    if len(mat)>noofvertices or len(mat)<noofvertices:
      print("False Adjacency Matrix")
      return 0
  for i in range(len(adjM)):
    mat=adjM[i]
    for j in range(len(mat)):
      if mat[j]==1:
        temp=[i,j]
        edges.append(temp)
  G=nx.Graph()
  G.add_edges_from(edges)
  nx.draw_networkx(G)
  plt.show()
  vertices=[i for i in range(len(adjM))]
  return vertices,edges

The main function of the above code is to create the list edges. The edges are created as a list of lists, with each inner list having two elements: starting vertex and ending vertex of the edge. The code runs through the length of the adjacency matrix, and for each element in the matrix, which is 1, the row number and the column number are stored as an edge. The code also checks a condition to ensure a square matrix has been provided as input. The function will exit prematurely if the dimensions do not satisfy the condition. The Graph() object of networkx uses the created edges list to visualize the graph. The vertices is a list of all vertices in the graph. It is simply made by enumerating the length of adjacency matrix as seen in Line 18. A collection of edges and vertices is returned as an output.

The following adjacency matrix of 5 vertices is used as a check input for the function createGraph():

adjM=[[1,0,1,0,1],[0,0,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,1,0]]

It produces an undirected graph as its output. It should be noted that the element at (0,0) is kept as 1, which means there is a looping edge at vertex 0. The adjacency matrix, when provided as an input, produces the following output

Graph Output Of CreateGraph Function
Graph Output Of CreateGraph() Function
([0, 1, 2, 3, 4],
 [[0, 0],
  [0, 2],
  [0, 4],
  [1, 2],
  [1, 3],
  [2, 0],
  [2, 1],
  [2, 3],
  [3, 0],
  [3, 1],
  [4, 3]])

The first element in the output is a list of vertices, having the first vertex as index 0. The second output is a list of lists showing the edges of the graph.

Source Code

I have developed the entire code in Google Colaboratory that demonstrates the given function and produces output. It can be accessed by anyone for the source code.

Conclusion

Adjacency Matrix is an important way of representing a Graph. In this article, we have learned how an adjacency matrix can be easily created and manipulated using Python. It is a square matrix having the dimensions as a number of edges on the Graph. An adjacency matrix can be created easily from a Graph input, and the reverse is also true. It is equally easy to implement a graph from an adjacency matrix. The time complexity of adjacency matrix creation would be O(n2), wherein n is the number of vertices in the graph.

References

Networkx Website