summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
raw | gz |
help

author | wenzelm |

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;

--- 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