Changeset View
Changeset View
Standalone View
Standalone View
java/src/main/java/org/softwareheritage/graph/Traversal.java
Show All 39 Lines | public class Traversal { | ||||
/** Number of edges accessed during traversal */ | /** Number of edges accessed during traversal */ | ||||
long nbEdgesAccessed; | long nbEdgesAccessed; | ||||
/** The anti Dos limit of edges traversed while a visit */ | /** The anti Dos limit of edges traversed while a visit */ | ||||
long maxEdges; | long maxEdges; | ||||
/** The string represent the set of type restriction */ | /** The string represent the set of type restriction */ | ||||
NodesFiltering ndsfilter; | NodesFiltering ndsfilter; | ||||
long currentEdgeAccessed = 0; | |||||
/** random number generator, for random walks */ | /** random number generator, for random walks */ | ||||
Random rng; | Random rng; | ||||
/** | /** | ||||
* Constructor. | * Constructor. | ||||
* | * | ||||
* @param graph graph used in the traversal | * @param graph graph used in the traversal | ||||
* @param direction a string (either "forward" or "backward") specifying edge orientation | * @param direction a string (either "forward" or "backward") specifying edge orientation | ||||
▲ Show 20 Lines • Show All 54 Lines • ▼ Show 20 Lines | public class Traversal { | ||||
} | } | ||||
/** | /** | ||||
* Push version of {@link #leaves} will fire passed callback for each leaf. | * Push version of {@link #leaves} will fire passed callback for each leaf. | ||||
*/ | */ | ||||
public void leavesVisitor(long srcNodeId, NodeIdConsumer cb) { | public void leavesVisitor(long srcNodeId, NodeIdConsumer cb) { | ||||
Stack<Long> stack = new Stack<>(); | Stack<Long> stack = new Stack<>(); | ||||
this.nbEdgesAccessed = 0; | this.nbEdgesAccessed = 0; | ||||
stack.push(srcNodeId); | stack.push(srcNodeId); | ||||
visited.add(srcNodeId); | visited.add(srcNodeId); | ||||
while (!stack.isEmpty()) { | while (!stack.isEmpty()) { | ||||
long currentNodeId = stack.pop(); | long currentNodeId = stack.pop(); | ||||
long neighborsCnt = 0; | long neighborsCnt = 0; | ||||
nbEdgesAccessed += graph.outdegree(currentNodeId); | nbEdgesAccessed += graph.outdegree(currentNodeId); | ||||
if (this.maxEdges > 0) { | |||||
if (nbEdgesAccessed >= this.maxEdges) { | |||||
break; | |||||
} | |||||
} | |||||
LazyLongIterator it = graph.successors(currentNodeId, edges); | LazyLongIterator it = graph.successors(currentNodeId, edges); | ||||
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { | for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { | ||||
neighborsCnt++; | neighborsCnt++; | ||||
if (this.maxEdges > 0) { | |||||
if (neighborsCnt >= this.maxEdges) { | |||||
return; | |||||
} | |||||
} | |||||
if (!visited.contains(neighborNodeId)) { | if (!visited.contains(neighborNodeId)) { | ||||
stack.push(neighborNodeId); | stack.push(neighborNodeId); | ||||
visited.add(neighborNodeId); | visited.add(neighborNodeId); | ||||
} | } | ||||
} | } | ||||
if (neighborsCnt == 0) { | if (neighborsCnt == 0) { | ||||
cb.accept(currentNodeId); | cb.accept(currentNodeId); | ||||
Show All 15 Lines | public ArrayList<Long> leaves(long srcNodeId) { | ||||
} | } | ||||
return nodeIds; | return nodeIds; | ||||
} | } | ||||
/** | /** | ||||
* Push version of {@link #neighbors}: will fire passed callback on each neighbor. | * Push version of {@link #neighbors}: will fire passed callback on each neighbor. | ||||
*/ | */ | ||||
public void neighborsVisitor(long srcNodeId, NodeIdConsumer cb) { | public void neighborsVisitor(long srcNodeId, NodeIdConsumer cb) { | ||||
this.nbEdgesAccessed = graph.outdegree(srcNodeId); | this.nbEdgesAccessed = graph.outdegree(srcNodeId); | ||||
LazyLongIterator it = graph.successors(srcNodeId, edges); | |||||
vlorentz: Why is it defined both here and as an object attribute? | |||||
Done Inline Actionsan error, my bad Hakimb: an error, my bad | |||||
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { | |||||
cb.accept(neighborNodeId); | |||||
this.currentEdgeAccessed++; | |||||
if (this.maxEdges > 0) { | if (this.maxEdges > 0) { | ||||
if (nbEdgesAccessed >= this.maxEdges) { | if (this.currentEdgeAccessed == this.maxEdges) { | ||||
return; | return; | ||||
} | } | ||||
} | } | ||||
LazyLongIterator it = graph.successors(srcNodeId, edges); | |||||
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { | |||||
cb.accept(neighborNodeId); | |||||
} | } | ||||
} | } | ||||
/** | /** | ||||
* Returns node direct neighbors (linked with exactly one edge). | * Returns node direct neighbors (linked with exactly one edge). | ||||
* | * | ||||
* @param srcNodeId source node | * @param srcNodeId source node | ||||
* @return list of node ids corresponding to the neighbors | * @return list of node ids corresponding to the neighbors | ||||
*/ | */ | ||||
public ArrayList<Long> neighbors(long srcNodeId) { | public ArrayList<Long> neighbors(long srcNodeId) { | ||||
ArrayList<Long> nodeIds = new ArrayList<>(); | ArrayList<Long> nodeIds = new ArrayList<>(); | ||||
neighborsVisitor(srcNodeId, nodeIds::add); | neighborsVisitor(srcNodeId, nodeIds::add); | ||||
if (ndsfilter.restricted) { | if (ndsfilter.restricted) { | ||||
return ndsfilter.filterByNodeTypes(nodeIds, graph); | return ndsfilter.filterByNodeTypes(nodeIds, graph); | ||||
} | } | ||||
return nodeIds; | return nodeIds; | ||||
} | } | ||||
/** | /** | ||||
* Push version of {@link #visitNodes}: will fire passed callback on each visited node. | * Push version of {@link #visitNodes}: will fire passed callback on each visited node. | ||||
*/ | */ | ||||
public void visitNodesVisitor(long srcNodeId, NodeIdConsumer nodeCb, EdgeIdConsumer edgeCb) { | public void visitNodesVisitor(long srcNodeId, NodeIdConsumer nodeCb, EdgeIdConsumer edgeCb) { | ||||
Stack<Long> stack = new Stack<>(); | Stack<Long> stack = new Stack<>(); | ||||
this.nbEdgesAccessed = 0; | this.nbEdgesAccessed = 0; | ||||
stack.push(srcNodeId); | stack.push(srcNodeId); | ||||
visited.add(srcNodeId); | visited.add(srcNodeId); | ||||
while (!stack.isEmpty()) { | while (!stack.isEmpty()) { | ||||
long currentNodeId = stack.pop(); | long currentNodeId = stack.pop(); | ||||
if (nodeCb != null) { | if (nodeCb != null) { | ||||
nodeCb.accept(currentNodeId); | |||||
} | |||||
nbEdgesAccessed += graph.outdegree(currentNodeId); | |||||
if (this.maxEdges > 0) { | if (this.maxEdges > 0) { | ||||
if (nbEdgesAccessed >= this.maxEdges) { | // we can go through n arcs, so at the end we must have | ||||
// the source node + n nodes reached through these n arcs | |||||
if (this.currentEdgeAccessed > this.maxEdges) { | |||||
break; | break; | ||||
} | } | ||||
} | } | ||||
nodeCb.accept(currentNodeId); | |||||
this.currentEdgeAccessed++; | |||||
} | |||||
nbEdgesAccessed += graph.outdegree(currentNodeId); | |||||
LazyLongIterator it = graph.successors(currentNodeId, edges); | LazyLongIterator it = graph.successors(currentNodeId, edges); | ||||
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { | for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { | ||||
if (edgeCb != null) { | if (edgeCb != null) { | ||||
if (this.maxEdges > 0) { | |||||
if (this.currentEdgeAccessed == this.maxEdges) { | |||||
return; | |||||
} | |||||
} | |||||
edgeCb.accept(currentNodeId, neighborNodeId); | edgeCb.accept(currentNodeId, neighborNodeId); | ||||
this.currentEdgeAccessed++; | |||||
} | } | ||||
if (!visited.contains(neighborNodeId)) { | if (!visited.contains(neighborNodeId)) { | ||||
stack.push(neighborNodeId); | stack.push(neighborNodeId); | ||||
visited.add(neighborNodeId); | visited.add(neighborNodeId); | ||||
} | } | ||||
} | } | ||||
} | } | ||||
} | } | ||||
Show All 37 Lines | public class Traversal { | ||||
public ArrayList<ArrayList<Long>> visitPaths(long srcNodeId) { | public ArrayList<ArrayList<Long>> visitPaths(long srcNodeId) { | ||||
ArrayList<ArrayList<Long>> paths = new ArrayList<>(); | ArrayList<ArrayList<Long>> paths = new ArrayList<>(); | ||||
visitPathsVisitor(srcNodeId, paths::add); | visitPathsVisitor(srcNodeId, paths::add); | ||||
return paths; | return paths; | ||||
} | } | ||||
private void visitPathsInternalVisitor(long currentNodeId, Stack<Long> currentPath, PathConsumer cb) { | private void visitPathsInternalVisitor(long currentNodeId, Stack<Long> currentPath, PathConsumer cb) { | ||||
currentPath.push(currentNodeId); | currentPath.push(currentNodeId); | ||||
long visitedNeighbors = 0; | long visitedNeighbors = 0; | ||||
nbEdgesAccessed += graph.outdegree(currentNodeId); | nbEdgesAccessed += graph.outdegree(currentNodeId); | ||||
LazyLongIterator it = graph.successors(currentNodeId, edges); | |||||
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { | |||||
if (this.maxEdges > 0) { | if (this.maxEdges > 0) { | ||||
if (nbEdgesAccessed >= this.maxEdges) { | if (this.currentEdgeAccessed == this.maxEdges) { | ||||
currentPath.pop(); | break; | ||||
return; | |||||
} | } | ||||
} | } | ||||
LazyLongIterator it = graph.successors(currentNodeId, edges); | this.currentEdgeAccessed++; | ||||
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { | |||||
visitPathsInternalVisitor(neighborNodeId, currentPath, cb); | visitPathsInternalVisitor(neighborNodeId, currentPath, cb); | ||||
visitedNeighbors++; | visitedNeighbors++; | ||||
} | } | ||||
if (visitedNeighbors == 0) { | if (visitedNeighbors == 0) { | ||||
ArrayList<Long> path = new ArrayList<>(currentPath); | ArrayList<Long> path = new ArrayList<>(currentPath); | ||||
cb.accept(path); | cb.accept(path); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 290 Lines • Show Last 20 Lines |
Why is it defined both here and as an object attribute?