You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@gearpump.apache.org by ma...@apache.org on 2016/05/27 06:41:39 UTC
incubator-gearpump git commit: fix GEARPUMP-114 fix dead loop in
graph with cycles
Repository: incubator-gearpump
Updated Branches:
refs/heads/master e95a31707 -> c80c06963
fix GEARPUMP-114 fix dead loop in graph with cycles
Author: huafengw <fv...@gmail.com>
Closes #24 from huafengw/gear_114.
Project: http://git-wip-us.apache.org/repos/asf/incubator-gearpump/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-gearpump/commit/c80c0696
Tree: http://git-wip-us.apache.org/repos/asf/incubator-gearpump/tree/c80c0696
Diff: http://git-wip-us.apache.org/repos/asf/incubator-gearpump/diff/c80c0696
Branch: refs/heads/master
Commit: c80c069637f57ff9691373e1194027a8613f174d
Parents: e95a317
Author: huafengw <fv...@gmail.com>
Authored: Fri May 27 14:41:31 2016 +0800
Committer: manuzhang <ow...@gmail.com>
Committed: Fri May 27 14:41:31 2016 +0800
----------------------------------------------------------------------
.../scala/org/apache/gearpump/util/Graph.scala | 22 ++++++++++++++-----
.../org/apache/gearpump/util/GraphSpec.scala | 23 ++++++++++++++------
2 files changed, 32 insertions(+), 13 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-gearpump/blob/c80c0696/core/src/main/scala/org/apache/gearpump/util/Graph.scala
----------------------------------------------------------------------
diff --git a/core/src/main/scala/org/apache/gearpump/util/Graph.scala b/core/src/main/scala/org/apache/gearpump/util/Graph.scala
index 6bb58b8..2ea552c 100644
--- a/core/src/main/scala/org/apache/gearpump/util/Graph.scala
+++ b/core/src/main/scala/org/apache/gearpump/util/Graph.scala
@@ -318,6 +318,11 @@ class Graph[N, E](vertexList: List[N], edgeList: List[(N, E, N)]) extends Serial
* http://www.drdobbs.com/database/topological-sorting/184410262
*/
def topologicalOrderWithCirclesIterator: Iterator[N] = {
+ val topo = getAcyclicCopy().topologicalOrderIterator
+ topo.flatMap(_.sortBy(_indexs(_)).iterator)
+ }
+
+ private def getAcyclicCopy(): Graph[mutable.MutableList[N], E] = {
val circles = findCircles
val newGraph = Graph.empty[mutable.MutableList[N], E]
circles.foreach {
@@ -339,9 +344,7 @@ class Graph[N, E](vertexList: List[N], edgeList: List[(N, E, N)]) extends Serial
}
}
}
-
- val topo = newGraph.topologicalOrderIterator
- topo.flatMap(_.sortBy(_indexs(_)).iterator)
+ newGraph
}
/**
@@ -377,12 +380,19 @@ class Graph[N, E](vertexList: List[N], edgeList: List[(N, E, N)]) extends Serial
* }}}
*/
def vertexHierarchyLevelMap(): Map[N, Int] = {
- val newGraph = copy
+ val newGraph = getAcyclicCopy()
var output = Map.empty[N, Int]
var level = 0
while (!newGraph.isEmpty) {
- output ++= newGraph.removeZeroInDegree.map((_, level)).toMap
- level += 1
+ val toBeRemovedLists = newGraph.removeZeroInDegree
+ val maxLength = toBeRemovedLists.map(_.length).max
+ for (subGraph <- toBeRemovedLists) {
+ val sorted = subGraph.sortBy(_indexs)
+ for (i <- sorted.indices) {
+ output += sorted(i) -> (level + i)
+ }
+ }
+ level += maxLength
}
output
}
http://git-wip-us.apache.org/repos/asf/incubator-gearpump/blob/c80c0696/core/src/test/scala/org/apache/gearpump/util/GraphSpec.scala
----------------------------------------------------------------------
diff --git a/core/src/test/scala/org/apache/gearpump/util/GraphSpec.scala b/core/src/test/scala/org/apache/gearpump/util/GraphSpec.scala
index 2b6df78..6663513 100644
--- a/core/src/test/scala/org/apache/gearpump/util/GraphSpec.scala
+++ b/core/src/test/scala/org/apache/gearpump/util/GraphSpec.scala
@@ -108,15 +108,15 @@ class GraphSpec extends PropSpec with PropertyChecks with Matchers {
val levelMap = graph.vertexHierarchyLevelMap()
// Check whether the rule holds: : if vertex A -> B, then level(A) < level(B)
- levelMap("A") < levelMap("B")
- levelMap("A") < levelMap("C")
- levelMap("B") < levelMap("C")
+ assert(levelMap("A") < levelMap("B"))
+ assert(levelMap("A") < levelMap("C"))
+ assert(levelMap("B") < levelMap("C"))
- levelMap("D") < levelMap("E")
- levelMap("D") < levelMap("F")
- levelMap("E") < levelMap("F")
+ assert(levelMap("D") < levelMap("E"))
+ assert(levelMap("D") < levelMap("F"))
+ assert(levelMap("E") < levelMap("F"))
- levelMap("C") < levelMap("F")
+ assert(levelMap("C") < levelMap("F"))
}
property("copy should return a immutalbe new Graph") {
@@ -196,6 +196,15 @@ class GraphSpec extends PropSpec with PropertyChecks with Matchers {
assert(trueTopoWithCircles.zip(topoWithCircles).forall(x => x._1 == x._2))
}
+ property("Hierarchy level map should handle graph with cycles") {
+ val graph = Graph(0 ~> 1 ~> 2 ~> 3 ~> 4, 3 ~>1)
+ val map = graph.vertexHierarchyLevelMap()
+ assert(map(0) < map(1))
+ assert(map(1) < map(2))
+ assert(map(2) < map(3))
+ assert(map(3) < map(4))
+ }
+
property("Duplicated edges detecting should work properly") {
val graph = Graph.empty[String, String]
val defaultEdge = "edge"