You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@gearpump.apache.org by "ASF GitHub Bot (JIRA)" <ji...@apache.org> on 2017/09/05 09:01:00 UTC
[jira] [Commented] (GEARPUMP-349) Graph#topologicalOrderIterator is
slow for large graph
[ https://issues.apache.org/jira/browse/GEARPUMP-349?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16153300#comment-16153300 ]
ASF GitHub Bot commented on GEARPUMP-349:
-----------------------------------------
GitHub user huafengw opened a pull request:
https://github.com/apache/incubator-gearpump/pull/223
[GEARPUMP-349] Optimize Graph topologicalOrderIterator performance
Be sure to do all of the following to help us incorporate your contribution
quickly and easily:
- [ ] Make sure the commit message is formatted like:
`[GEARPUMP-<Jira issue #>] Meaningful description of pull request`
- [ ] Make sure tests pass via `sbt clean test`.
- [ ] Make sure old documentation affected by the pull request has been updated and new documentation added for new functionality.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/huafengw/incubator-gearpump graph
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/incubator-gearpump/pull/223.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #223
----
commit 2673c99cb26a8a0733af772f01748f818ea08857
Author: huafengw <fv...@gmail.com>
Date: 2017-09-05T08:59:49Z
[GEARPUMP-349] Optimize Graph topologicalOrderIterator performance
----
> 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
> Assignee: Huafeng Wang
> 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)