In This Article, You Will Learn About Python SciPy Graph.
Python SciPy Graphs – Before moving ahead, let’s know a bit about Python SciPy Sparse Data
Table of Contents
Get started with Graphs
A graph is one of the essential data structures in SciPy. To work with such kinds of data structures, SciPy provides a module named scipy.sparse.csgraph.
Adjacency Matrix
An adjacency matrix is a type of nxn matrix where n refers to the number of elements in a graph representing the connection between the elements.
A representation of Graph’s point A, B, C such as:
A&B is connected, type of matrix 1.
A&C is connected, type of matrix 2.
B&C is not connected.
The matrix will look like:
Now, Let’s take a look at methods of Adjacency matrix.
Connected Components
To find out all the connected components, use the connected_components() method.
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
Array = np.array([[1,2,3],
[4,5,6],
[7,8,9]])
New_Array = csr_matrix(Array)
print(connected_components(New_Array))
As a result, it returned the connected points from array.
Dijkstra
To find out the shortest path in graph from one point to another point, use the dijkstra method.
It includes following arguments –
- return_predecessors: Boolean Value. Returns True to whole path of traversal, otherwise False.
- indices: index of the element to return all paths from that element only.
- limit: max weight of path.
Example – Finding the shortest part from element 1 to 2.
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
Array = np.array([[1,0,2],
[0,1,2],
[1,2,0]])
New_Array = csr_matrix(Array)
print(dijkstra(New_Array, return_predecessors=True, indices=0))
As a result, it returned shortest part from element 1 to 2.
Floyd Warshall
To find the shortest path between all pairs of elements, use the floyd_warshall() method.
Example – Finding the shortest path between all pairs of elements.
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
Array = np.array([[1,0,2],
[0,1,2],
[1,2,0]])
New_Array = csr_matrix(Array)
print(floyd_warshall(New_Array, return_predecessors=True))
As it is shown clearly, it returned shortest path between all pairs of elements.
Bellman Ford
The Bellman’s bellman_ford() method can identify the shortest path between any pair of elements. This method is able to handle negative weights too.
Example – Finding shortest path between any pair of elements with negative weights.
import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix
Array = np.array([[1,0,2],
[0,1,2],
[1,2,0]])
New_Array = csr_matrix(Array)
print(bellman_ford(New_Array, return_predecessors=True, indices=0))
As a result, it returned shortest path between pair of elements with negative weights.
Depth First Order
The depth_first_order() method returns a depth first traversal from a node.
This function includes two arguments-
- the graph.
- the starting element to traverse graph from.
Example – Traverse the graph depth first for given adjacency matrix.
import numpy as np
from scipy.sparse.csgraph import depth_first_order
from scipy.sparse import csr_matrix
Array = np.array([[0, 2, 0, 2],
[0, 1, 1, 1],
[2, 1, 0, 1],
[1, 2, 0, 1]])
New_Array = csr_matrix(Array)
print(depth_first_order(New_Array, 1))
As a result, returns a depth first traversal from a node.
Breadth First Order
The breadth_first_order() method returns a breadth first traversal from a node.
This function includes two arguments-
- the graph.
- the starting element to traverse graph from.
Example – Traverse the graph breadth first for given adjacency matrix.
import numpy as np
from scipy.sparse.csgraph import breadth_first_order
from scipy.sparse import csr_matrix
Array = np.array([[0, 2, 0, 2],
[0, 1, 1, 1],
[2, 1, 0, 1],
[1, 2, 0, 1]])
New_Array = csr_matrix(Array)
print(breadth_first_order(New_Array, 1))
As shown above, it returns a breadth first traversal from a node.
If you find anything incorrect in the above-discussed topic and have any further questions, please comment below.
