gearpump-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Manu Zhang (JIRA)" <j...@apache.org>
Subject [jira] [Created] (GEARPUMP-349) Graph#topologicalOrderIterator is slow for large graph
Date Mon, 04 Sep 2017 11:47:00 GMT
Manu Zhang created GEARPUMP-349:
-----------------------------------

             Summary: 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



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

Mime
View raw message