fix #1935, add topological sort algorithm for graph with circles
Project: http://git-wip-us.apache.org/repos/asf/incubator-gearpump/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-gearpump/commit/55135fbb Tree: http://git-wip-us.apache.org/repos/asf/incubator-gearpump/tree/55135fbb Diff: http://git-wip-us.apache.org/repos/asf/incubator-gearpump/diff/55135fbb Branch: refs/heads/master Commit: 55135fbb459935064dd0f6fa0843601698dd71e3 Parents: 20c62e5 Author: pangolulu <[email protected]> Authored: Thu Jan 28 23:32:06 2016 +0800 Committer: pangolulu <[email protected]> Committed: Mon Feb 1 19:12:42 2016 +0800 ---------------------------------------------------------------------- .../src/main/scala/io/gearpump/util/Graph.scala | 88 ++++++++++++++++++++ .../test/scala/io/gearpump/util/GraphSpec.scala | 17 ++++ 2 files changed, 105 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-gearpump/blob/55135fbb/core/src/main/scala/io/gearpump/util/Graph.scala ---------------------------------------------------------------------- diff --git a/core/src/main/scala/io/gearpump/util/Graph.scala b/core/src/main/scala/io/gearpump/util/Graph.scala index c3035d0..6bff9da 100644 --- a/core/src/main/scala/io/gearpump/util/Graph.scala +++ b/core/src/main/scala/io/gearpump/util/Graph.scala @@ -254,6 +254,94 @@ class Graph[N, E](vertexList: List[N], edgeList: List[(N, E, N)]) extends Serial } /** + * Return all circles in graph. + * The reference of this algorithm is: + * https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm + */ + private def findCircles: mutable.MutableList[mutable.MutableList[N]] = { + val inStack = mutable.Map.empty[N, Boolean] + val stack = mutable.Stack[N]() + val indexMap = mutable.Map.empty[N, Int] + val lowLink = mutable.Map.empty[N, Int] + var index = 0 + + val circles = mutable.MutableList.empty[mutable.MutableList[N]] + + def tarjan(node: N): Unit = { + indexMap(node) = index + lowLink(node) = index + index += 1 + inStack(node) = true + stack.push(node) + + outgoingEdgesOf(node).foreach { + edge => { + if (!indexMap.contains(edge._3)) { + tarjan(edge._3) + if (lowLink.get(edge._3).get < lowLink.get(node).get) + lowLink(node) = lowLink(edge._3) + } else { + if (inStack.get(edge._3).get && (indexMap.get(edge._3).get < lowLink.get(node).get)) + lowLink(node) = indexMap(edge._3) + } + } + } + + if (indexMap.get(node).get == lowLink.get(node).get) { + val circle = mutable.MutableList.empty[N] + var n = node + do { + n = stack.pop() + inStack(n) = false + circle += n + } while (n != node) + circles += circle + } + } + + vertices.foreach { + node => { + if (!indexMap.contains(node)) tarjan(node) + } + } + + circles + } + + /** + * Return an iterator of vertex in topological order of graph with circles + * The node returned by Iterator is stable sorted. + * The reference of this algorithm is: + * http://www.drdobbs.com/database/topological-sorting/184410262 + */ + def topologicalOrderWithCirclesIterator: Iterator[N] = { + val circles = findCircles + val newGraph = Graph.empty[mutable.MutableList[N], E] + circles.foreach { + circle => { + newGraph.addVertex(circle) + } + } + + for (circle1 <- circles; circle2 <- circles; if circle1 != circle2) yield { + for (node1 <- circle1; node2 <- circle2) yield { + var edges = outgoingEdgesOf(node1) + for (edge <- edges; if edge._3 == node2) yield { + newGraph.addEdge(circle1, edge._2, circle2) + } + + edges = outgoingEdgesOf(node2) + for (edge <- edges; if edge._3 == node1) yield { + newGraph.addEdge(circle2, edge._2, circle1) + } + } + } + + val topo = newGraph.topologicalOrderIterator + topo.flatMap(_.sortBy(_indexs(_)).iterator) + } + + /** * check whether there is a loop */ def hasCycle(): Boolean = { http://git-wip-us.apache.org/repos/asf/incubator-gearpump/blob/55135fbb/core/src/test/scala/io/gearpump/util/GraphSpec.scala ---------------------------------------------------------------------- diff --git a/core/src/test/scala/io/gearpump/util/GraphSpec.scala b/core/src/test/scala/io/gearpump/util/GraphSpec.scala index 892350c..0028446 100644 --- a/core/src/test/scala/io/gearpump/util/GraphSpec.scala +++ b/core/src/test/scala/io/gearpump/util/GraphSpec.scala @@ -178,6 +178,23 @@ class GraphSpec extends PropSpec with PropertyChecks with Matchers { assert(graph.hasCycle()) } + property("topologicalOrderIterator " + + "and topologicalOrderWithCirclesIterator method should return equal order of graph with no circle") { + val graph = Graph(1 ~> 2 ~> 3, 4 ~> 2, 2 ~> 5) + val topoNoCircles = graph.topologicalOrderIterator + val topoWithCircles = graph.topologicalOrderWithCirclesIterator + + assert(topoNoCircles.zip(topoWithCircles).forall(x => x._1 == x._2)) + } + + property("Topological sort of graph with circles should work properly") { + val graph = Graph(0 ~> 1 ~> 3 ~> 4 ~> 6 ~> 5 ~> 7, 4 ~> 1, 1 ~> 2 ~> 4, 7 ~> 6, 8 ~> 2, 6 ~> 9, 4 ~> 10) + val topoWithCircles = graph.topologicalOrderWithCirclesIterator + val trueTopoWithCircles = Iterator[Int](0, 8, 1, 3, 4, 2, 6 ,5, 7, 10, 9) + + assert(trueTopoWithCircles.zip(topoWithCircles).forall(x => x._1 == x._2)) + } + property("Duplicated edges detecting should work properly") { val graph = Graph.empty[String, String] val defaultEdge = "edge"
