| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.Graph.Haggle.Algorithms.DFS
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
- xdfsWith :: Graph g => g -> (Vertex -> [Vertex]) -> (Vertex -> c) -> [Vertex] -> [c]
- dfsWith :: Graph g => g -> (Vertex -> c) -> [Vertex] -> [c]
- dfs :: Graph g => g -> [Vertex] -> [Vertex]
- rdfsWith :: Bidirectional g => g -> (Vertex -> c) -> [Vertex] -> [c]
- rdfs :: Bidirectional g => g -> [Vertex] -> [Vertex]
- udfsWith :: Bidirectional g => g -> (Vertex -> c) -> [Vertex] -> [c]
- udfs :: Bidirectional g => g -> [Vertex] -> [Vertex]
- xdffWith :: Graph g => g -> (Vertex -> [Vertex]) -> (Vertex -> c) -> [Vertex] -> [Tree c]
- 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]
- components :: Bidirectional g => g -> [[Vertex]]
- noComponents :: Bidirectional g => g -> Int
- isConnected :: Bidirectional g => g -> Bool
- topsort :: Graph g => g -> [Vertex]
- scc :: Bidirectional g => g -> [[Vertex]]
- reachable :: Graph g => Vertex -> g -> [Vertex]
Depth-first Searches
xdfsWith :: Graph g => g -> (Vertex -> [Vertex]) -> (Vertex -> c) -> [Vertex] -> [c] Source #
The most general DFS
rdfsWith :: Bidirectional g => g -> (Vertex -> c) -> [Vertex] -> [c] Source #
Reverse parameterized DFS
udfsWith :: Bidirectional g => g -> (Vertex -> c) -> [Vertex] -> [c] Source #
Undirected parameterized DFS. This variant follows both
incoming and outgoing edges from each Vertex.
Depth-first Forests
xdffWith :: Graph g => g -> (Vertex -> [Vertex]) -> (Vertex -> c) -> [Vertex] -> [Tree c] Source #
The most general depth-first forest.
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.
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.