[ https://issues.apache.org/jira/browse/GEARPUMP349?page=com.atlassian.jira.plugin.system.issuetabpanels:alltabpanel
]
Manu Zhang updated GEARPUMP349:

Description:
The algorithm is as follows
1. find zero indegree 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 indegree 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: GEARPUMP349
> URL: https://issues.apache.org/jira/browse/GEARPUMP349
> 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 indegree 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)
