Tutorials References Exercises Videos Menu
Create Website Get Certified Upgrade

SciPy Graphs


Working with Graphs

Graphs are an essential data structure.

SciPy provides us with the module scipy.sparse.csgraph for working with such data structures.


Adjacency Matrix

Adjacency matrix is a nxn matrix where n is the number of elements in a graph.

And the values represents the connection between the elements.

Example:

For a graph like this, with elements A, B and C, the connections are:

A & B are connected with weight 1.

A & C are connected with weight 2.

C & B is not connected.

The Adjency Matrix would look like this:


      A B C
   A:[0 1 2]  
   B:[1 0 0]
   C:[2 0 0]

Below follows some of the most used methods for working with adjacency matrices.


Connected Components

Find all of the connected components with the connected_components() method.

Example

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(connected_components(newarr))
Try it Yourself »


Dijkstra

Use the dijkstra method to find the shortest path in a graph from one element to another.

It takes following arguments:

  1. return_predecessors: boolean (True to return 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

Find the shortest path from element 1 to 2:

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(dijkstra(newarr, return_predecessors=True, indices=0))
Try it Yourself »

Floyd Warshall

Use the floyd_warshall() method to find shortest path between all pairs of elements.

Example

Find 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

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(floyd_warshall(newarr, return_predecessors=True))
Try it Yourself »

Bellman Ford

The bellman_ford() method can also find the shortest path between all pairs of elements, but this method can handle negative weights as well.

Example

Find shortest path from element 1 to 2 with given graph with a negative weight:

import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

arr = np.array([
  [0, -1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(bellman_ford(newarr, return_predecessors=True, indices=0))
Try it Yourself »

Depth First Order

The depth_first_order() method returns a depth first traversal from a node.

This function takes following 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

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(depth_first_order(newarr, 1))
Try it Yourself »

Breadth First Order

The breadth_first_order() method returns a breadth first traversal from a node.

This function takes following 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

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(breadth_first_order(newarr, 1))
Try it Yourself »

Test Yourself With Exercises

Exercise:

Insert the missing method to find all the connected components:

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print((newarr))

Start the Exercise