Data.Graph.Haggle.Algorithms.DFS

Depth-first search and derived operations.

All of the search variants take a list of Vertex that serves as roots for the search.

The [x] variants (xdfsWith and xdffWith) are the most general and are fully configurable in direction and action. They take a "direction" function that tells the search what vertices are next from the current Vertex. They also take a summarization function to convert a Vertex into some other value. This could be id or a function to extract a label, if supported by your graph type.

The [r] variants are reverse searches, while the [u] variants are undirected.

A depth-first forest is a collection (list) of depth-first trees. A depth-first tree is an n-ary tree rooted at a vertex that contains the vertices reached in a depth-first search from that root. The edges in the tree are a subset of the edges in the graph.

Depth-first Searches

xdfsWith :: Graph g => g -> (Vertex -> [Vertex]) -> (Vertex -> c) -> [Vertex] -> [c]

The most general DFS

dfsWith :: Graph g => g -> (Vertex -> c) -> [Vertex] -> [c]

Forward parameterized DFS

dfs :: Graph g => g -> [Vertex] -> [Vertex]

Forward DFS

rdfsWith :: Bidirectional g => g -> (Vertex -> c) -> [Vertex] -> [c]

Reverse parameterized DFS

rdfs :: Bidirectional g => g -> [Vertex] -> [Vertex]

Reverse DFS

udfsWith :: Bidirectional g => g -> (Vertex -> c) -> [Vertex] -> [c]

Undirected parameterized DFS. This variant follows both incoming and outgoing edges from each Vertex.

udfs :: Bidirectional g => g -> [Vertex] -> [Vertex]

Undirected DFS

Depth-first Forests

xdffWith :: Graph g => g -> (Vertex -> [Vertex]) -> (Vertex -> c) -> [Vertex] -> [Tree c]

The most general depth-first forest.

dffWith :: Graph g => g -> (Vertex -> c) -> [Vertex] -> [Tree c]

dff :: Graph g => g -> [Vertex] -> [Tree Vertex]

rdffWith :: Bidirectional g => g -> (Vertex -> c) -> [Vertex] -> [Tree c]

rdff :: Bidirectional g => g -> [Vertex] -> [Tree Vertex]

udffWith :: Bidirectional g => g -> (Vertex -> c) -> [Vertex] -> [Tree c]

udff :: Bidirectional g => g -> [Vertex] -> [Tree Vertex]

Derived Queries

components :: Bidirectional g => g -> [[Vertex]]

Return a list of each connected component in the graph

noComponents :: Bidirectional g => g -> Int

The number of components in the graph

isConnected :: Bidirectional g => g -> Bool

True if there is only a single component in the graph.

topsort :: Graph g => g -> [Vertex]

Topologically sort the graph; the input must be a DAG.

scc :: Bidirectional g => g -> [[Vertex]]

Return a list of each strongly-connected component in the graph. In a strongly-connected component, every vertex is reachable from every other vertex.

reachable :: Graph g => Vertex -> g -> [Vertex]

Compute the set of vertices reachable from a root Vertex.