-- ** Building graphs
- graphFromEdges, buildG, transposeG,
+ graphFromEdges, graphFromEdges', buildG, transposeG,
-- reverseE,
-- ** Graph properties
components,
scc,
bcc,
- -- back, cross, forward,
+ -- tree, back, cross, forward,
reachable, path,
module Data.Tree
import Data.Array
import Data.List
+#ifdef __HADDOCK__
+import Prelude
+#endif
+
-------------------------------------------------------------------------
-- -
-- External interface
-- | 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.
--- The "R" interface is used when you expect to apply 'SCC' to
+-- 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.
stronglyConnCompR
stronglyConnCompR edges0
= map decode forest
where
- (graph, vertex_fn) = graphFromEdges edges0
+ (graph, vertex_fn,_) = graphFromEdges edges0
forest = scc graph
decode (Node v []) | mentions_itself v = CyclicSCC [vertex_fn v]
| otherwise = AcyclicSCC (vertex_fn v)
indegree :: Graph -> Table Int
indegree = outdegree . transposeG
+-- | 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.
+graphFromEdges'
+ :: Ord key
+ => [(node, key, [key])]
+ -> (Graph, Vertex -> (node, key, [key]))
+graphFromEdges' x = (a,b) where
+ (a,b,_) = graphFromEdges x
+
-- | 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
graphFromEdges
:: Ord key
=> [(node, key, [key])]
- -> (Graph, Vertex -> (node, key, [key]))
+ -> (Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex)
graphFromEdges edges0
- = (graph, \v -> vertex_map ! v)
+ = (graph, \v -> vertex_map ! v, key_vertex)
where
max_v = length edges0 - 1
bounds0 = (0,max_v) :: (Vertex, Vertex)
-- Algorithm 5: Classifying edges
------------------------------------------------------------
+tree :: Bounds -> Forest Vertex -> Graph
+tree bnds ts = buildG bnds (concat (map flat ts))
+ where flat (Node v ts) = [ (v, w) | Node w _us <- ts ] ++ concat (map flat ts)
+
back :: Graph -> Table Int -> Graph
back g post = mapT select g
where select v ws = [ w | w <- ws, post!v < post!w ]