inferlo.graphs.fast_dfs

inferlo.graphs.fast_dfs(vert_num: int, edges: ndarray) → FastDfsResult[source]

Depth-first search.

Runs the depth-first search algorithm on given simple undirected graph represented by an edge list and returns edges of DFS tree in order of visiting.

If input graph is disconnected, completes it to connected by adding edges between vertex 0 and vertices with minimal index from other connected components. If this was done, will set was_disconnected=True in returned object. Thanks to this, result always has exactly vert_num - 1 edges.

If input graph has cycles, not all edges of original graph will be in the output, and algorithm will indicate that by setting had_cycles=True in output object.

Parameters:

  • vert_num – Number of vertices in the graph.

  • edges – List of edges in the graph. np.array of type np.int32 and shape (num_edges, 2).

Returns:

FastDfsResult object with result of the DFS and additional data.

Fields in result object

  • dfs_edges - np.array of type np.int32 and shape (vert_num-1, 2). Contains edges in DFS tree in DFS traversal order (from root to leafs). These edges are guaranteed to form a tree.

  • had_cycles - whether input graph had cycles.

  • was_disconnected - whether input graph was disconnected.

  • was_tree - whether input graph was a tree.

See https://en.wikipedia.org/wiki/Depth-first_search.