haggle-0.1.0.0: A graph library offering mutable, immutable, and inductive graphs

Safe HaskellNone
LanguageHaskell2010

Data.Graph.Haggle.Algorithms.DFS

Contents

Description

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.

Synopsis

Depth-first Searches

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

The most general DFS

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

Forward parameterized DFS

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

Forward DFS

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

Reverse parameterized DFS

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

Reverse DFS

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

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

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

Undirected DFS

Depth-first Forests

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

The most general depth-first forest.

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

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

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

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

Derived Queries

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

Return a list of each connected component in the graph

noComponents :: Bidirectional g => g -> Int Source #

The number of components in the graph

isConnected :: Bidirectional g => g -> Bool Source #

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

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

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

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

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] Source #

Compute the set of vertices reachable from a root Vertex.