You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@gearpump.apache.org by "Manu Zhang (JIRA)" <ji...@apache.org> on 2017/09/04 11:47:00 UTC
[jira] [Created] (GEARPUMP-349) Graph#topologicalOrderIterator is
slow for large graph
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)