Copyright | (c) The University of Glasgow 2002 |
---|---|
License | BSD-style (see the file libraries/base/LICENSE) |
Maintainer | libraries@haskell.org |
Portability | portable |
Safe Haskell | Trustworthy |
Language | Haskell98 |
A version of the graph algorithms described in:
Structuring Depth-First Search Algorithms in Haskell, by David King and John Launchbury.
Synopsis
- 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
- type Forest a = [Tree a]
- data Tree a = Node a (Forest a)
External interface
:: 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.
:: 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.
Strongly connected component.
AcyclicSCC vertex | A single vertex that is not in any cycle. |
CyclicSCC [vertex] | A maximal set of mutually reachable vertices. |
Instances
Functor SCC Source # | Since: containers-0.5.4 |
Foldable SCC Source # | Since: containers-0.5.9 |
Defined in Data.Graph fold :: Monoid m => SCC m -> m Source # foldMap :: Monoid m => (a -> m) -> SCC a -> m Source # foldr :: (a -> b -> b) -> b -> SCC a -> b Source # foldr' :: (a -> b -> b) -> b -> SCC a -> b Source # foldl :: (b -> a -> b) -> b -> SCC a -> b Source # foldl' :: (b -> a -> b) -> b -> SCC a -> b Source # foldr1 :: (a -> a -> a) -> SCC a -> a Source # foldl1 :: (a -> a -> a) -> SCC a -> a Source # toList :: SCC a -> [a] Source # null :: SCC a -> Bool Source # length :: SCC a -> Int Source # elem :: Eq a => a -> SCC a -> Bool Source # maximum :: Ord a => SCC a -> a Source # minimum :: Ord a => SCC a -> a Source # | |
Traversable SCC Source # | Since: containers-0.5.9 |
Eq1 SCC Source # | Since: containers-0.5.9 |
Read1 SCC Source # | Since: containers-0.5.9 |
Defined in Data.Graph | |
Show1 SCC Source # | Since: containers-0.5.9 |
Eq vertex => Eq (SCC vertex) Source # | Since: containers-0.5.9 |
Data vertex => Data (SCC vertex) Source # | Since: containers-0.5.9 |
Defined in Data.Graph gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SCC vertex -> c (SCC vertex) Source # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SCC vertex) Source # toConstr :: SCC vertex -> Constr Source # dataTypeOf :: SCC vertex -> DataType Source # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SCC vertex)) Source # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SCC vertex)) Source # gmapT :: (forall b. Data b => b -> b) -> SCC vertex -> SCC vertex Source # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SCC vertex -> r Source # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SCC vertex -> r Source # gmapQ :: (forall d. Data d => d -> u) -> SCC vertex -> [u] Source # gmapQi :: Int -> (forall d. Data d => d -> u) -> SCC vertex -> u Source # gmapM :: Monad m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) Source # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) Source # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) Source # | |
Read vertex => Read (SCC vertex) Source # | Since: containers-0.5.9 |
Show vertex => Show (SCC vertex) Source # | Since: containers-0.5.9 |
Generic (SCC vertex) Source # | |
NFData a => NFData (SCC a) Source # | |
Defined in Data.Graph | |
Generic1 SCC Source # | |
type Rep (SCC vertex) Source # | Since: containers-0.5.9 |
Defined in Data.Graph type Rep (SCC vertex) = D1 (MetaData "SCC" "Data.Graph" "containers-0.5.11.0" False) (C1 (MetaCons "AcyclicSCC" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 vertex)) :+: C1 (MetaCons "CyclicSCC" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 [vertex]))) | |
type Rep1 SCC Source # | Since: containers-0.5.9 |
Defined in Data.Graph type Rep1 SCC = D1 (MetaData "SCC" "Data.Graph" "containers-0.5.11.0" False) (C1 (MetaCons "AcyclicSCC" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1) :+: C1 (MetaCons "CyclicSCC" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec1 []))) |
flattenSCC :: SCC vertex -> [vertex] Source #
The vertices of a strongly connected component.
flattenSCCs :: [SCC a] -> [a] Source #
The vertices of a list of strongly connected components.
Graphs
type Graph = Table [Vertex] Source #
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) Source #
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])) Source #
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 Source #
The graph obtained by reversing all edges.
Graph properties
Algorithms
dfs :: Graph -> [Vertex] -> Forest Vertex Source #
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.
dff :: Graph -> Forest Vertex Source #
A spanning forest of the graph, obtained from a depth-first search of the graph starting from each vertex in an unspecified order.
topSort :: Graph -> [Vertex] Source #
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 Source #
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] Source #
The biconnected components of a graph. An undirected graph is biconnected if the deletion of any vertex leaves it connected.
Multi-way trees, also known as rose trees.
Instances
Monad Tree Source # | |
Functor Tree Source # | |
MonadFix Tree Source # | Since: containers-0.5.11 |
Applicative Tree Source # | |
Foldable Tree Source # | |
Defined in Data.Tree fold :: Monoid m => Tree m -> m Source # foldMap :: Monoid m => (a -> m) -> Tree a -> m Source # foldr :: (a -> b -> b) -> b -> Tree a -> b Source # foldr' :: (a -> b -> b) -> b -> Tree a -> b Source # foldl :: (b -> a -> b) -> b -> Tree a -> b Source # foldl' :: (b -> a -> b) -> b -> Tree a -> b Source # foldr1 :: (a -> a -> a) -> Tree a -> a Source # foldl1 :: (a -> a -> a) -> Tree a -> a Source # toList :: Tree a -> [a] Source # null :: Tree a -> Bool Source # length :: Tree a -> Int Source # elem :: Eq a => a -> Tree a -> Bool Source # maximum :: Ord a => Tree a -> a Source # minimum :: Ord a => Tree a -> a Source # | |
Traversable Tree Source # | |
Eq1 Tree Source # | Since: containers-0.5.9 |
Ord1 Tree Source # | Since: containers-0.5.9 |
Read1 Tree Source # | Since: containers-0.5.9 |
Defined in Data.Tree liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Tree a) Source # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Tree a] Source # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Tree a) Source # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Tree a] Source # | |
Show1 Tree Source # | Since: containers-0.5.9 |
MonadZip Tree Source # | |
Eq a => Eq (Tree a) Source # | |
Data a => Data (Tree a) Source # | |
Defined in Data.Tree gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Tree a -> c (Tree a) Source # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Tree a) Source # toConstr :: Tree a -> Constr Source # dataTypeOf :: Tree a -> DataType Source # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Tree a)) Source # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Tree a)) Source # gmapT :: (forall b. Data b => b -> b) -> Tree a -> Tree a Source # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r Source # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r Source # gmapQ :: (forall d. Data d => d -> u) -> Tree a -> [u] Source # gmapQi :: Int -> (forall d. Data d => d -> u) -> Tree a -> u Source # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Tree a -> m (Tree a) Source # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Tree a -> m (Tree a) Source # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Tree a -> m (Tree a) Source # | |
Read a => Read (Tree a) Source # | |
Show a => Show (Tree a) Source # | |
Generic (Tree a) Source # | |
NFData a => NFData (Tree a) Source # | |
Generic1 Tree Source # | |
type Rep (Tree a) Source # | Since: containers-0.5.8 |
Defined in Data.Tree type Rep (Tree a) = D1 (MetaData "Tree" "Data.Tree" "containers-0.5.11.0" False) (C1 (MetaCons "Node" PrefixI True) (S1 (MetaSel (Just "rootLabel") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a) :*: S1 (MetaSel (Just "subForest") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Forest a)))) | |
type Rep1 Tree Source # | Since: containers-0.5.8 |
Defined in Data.Tree type Rep1 Tree = D1 (MetaData "Tree" "Data.Tree" "containers-0.5.11.0" False) (C1 (MetaCons "Node" PrefixI True) (S1 (MetaSel (Just "rootLabel") NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1 :*: S1 (MetaSel (Just "subForest") NoSourceUnpackedness NoSourceStrictness DecidedLazy) ([] :.: Rec1 Tree))) |