Skip to content

Instantly share code, notes, and snippets.

@jponge
Created October 12, 2009 08:53
Show Gist options
  • Save jponge/208252 to your computer and use it in GitHub Desktop.
Save jponge/208252 to your computer and use it in GitHub Desktop.
From d0944d060b334922deefcf9afe44177df34ea347 Mon Sep 17 00:00:00 2001
From: jponge <jponge@2ab7d874-170b-494a-809f-82cdd2dfc457>
Date: Mon, 12 Oct 2009 08:42:52 +0000
Subject: [PATCH] More efficient and more functional directed graph completion.
git-svn-id: https://scm.gforge.inria.fr/svn/amazones/sandbox/amazones-protocols@601 2ab7d874-170b-494a-809f-82cdd2dfc457
---
.../amazones/protocols/model/DirectedGraph.scala | 17 +++++++++--------
1 files changed, 9 insertions(+), 8 deletions(-)
diff --git a/graphmodels/src/main/scala/fr/inria/amazones/protocols/model/DirectedGraph.scala b/graphmodels/src/main/scala/fr/inria/amazones/protocols/model/DirectedGraph.scala
index 7a204f1..09c384e 100644
--- a/graphmodels/src/main/scala/fr/inria/amazones/protocols/model/DirectedGraph.scala
+++ b/graphmodels/src/main/scala/fr/inria/amazones/protocols/model/DirectedGraph.scala
@@ -40,16 +40,17 @@ class DirectedGraph[V, E](val vertices: Set[V], val edges: Set[EdgeNode[V, E]])
def complete(sink: V): DirectedGraph[V, E] = complete(sink, edgeValues)
def complete(sink: V, values: Set[E]): DirectedGraph[V, E] = {
- var dg = this + sink
- values.foreach {
- v => dg = dg + EdgeNode(sink, v, sink)
- }
- vertices.foreach {
- vertice => (values -- dg.outgoingEdgeValues(vertice)).foreach {
- missing => dg = dg + EdgeNode(vertice, missing, sink)
+ val sinkToSink = values.map(EdgeNode(sink, _, sink))
+
+ val missingToSink = vertices.foldLeft(Set[EdgeNode[V, E]]()) {
+ (curSet, nextVertice) => {
+ (values -- outgoingEdgeValues(nextVertice)).foldLeft(curSet) {
+ (set, missingEdge) => set + EdgeNode(nextVertice, missingEdge, sink)
+ }
}
}
- dg
+
+ new DirectedGraph(vertices + sink, edges ++ sinkToSink ++ missingToSink)
}
def reachableFrom(vertice: V) = {
--
1.6.4.4+GitX
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment