[
https://issues.apache.org/jira/browse/GEARPUMP-349?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16167305#comment-16167305
]
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_r139061240
--- Diff: core/src/main/scala/org/apache/gearpump/util/Graph.scala ---
@@ -140,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 newVertices = getVertices.map(node => (node, fun(node)))
- val vertexMap: Map[N, NewNode] = vertexes.toMap
+ val vertexMap: Map[N, NewNode] = newVertices.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(newVertices.map(_._2), newEdges)
}
/**
* Map a graph to a new graph, with edge converted to new type
* Current graph is not changed.
*/
def mapEdge[NewEdge](fun: (N, E, N) => NewEdge): Graph[N, NewEdge] = {
- val newEdges = edges.map { edge =>
+ val newEdges = getEdges.map { edge =>
(edge._1, fun(edge._1, edge._2, edge._3), edge._3)
}
- new Graph(vertices, newEdges)
+ new Graph(getVertices, newEdges)
}
/**
* edges connected to node
*/
def edgesOf(node: N): List[(N, E, N)] = {
- (incomingEdgesOf(node) ++ outgoingEdgesOf(node)).toSet[(N, E,
N)].toList.sortBy(_indexs(_))
+ (incomingEdgesOf(node) ++ outgoingEdgesOf(node)).toList
--- End diff --
no need to sort now ?
> 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)
