X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=Data%2FGraph.hs;h=6627f0476ac4591c16016c15882ab3810943ca23;hb=4c6a5640f35898d9f3526b98a5b89e6af9d793a9;hp=42059640f4671e79cb5db43399b3ec4a44d30389;hpb=715c78df1e7cdd474926cd919f4193fa9d23ab5e;p=haskell-directory.git

diff --git a/Data/Graph.hs b/Data/Graph.hs
index 4205964..6627f04 100644
--- a/Data/Graph.hs
+++ b/Data/Graph.hs
@@ -6,7 +6,7 @@
 -- 
 -- Maintainer  :  libraries@haskell.org
 -- Stability   :  experimental
--- Portability :  non-portable (requires non-portable module ST)
+-- Portability :  non-portable (uses Control.Monad.ST)
 --
 -- A version of the graph algorithms described in:
 --
@@ -28,7 +28,7 @@ module Data.Graph(
 
 	-- ** Building graphs
 
-	graphFromEdges, buildG, transposeG,
+	graphFromEdges, graphFromEdges', buildG, transposeG,
 	-- reverseE,
 
 	-- ** Graph properties
@@ -121,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)
@@ -179,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
@@ -186,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)