Directed v/s Undirected Graph
|
|
||
|
Edge Representation |
Edges have a specific direction between Nodes. For example: If you see the output of Example-2 there is a directed edge from 0 to 1, it signifies that we can move from 0 to 1. But we can’t move from 1 to 0. |
In an undirected graph, the edges do not have any specific direction For example: If you see the output of the above example there is an edge from 0 to 1 and also an edge from 1 to 0. It signifies that we can move from 0 to 1 and also we can move from 1 to 0 |
|
Symmetry |
The adjacency matrix is asymmetric or the Relationship between vertices is asymmetric. The adjacency matrix of example-2 is asymmetric. |
The adjacency matrix is symmetric or the Relationship between vertices is symmetric. The adjacency matrix of the above example is symmetric. |
|
Edge Notation |
Represented as (source vertex, target vertex). |
Represented as an unordered pair {vertex A, vertex B}. |
|
|
Flow charts, one-way streets |
Bidirectional streets |
Conclusion:
Throughout this article, we explored the key features and functionalities of scipy.sparse.csgraph. We discussed how to create a graph using different methods such as COO matrix representation and dense matrix conversion. We learned about important graph algorithms like Dijkstra’s algorithm for finding the shortest paths and the maximum flow algorithm for network flow problems.
As you continue exploring the capabilities of scipy.sparse.csgraph, you’ll discover a rich collection of algorithms and methods that can be applied to a wide range of graph-related problems. From graph traversal and connectivity analysis to graph partitioning and network flow optimization, scipy.sparse.csgraph is a versatile tool that opens up a world of possibilities for graph analysis and optimization.
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.