[ https://issues.apache.org/jira/browse/GEARPUMP-349?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16167223#comment-16167223 ]
ASF GitHub Bot commented on GEARPUMP-349: ----------------------------------------- Github user manuzhang commented on a diff in the pull request: https://github.com/apache/incubator-gearpump/pull/223#discussion_r139049560 --- Diff: core/src/main/scala/org/apache/gearpump/util/Graph.scala --- @@ -156,64 +155,64 @@ class Graph[N, E](vertexList: List[N], edgeList: List[(N, E, N)]) extends Serial * Current Graph is not changed. */ def mapVertex[NewNode](fun: N => NewNode): Graph[NewNode, E] = { - val vertexes = vertices.map(node => (node, fun(node))) + val newVertexes = getVertices.map(node => (node, fun(node))) - val vertexMap: Map[N, NewNode] = vertexes.toMap + val vertexMap: Map[N, NewNode] = newVertexes.toMap - val newEdges = edges.map { edge => + val newEdges = getEdges.map { edge => (vertexMap(edge._1), edge._2, vertexMap(edge._3)) } - new Graph(vertexes.map(_._2), newEdges) + new Graph(newVertexes.map(_._2), newEdges) --- End diff -- I believe the plural of Vertex is Vertices > 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)