Mailing-List: contact dev-help@gearpump.incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@gearpump.incubator.apache.org
Date: Thu, 14 Sep 2017 12:53:00 +0000 (UTC)
From: "ASF GitHub Bot (JIRA)" <jira@apache.org>
To: dev@gearpump.incubator.apache.org
Message-ID: <JIRA.13099591.1504525572000.112112.1505393580260@Atlassian.JIRA>
In-Reply-To: <JIRA.13099591.1504525572000@Atlassian.JIRA>
References: <JIRA.13099591.1504525572000@Atlassian.JIRA> <JIRA.13099591.1504525572778@jira-lw-us.apache.org>
Subject: [jira] [Commented] (GEARPUMP-349) Graph#topologicalOrderIterator is
 slow for large graph
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
archived-at: Thu, 14 Sep 2017 12:53:05 -0000


    [ https://issues.apache.org/jira/browse/GEARPUMP-349?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16166199#comment-16166199 ] 

ASF GitHub Bot commented on GEARPUMP-349:
-----------------------------------------

Github user manuzhang commented on a diff in the pull request:

    https://github.com/apache/incubator-gearpump/pull/223#discussion_r138883853
  
    --- Diff: core/src/main/scala/org/apache/gearpump/util/Graph.scala ---
    @@ -243,13 +259,34 @@ class Graph[N, E](vertexList: List[N], edgeList: List[(N, E, N)]) extends Serial
        * The node returned by Iterator is stable sorted.
        */
       def topologicalOrderIterator: Iterator[N] = {
    -    val newGraph = copy
    -    var output = List.empty[N]
    -
    -    while (!newGraph.isEmpty) {
    -      output ++= newGraph.removeZeroInDegree
    +    tryTopologicalOrderIterator.get
    --- End diff --
    
    Then return a `Try` is better since the caller will be aware this method may fail then.


> 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)