[ 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 {{Graph#hasCycle}} has a similar issue 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 The same applies for {{Graph#hasCycle}} > 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 > {{Graph#hasCycle}} has a similar issue -- This message was sent by Atlassian JIRA (v6.4.14#64029)