gearpump-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (GEARPUMP-349) Graph#topologicalOrderIterator is slow for large graph
Date Fri, 15 Sep 2017 01:56:00 GMT

    [ https://issues.apache.org/jira/browse/GEARPUMP-349?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16167222#comment-16167222
] 

ASF GitHub Bot commented on GEARPUMP-349:
-----------------------------------------

Github user huafengw commented on a diff in the pull request:

    https://github.com/apache/incubator-gearpump/pull/223#discussion_r139049494
  
    --- Diff: core/src/main/scala/org/apache/gearpump/util/Graph.scala ---
    @@ -81,28 +86,35 @@ class Graph[N, E](vertexList: List[N], edgeList: List[(N, E, N)])
extends Serial
        * out degree
        */
       def outDegreeOf(node: N): Int = {
    -    edges.count(_._1 == node)
    +    outgoingEdgesOf(node).size
       }
     
       /**
        * in degree
        */
       def inDegreeOf(node: N): Int = {
    -    edges.count(_._3 == node)
    +    incomingEdgesOf(node).size
       }
     
       /**
        * out going edges.
        */
       def outgoingEdgesOf(node: N): List[(N, E, N)] = {
    -    edges.filter(_._1 == node)
    +    _outEdges.getOrElse(node, List.empty)
       }
     
       /**
        * incoming edges.
        */
       def incomingEdgesOf(node: N): List[(N, E, N)] = {
    -    edges.filter(_._3 == node)
    +    _inEdges.getOrElse(node, List.empty)
    +  }
    +
    +  /**
    +   * adjacent vertices.
    +   */
    +  def adjacentVertices(node: N): List[N] = {
    --- End diff --
    
    sure


> 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)

Mime
View raw message