gearpump-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <>
Subject [jira] [Commented] (GEARPUMP-349) Graph#topologicalOrderIterator is slow for large graph
Date Tue, 05 Sep 2017 09:01:00 GMT


ASF GitHub Bot commented on GEARPUMP-349:

GitHub user huafengw opened a pull request:

    [GEARPUMP-349] Optimize Graph topologicalOrderIterator performance

    Be sure to do all of the following to help us incorporate your contribution
    quickly and easily:
     - [ ] Make sure the commit message is formatted like:
       `[GEARPUMP-<Jira issue #>] Meaningful description of pull request` 
     - [ ] Make sure tests pass via `sbt clean test`.
     - [ ] Make sure old documentation affected by the pull request has been updated and new
documentation added for new functionality. 

You can merge this pull request into a Git repository by running:

    $ git pull graph

Alternatively you can review and apply these changes as the patch at:

To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:

    This closes #223
commit 2673c99cb26a8a0733af772f01748f818ea08857
Author: huafengw <>
Date:   2017-09-05T08:59:49Z

    [GEARPUMP-349] Optimize Graph topologicalOrderIterator performance


> Graph#topologicalOrderIterator is slow for large graph
> ------------------------------------------------------
>                 Key: GEARPUMP-349
>                 URL:
>             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

View raw message