| Copyright | (c) The University of Glasgow 2002 |
|---|---|
| License | BSD-style (see the file libraries/base/LICENSE) |
| Maintainer | libraries@haskell.org |
| Stability | experimental |
| Portability | portable |
| Safe Haskell | Trustworthy |
| Language | Haskell98 |
Data.Graph
Description
A version of the graph algorithms described in:
Structuring Depth-First Search Algorithms in Haskell, by David King and John Launchbury.
- stronglyConnComp :: Ord key => [(node, key, [key])] -> [SCC node]
- stronglyConnCompR :: Ord key => [(node, key, [key])] -> [SCC (node, key, [key])]
- data SCC vertex
- = AcyclicSCC vertex
- | CyclicSCC [vertex]
- flattenSCC :: SCC vertex -> [vertex]
- flattenSCCs :: [SCC a] -> [a]
- type Graph = Table [Vertex]
- type Table a = Array Vertex a
- type Bounds = (Vertex, Vertex)
- type Edge = (Vertex, Vertex)
- type Vertex = Int
- graphFromEdges :: Ord key => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex)
- graphFromEdges' :: Ord key => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key]))
- buildG :: Bounds -> [Edge] -> Graph
- transposeG :: Graph -> Graph
- vertices :: Graph -> [Vertex]
- edges :: Graph -> [Edge]
- outdegree :: Graph -> Table Int
- indegree :: Graph -> Table Int
- dfs :: Graph -> [Vertex] -> Forest Vertex
- dff :: Graph -> Forest Vertex
- topSort :: Graph -> [Vertex]
- components :: Graph -> Forest Vertex
- scc :: Graph -> Forest Vertex
- bcc :: Graph -> Forest [Vertex]
- reachable :: Graph -> Vertex -> [Vertex]
- path :: Graph -> Vertex -> Vertex -> Bool
- module Data.Tree
External interface
Arguments
| :: Ord key | |
| => [(node, key, [key])] | The graph: a list of nodes uniquely identified by keys, with a list of keys of nodes this node has edges to. The out-list may contain keys that don't correspond to nodes of the graph; such edges are ignored. |
| -> [SCC node] |
The strongly connected components of a directed graph, topologically sorted.
Arguments
| :: Ord key | |
| => [(node, key, [key])] | The graph: a list of nodes uniquely identified by keys, with a list of keys of nodes this node has edges to. The out-list may contain keys that don't correspond to nodes of the graph; such edges are ignored. |
| -> [SCC (node, key, [key])] | Topologically sorted |
The strongly connected components of a directed graph, topologically
sorted. The function is the same as stronglyConnComp, except that
all the information about each node retained.
This interface is used when you expect to apply SCC to
(some of) the result of SCC, so you don't want to lose the
dependency information.
data SCC vertex
Strongly connected component.
Constructors
| AcyclicSCC vertex | A single vertex that is not in any cycle. |
| CyclicSCC [vertex] | A maximal set of mutually reachable vertices. |
flattenSCC :: SCC vertex -> [vertex]
The vertices of a strongly connected component.
flattenSCCs :: [SCC a] -> [a]
The vertices of a list of strongly connected components.
Graphs
Adjacency list representation of a graph, mapping each vertex to its list of successors.
Building graphs
graphFromEdges :: Ord key => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex)
Build a graph from a list of nodes uniquely identified by keys, with a list of keys of nodes this node should have edges to. The out-list may contain keys that don't correspond to nodes of the graph; they are ignored.
graphFromEdges' :: Ord key => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key]))
Identical to graphFromEdges, except that the return value
does not include the function which maps keys to vertices. This
version of graphFromEdges is for backwards compatibility.
transposeG :: Graph -> Graph
The graph obtained by reversing all edges.
Graph properties
Algorithms
dfs :: Graph -> [Vertex] -> Forest Vertex
A spanning forest of the part of the graph reachable from the listed vertices, obtained from a depth-first search of the graph starting at each of the listed vertices in order.
A spanning forest of the graph, obtained from a depth-first search of the graph starting from each vertex in an unspecified order.
A topological sort of the graph. The order is partially specified by the condition that a vertex i precedes j whenever j is reachable from i but not vice versa.
components :: Graph -> Forest Vertex
The connected components of a graph. Two vertices are connected if there is a path between them, traversing edges in either direction.
bcc :: Graph -> Forest [Vertex]
The biconnected components of a graph. An undirected graph is biconnected if the deletion of any vertex leaves it connected.
module Data.Tree