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

Dijkstra

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

It takes following arguments:

• **return_predecessors:** boolean (True to return whole path of traversal otherwise False).
• **indices:** index of the element to return all paths from that element only.
• **limit:** max weight of path.

Floyd Warshall

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

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.

Depth First Order

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

This function takes following arguments:

• the graph.
• the starting element to traverse graph from.

Breadth First Order

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

This function takes following arguments:

• the graph.
• the starting element to traverse graph from.