Repository: incubator-gearpump Updated Branches: refs/heads/master e95a31707 -> c80c06963
fix GEARPUMP-114 fix dead loop in graph with cycles Author: huafengw <[email protected]> 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 <[email protected]> Authored: Fri May 27 14:41:31 2016 +0800 Committer: manuzhang <[email protected]> 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"
