diff --git a/java/server/src/main/java/org/softwareheritage/graph/Endpoint.java b/java/server/src/main/java/org/softwareheritage/graph/Endpoint.java
index b1993bc..2323c3f 100644
--- a/java/server/src/main/java/org/softwareheritage/graph/Endpoint.java
+++ b/java/server/src/main/java/org/softwareheritage/graph/Endpoint.java
@@ -1,313 +1,313 @@
package org.softwareheritage.graph;
import java.util.ArrayList;
import org.softwareheritage.graph.Graph;
import org.softwareheritage.graph.SwhPID;
import org.softwareheritage.graph.SwhPath;
import org.softwareheritage.graph.algo.Traversal;
import org.softwareheritage.graph.benchmark.utils.Timing;
/**
* REST API endpoints wrapper functions.
*
* Graph operations are segmented between high-level class (this one) and the low-level class
* ({@link Traversal}). The {@link Endpoint} class creates wrappers for each endpoints by performing
* all the input/output node ids conversions and logging timings.
*
* @author Thibault Allançon
* @version 0.0.1
* @since 0.0.1
* @see org.softwareheritage.graph.algo.Traversal
*/
public class Endpoint {
/**
* Wrapper class to unify traversal methods input signatures.
*/
public static class Input {
/** Source node of endpoint call specified as a {@link SwhPID} */
public SwhPID src;
/**
* Destination formatted string as described in the API
*/
public String dstFmt;
/** Traversal algorithm used in endpoint call (either "dfs" or "bfs") */
public String algorithm;
public Input(SwhPID src) {
this.src = src;
}
public Input(SwhPID src, String dstFmt, String algorithm) {
this.src = src;
this.dstFmt = dstFmt;
this.algorithm = algorithm;
}
}
/**
* Wrapper class to return both the endpoint result and metadata (such as timings).
*/
public static class Output {
/** The result content itself */
public T result;
/** Various metadata about the result */
public Meta meta;
public Output() {
this.result = null;
this.meta = new Meta();
}
/**
* Endpoint result metadata.
*/
public class Meta {
/** Operations timings */
public Timings timings;
/** Number of edges accessed during traversal */
public long nbEdgesAccessed;
public Meta() {
this.timings = new Timings();
this.nbEdgesAccessed = 0;
}
/**
* Wrapper class for JSON output format.
*/
public class Timings {
/** Time in seconds to do the traversal */
public double traversal;
/** Time in seconds to convert input SWH PID to node id */
public double pid2node;
/** Time in seconds to convert output node ids to SWH PIDs */
public double node2pid;
}
}
}
/** Graph where traversal endpoint is performed */
Graph graph;
/** Internal traversal API */
Traversal traversal;
/**
* Constructor.
*
* @param graph the graph used for traversal endpoint
* @param direction a string (either "forward" or "backward") specifying edge orientation
* @param edgesFmt a formatted string describing allowed edges
*/
public Endpoint(Graph graph, String direction, String edgesFmt) {
this.graph = graph;
this.traversal = new Traversal(graph, direction, edgesFmt);
}
/**
* Converts a list of (internal) long node ids to a list of corresponding (external) SWH PIDs.
*
* @param nodeIds the list of long node ids
* @return a list of corresponding SWH PIDs
*/
private ArrayList convertNodesToSwhPIDs(ArrayList nodeIds) {
ArrayList swhPIDs = new ArrayList<>();
for (long nodeId : nodeIds) {
swhPIDs.add(graph.getSwhPID(nodeId));
}
return swhPIDs;
}
/**
* Converts a list of (internal) long node ids to the corresponding {@link SwhPath}.
*
* @param nodeIds the list of long node ids
* @return the corresponding {@link SwhPath}
* @see org.softwareheritage.graph.SwhPath
*/
private SwhPath convertNodesToSwhPath(ArrayList nodeIds) {
SwhPath path = new SwhPath();
for (long nodeId : nodeIds) {
path.add(graph.getSwhPID(nodeId));
}
return path;
}
/**
* Converts a list of paths made of (internal) long node ids to one made of {@link SwhPath}-s.
*
* @param pathsNodeId the list of paths with long node ids
* @return a list of corresponding {@link SwhPath}
* @see org.softwareheritage.graph.SwhPath
*/
private ArrayList convertPathsToSwhPIDs(ArrayList> pathsNodeId) {
ArrayList paths = new ArrayList<>();
for (ArrayList path : pathsNodeId) {
paths.add(convertNodesToSwhPath(path));
}
return paths;
}
/**
* Leaves endpoint wrapper.
*
* @param input input parameters for the underlying endpoint call
* @return the resulting list of {@link SwhPID} from endpoint call and operation metadata
* @see org.softwareheritage.graph.SwhPID
* @see org.softwareheritage.graph.algo.Traversal#leaves(long)
*/
public Output leaves(Input input) {
Output> output = new Output<>();
long startTime;
startTime = Timing.start();
long srcNodeId = graph.getNodeId(input.src);
output.meta.timings.pid2node = Timing.stop(startTime);
startTime = Timing.start();
ArrayList nodeIds = traversal.leaves(srcNodeId);
output.meta.timings.traversal = Timing.stop(startTime);
- output.meta.nbEdgesAccessed = traversal.getnbEdgesAccessed();
+ output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed();
startTime = Timing.start();
output.result = convertNodesToSwhPIDs(nodeIds);
output.meta.timings.node2pid = Timing.stop(startTime);
return output;
}
/**
* Neighbors endpoint wrapper.
*
* @param input input parameters for the underlying endpoint call
* @return the resulting list of {@link SwhPID} from endpoint call and operation metadata
* @see org.softwareheritage.graph.SwhPID
* @see org.softwareheritage.graph.algo.Traversal#neighbors(long)
*/
public Output neighbors(Input input) {
Output> output = new Output<>();
long startTime;
startTime = Timing.start();
long srcNodeId = graph.getNodeId(input.src);
output.meta.timings.pid2node = Timing.stop(startTime);
startTime = Timing.start();
ArrayList nodeIds = traversal.neighbors(srcNodeId);
output.meta.timings.traversal = Timing.stop(startTime);
- output.meta.nbEdgesAccessed = traversal.getnbEdgesAccessed();
+ output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed();
startTime = Timing.start();
output.result = convertNodesToSwhPIDs(nodeIds);
output.meta.timings.node2pid = Timing.stop(startTime);
return output;
}
/**
* Walk endpoint wrapper.
*
* @param input input parameters for the underlying endpoint call
* @return the resulting {@link SwhPath} from endpoint call and operation metadata
* @see org.softwareheritage.graph.SwhPID
* @see org.softwareheritage.graph.SwhPath
* @see org.softwareheritage.graph.algo.Traversal#walk
*/
public Output walk(Input input) {
Output output = new Output<>();
long startTime;
startTime = Timing.start();
long srcNodeId = graph.getNodeId(input.src);
output.meta.timings.pid2node = Timing.stop(startTime);
ArrayList nodeIds = new ArrayList();
// Destination is either a SWH PID or a node type
try {
SwhPID dstSwhPID = new SwhPID(input.dstFmt);
long dstNodeId = graph.getNodeId(dstSwhPID);
startTime = Timing.start();
nodeIds = traversal.walk(srcNodeId, dstNodeId, input.algorithm);
output.meta.timings.traversal = Timing.stop(startTime);
} catch (IllegalArgumentException ignored1) {
try {
Node.Type dstType = Node.Type.fromStr(input.dstFmt);
startTime = Timing.start();
nodeIds = traversal.walk(srcNodeId, dstType, input.algorithm);
output.meta.timings.traversal = Timing.stop(startTime);
} catch (IllegalArgumentException ignored2) {
}
}
- output.meta.nbEdgesAccessed = traversal.getnbEdgesAccessed();
+ output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed();
startTime = Timing.start();
output.result = convertNodesToSwhPath(nodeIds);
output.meta.timings.node2pid = Timing.stop(startTime);
return output;
}
/**
* VisitNodes endpoint wrapper.
*
* @param input input parameters for the underlying endpoint call
* @return the resulting list of {@link SwhPID} from endpoint call and operation metadata
* @see org.softwareheritage.graph.SwhPID
* @see org.softwareheritage.graph.algo.Traversal#visitNodes(long)
*/
public Output visitNodes(Input input) {
Output> output = new Output<>();
long startTime;
startTime = Timing.start();
long srcNodeId = graph.getNodeId(input.src);
output.meta.timings.pid2node = Timing.stop(startTime);
startTime = Timing.start();
ArrayList nodeIds = traversal.visitNodes(srcNodeId);
output.meta.timings.traversal = Timing.stop(startTime);
- output.meta.nbEdgesAccessed = traversal.getnbEdgesAccessed();
+ output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed();
startTime = Timing.start();
output.result = convertNodesToSwhPIDs(nodeIds);
output.meta.timings.node2pid = Timing.stop(startTime);
return output;
}
/**
* VisitPaths endpoint wrapper.
*
* @param input input parameters for the underlying endpoint call
* @return the resulting list of {@link SwhPath} from endpoint call and operation metadata
* @see org.softwareheritage.graph.SwhPID
* @see org.softwareheritage.graph.SwhPath
* @see org.softwareheritage.graph.algo.Traversal#visitPaths(long)
*/
public Output visitPaths(Input input) {
Output> output = new Output<>();
long startTime;
startTime = Timing.start();
long srcNodeId = graph.getNodeId(input.src);
output.meta.timings.pid2node = Timing.stop(startTime);
startTime = Timing.start();
ArrayList> paths = traversal.visitPaths(srcNodeId);
output.meta.timings.traversal = Timing.stop(startTime);
- output.meta.nbEdgesAccessed = traversal.getnbEdgesAccessed();
+ output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed();
startTime = Timing.start();
output.result = convertPathsToSwhPIDs(paths);
output.meta.timings.node2pid = Timing.stop(startTime);
return output;
}
}
diff --git a/java/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java b/java/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java
index 702edf4..7033c8b 100644
--- a/java/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java
+++ b/java/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java
@@ -1,334 +1,334 @@
package org.softwareheritage.graph.algo;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;
import it.unimi.dsi.bits.LongArrayBitVector;
import org.softwareheritage.graph.AllowedEdges;
import org.softwareheritage.graph.Endpoint;
import org.softwareheritage.graph.Graph;
import org.softwareheritage.graph.Neighbors;
import org.softwareheritage.graph.Node;
/**
* Traversal algorithms on the compressed graph.
*
* 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
* PID.
*
* @author Thibault Allançon
* @version 0.0.1
* @since 0.0.1
* @see org.softwareheritage.graph.Endpoint
*/
public class Traversal {
/** Graph used in the traversal */
Graph graph;
/** Boolean to specify the use of the transposed graph */
boolean useTransposed;
/** Graph edge restriction */
AllowedEdges edges;
/** Bit array storing if we have visited a node */
LongArrayBitVector visited;
/** Hash map storing parent node id for each nodes during a traversal */
Map parentNode;
/** Number of edges accessed during traversal */
long nbEdgesAccessed;
/**
* Constructor.
*
* @param graph graph used in the traversal
* @param direction a string (either "forward" or "backward") specifying edge orientation
* @param edgesFmt a formatted string describing allowed edges
*/
public Traversal(Graph graph, String direction, String edgesFmt) {
if (!direction.matches("forward|backward")) {
throw new IllegalArgumentException("Unknown traversal direction: " + direction);
}
this.graph = graph;
this.useTransposed = (direction.equals("backward"));
this.edges = new AllowedEdges(graph, edgesFmt);
long nbNodes = graph.getNbNodes();
this.visited = LongArrayBitVector.ofLength(nbNodes);
this.parentNode = new HashMap<>();
this.nbEdgesAccessed = 0;
}
/**
* Returns number of accessed edges during traversal.
*
* @return number of edges accessed in last traversal
*/
- public long getnbEdgesAccessed() {
+ public long getNbEdgesAccessed() {
return nbEdgesAccessed;
}
/**
* Returns the leaves of a subgraph rooted at the specified source node.
*
* @param srcNodeId source node
* @return list of node ids corresponding to the leaves
*/
public ArrayList leaves(long srcNodeId) {
ArrayList nodeIds = new ArrayList();
Stack stack = new Stack();
this.visited.fill(false);
this.nbEdgesAccessed = 0;
stack.push(srcNodeId);
visited.set(srcNodeId);
while (!stack.isEmpty()) {
long currentNodeId = stack.pop();
long neighborsCnt = 0;
nbEdgesAccessed += graph.degree(currentNodeId, useTransposed);
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
neighborsCnt++;
if (!visited.getBoolean(neighborNodeId)) {
stack.push(neighborNodeId);
visited.set(neighborNodeId);
}
}
if (neighborsCnt == 0) {
nodeIds.add(currentNodeId);
}
}
return nodeIds;
}
/**
* Returns node direct neighbors (linked with exactly one edge).
*
* @param srcNodeId source node
* @return list of node ids corresponding to the neighbors
*/
public ArrayList neighbors(long srcNodeId) {
ArrayList nodeIds = new ArrayList();
this.nbEdgesAccessed = graph.degree(srcNodeId, useTransposed);
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, srcNodeId)) {
nodeIds.add(neighborNodeId);
}
return nodeIds;
}
/**
* Performs a graph traversal and returns explored nodes.
*
* @param srcNodeId source node
* @return list of explored node ids
*/
public ArrayList visitNodes(long srcNodeId) {
ArrayList nodeIds = new ArrayList();
Stack stack = new Stack();
this.visited.fill(false);
this.nbEdgesAccessed = 0;
stack.push(srcNodeId);
visited.set(srcNodeId);
while (!stack.isEmpty()) {
long currentNodeId = stack.pop();
nodeIds.add(currentNodeId);
nbEdgesAccessed += graph.degree(currentNodeId, useTransposed);
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
if (!visited.getBoolean(neighborNodeId)) {
stack.push(neighborNodeId);
visited.set(neighborNodeId);
}
}
}
return nodeIds;
}
/**
* Performs a graph traversal and returns explored paths.
*
* @param srcNodeId source node
* @return list of explored paths (represented as a list of node ids)
*/
public ArrayList> visitPaths(long srcNodeId) {
ArrayList> paths = new ArrayList<>();
Stack currentPath = new Stack();
this.nbEdgesAccessed = 0;
visitPathsInternal(srcNodeId, paths, currentPath);
return paths;
}
/**
* Internal recursive function of {@link #visitPaths}.
*
* @param currentNodeId current node
* @param paths list of currently stored paths
* @param currentPath current path as node ids
*/
private void visitPathsInternal(
long currentNodeId, ArrayList> paths, Stack currentPath) {
currentPath.push(currentNodeId);
long visitedNeighbors = 0;
nbEdgesAccessed += graph.degree(currentNodeId, useTransposed);
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
visitPathsInternal(neighborNodeId, paths, currentPath);
visitedNeighbors++;
}
if (visitedNeighbors == 0) {
ArrayList path = new ArrayList();
for (long nodeId : currentPath) {
path.add(nodeId);
}
paths.add(path);
}
currentPath.pop();
}
/**
* Performs a graph traversal and returns the first found path from source to destination.
*
* @param srcNodeId source node
* @param dst destination (either a node or a node type)
* @return found path as a list of node ids
*/
public ArrayList walk(long srcNodeId, T dst, String algorithm) {
long dstNodeId = -1;
if (algorithm.equals("dfs")) {
dstNodeId = walkInternalDfs(srcNodeId, dst);
} else if (algorithm.equals("bfs")) {
dstNodeId = walkInternalBfs(srcNodeId, dst);
} else {
throw new IllegalArgumentException("Unknown traversal algorithm: " + algorithm);
}
if (dstNodeId == -1) {
throw new IllegalArgumentException("Unable to find destination point: " + dst);
}
ArrayList nodeIds = backtracking(srcNodeId, dstNodeId);
return nodeIds;
}
/**
* Internal DFS function of {@link #walk}.
*
* @param srcNodeId source node
* @param dst destination (either a node or a node type)
* @return final destination node or -1 if no path found
*/
private long walkInternalDfs(long srcNodeId, T dst) {
Stack stack = new Stack();
this.visited.fill(false);
this.nbEdgesAccessed = 0;
stack.push(srcNodeId);
visited.set(srcNodeId);
while (!stack.isEmpty()) {
long currentNodeId = stack.pop();
if (isDstNode(currentNodeId, dst)) {
return currentNodeId;
}
nbEdgesAccessed += graph.degree(currentNodeId, useTransposed);
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
if (!visited.getBoolean(neighborNodeId)) {
stack.push(neighborNodeId);
visited.set(neighborNodeId);
parentNode.put(neighborNodeId, currentNodeId);
}
}
}
return -1;
}
/**
* Internal BFS function of {@link #walk}.
*
* @param srcNodeId source node
* @param dst destination (either a node or a node type)
* @return final destination node or -1 if no path found
*/
private long walkInternalBfs(long srcNodeId, T dst) {
Queue queue = new LinkedList();
this.visited.fill(false);
this.nbEdgesAccessed = 0;
queue.add(srcNodeId);
visited.set(srcNodeId);
while (!queue.isEmpty()) {
long currentNodeId = queue.poll();
if (isDstNode(currentNodeId, dst)) {
return currentNodeId;
}
nbEdgesAccessed += graph.degree(currentNodeId, useTransposed);
for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) {
if (!visited.getBoolean(neighborNodeId)) {
queue.add(neighborNodeId);
visited.set(neighborNodeId);
parentNode.put(neighborNodeId, currentNodeId);
}
}
}
return -1;
}
/**
* Internal function of {@link #walk} to check if a node corresponds to the destination.
*
* @param nodeId current node
* @param dst destination (either a node or a node type)
* @return true if the node is a destination, or false otherwise
*/
private boolean isDstNode(long nodeId, T dst) {
if (dst instanceof Long) {
long dstNodeId = (Long) dst;
return nodeId == dstNodeId;
} else if (dst instanceof Node.Type) {
Node.Type dstType = (Node.Type) dst;
return graph.getNodeType(nodeId) == dstType;
} else {
return false;
}
}
/**
* Internal backtracking function of {@link #walk}.
*
* @param srcNodeId source node
* @param dstNodeId destination node
* @return the found path, as a list of node ids
*/
private ArrayList backtracking(long srcNodeId, long dstNodeId) {
ArrayList path = new ArrayList();
long currentNodeId = dstNodeId;
while (currentNodeId != srcNodeId) {
path.add(currentNodeId);
currentNodeId = parentNode.get(currentNodeId);
}
path.add(srcNodeId);
Collections.reverse(path);
return path;
}
}