Changeset View
Changeset View
Standalone View
Standalone View
java/src/main/java/org/softwareheritage/graph/Traversal.java
Show First 20 Lines • Show All 140 Lines • ▼ Show 20 Lines | public ArrayList<Long> neighbors(long srcNodeId) { | ||||
ArrayList<Long> nodeIds = new ArrayList<>(); | ArrayList<Long> nodeIds = new ArrayList<>(); | ||||
neighborsVisitor(srcNodeId, nodeIds::add); | neighborsVisitor(srcNodeId, nodeIds::add); | ||||
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, Object max_edges, | ||||
boolean limitedVisit) { | |||||
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); | ||||
Long limit_edges = null; | |||||
if (!Objects.isNull(max_edges)) { | |||||
limitedVisit = true; | |||||
limit_edges = Long.valueOf(max_edges.toString()); | |||||
} | |||||
while (!stack.isEmpty()) { | while (!stack.isEmpty()) { | ||||
long currentNodeId = stack.pop(); | long currentNodeId = stack.pop(); | ||||
if (nodeCb != null) { | if (nodeCb != null) { | ||||
nodeCb.accept(currentNodeId); | nodeCb.accept(currentNodeId); | ||||
} | } | ||||
nbEdgesAccessed += graph.outdegree(currentNodeId); | nbEdgesAccessed += graph.outdegree(currentNodeId); | ||||
if (limitedVisit) { | |||||
if (limit_edges.compareTo(nbEdgesAccessed) <= 0) { | |||||
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;) { | ||||
if (edgeCb != null) { | if (edgeCb != null) { | ||||
edgeCb.accept(currentNodeId, neighborNodeId); | edgeCb.accept(currentNodeId, neighborNodeId); | ||||
} | } | ||||
if (!visited.contains(neighborNodeId)) { | if (!visited.contains(neighborNodeId)) { | ||||
stack.push(neighborNodeId); | stack.push(neighborNodeId); | ||||
visited.add(neighborNodeId); | visited.add(neighborNodeId); | ||||
} | } | ||||
} | } | ||||
} | } | ||||
} | } | ||||
/** One-argument version to handle callbacks properly */ | /** Two argument version for count_visitor */ | ||||
public void visitNodesVisitor(long srcNodeId, NodeIdConsumer cb) { | public void visitNodesVisitor(long srcNodeId, NodeIdConsumer cb) { | ||||
visitNodesVisitor(srcNodeId, cb, null); | visitNodesVisitor(srcNodeId, cb, null, null, false); | ||||
} | |||||
/** One-argument version to handle callbacks properly */ | |||||
public void visitNodesVisitor(long srcNodeId, NodeIdConsumer cb, Object max_edges) { | |||||
visitNodesVisitor(srcNodeId, cb, null, max_edges, false); | |||||
} | } | ||||
/** | /** | ||||
* Performs a graph traversal and returns explored nodes. | * Performs a graph traversal and returns explored nodes. | ||||
* | * | ||||
* @param srcNodeId source node | * @param srcNodeId source node | ||||
* @return list of explored node ids | * @return list of explored node ids | ||||
*/ | */ | ||||
public ArrayList<Long> visitNodes(long srcNodeId) { | public ArrayList<Long> visitNodes(long srcNodeId) { | ||||
ArrayList<Long> nodeIds = new ArrayList<>(); | ArrayList<Long> nodeIds = new ArrayList<>(); | ||||
visitNodesVisitor(srcNodeId, nodeIds::add); | visitNodesVisitor(srcNodeId, nodeIds::add, null); | ||||
return nodeIds; | return nodeIds; | ||||
} | } | ||||
/** | /** | ||||
* Push version of {@link #visitPaths}: will fire passed callback on each discovered (complete) | * Push version of {@link #visitPaths}: will fire passed callback on each discovered (complete) | ||||
* path. | * path. | ||||
*/ | */ | ||||
public void visitPathsVisitor(long srcNodeId, PathConsumer cb) { | public void visitPathsVisitor(long srcNodeId, PathConsumer cb, Object max_edges) { | ||||
Stack<Long> currentPath = new Stack<>(); | Stack<Long> currentPath = new Stack<>(); | ||||
this.nbEdgesAccessed = 0; | this.nbEdgesAccessed = 0; | ||||
visitPathsInternalVisitor(srcNodeId, currentPath, cb); | boolean limitedVisit = false; | ||||
if (!Objects.isNull(max_edges)) { | |||||
limitedVisit = true; | |||||
Long l = Long.valueOf(max_edges.toString()); | |||||
visitPathsInternalVisitor(srcNodeId, currentPath, cb, l, limitedVisit); | |||||
} else { | |||||
visitPathsInternalVisitor(srcNodeId, currentPath, cb, null, limitedVisit); | |||||
} | |||||
} | } | ||||
/** | /** | ||||
* Performs a graph traversal and returns explored paths. | * Performs a graph traversal and returns explored paths. | ||||
* | * | ||||
* @param srcNodeId source node | * @param srcNodeId source node | ||||
* @return list of explored paths (represented as a list of node ids) | * @return list of explored paths (represented as a list of node ids) | ||||
*/ | */ | ||||
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, null); | ||||
return paths; | return paths; | ||||
} | } | ||||
private void visitPathsInternalVisitor(long currentNodeId, Stack<Long> currentPath, PathConsumer cb) { | private void visitPathsInternalVisitor(long currentNodeId, Stack<Long> currentPath, PathConsumer cb, Long max_edges, | ||||
boolean limitedVisit) { | |||||
currentPath.push(currentNodeId); | currentPath.push(currentNodeId); | ||||
long visitedNeighbors = 0; | long visitedNeighbors = 0; | ||||
nbEdgesAccessed += graph.outdegree(currentNodeId); | nbEdgesAccessed += graph.outdegree(currentNodeId); | ||||
if (limitedVisit) { | |||||
if (max_edges.compareTo(nbEdgesAccessed) <= 0) { | |||||
currentPath.pop(); | |||||
return; | |||||
} | |||||
} | |||||
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;) { | ||||
visitPathsInternalVisitor(neighborNodeId, currentPath, cb); | visitPathsInternalVisitor(neighborNodeId, currentPath, cb, max_edges, limitedVisit); | ||||
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 286 Lines • Show Last 20 Lines |