SciPy Graphs

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:

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

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:

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:

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:

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:

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:

Try it Yourself »


Test Yourself With Exercises

Exercise:

Insert the missing method to find all the connected components:

Start the Exercise

ArmenianEnglish