SciPy provides tools for creating and manipulating graphs (networks) through the scipy.sparse module and visualization with Matplotlib.
An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
Example: Creating an Adjacency Matrix
import numpy as np
# Define the adjacency matrix for a simple graph
adjacency_matrix = np.array([
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 0],
[0, 1, 0, 0]
])
print("Adjacency Matrix:")
print(adjacency_matrix)
A connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths.
Example: Finding Connected Components
import scipy.sparse.csgraph as csgraph
import numpy as np
# Define the adjacency matrix for a graph
adjacency_matrix = np.array([
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 0],
[0, 1, 0, 0]
])
# Find the connected components
n_components, labels = csgraph.connected_components(csgraph=adjacency_matrix, directed=False)
print(f"Number of connected components: {n_components}")
print(f"Component labels: {labels}")
Dijkstra's algorithm finds the shortest paths from a source vertex to all other vertices in a graph.
Example: Finding Shortest Path Using Dijkstra's Algorithm
import scipy.sparse.csgraph as csgraph
import numpy as np
# Define the adjacency matrix with weights for a graph
adjacency_matrix = np.array([
[0, 1, 4, 0, 0, 0],
[1, 0, 4, 2, 7, 0],
[4, 4, 0, 3, 5, 0],
[0, 2, 3, 0, 4, 6],
[0, 7, 5, 4, 0, 7],
[0, 0, 0, 6, 7, 0]
])
# Find the shortest path from the source (vertex 0) to all other vertices
dist_matrix, predecessors = csgraph.dijkstra(csgraph=adjacency_matrix, directed=False, return_predecessors=True, indices=0)
print("Shortest path distances from source (vertex 0):")
print(dist_matrix)
print("\nPredecessors in the shortest path tree:")
print(predecessors)
Adjacency Matrix:
adjacency_matrix[i][j] is
1 if there is
an edge between vertex i and vertex j, otherwise 0.Connected Components:
csgraph.connected_components from scipy.sparse.csgraph
to find the
number of connected components and the labels for each vertex.n_components gives the number of connected components.labels is an array where the value at each index represents the component
number to which
that vertex belongs.Dijkstra's Algorithm:
csgraph.dijkstra from scipy.sparse.csgraph to find the
shortest
paths.dist_matrix contains the shortest distances from the source vertex to all
other vertices.
predecessors is an array where each entry indicates the predecessor of the
vertex in the
shortest path tree.Here is the complete code for all three topics together:
import numpy as np
import scipy.sparse.csgraph as csgraph
# Adjacency Matrix
adjacency_matrix = np.array([
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 0],
[0, 1, 0, 0]
])
print("Adjacency Matrix:")
print(adjacency_matrix)
# Connected Components
n_components, labels = csgraph.connected_components(csgraph=adjacency_matrix, directed=False)
print(f"\nNumber of connected components: {n_components}")
print(f"Component labels: {labels}")
# Dijkstra's Algorithm
adjacency_matrix_with_weights = np.array([
[0, 1, 4, 0, 0, 0],
[1, 0, 4, 2, 7, 0],
[4, 4, 0, 3, 5, 0],
[0, 2, 3, 0, 4, 6],
[0, 7, 5, 4, 0, 7],
[0, 0, 0, 6, 7, 0]
])
dist_matrix, predecessors = csgraph.dijkstra(csgraph=adjacency_matrix_with_weights, directed=False, return_predecessors=True, indices=0)
print("\nShortest path distances from source (vertex 0):")
print(dist_matrix)
print("\nPredecessors in the shortest path tree:")
print(predecessors)