Introduction to Python SciPy Graphs

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))

				
			
python-scipy-graphs

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 –

  1. return_predecessors: Boolean Value. Returns True to whole path of traversal, otherwise False.
  2. indices: index of the element to return all paths from that element only.
  3. 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))


				
			
python-scipy-graphs

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))

				
			
python-scipy-graphs

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-

  1. the graph.
  2. 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))

				
			
python-scipy-graphs

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-

  1. the graph.
  2. 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))

				
			
python-scipy-graphs

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.

1 thought on “Introduction to Python SciPy Graphs”

Leave a Comment

Stay in the loop

codingstreets