[
https://issues.apache.org/jira/browse/GEARPUMP-349?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16166191#comment-16166191
]
ASF GitHub Bot commented on GEARPUMP-349:
-----------------------------------------
Github user huafengw commented on a diff in the pull request:
https://github.com/apache/incubator-gearpump/pull/223#discussion_r138882103
--- Diff: core/src/main/scala/org/apache/gearpump/util/Graph.scala ---
@@ -355,19 +393,7 @@ class Graph[N, E](vertexList: List[N], edgeList:
List[(N, E, N)]) extends Serial
* check whether there is a loop
*/
def hasCycle(): Boolean = {
- @tailrec
- def detectCycle(graph: Graph[N, E]): Boolean = {
- if (graph.edges.isEmpty) {
- false
- } else if (graph.vertices.nonEmpty &&
!graph.vertices.exists(graph.inDegreeOf(_) == 0)) {
- true
- } else {
- graph.removeZeroInDegree
- detectCycle(graph)
- }
- }
-
- detectCycle(copy)
+ tryTopologicalOrderIterator.isFailure
--- End diff --
The graph is mutable so we have to check whether the Graph is changed if
caching the result.
> Graph#topologicalOrderIterator is slow for large graph
> ------------------------------------------------------
>
> Key: GEARPUMP-349
> URL: https://issues.apache.org/jira/browse/GEARPUMP-349
> Project: Apache Gearpump
> Issue Type: Improvement
> Components: core
> Affects Versions: 0.8.4
> Reporter: Manu Zhang
> Assignee: Huafeng Wang
> Fix For: 0.8.5
>
>
> The algorithm is as follows
> 1. find zero in-degree nodes from a copied graph.
> 2. remove nodes from the copied graph and add them to the output
> 3. repeat 1
> The issue is that step 1 traverses all remaining nodes each time, which costs
> the algorithm {{O(n^2)}} time
> {{Graph#hasCycle}} has a similar issue
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
