Changeset View
Changeset View
Standalone View
Standalone View
java/src/main/java/org/softwareheritage/graph/algo/Traversal.java
package org.softwareheritage.graph.algo; | package org.softwareheritage.graph.algo; | ||||
import java.util.*; | import java.util.*; | ||||
import it.unimi.dsi.bits.LongArrayBitVector; | |||||
import org.softwareheritage.graph.AllowedEdges; | import org.softwareheritage.graph.AllowedEdges; | ||||
import org.softwareheritage.graph.Endpoint; | import org.softwareheritage.graph.Endpoint; | ||||
import org.softwareheritage.graph.Graph; | import org.softwareheritage.graph.Graph; | ||||
import org.softwareheritage.graph.Neighbors; | import org.softwareheritage.graph.Neighbors; | ||||
import org.softwareheritage.graph.Node; | import org.softwareheritage.graph.Node; | ||||
/** | /** | ||||
* Traversal algorithms on the compressed graph. | * Traversal algorithms on the compressed graph. | ||||
* <p> | * <p> | ||||
* Internal implementation of the traversal API endpoints. These methods only input/output internal | * Internal implementation of the traversal API endpoints. These methods only input/output internal | ||||
* long ids, which are converted in the {@link Endpoint} higher-level class to Software Heritage | * long ids, which are converted in the {@link Endpoint} higher-level class to Software Heritage | ||||
* PID. | * PID. | ||||
* | * | ||||
* @author The Software Heritage developers | * @author The Software Heritage developers | ||||
* @see org.softwareheritage.graph.Endpoint | * @see org.softwareheritage.graph.Endpoint | ||||
*/ | */ | ||||
public class Traversal { | public class Traversal { | ||||
/** Graph used in the traversal */ | /** Graph used in the traversal */ | ||||
Graph graph; | Graph graph; | ||||
/** Boolean to specify the use of the transposed graph */ | |||||
boolean useTransposed; | |||||
/** Graph edge restriction */ | /** Graph edge restriction */ | ||||
AllowedEdges edges; | AllowedEdges edges; | ||||
/** Hash set storing if we have visited a node */ | /** Hash set storing if we have visited a node */ | ||||
HashSet<Long> visited; | HashSet<Long> visited; | ||||
/** Hash map storing parent node id for each nodes during a traversal */ | /** Hash map storing parent node id for each nodes during a traversal */ | ||||
Map<Long, Long> parentNode; | Map<Long, Long> parentNode; | ||||
/** Number of edges accessed during traversal */ | /** Number of edges accessed during traversal */ | ||||
Show All 10 Lines | public class Traversal { | ||||
* @param edgesFmt a formatted string describing <a | * @param edgesFmt a formatted string describing <a | ||||
* href="https://docs.softwareheritage.org/devel/swh-graph/api.html#terminology">allowed edges</a> | * href="https://docs.softwareheritage.org/devel/swh-graph/api.html#terminology">allowed edges</a> | ||||
*/ | */ | ||||
public Traversal(Graph graph, String direction, String edgesFmt) { | public Traversal(Graph graph, String direction, String edgesFmt) { | ||||
if (!direction.matches("forward|backward")) { | if (!direction.matches("forward|backward")) { | ||||
throw new IllegalArgumentException("Unknown traversal direction: " + direction); | throw new IllegalArgumentException("Unknown traversal direction: " + direction); | ||||
} | } | ||||
if (direction.equals("backward")) { | |||||
this.graph = graph.transpose(); | |||||
} else { | |||||
this.graph = graph; | this.graph = graph; | ||||
this.useTransposed = (direction.equals("backward")); | } | ||||
this.edges = new AllowedEdges(graph, edgesFmt); | this.edges = new AllowedEdges(graph, edgesFmt); | ||||
long nbNodes = graph.getNbNodes(); | |||||
this.visited = new HashSet<>(); | this.visited = new HashSet<>(); | ||||
this.parentNode = new HashMap<>(); | this.parentNode = new HashMap<>(); | ||||
this.nbEdgesAccessed = 0; | this.nbEdgesAccessed = 0; | ||||
this.rng = new Random(); | this.rng = new Random(); | ||||
} | } | ||||
/** | /** | ||||
* Returns number of accessed edges during traversal. | * Returns number of accessed edges during traversal. | ||||
Show All 9 Lines | public class Traversal { | ||||
* | * | ||||
* @return number of nodes accessed in last traversal | * @return number of nodes accessed in last traversal | ||||
*/ | */ | ||||
public long getNbNodesAccessed() { | public long getNbNodesAccessed() { | ||||
return this.visited.size(); | return this.visited.size(); | ||||
} | } | ||||
/** | /** | ||||
* 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<Long>(); | 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.degree(currentNodeId, useTransposed); | nbEdgesAccessed += graph.outdegree(currentNodeId); | ||||
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { | for (long neighborNodeId : new Neighbors(graph, edges, currentNodeId)) { | ||||
neighborsCnt++; | neighborsCnt++; | ||||
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); | ||||
} | } | ||||
} | } | ||||
} | } | ||||
/** | /** | ||||
* Returns the leaves of a subgraph rooted at the specified source node. | * Returns the leaves of a subgraph rooted at the specified source node. | ||||
* | * | ||||
* @param srcNodeId source node | * @param srcNodeId source node | ||||
* @return list of node ids corresponding to the leaves | * @return list of node ids corresponding to the leaves | ||||
*/ | */ | ||||
public ArrayList<Long> leaves(long srcNodeId) { | public ArrayList<Long> leaves(long srcNodeId) { | ||||
ArrayList<Long> nodeIds = new ArrayList<Long>(); | ArrayList<Long> nodeIds = new ArrayList<>(); | ||||
leavesVisitor(srcNodeId, (nodeId) -> nodeIds.add(nodeId)); | leavesVisitor(srcNodeId, nodeIds::add); | ||||
return nodeIds; | return nodeIds; | ||||
} | } | ||||
/** | /** | ||||
* Push version of {@link neighbors}: will fire passed callback on each | * Push version of {@link #neighbors}: will fire passed callback on each | ||||
* neighbor. | * neighbor. | ||||
*/ | */ | ||||
public void neighborsVisitor(long srcNodeId, NodeIdConsumer cb) { | public void neighborsVisitor(long srcNodeId, NodeIdConsumer cb) { | ||||
this.nbEdgesAccessed = graph.degree(srcNodeId, useTransposed); | this.nbEdgesAccessed = graph.outdegree(srcNodeId); | ||||
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, srcNodeId)) { | for (long neighborNodeId : new Neighbors(graph, edges, srcNodeId)) { | ||||
cb.accept(neighborNodeId); | 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<Long>(); | ArrayList<Long> nodeIds = new ArrayList<>(); | ||||
neighborsVisitor(srcNodeId, (nodeId) -> nodeIds.add(nodeId)); | neighborsVisitor(srcNodeId, nodeIds::add); | ||||
return nodeIds; | return nodeIds; | ||||
} | } | ||||
/** | /** | ||||
* Push version of {@link visitNodes}: will fire passed callback on each | * Push version of {@link #visitNodes}: will fire passed callback on each | ||||
* visited node. | * 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<Long>(); | 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); | nodeCb.accept(currentNodeId); | ||||
} | } | ||||
nbEdgesAccessed += graph.degree(currentNodeId, useTransposed); | nbEdgesAccessed += graph.outdegree(currentNodeId); | ||||
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { | for (long neighborNodeId : new Neighbors(graph, edges, currentNodeId)) { | ||||
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 */ | /** One-argument version to handle callbacks properly */ | ||||
public void visitNodesVisitor(long srcNodeId, NodeIdConsumer cb) { | public void visitNodesVisitor(long srcNodeId, NodeIdConsumer cb) { | ||||
visitNodesVisitor(srcNodeId, cb, null); | visitNodesVisitor(srcNodeId, cb, null); | ||||
} | } | ||||
/** | /** | ||||
* 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<Long>(); | ArrayList<Long> nodeIds = new ArrayList<>(); | ||||
visitNodesVisitor(srcNodeId, (nodeId) -> nodeIds.add(nodeId)); | visitNodesVisitor(srcNodeId, nodeIds::add); | ||||
return nodeIds; | return nodeIds; | ||||
} | } | ||||
/** | /** | ||||
* Push version of {@link visitPaths}: will fire passed callback on each | * Push version of {@link #visitPaths}: will fire passed callback on each | ||||
* discovered (complete) path. | * discovered (complete) path. | ||||
*/ | */ | ||||
public void visitPathsVisitor(long srcNodeId, PathConsumer cb) { | public void visitPathsVisitor(long srcNodeId, PathConsumer cb) { | ||||
Stack<Long> currentPath = new Stack<Long>(); | Stack<Long> currentPath = new Stack<>(); | ||||
this.nbEdgesAccessed = 0; | this.nbEdgesAccessed = 0; | ||||
visitPathsInternalVisitor(srcNodeId, currentPath, cb); | visitPathsInternalVisitor(srcNodeId, currentPath, cb); | ||||
} | } | ||||
/** | /** | ||||
* 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, (path) -> paths.add(path)); | visitPathsVisitor(srcNodeId, paths::add); | ||||
return paths; | return paths; | ||||
} | } | ||||
private void visitPathsInternalVisitor(long currentNodeId, | private void visitPathsInternalVisitor(long currentNodeId, | ||||
Stack<Long> currentPath, | Stack<Long> currentPath, | ||||
PathConsumer cb) { | PathConsumer cb) { | ||||
currentPath.push(currentNodeId); | currentPath.push(currentNodeId); | ||||
long visitedNeighbors = 0; | long visitedNeighbors = 0; | ||||
nbEdgesAccessed += graph.degree(currentNodeId, useTransposed); | nbEdgesAccessed += graph.outdegree(currentNodeId); | ||||
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { | for (long neighborNodeId : new Neighbors(graph, edges, currentNodeId)) { | ||||
visitPathsInternalVisitor(neighborNodeId, currentPath, cb); | visitPathsInternalVisitor(neighborNodeId, currentPath, cb); | ||||
visitedNeighbors++; | visitedNeighbors++; | ||||
} | } | ||||
if (visitedNeighbors == 0) { | if (visitedNeighbors == 0) { | ||||
ArrayList<Long> path = new ArrayList<Long>(); | ArrayList<Long> path = new ArrayList<>(currentPath); | ||||
for (long nodeId : currentPath) { | |||||
path.add(nodeId); | |||||
} | |||||
cb.accept(path); | cb.accept(path); | ||||
} | } | ||||
currentPath.pop(); | currentPath.pop(); | ||||
} | } | ||||
/** | /** | ||||
* Performs a graph traversal with backtracking, and returns the first | * Performs a graph traversal with backtracking, and returns the first | ||||
* found path from source to destination. | * found path from source to destination. | ||||
* | * | ||||
* @param srcNodeId source node | * @param srcNodeId source node | ||||
* @param dst destination (either a node or a node type) | * @param dst destination (either a node or a node type) | ||||
* @return found path as a list of node ids | * @return found path as a list of node ids | ||||
*/ | */ | ||||
public <T> ArrayList<Long> walk(long srcNodeId, T dst, String visitOrder) { | public <T> ArrayList<Long> walk(long srcNodeId, T dst, String visitOrder) { | ||||
long dstNodeId = -1; | long dstNodeId; | ||||
if (visitOrder.equals("dfs")) { | if (visitOrder.equals("dfs")) { | ||||
dstNodeId = walkInternalDFS(srcNodeId, dst); | dstNodeId = walkInternalDFS(srcNodeId, dst); | ||||
} else if (visitOrder.equals("bfs")) { | } else if (visitOrder.equals("bfs")) { | ||||
dstNodeId = walkInternalBFS(srcNodeId, dst); | dstNodeId = walkInternalBFS(srcNodeId, dst); | ||||
} else { | } else { | ||||
throw new IllegalArgumentException("Unknown visit order: " + visitOrder); | throw new IllegalArgumentException("Unknown visit order: " + visitOrder); | ||||
} | } | ||||
if (dstNodeId == -1) { | if (dstNodeId == -1) { | ||||
throw new IllegalArgumentException("Cannot find destination: " + dst); | throw new IllegalArgumentException("Cannot find destination: " + dst); | ||||
} | } | ||||
ArrayList<Long> nodeIds = backtracking(srcNodeId, dstNodeId); | return backtracking(srcNodeId, dstNodeId); | ||||
return nodeIds; | |||||
} | } | ||||
/** | /** | ||||
* Performs a random walk (picking a random successor at each step) from | * Performs a random walk (picking a random successor at each step) from | ||||
* source to destination. | * source to destination. | ||||
* | * | ||||
* @param srcNodeId source node | * @param srcNodeId source node | ||||
* @param dst destination (either a node or a node type) | * @param dst destination (either a node or a node type) | ||||
Show All 13 Lines | public class Traversal { | ||||
* @param srcNodeId source node | * @param srcNodeId source node | ||||
* @param dst destination (either a node or a node type) | * @param dst destination (either a node or a node type) | ||||
* @param retries number of times to retry; 0 means no retries (single walk) | * @param retries number of times to retry; 0 means no retries (single walk) | ||||
* @return found path as a list of node ids or an empty path to indicate | * @return found path as a list of node ids or an empty path to indicate | ||||
* that no suitable path have been found | * that no suitable path have been found | ||||
*/ | */ | ||||
public <T> ArrayList<Long> randomWalk(long srcNodeId, T dst, int retries) { | public <T> ArrayList<Long> randomWalk(long srcNodeId, T dst, int retries) { | ||||
long curNodeId = srcNodeId; | long curNodeId = srcNodeId; | ||||
ArrayList<Long> path = new ArrayList<Long>(); | ArrayList<Long> path = new ArrayList<>(); | ||||
this.nbEdgesAccessed = 0; | this.nbEdgesAccessed = 0; | ||||
boolean found; | boolean found; | ||||
if (retries < 0) { | if (retries < 0) { | ||||
throw new IllegalArgumentException("Negative number of retries given: " + retries); | throw new IllegalArgumentException("Negative number of retries given: " + retries); | ||||
} | } | ||||
while (true) { | while (true) { | ||||
path.add(curNodeId); | path.add(curNodeId); | ||||
Neighbors neighbors = new Neighbors(graph, useTransposed, edges, curNodeId); | Neighbors neighbors = new Neighbors(graph, edges, curNodeId); | ||||
curNodeId = randomPick(neighbors.iterator()); | curNodeId = randomPick(neighbors.iterator()); | ||||
if (curNodeId < 0) { | if (curNodeId < 0) { | ||||
found = false; | found = false; | ||||
break; | break; | ||||
} | } | ||||
if (isDstNode(curNodeId, dst)) { | if (isDstNode(curNodeId, dst)) { | ||||
path.add(curNodeId); | path.add(curNodeId); | ||||
found = true; | found = true; | ||||
Show All 35 Lines | public class Traversal { | ||||
/** | /** | ||||
* Internal DFS function of {@link #walk}. | * Internal DFS function of {@link #walk}. | ||||
* | * | ||||
* @param srcNodeId source node | * @param srcNodeId source node | ||||
* @param dst destination (either a node or a node type) | * @param dst destination (either a node or a node type) | ||||
* @return final destination node or -1 if no path found | * @return final destination node or -1 if no path found | ||||
*/ | */ | ||||
private <T> long walkInternalDFS(long srcNodeId, T dst) { | private <T> long walkInternalDFS(long srcNodeId, T dst) { | ||||
Stack<Long> stack = new Stack<Long>(); | 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 (isDstNode(currentNodeId, dst)) { | if (isDstNode(currentNodeId, dst)) { | ||||
return currentNodeId; | return currentNodeId; | ||||
} | } | ||||
nbEdgesAccessed += graph.degree(currentNodeId, useTransposed); | nbEdgesAccessed += graph.outdegree(currentNodeId); | ||||
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { | for (long neighborNodeId : new Neighbors(graph, edges, currentNodeId)) { | ||||
if (!visited.contains(neighborNodeId)) { | if (!visited.contains(neighborNodeId)) { | ||||
stack.push(neighborNodeId); | stack.push(neighborNodeId); | ||||
visited.add(neighborNodeId); | visited.add(neighborNodeId); | ||||
parentNode.put(neighborNodeId, currentNodeId); | parentNode.put(neighborNodeId, currentNodeId); | ||||
} | } | ||||
} | } | ||||
} | } | ||||
return -1; | return -1; | ||||
} | } | ||||
/** | /** | ||||
* Internal BFS function of {@link #walk}. | * Internal BFS function of {@link #walk}. | ||||
* | * | ||||
* @param srcNodeId source node | * @param srcNodeId source node | ||||
* @param dst destination (either a node or a node type) | * @param dst destination (either a node or a node type) | ||||
* @return final destination node or -1 if no path found | * @return final destination node or -1 if no path found | ||||
*/ | */ | ||||
private <T> long walkInternalBFS(long srcNodeId, T dst) { | private <T> long walkInternalBFS(long srcNodeId, T dst) { | ||||
Queue<Long> queue = new LinkedList<Long>(); | Queue<Long> queue = new LinkedList<>(); | ||||
this.nbEdgesAccessed = 0; | this.nbEdgesAccessed = 0; | ||||
queue.add(srcNodeId); | queue.add(srcNodeId); | ||||
visited.add(srcNodeId); | visited.add(srcNodeId); | ||||
while (!queue.isEmpty()) { | while (!queue.isEmpty()) { | ||||
long currentNodeId = queue.poll(); | long currentNodeId = queue.poll(); | ||||
if (isDstNode(currentNodeId, dst)) { | if (isDstNode(currentNodeId, dst)) { | ||||
return currentNodeId; | return currentNodeId; | ||||
} | } | ||||
nbEdgesAccessed += graph.degree(currentNodeId, useTransposed); | nbEdgesAccessed += graph.outdegree(currentNodeId); | ||||
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { | for (long neighborNodeId : new Neighbors(graph, edges, currentNodeId)) { | ||||
if (!visited.contains(neighborNodeId)) { | if (!visited.contains(neighborNodeId)) { | ||||
queue.add(neighborNodeId); | queue.add(neighborNodeId); | ||||
visited.add(neighborNodeId); | visited.add(neighborNodeId); | ||||
parentNode.put(neighborNodeId, currentNodeId); | parentNode.put(neighborNodeId, currentNodeId); | ||||
} | } | ||||
} | } | ||||
} | } | ||||
Show All 22 Lines | public class Traversal { | ||||
/** | /** | ||||
* Internal backtracking function of {@link #walk}. | * Internal backtracking function of {@link #walk}. | ||||
* | * | ||||
* @param srcNodeId source node | * @param srcNodeId source node | ||||
* @param dstNodeId destination node | * @param dstNodeId destination node | ||||
* @return the found path, as a list of node ids | * @return the found path, as a list of node ids | ||||
*/ | */ | ||||
private ArrayList<Long> backtracking(long srcNodeId, long dstNodeId) { | private ArrayList<Long> backtracking(long srcNodeId, long dstNodeId) { | ||||
ArrayList<Long> path = new ArrayList<Long>(); | ArrayList<Long> path = new ArrayList<>(); | ||||
long currentNodeId = dstNodeId; | long currentNodeId = dstNodeId; | ||||
while (currentNodeId != srcNodeId) { | while (currentNodeId != srcNodeId) { | ||||
path.add(currentNodeId); | path.add(currentNodeId); | ||||
currentNodeId = parentNode.get(currentNodeId); | currentNodeId = parentNode.get(currentNodeId); | ||||
} | } | ||||
path.add(srcNodeId); | path.add(srcNodeId); | ||||
Collections.reverse(path); | Collections.reverse(path); | ||||
return path; | return path; | ||||
} | } | ||||
/** | |||||
* Find a common descendant between two given nodes using two parallel BFS | |||||
* | |||||
* @param lhsNode the first node | |||||
* @param rhsNode the second node | |||||
* @return the found path, as a list of node ids | |||||
*/ | |||||
public Long findCommonDescendant(long lhsNode, long rhsNode) { | public Long findCommonDescendant(long lhsNode, long rhsNode) { | ||||
Queue<Long> lhsStack = new ArrayDeque<>(); | Queue<Long> lhsStack = new ArrayDeque<>(); | ||||
Queue<Long> rhsStack = new ArrayDeque<>(); | Queue<Long> rhsStack = new ArrayDeque<>(); | ||||
HashSet<Long> lhsVisited = new HashSet<>(); | HashSet<Long> lhsVisited = new HashSet<>(); | ||||
HashSet<Long> rhsVisited = new HashSet<>(); | HashSet<Long> rhsVisited = new HashSet<>(); | ||||
lhsStack.add(lhsNode); | lhsStack.add(lhsNode); | ||||
rhsStack.add(rhsNode); | rhsStack.add(rhsNode); | ||||
lhsVisited.add(lhsNode); | lhsVisited.add(lhsNode); | ||||
rhsVisited.add(rhsNode); | rhsVisited.add(rhsNode); | ||||
this.nbEdgesAccessed = 0; | this.nbEdgesAccessed = 0; | ||||
Long curNode; | Long curNode; | ||||
while (!lhsStack.isEmpty() || !rhsStack.isEmpty()) { | while (!lhsStack.isEmpty() || !rhsStack.isEmpty()) { | ||||
if (!lhsStack.isEmpty()) { | if (!lhsStack.isEmpty()) { | ||||
curNode = lhsStack.poll(); | curNode = lhsStack.poll(); | ||||
nbEdgesAccessed += graph.degree(curNode, useTransposed); | nbEdgesAccessed += graph.outdegree(curNode); | ||||
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, curNode)) { | for (long neighborNodeId : new Neighbors(graph, edges, curNode)) { | ||||
if (!lhsVisited.contains(neighborNodeId)) { | if (!lhsVisited.contains(neighborNodeId)) { | ||||
if (rhsVisited.contains(neighborNodeId)) | if (rhsVisited.contains(neighborNodeId)) | ||||
return neighborNodeId; | return neighborNodeId; | ||||
lhsStack.add(neighborNodeId); | lhsStack.add(neighborNodeId); | ||||
lhsVisited.add(neighborNodeId); | lhsVisited.add(neighborNodeId); | ||||
} | } | ||||
} | } | ||||
} | } | ||||
if (!rhsStack.isEmpty()) { | if (!rhsStack.isEmpty()) { | ||||
curNode = rhsStack.poll(); | curNode = rhsStack.poll(); | ||||
nbEdgesAccessed += graph.degree(curNode, useTransposed); | nbEdgesAccessed += graph.outdegree(curNode); | ||||
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, curNode)) { | for (long neighborNodeId : new Neighbors(graph, edges, curNode)) { | ||||
if (!rhsVisited.contains(neighborNodeId)) { | if (!rhsVisited.contains(neighborNodeId)) { | ||||
if (lhsVisited.contains(neighborNodeId)) | if (lhsVisited.contains(neighborNodeId)) | ||||
return neighborNodeId; | return neighborNodeId; | ||||
rhsStack.add(neighborNodeId); | rhsStack.add(neighborNodeId); | ||||
rhsVisited.add(neighborNodeId); | rhsVisited.add(neighborNodeId); | ||||
} | } | ||||
} | } | ||||
} | } | ||||
} | } | ||||
return null; | return null; | ||||
} | } | ||||
} | } |