Copyright	(c) The University of Glasgow 2002
License	BSD-style (see the file libraries/base/LICENSE)
Maintainer	libraries@haskell.org
Portability	portable
Safe Haskell	Safe
Language	Haskell98

Data.Graph

Contents

Graphs
Strongly Connected Components
- Construction
- Conversion
Trees

Description

Finite Graphs

The Graph type is an adjacency list representation of a finite, directed graph with vertices of type Int.

The SCC type represents a strongly-connected component of a graph.

Implementation

The implementation is based on

Structuring Depth-First Search Algorithms in Haskell, by David King and John Launchbury.

Synopsis

type Graph = Array Vertex [Vertex]
type Bounds = (Vertex, Vertex)
type Edge = (Vertex, Vertex)
type Vertex = Int
type Table a = Array Vertex a
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
vertices :: Graph -> [Vertex]
edges :: Graph -> [Edge]
outdegree :: Graph -> Array Vertex Int
indegree :: Graph -> Array Vertex Int
transposeG :: Graph -> Graph
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
data SCC vertex
- = AcyclicSCC vertex
- | CyclicSCC [vertex]
stronglyConnComp :: Ord key => [(node, key, [key])] -> [SCC node]
stronglyConnCompR :: Ord key => [(node, key, [key])] -> [SCC (node, key, [key])]
flattenSCC :: SCC vertex -> [vertex]
flattenSCCs :: [SCC a] -> [a]
type Forest a = [Tree a]
data Tree a = Node a (Forest a)

Graphs

type Graph = Array Vertex [Vertex] Source #

Adjacency list representation of a graph, mapping each vertex to its list of successors.

type Bounds = (Vertex, Vertex) Source #

The bounds of an Array.

type Edge = (Vertex, Vertex) Source #

An edge from the first vertex to the second.

type Vertex = Int Source #

Abstract representation of vertices.

type Table a = Array Vertex a Source #

Table indexed by a contiguous set of vertices.

Note: This is included for backwards compatibility.

Graph Construction

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.

This function takes an adjacency list representing a graph with vertices of type key labeled by values of type node and produces a Graph-based representation of that list. The Graph result represents the shape of the graph, and the functions describe a) how to retrieve the label and adjacent vertices of a given vertex, and b) how to retrive a vertex given a key.

(graph, nodeFromVertex, vertexFromKey) = graphFromEdges edgeList

graph :: Graph is the raw, array based adjacency list for the graph.
nodeFromVertex :: Vertex -> (node, key, [key]) returns the node associated with the given 0-based Int vertex; see warning below.
vertexFromKey :: key -> Maybe Vertex returns the Int vertex for the key if it exists in the graph, Nothing otherwise.

To safely use this API you must either extract the list of vertices directly from the graph or first call vertexFromKey k to check if a vertex corresponds to the key k. Once it is known that a vertex exists you can use nodeFromVertex to access the labelled node and adjacent vertices. See below for examples.

Note: The out-list may contain keys that don't correspond to nodes of the graph; they are ignored.

Warning: The nodeFromVertex function will cause a runtime exception if the given Vertex does not exist.

Examples

Expand

An empty graph.

(graph, nodeFromVertex, vertexFromKey) = graphFromEdges []
graph = array (0,-1) []

A graph where the out-list references unspecified nodes (c), these are ignored.

(graph, _, _) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c'])]
array (0,1) [(0,[1]),(1,[])]

A graph with 3 vertices: ("a") -> ("b") -> ("c")

(graph, nodeFromVertex, vertexFromKey) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c']), ("c", 'c', [])]
graph == array (0,2) [(0,[1]),(1,[2]),(2,[])]
nodeFromVertex 0 == ("a",'a',"b")
vertexFromKey 'a' == Just 0

Get the label for a given key.

let getNodePart (n, _, _) = n
(graph, nodeFromVertex, vertexFromKey) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c']), ("c", 'c', [])]
getNodePart . nodeFromVertex <$> vertexFromKey 'a' == Just "A"

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.

buildG :: Bounds -> [Edge] -> Graph Source #

Build a graph from a list of edges.

Warning: This function will cause a runtime exception if a vertex in the edge list is not within the given Bounds.

Examples

Expand

buildG (0,-1) [] == array (0,-1) []
buildG (0,2) [(0,1), (1,2)] == array (0,1) [(0,[1]),(1,[2])]
buildG (0,2) [(0,1), (0,2), (1,2)] == array (0,2) [(0,[2,1]),(1,[2]),(2,[])]

Graph Properties

vertices :: Graph -> [Vertex] Source #

Returns the list of vertices in the graph.

Examples

Expand

vertices (buildG (0,-1) []) == []

vertices (buildG (0,2) [(0,1),(1,2)]) == [0,1,2]

edges :: Graph -> [Edge] Source #

Returns the list of edges in the graph.

Examples

Expand

edges (buildG (0,-1) []) == []

edges (buildG (0,2) [(0,1),(1,2)]) == [(0,1),(1,2)]

outdegree :: Graph -> Array Vertex Int Source #

A table of the count of edges from each node.

Examples

Expand

outdegree (buildG (0,-1) []) == array (0,-1) []

outdegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,1),(1,1),(2,0)]

indegree :: Graph -> Array Vertex Int Source #

A table of the count of edges into each node.

Examples

Expand

indegree (buildG (0,-1) []) == array (0,-1) []

indegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,0),(1,1),(2,1)]

Graph Transformations

transposeG :: Graph -> Graph Source #

The graph obtained by reversing all edges.

Examples

Expand

transposeG (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,[]),(1,[0]),(2,[1])]

Graph 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.

scc :: Graph -> Forest Vertex Source #

The strongly connected components of a graph.

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.

reachable :: Graph -> Vertex -> [Vertex] Source #

Returns the list of vertices reachable from a given vertex.

Examples

Expand

reachable (buildG (0,0) []) 0 == [0]

reachable (buildG (0,2) [(0,1), (1,2)]) 0 == [0,1,2]

path :: Graph -> Vertex -> Vertex -> Bool Source #

Returns True if the second vertex reachable from the first.

Examples

Expand

path (buildG (0,0) []) 0 0 == True

path (buildG (0,2) [(0,1), (1,2)]) 0 2 == True

path (buildG (0,2) [(0,1), (1,2)]) 2 0 == False

Strongly Connected Components

data SCC vertex Source #

Strongly connected component.

Constructors

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
Instance details Defined in Data.Graph Methods fmap :: (a -> b) -> SCC a -> SCC b # (<$) :: a -> SCC b -> SCC a #
Foldable SCC Source #	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods fold :: Monoid m => SCC m -> m # foldMap :: Monoid m => (a -> m) -> SCC a -> m # foldr :: (a -> b -> b) -> b -> SCC a -> b # foldr' :: (a -> b -> b) -> b -> SCC a -> b # foldl :: (b -> a -> b) -> b -> SCC a -> b # foldl' :: (b -> a -> b) -> b -> SCC a -> b # foldr1 :: (a -> a -> a) -> SCC a -> a # foldl1 :: (a -> a -> a) -> SCC a -> a # toList :: SCC a -> [a] # null :: SCC a -> Bool # length :: SCC a -> Int # elem :: Eq a => a -> SCC a -> Bool # maximum :: Ord a => SCC a -> a # minimum :: Ord a => SCC a -> a # sum :: Num a => SCC a -> a # product :: Num a => SCC a -> a #
Traversable SCC Source #	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods traverse :: Applicative f => (a -> f b) -> SCC a -> f (SCC b) # sequenceA :: Applicative f => SCC (f a) -> f (SCC a) # mapM :: Monad m => (a -> m b) -> SCC a -> m (SCC b) # sequence :: Monad m => SCC (m a) -> m (SCC a) #
Eq1 SCC Source #	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods liftEq :: (a -> b -> Bool) -> SCC a -> SCC b -> Bool #
Read1 SCC Source #	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (SCC a) # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [SCC a] # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (SCC a) # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [SCC a] #
Show1 SCC Source #	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> SCC a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [SCC a] -> ShowS #
Eq vertex => Eq (SCC vertex) Source #	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods (==) :: SCC vertex -> SCC vertex -> Bool # (/=) :: SCC vertex -> SCC vertex -> Bool #
Data vertex => Data (SCC vertex) Source #	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SCC vertex -> c (SCC vertex) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SCC vertex) # toConstr :: SCC vertex -> Constr # dataTypeOf :: SCC vertex -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SCC vertex)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SCC vertex)) # gmapT :: (forall b. Data b => b -> b) -> SCC vertex -> SCC vertex # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SCC vertex -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SCC vertex -> r # gmapQ :: (forall d. Data d => d -> u) -> SCC vertex -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> SCC vertex -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) #
Read vertex => Read (SCC vertex) Source #	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods readsPrec :: Int -> ReadS (SCC vertex) # readList :: ReadS [SCC vertex] # readPrec :: ReadPrec (SCC vertex) # readListPrec :: ReadPrec [SCC vertex] #
Show vertex => Show (SCC vertex) Source #	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods showsPrec :: Int -> SCC vertex -> ShowS # show :: SCC vertex -> String # showList :: [SCC vertex] -> ShowS #
Generic (SCC vertex) Source #
Instance details Defined in Data.Graph Associated Types type Rep (SCC vertex) :: * -> * # Methods from :: SCC vertex -> Rep (SCC vertex) x # to :: Rep (SCC vertex) x -> SCC vertex #
NFData a => NFData (SCC a) Source #
Instance details Defined in Data.Graph Methods rnf :: SCC a -> () #
Generic1 SCC Source #
Instance details Defined in Data.Graph Associated Types type Rep1 SCC :: k -> * # Methods from1 :: SCC a -> Rep1 SCC a # to1 :: Rep1 SCC a -> SCC a #
type Rep (SCC vertex) Source #	Since: containers-0.5.9
Instance details Defined in Data.Graph type Rep (SCC vertex) = D1 (MetaData "SCC" "Data.Graph" "containers-0.6.0.1-6dUFjaTrYaoIACE6pzeQpO" 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
Instance details Defined in Data.Graph type Rep1 SCC = D1 (MetaData "SCC" "Data.Graph" "containers-0.6.0.1-6dUFjaTrYaoIACE6pzeQpO" 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 [])))

Construction

stronglyConnComp Source #

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.

stronglyConnCompR Source #

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.

Conversion

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.

Trees

type Forest a = [Tree a] Source #

data Tree a Source #

Non-empty, possibly infinite, multi-way trees; also known as rose trees.

Constructors

Node a (Forest a)

Instances

Monad Tree Source #
Instance details Defined in Data.Tree Methods (>>=) :: Tree a -> (a -> Tree b) -> Tree b # (>>) :: Tree a -> Tree b -> Tree b # return :: a -> Tree a # fail :: String -> Tree a #
Functor Tree Source #
Instance details Defined in Data.Tree Methods fmap :: (a -> b) -> Tree a -> Tree b # (<$) :: a -> Tree b -> Tree a #
MonadFix Tree Source #	Since: containers-0.5.11
Instance details Defined in Data.Tree Methods mfix :: (a -> Tree a) -> Tree a #
Applicative Tree Source #
Instance details Defined in Data.Tree Methods pure :: a -> Tree a # (<>) :: Tree (a -> b) -> Tree a -> Tree b # liftA2 :: (a -> b -> c) -> Tree a -> Tree b -> Tree c # (>) :: Tree a -> Tree b -> Tree b # (<*) :: Tree a -> Tree b -> Tree a #
Foldable Tree Source #
Instance details Defined in Data.Tree Methods fold :: Monoid m => Tree m -> m # foldMap :: Monoid m => (a -> m) -> Tree a -> m # foldr :: (a -> b -> b) -> b -> Tree a -> b # foldr' :: (a -> b -> b) -> b -> Tree a -> b # foldl :: (b -> a -> b) -> b -> Tree a -> b # foldl' :: (b -> a -> b) -> b -> Tree a -> b # foldr1 :: (a -> a -> a) -> Tree a -> a # foldl1 :: (a -> a -> a) -> Tree a -> a # toList :: Tree a -> [a] # null :: Tree a -> Bool # length :: Tree a -> Int # elem :: Eq a => a -> Tree a -> Bool # maximum :: Ord a => Tree a -> a # minimum :: Ord a => Tree a -> a # sum :: Num a => Tree a -> a # product :: Num a => Tree a -> a #
Traversable Tree Source #
Instance details Defined in Data.Tree Methods traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b) # sequenceA :: Applicative f => Tree (f a) -> f (Tree a) # mapM :: Monad m => (a -> m b) -> Tree a -> m (Tree b) # sequence :: Monad m => Tree (m a) -> m (Tree a) #
Eq1 Tree Source #	Since: containers-0.5.9
Instance details Defined in Data.Tree Methods liftEq :: (a -> b -> Bool) -> Tree a -> Tree b -> Bool #
Ord1 Tree Source #	Since: containers-0.5.9
Instance details Defined in Data.Tree Methods liftCompare :: (a -> b -> Ordering) -> Tree a -> Tree b -> Ordering #
Read1 Tree Source #	Since: containers-0.5.9
Instance details Defined in Data.Tree Methods liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Tree a) # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Tree a] # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Tree a) # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Tree a] #
Show1 Tree Source #	Since: containers-0.5.9
Instance details Defined in Data.Tree Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Tree a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Tree a] -> ShowS #
MonadZip Tree Source #
Instance details Defined in Data.Tree Methods mzip :: Tree a -> Tree b -> Tree (a, b) # mzipWith :: (a -> b -> c) -> Tree a -> Tree b -> Tree c # munzip :: Tree (a, b) -> (Tree a, Tree b) #
Eq a => Eq (Tree a) Source #
Instance details Defined in Data.Tree Methods (==) :: Tree a -> Tree a -> Bool # (/=) :: Tree a -> Tree a -> Bool #
Data a => Data (Tree a) Source #
Instance details Defined in Data.Tree Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Tree a -> c (Tree a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Tree a) # toConstr :: Tree a -> Constr # dataTypeOf :: Tree a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Tree a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Tree a)) # gmapT :: (forall b. Data b => b -> b) -> Tree a -> Tree a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r # gmapQ :: (forall d. Data d => d -> u) -> Tree a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Tree a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Tree a -> m (Tree a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Tree a -> m (Tree a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Tree a -> m (Tree a) #
Read a => Read (Tree a) Source #
Instance details Defined in Data.Tree Methods readsPrec :: Int -> ReadS (Tree a) # readList :: ReadS [Tree a] # readPrec :: ReadPrec (Tree a) # readListPrec :: ReadPrec [Tree a] #
Show a => Show (Tree a) Source #
Instance details Defined in Data.Tree Methods showsPrec :: Int -> Tree a -> ShowS # show :: Tree a -> String # showList :: [Tree a] -> ShowS #
Generic (Tree a) Source #
Instance details Defined in Data.Tree Associated Types type Rep (Tree a) :: * -> * # Methods from :: Tree a -> Rep (Tree a) x # to :: Rep (Tree a) x -> Tree a #
NFData a => NFData (Tree a) Source #
Instance details Defined in Data.Tree Methods rnf :: Tree a -> () #
Generic1 Tree Source #
Instance details Defined in Data.Tree Associated Types type Rep1 Tree :: k -> * # Methods from1 :: Tree a -> Rep1 Tree a # to1 :: Rep1 Tree a -> Tree a #
type Rep (Tree a) Source #	Since: containers-0.5.8
Instance details Defined in Data.Tree type Rep (Tree a) = D1 (MetaData "Tree" "Data.Tree" "containers-0.6.0.1-6dUFjaTrYaoIACE6pzeQpO" 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
Instance details Defined in Data.Tree type Rep1 Tree = D1 (MetaData "Tree" "Data.Tree" "containers-0.6.0.1-6dUFjaTrYaoIACE6pzeQpO" False) (C1 (MetaCons "Node" PrefixI True) (S1 (MetaSel (Just "rootLabel") NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1 :*: S1 (MetaSel (Just "subForest") NoSourceUnpackedness NoSourceStrictness DecidedLazy) ([] :.: Rec1 Tree)))