Creating CSGraph From Adjacency Matrix

Define an adjacency matrix that represents the connectivity of the graph.
Convert the adjacency matrix to a sparse matrix representation (e.g., CSR, CSC).
Use the csgraph_from_dense function to convert the sparse matrix to a graph representation
The graph is directed.

In this example, we are using the Numpy and Scipy for creating a sparse matrix and then it’s converted into a graph.

Python3

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import csgraph_from_dense
 
# Creating a 3 * 3 sparse matrix .
sparseMatrix = csr_matrix((3, 3),
                          dtype=np.int8).toarray()
 
# converting sparse matrix to graph
graph = csgraph_from_dense(sparseMatrix)
 
print(graph.toarray())

Output:

[[0. 0. 0.]
 [0. 0. 0.]
 [0. 0. 0.]]

In this example first, we created the adjacency matrix, then we converted it into a sparse matrix.

Python3

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import csgraph_from_dense
 
# Define the adjacency matrix for a directed graph
adjacency_matrix = [[0, 1, 0, 1],
                    [0, 0, 1, 0],
                    [0, 0, 0, 1],
                    [0, 0, 0, 0]]
 
# Convert the adjacency matrix to CSR format
graph_sparse = csr_matrix(adjacency_matrix).toarray()
 
# Convert CSR format to graph representation
graph = csgraph_from_dense(graph_sparse)
# it will print graph as=> (source,destination) edge-weight
print(graph)  

Output:

  (0, 1)    1.0
  (0, 3)    1.0
  (1, 2)    1.0
  (2, 3)    1.0

SciPy CSGraph – Compressed Sparse Graph

Graphs are powerful mathematical structures used to represent relationships between entities in various fields, including computer science, social networks, transportation systems, and more. Analyzing and computing graphs is a fundamental task in many applications, but it can be challenging, especially when dealing with large graphs with sparse connectivity. Fortunately, the scipy.sparse.csgraph subpackage in the SciPy library offers a comprehensive set of tools and algorithms specifically designed for efficient graph analysis using sparse matrix representations. Sparse matrices are matrices where the majority of elements are zero, making them ideal for representing and manipulating large graphs with sparse connectivity.

Note: Before going further strongly recommended to know how to create a sparse matrix in Python (Refer to this article How to Create a Sparse Matrix in Python).

Key Functionalities of SciPy CSGraph

The scipy.sparse.csgraph subpackage offers a wide range of functionalities and algorithms for efficient graph analysis. Let’s delve into its key features:

Shortest Path Algorithms
- Dijkstra’s Algorithm: Find the shortest path between nodes using the shortest_path function.
- Bellman-Ford Algorithm: Compute the shortest path considering negative edge weights with bellman_ford.
- Floyd-Warshall Algorithm: Determine the shortest path between all pairs of nodes using floyd_warshall.
Connected Components
- connected_components: Identify the connected components in a graph, providing the number of components and labels for each node.
- connected_components_dist: Compute the connected components considering edge weights.
Minimum Spanning Tree
- minimum_spanning_tree: Calculate the minimum spanning tree of a graph, finding the subset of edges with the minimum total weight.
- minimum_spanning_tree_csr: Compute the minimum spanning tree for graphs represented as Compressed Sparse Row (CSR) matrices.
Strongly Connected Components
- strongly_connected_components: Identify strongly connected components in a directed graph.
- strongly_connected_components_csr: Compute strongly connected components for CSR matrix representation.

Tags:

#Python #python

Creating CSGraph from Edge List

Creating CSGraph From Adjacency Matrix

Python3

Python3

SciPy CSGraph – Compressed Sparse Graph

Key Functionalities of SciPy CSGraph

Similar Reads