❮ Scipy Matlab Arrays Scipy Interpolation ❯

SciPy Graph Structures

Graph structures are one of the most powerful frameworks in algorithmic studies.

A graph is a collection of nodes and edges representing various relationships, where nodes are vertices corresponding to objects, and edges are connections between objects.

SciPy provides the scipy.sparse.csgraph module for handling graph structures.

Adjacency Matrix

An adjacency matrix is a matrix that represents the adjacency relationships between vertices.

The logical structure of an adjacency matrix is divided into two parts: the set of vertices (V) and the set of edges (E). Edges can sometimes have weights, representing the strength of connections between nodes.

A one-dimensional array stores all vertex data in the graph, and a two-dimensional array stores the data of relationships (edges or arcs) between vertices. This two-dimensional array is called an adjacency matrix.

Consider the following example:

Vertices are A, B, C, and edge weights are 1 and 2.

A is connected to B with a weight of 1.

A is connected to C with a weight of 2.

C is not connected to B.

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

Adjacency matrices can be either directed graph adjacency matrices or undirected graph adjacency matrices.

An undirected graph represents a bidirectional relationship, where edges have no direction.

Note: The D node in the above two graphs is a self-loop, which is an edge whose ends are the same node.

Connected Components

To view all connected components, use 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))

The above code outputs:

(1, array([0, 0, 0], dtype=int32))

Dijkstra - Shortest Path Algorithm

Dijkstra's shortest path algorithm is used to calculate the shortest path from one node to all other nodes.

Scipy uses the dijkstra() method to calculate the shortest path from one element to all other elements.

return_predecessors: Boolean, set to True to traverse all paths. If you do not want to traverse all paths, set it to False.
indices: The index of the element, returns all paths for this element.
limit: The maximum weight of the 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))

The above code outputs:

(array([ 0.,  1.,  2.]), array([-9999,     0,     0], dtype=int32))

Floyd Warshall - Floyd's Algorithm

Floyd's algorithm is used to find the shortest path between any two points.

Scipy uses the floyd_warshall() method to find the 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))

The above code outputs:

(array([[ 0.,  1.,  2.],
       [ 1.,  0.,  3.],
       [ 2.,  3.,  0.]]), array([[-9999,     0,     0],
       [    1, -9999,     0],
       [    2,     0, -9999]], dtype=int32))

Bellman Ford - Bellman-Ford Algorithm

The Bellman-Ford algorithm is used to find the shortest path between any two points.

Scipy uses the bellman_ford() method to find the shortest path between all pairs of elements, typically usable in any graph, including directed graphs and graphs with negative-weight edges.

Example

Find the shortest path from element 1 to element 2 using a graph with negative-weight edges:

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

The above code outputs:

(array([ 0., -1.,  2.]), array([-9999,     0,     0], dtype=int32))

Depth-First Order

The depth_first_order() method returns the order of a depth-first traversal from a node.

It can take the following parameters:

Graph
Element from which the graph starts to traverse

Example

Given an adjacency matrix, return the order of a depth-first traversal:

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

The above code outputs:

(array([1, 0, 3, 2], dtype=int32), array([    1, -9999,     1,     0], dtype=int32))

Breadth-First Order

The breadth_first_order() method returns the order of a breadth-first traversal from a node.

It can take the following parameters:

Graph
Element from which the graph starts to traverse

Example

Given an adjacency matrix, return the order of a breadth-first traversal:

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

The above code outputs:

(array([1, 0, 2, 3], dtype=int32), array([    1, -9999,     1,     1], dtype=int32))

❮ Scipy Matlab Arrays Scipy Interpolation ❯