YouTip

Graph structure is one of the most powerful frameworks in algorithmics. A graph is a collection of nodes and edges for various relationships, where nodes are vertices corresponding to objects, and edges are connections between objects. SciPy provides the scipy.sparse.csgraph module to handle graph structures. ### Adjacency Matrix Adjacency Matrix is a matrix that represents the adjacency relationship between vertices. The logical structure of adjacency matrix is divided into two parts: V and E sets, where V is vertices, E is edges, and edges sometimes have weights indicating the connection strength between nodes. !(#) Use a one-dimensional array to store all vertex data in the graph, and a two-dimensional array to store the data of relationships between vertices (edges or arcs), this two-dimensional array is called an adjacency matrix. Look at the example below: !(#) Vertices are A, B, C, edge weights are 1 and 2. A is connected to B, weight is 1. A is connected to C, weight is 2. C is not connected to B. This adjacency matrix can be represented as the following two-dimensional array: A B C A: B: C: Adjacency matrix is divided into directed graph adjacency matrix and undirected graph adjacency matrix. Undirected graph is a bidirectional relationship, edges have no direction: !(#) Directed graph's edges have direction, it is a unidirectional relationship: !(#) **Note:** The D node in both graphs above is a self-loop, a self-loop is an edge whose both ends are the same node. ### Connected Components Use connected_components() method to find all connected components. ## 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 output of the above code is: (1, array([0, 0, 0], dtype=int32)) ### Dijkstra -- Shortest Path Algorithm Dijkstra shortest path algorithm is used to calculate the shortest path from one node to all other nodes. Scipy uses dijkstra() method to calculate the shortest path from one element to other elements. The dijkstra() method can set the following parameters: 1. **return_predecessors:** Boolean value, set to True to traverse all paths, set to False if you don't want to traverse all paths. 2. **indices:** Element index, return all paths for that element. 3. **limit:** Maximum weight of the path. ## Example Find the shortest path from element 1 to element 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 output of the above code is: (array([ 0., 1., 2.]), array([-9999, 0, 0], dtype=int32)) ### Floyd Warshall -- Floyd Algorithm Floyd algorithm is an algorithm for solving the shortest path between any two points. Scipy uses 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 output of the above code is: (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 Bellman-Ford algorithm is an algorithm for solving the shortest path between any two points. Scipy uses bellman_ford() method to find the shortest path between all pairs of elements, it can usually be used in any graph, including directed graphs and graphs with negative edge weights. ## Example Using a graph with negative edge weights, find the shortest path from element 1 to element 2: 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 output of the above code is: (array([ 0., -1., 2.]), array([-9999, 0, 0], dtype=int32)) ### Depth First Order depth_first_order() method returns the depth-first traversal order from a node. It can accept the following parameters: * Graph * Element to start traversing the graph ## Example