[project @ 2005-02-03 10:38:44 by simonmar]

[ghc-base.git] / Data / Graph.hs

diff --git a/Data/Graph.hs b/Data/Graph.hs
index 130c7dd..4205964 100644 (file)
--- a/Data/Graph.hs
+++ b/Data/Graph.hs
@@ -43,7 +43,7 @@ module Data.Graph(
        components,
        scc,
        bcc,
-       -- back, cross, forward,
+       -- tree, back, cross, forward,
        reachable, path,
 
        module Data.Tree
@@ -60,6 +60,10 @@ import Data.Maybe
 import Data.Array
 import Data.List
 
+#ifdef __HADDOCK__
+import Prelude
+#endif
+
 -------------------------------------------------------------------------
 --                                                                     -
 --     External interface
@@ -101,7 +105,7 @@ stronglyConnComp edges0
 -- | 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
@@ -321,6 +325,10 @@ scc g = dfs g (reverse (postOrd (transposeG g)))
 -- 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 ]