scipy.sparse.csgraph.depth_first_order in Python

By Shagun Bidawatka

depth_first_order is a function that is present in scipy.sparse.csgraph module of Python. Here we will discuss the introduction of scipy, sparse, csgraph, and depth_first_order with implementation in Python.

Python scipy.sparse.csgraph.depth_first_order with code example

SciPy:

It is an open-source scientific library for python. The SciPy library depends on NumPy.

Sparse: 

To generate the sparse matrix or graph scipy provides us a tool. Therefore we can use scipy.sparse to create the sparse matrix or graphs.

csgraph:

csgraph denotes Compresses Sparse Graph

It focuses on sparse matrix representation based Fast graph algorithms.

scipy.sparse.csgraph.depth_first_order:

scipy.sparse.csgraph.depth_first_order(csgraph, i_start, directed=True, return_predecessors=True)

This function returns a depth-first-order starting with specific node.

However, depth-first-node is not unique for a graph.

Parameters:

• csgraph – array / sparse matrix

We are converting the input csgraph to a csr format for the calculation.

• i_start – int

Starting node index.

• directed (optional) – bool

If true, then operate on a directed graph from point i to point j along paths csgraph[i,j].

If the value is false, then it finds the undirected graph shortest path.

• return_predecessors(optional) – bool

If true, then returns predecessors array.

Return:

• node_array – n- dimension array, 1- dimension

The depth-first list of nodes starts with a particular node. The length of node_array refers to the number of reachable nodes from the particular node.

• predecessors – n- dimension array, 1-dimension

Returns when return_predecessors is True.

Example (Code):

• Importing Modules

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import depth_first_order

• Creating graph and then sparse graph

graph = [[0, 1 , 2, 0],[0, 2, 0, 1],[2, 0, 0, 1],[0, 0, 0, 0]]
graph = csr_matrix(graph)
print(graph)

Output:

 (0, 1) 1 
 (0, 2) 2 
 (1, 1) 2
 (1, 3) 1
 (2, 0) 2
 (2, 3) 1

• Depth First Order

depth_first_order(graph,0)

Output:

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

You can perform many more operations using  SciPy on matrix, graph, and tree.