clarified transitive_closure: proper cumulation of transitive steps, which is essential for Warshall-style algorithms;
authorwenzelm
Mon, 10 Dec 2012 10:41:29 +0100
changeset 50447 2e22cdccdc38
parent 50446 8dc05db0bf69
child 50449 75e00ff42870
child 50450 358b6020f8b6
clarified transitive_closure: proper cumulation of transitive steps, which is essential for Warshall-style algorithms;
src/Pure/General/graph.scala
--- a/src/Pure/General/graph.scala	Sun Dec 09 14:05:21 2012 +0100
+++ b/src/Pure/General/graph.scala	Mon Dec 10 10:41:29 2012 +0100
@@ -224,17 +224,16 @@
 
   /* transitive closure and reduction */
 
-  def transitive_closure: Graph[Key, A] =
+  private def transitive_step(z: Key): Graph[Key, A] =
   {
+    val (preds, succs) = get_entry(z)._2
     var graph = this
-    for {
-      (_, (_, (preds, succs))) <- this.entries
-      x <- preds
-      y <- succs
-    } graph = graph.add_edge(x, y)
+    for (x <- preds; y <- succs) graph = graph.add_edge(x, y)
     graph
   }
 
+  def transitive_closure: Graph[Key, A] = (this /: keys)(_.transitive_step(_))
+
   def transitive_reduction_acyclic: Graph[Key, A] =
   {
     val trans = this.transitive_closure