[project @ 2005-03-15 13:38:27 by simonmar]

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

diff --git a/Data/Graph.hs b/Data/Graph.hs
index 12b3a01..2edf495 100644 (file)
--- a/Data/Graph.hs
+++ b/Data/Graph.hs
@@ -28,7 +28,7 @@ module Data.Graph(
 
        -- ** Building graphs
 
-       graphFromEdges, buildG, transposeG,
+       graphFromEdges, graphFromEdges', buildG, transposeG,
        -- reverseE,
 
        -- ** Graph properties
@@ -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
@@ -117,7 +121,7 @@ stronglyConnCompR [] = []  -- added to avoid creating empty array in graphFromEd
 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)
@@ -175,6 +179,16 @@ outdegree  = mapT numEdges
 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
@@ -182,9 +196,9 @@ indegree  = outdegree . transposeG
 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)
@@ -321,6 +335,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 ]