| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Graph.DFS
Description
Synopsis
- dfs :: forall s w v e f. PlanarGraph s w v e f -> VertexId s w -> Tree (VertexId s w)
- type AdjacencyLists s w = Vector [VertexId s w]
- adjacencyLists :: PlanarGraph s w v e f -> AdjacencyLists s w
- dfs' :: forall s w. AdjacencyLists s w -> VertexId s w -> Tree (VertexId s w)
- dfsSensitive :: forall s w. (VertexId s w -> [VertexId s w]) -> VertexId s w -> Tree (VertexId s w)
- dfsFilterCycles :: Tree (VertexId s w) -> Tree (VertexId s w)
Documentation
dfs :: forall s w v e f. PlanarGraph s w v e f -> VertexId s w -> Tree (VertexId s w) Source #
DFS on a planar graph.
Running time: \(O(n)\)
Note that since our planar graphs are always connected there is no need need for dfs to take a list of start vertices.
type AdjacencyLists s w = Vector [VertexId s w] Source #
Adjacency list representation of a graph: for each vertex we simply list all connected neighbours.
adjacencyLists :: PlanarGraph s w v e f -> AdjacencyLists s w Source #
Transform into adjacencylist representation
dfs' :: forall s w. AdjacencyLists s w -> VertexId s w -> Tree (VertexId s w) Source #
DFS, from a given vertex, on a graph in AdjacencyLists representation.
Running time: \(O(n)\)
dfsSensitive :: forall s w. (VertexId s w -> [VertexId s w]) -> VertexId s w -> Tree (VertexId s w) Source #
DFS, from a given vertex, on a graph in AdjacencyLists representation. Cycles are not removed.
If your graph may contain cycles, see dfsFilterCycles.
Running time: \(O(k)\), where \(k\) is the number of nodes consumed.