[jira] [Updated] (GEARPUMP-349) Graph#topologicalOrderIterator is slow for large graph

["Manu Zhang (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/GEARPUMP-349?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Manu Zhang updated GEARPUMP-349:
--------------------------------
    Description: 
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

The same applies for {{Graph#hasCycle}}

  was:
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#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
>             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
> The same applies for {{Graph#hasCycle}}



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)