hgeometry-combinatorial-0.12.0.2: Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

Algorithms.Graph.DFS

Description

 
Synopsis

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.

dfsFilterCycles :: Tree (VertexId s w) -> Tree (VertexId s w) Source #

Remove infinite cycles from a DFS search tree.