1) Adjacency Matrix
Definition of an Adjacency Matrix:
An adjacency matrix is a square matrix or a table that stores information about the edges of a graph. Each row and column of the matrix corresponds to a vertex or node of the graph.
The entries of the matrix indicate whether two vertices are adjacent or not, based on the presence or absence of edges in the graph.
Calculation of Adjacency Matrix:
To calculate the adjacency matrix of a graph with n vertices, we assign a unique integer label from 1 to n to each vertex.
Then, we create an n x n matrix, where the entry at row i and column j represents the edge between vertex i and vertex j. If there is an edge between vertex i and vertex j, we assign 1 to the (i,j)-th entry, and if there is no edge between them, we assign 0 to the (i,j)-th entry.
Example of Adjacency Matrix:
Consider an undirected graph with four vertices and five edges as shown in the figure below.
We can represent the graph using a 4 x 4 adjacency matrix A as follows:
A =
[0 1 1 0]
[1 0 1 1]
[1 1 0 1]
[0 1 1 0]
The (i,j)-th entry of the matrix A represents the edge between the i-th vertex and the j-th vertex.
For example, the entry at (1,2) is 1, indicating that there is an edge between vertex 1 and vertex 2.
2) Creating Adjacency Matrix in Python
Method 1: Creating Adjacency Matrix from Graph Vertices and Edges:
Python provides several libraries to work with graphs. One such library is the networkx module that can create and manipulate graphs.
Here, we demonstrate how to create an adjacency matrix from a graph using networkx module.
Consider a graph G with the vertices {1, 2, 3, 4} and edges {(1,2), (2,3), (3,4), (4,1)}.
We can represent the graph using networkx module by defining a list of edges and calling the Graph function as follows:
import networkx as nx
edges = [(1,2), (2,3), (3,4), (4,1)]
G = nx.Graph(edges)
To find the adjacency matrix from the graph G, we can call the to_numpy_matrix function of networkx module as follows:
A = nx.to_numpy_matrix(G, nodelist=[1,2,3,4])
print(A)
The output of the above code is:
[[0. 1.
0. 1.]
[1.
0. 1.
0.]
[0. 1.
0. 1.]
[1.
0. 1.
0.]]
The output is a 4 x 4 numpy array, which is the adjacency matrix of the graph G.
Method 2: Creating Graph from Adjacency Matrix:
We can also create a graph from an adjacency matrix in Python using the networkx module.
This feature is useful when we have the adjacency matrix of a graph containing a large number of vertices and edges.
Consider the adjacency matrix A of the graph G, as shown below.
A =
[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]
To create a graph from the adjacency matrix A, we can call the from_numpy_matrix function of the networkx module as follows:
import networkx as nx
import numpy as np
A = np.array([[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0]])
G = nx.from_numpy_matrix(A)
We can visualize the graph G using the draw function of the networkx module, as shown below:
import matplotlib.pyplot as plt
nx.draw(G, with_labels=True)
plt.show()
The output of the above code is as shown in the figure below:
3) Code Implementation
Creating Adjacency Matrix From Graph Vertices and Edges
To create an adjacency matrix from graph vertices and edges, we need to define a function that takes the list of vertices and edges as input. The function should initialize the adjacency matrix, iterate through the edges, and update the corresponding entries of the adjacency matrix.
Below is the implementation of adjacency matrix creation function in Python.
def create_adjacency_matrix(vertices, edges):
# Initialize adjacency matrix
matrix = [[0 for _ in range(len(vertices))] for _ in range(len(vertices))]
# Traverse through the edges and update matrix entries
for edge in edges:
source = edge[0]
target = edge[1]
matrix[vertices.index(source)][vertices.index(target)] = 1
matrix[vertices.index(target)][vertices.index(source)] = 1
return matrix
The function create_adjacency_matrix takes two arguments: vertices and edges.
vertices is a list of vertices or nodes of the graph, and edges is a list of edges that connect the vertices. The matrix variable initially creates a zero matrix of dimensions n x n, where n is the number of vertices in the graph.
The for loop traverses through the edges list, takes the first and second vertices of each edge, and updates the corresponding entries in the matrix. After populating the entries, the function returns the completed adjacency matrix.
Let’s put the function to the test with the following sample inputs:
vertices = [1,2,3,4,5]
edges = [(1,2),(1,3),(2,3),(2,4),(3,4),(4,5)]
matrix = create_adjacency_matrix(vertices, edges)
print(matrix)
The output of the above code:
[[0, 1, 1, 0, 0], [1, 0, 1, 1, 0], [1, 1, 0, 1, 0], [0, 1, 1, 0, 1], [0, 0, 0, 1, 0]]
The output is a 5 x 5 adjacency matrix corresponding to the given input vertices and edges.
Creating Graph from Adjacency Matrix
To create a graph from an adjacency matrix in Python, we use the numpy module to create a numpy array from the adjacency matrix, and then pass it to the networkx from_numpy_matrix function to create a graph. We also need to define the graph type as directed or undirected depending on the edges of the adjacency matrix.
Below is the code implementation of the function to create a graph from an adjacency matrix.
import networkx as nx
import numpy as np
def create_graph_from_adjacency_matrix(matrix, graph_type):
# Convert matrix to numpy array
adj_matrix = np.array(matrix)
# Create graph from numpy array
if graph_type == 'directed':
graph = nx.DiGraph(adj_matrix)
else:
graph = nx.Graph(adj_matrix)
return graph
The function create_graph_from_adjacency_matrix takes two arguments: matrix and graph_type. matrix is the adjacency matrix of the graph, and graph_type is a string variable that defines whether the graph is directed or undirected.
The function first converts the matrix to a numpy array. Then, it creates a graph based on the type, where directed edges are created when graph_type is directed, and undirected edges are created when graph_type is undirected.
The function returns the created graph object. Let’s use the adjacency matrix created earlier to create an undirected graph.
The code is as follows:
graph = create_graph_from_adjacency_matrix(matrix, 'undirected')
nx.draw(graph, with_labels=True)
The output of the above code creates a visualization of the graph with node labels as:
4) Conclusion
Importance of Adjacency Matrix in Graph Theory
Adjacency matrix is a fundamental concept in graph theory. It is an efficient way to represent a graph and its relationships between vertices.
Adjacency matrices help us to study graphs by providing a convenient way to compute graph properties. These properties include degrees of vertices, eigenvalues and eigenvectors, graph connectivity, and graph isomorphism.
Ease of Creating and Manipulating Adjacency Matrix Using Python
Python provides several libraries to work with graphs, including networkx, igraph, and graph tool. These libraries offer a wide range of functionality related to graphs, including creating and manipulating adjacency matrices.
With the help of these libraries, you can easily create, visualize, and analyze graphs and their properties. Python’s flexible nature and extensive library support make it an excellent choice for graph theory problems.
This article explored the concept of an adjacency matrix, which is a mathematical representation of a graph and its relationships between vertices. We discussed how to calculate and create an adjacency matrix in Python using the networkx module.
Additionally, we provided code implementation to create an adjacency matrix from graph vertices and edges and create a graph from an adjacency matrix. The adjacency matrix is a crucial tool in graph theory that allows us to study graph properties such as connectivity, isomorphism, and more.
Python’s extensive library support and flexibility make it an ideal language to work with graph theory problems. Regardless of the graph type, adjacency matrices are a powerful and efficient way to represent and analyze relationships between vertices.