diff --git a/java/README.md b/java/README.md index daab1a9..d023a8f 100644 --- a/java/README.md +++ b/java/README.md @@ -1,50 +1,51 @@ Graph service - Java backend ============================ Server side Java REST API. Build ----- ```bash $ mvn compile assembly:single ``` Start REST API -------------- ```bash $ java -cp target/swh-graph-*.jar \ org.softwareheritage.graph.server.App \ ``` Default port is 5009 (use the `--port` option to change port number). If you need timings metadata send back to the client in addition to the result, use the `--timings` flag. Tests ----- Unit tests rely on test data that are already available in the Git repository -(under `src/swh/graph/tests/dataset/`). You generally only need to run them using Maven: +(under `src/swh/graph/tests/dataset/`). You generally only need to run them +using Maven: ```bash $ mvn test ``` In case you want to regenerate the test data: ```bash # Graph compression $ cd src/swh/graph/tests/dataset $ ./generate_graph.sh $ cd ../../../.. $ mvn compile assembly:single # Dump mapping files $ java -cp target/swh-graph-*.jar \ org.softwareheritage.graph.maps.NodeMapBuilder \ src/swh/graph/tests/dataset/example.nodes.csv.gz \ src/swh/graph/tests/dataset/output/example ``` diff --git a/java/src/main/java/org/softwareheritage/graph/Graph.java b/java/src/main/java/org/softwareheritage/graph/Graph.java index 8103229..f8799e9 100644 --- a/java/src/main/java/org/softwareheritage/graph/Graph.java +++ b/java/src/main/java/org/softwareheritage/graph/Graph.java @@ -1,256 +1,256 @@ package org.softwareheritage.graph; import it.unimi.dsi.big.webgraph.BVGraph; import it.unimi.dsi.big.webgraph.ImmutableGraph; import it.unimi.dsi.big.webgraph.LazyLongIterator; import it.unimi.dsi.big.webgraph.Transform; import org.softwareheritage.graph.maps.NodeIdMap; import org.softwareheritage.graph.maps.NodeTypesMap; import java.io.IOException; /** * Main class storing the compressed graph and node id mappings. *

* The compressed graph is stored using the WebGraph * ecosystem. Additional mappings are necessary because Software Heritage uses string based persistent - * identifiers (PID) while WebGraph uses integers internally. These two mappings (long id ↔ - * PID) are used for the input (users refer to the graph using PID) and the output (convert back to - * PID for users results). However, since graph traversal can be restricted depending on the node + * identifiers (SWHID) while WebGraph uses integers internally. These two mappings (long id ↔ + * SWHID) are used for the input (users refer to the graph using SWHID) and the output (convert back to + * SWHID for users results). However, since graph traversal can be restricted depending on the node * type (see {@link AllowedEdges}), a long id → node type map is stored as well to avoid a full - * PID lookup. + * SWHID lookup. * * @author The Software Heritage developers * @see org.softwareheritage.graph.AllowedEdges * @see org.softwareheritage.graph.maps.NodeIdMap * @see org.softwareheritage.graph.maps.NodeTypesMap */ public class Graph extends ImmutableGraph { - /** File extension for the SWH PID to long node id map */ - public static final String PID_TO_NODE = ".pid2node.bin"; - /** File extension for the long node id to SWH PID map */ - public static final String NODE_TO_PID = ".node2pid.bin"; + /** File extension for the SWHID to long node id map */ + public static final String SWHID_TO_NODE = ".swhid2node.bin"; + /** File extension for the long node id to SWHID map */ + public static final String NODE_TO_SWHID = ".node2swhid.bin"; /** File extension for the long node id to node type map */ public static final String NODE_TO_TYPE = ".node2type.map"; /** Compressed graph stored as a {@link it.unimi.dsi.big.webgraph.BVGraph} */ ImmutableGraph graph; /** Transposed compressed graph (used for backward traversals) */ ImmutableGraph graphTransposed; /** Path and basename of the compressed graph */ String path; - /** Mapping long id ↔ SWH PIDs */ + /** Mapping long id ↔ SWHIDs */ NodeIdMap nodeIdMap; /** Mapping long id → node types */ NodeTypesMap nodeTypesMap; /** * Constructor. * * @param path path and basename of the compressed graph to load */ public Graph(String path) throws IOException { this.path = path; this.graph = BVGraph.loadMapped(path); this.graphTransposed = BVGraph.loadMapped(path + "-transposed"); this.nodeTypesMap = new NodeTypesMap(path); this.nodeIdMap = new NodeIdMap(path, numNodes()); } protected Graph(ImmutableGraph graph, ImmutableGraph graphTransposed, String path, NodeIdMap nodeIdMap, NodeTypesMap nodeTypesMap) { this.graph = graph; this.graphTransposed = graphTransposed; this.path = path; this.nodeIdMap = nodeIdMap; this.nodeTypesMap = nodeTypesMap; } /** * Return a flyweight copy of the graph. */ @Override public Graph copy() { return new Graph(this.graph.copy(), this.graphTransposed.copy(), this.path, this.nodeIdMap, this.nodeTypesMap); } @Override public boolean randomAccess() { return graph.randomAccess() && graphTransposed.randomAccess(); } /** * Return a transposed version of the graph. */ public Graph transpose() { return new Graph(this.graphTransposed, this.graph, this.path, this.nodeIdMap, this.nodeTypesMap); } /** * Return a symmetric version of the graph. */ public Graph symmetrize() { ImmutableGraph symmetric = Transform.union(graph, graphTransposed); return new Graph(symmetric, symmetric, this.path, this.nodeIdMap, this.nodeTypesMap); } /** * Cleans up graph resources after use. */ public void cleanUp() throws IOException { nodeIdMap.close(); } /** * Returns number of nodes in the graph. * * @return number of nodes in the graph */ @Override public long numNodes() { return graph.numNodes(); } /** * Returns number of edges in the graph. * * @return number of edges in the graph */ @Override public long numArcs() { return graph.numArcs(); } /** * Returns lazy iterator of successors of a node. * * @param nodeId node specified as a long id * @return lazy iterator of successors of the node, specified as a WebGraph LazyLongIterator */ @Override public LazyLongIterator successors(long nodeId) { return graph.successors(nodeId); } /** * Returns lazy iterator of successors of a node while following a specific set of edge types. * * @param nodeId node specified as a long id * @param allowedEdges the specification of which edges can be traversed * @return lazy iterator of successors of the node, specified as a WebGraph LazyLongIterator */ public LazyLongIterator successors(long nodeId, AllowedEdges allowedEdges) { if (allowedEdges.restrictedTo == null) { // All edges are allowed, bypass edge check return this.successors(nodeId); } else { LazyLongIterator allSuccessors = this.successors(nodeId); return new LazyLongIterator() { @Override public long nextLong() { long neighbor; while ((neighbor = allSuccessors.nextLong()) != -1) { if (allowedEdges.isAllowed(nodeId, neighbor)) { return neighbor; } } return -1; } @Override public long skip(final long n) { long i; for (i = 0; i < n && nextLong() != -1; i++) ; return i; } }; } } /** * Returns the outdegree of a node. * * @param nodeId node specified as a long id * @return outdegree of a node */ @Override public long outdegree(long nodeId) { return graph.outdegree(nodeId); } /** * Returns lazy iterator of predecessors of a node. * * @param nodeId node specified as a long id * @return lazy iterator of predecessors of the node, specified as a WebGraph LazyLongIterator */ public LazyLongIterator predecessors(long nodeId) { return this.transpose().successors(nodeId); } /** * Returns the indegree of a node. * * @param nodeId node specified as a long id * @return indegree of a node */ public long indegree(long nodeId) { return this.transpose().outdegree(nodeId); } /** * Returns the underlying BVGraph. * * @return WebGraph BVGraph */ public ImmutableGraph getGraph() { return this.graph; } /** * Returns the graph full path. * * @return graph full path */ public String getPath() { return path; } /** - * Converts {@link SwhPID} node to long. + * Converts {@link SWHID} node to long. * - * @param swhPID node specified as a {@link SwhPID} + * @param swhid node specified as a {@link SWHID} * @return internal long node id - * @see org.softwareheritage.graph.SwhPID + * @see SWHID */ - public long getNodeId(SwhPID swhPID) { - return nodeIdMap.getNodeId(swhPID); + public long getNodeId(SWHID swhid) { + return nodeIdMap.getNodeId(swhid); } /** - * Converts long id node to {@link SwhPID}. + * Converts long id node to {@link SWHID}. * * @param nodeId node specified as a long id - * @return external SWH PID - * @see org.softwareheritage.graph.SwhPID + * @return external SWHID + * @see SWHID */ - public SwhPID getSwhPID(long nodeId) { - return nodeIdMap.getSwhPID(nodeId); + public SWHID getSWHID(long nodeId) { + return nodeIdMap.getSWHID(nodeId); } /** * Returns node type. * * @param nodeId node specified as a long id * @return corresponding node type * @see org.softwareheritage.graph.Node.Type */ public Node.Type getNodeType(long nodeId) { return nodeTypesMap.getType(nodeId); } } diff --git a/java/src/main/java/org/softwareheritage/graph/SwhPID.java b/java/src/main/java/org/softwareheritage/graph/SWHID.java similarity index 58% rename from java/src/main/java/org/softwareheritage/graph/SwhPID.java rename to java/src/main/java/org/softwareheritage/graph/SWHID.java index c44abdc..6b810cc 100644 --- a/java/src/main/java/org/softwareheritage/graph/SwhPID.java +++ b/java/src/main/java/org/softwareheritage/graph/SWHID.java @@ -1,124 +1,124 @@ package org.softwareheritage.graph; import com.fasterxml.jackson.annotation.JsonValue; import org.apache.commons.codec.DecoderException; import org.apache.commons.codec.binary.Hex; /** - * A Software Heritage PID, see persistent * identifier documentation. * * @author The Software Heritage developers */ -public class SwhPID { - /** Fixed hash length of the PID */ +public class SWHID { + /** Fixed hash length of the SWHID */ public static final int HASH_LENGTH = 40; - /** Full PID as a string */ - String swhPID; - /** PID node type */ + /** Full SWHID as a string */ + String swhid; + /** SWHID node type */ Node.Type type; /** * Constructor. * - * @param swhPID full PID as a string + * @param swhid full SWHID as a string */ - public SwhPID(String swhPID) { - this.swhPID = swhPID; + public SWHID(String swhid) { + this.swhid = swhid; - // PID format: 'swh:1:type:hash' - String[] parts = swhPID.split(":"); + // SWHID format: 'swh:1:type:hash' + String[] parts = swhid.split(":"); if (parts.length != 4 || !parts[0].equals("swh") || !parts[1].equals("1")) { - throw new IllegalArgumentException("malformed SWH PID: " + swhPID); + throw new IllegalArgumentException("malformed SWHID: " + swhid); } this.type = Node.Type.fromStr(parts[2]); if (!parts[3].matches("[0-9a-f]{" + HASH_LENGTH + "}")) { - throw new IllegalArgumentException("malformed SWH PID: " + swhPID); + throw new IllegalArgumentException("malformed SWHID: " + swhid); } } /** - * Creates a SwhPID from a compact binary representation. + * Creates a SWHID from a compact binary representation. *

* The binary format is specified in the Python module - * swh.graph.pid:str_to_bytes . + * swh.graph.swhid:str_to_bytes . */ - public static SwhPID fromBytes(byte[] input) { + public static SWHID fromBytes(byte[] input) { byte[] digest = new byte[20]; System.arraycopy(input, 2, digest, 0, digest.length); - String pidStr = String.format( + String swhidStr = String.format( "swh:%d:%s:%s", input[0], Node.Type.fromInt(input[1]).toString().toLowerCase(), Hex.encodeHexString(digest) ); - return new SwhPID(pidStr); + return new SWHID(swhidStr); } @Override public boolean equals(Object otherObj) { if (otherObj == this) return true; - if (!(otherObj instanceof SwhPID)) + if (!(otherObj instanceof SWHID)) return false; - SwhPID other = (SwhPID) otherObj; - return swhPID.equals(other.getSwhPID()); + SWHID other = (SWHID) otherObj; + return swhid.equals(other.getSWHID()); } @Override public int hashCode() { - return swhPID.hashCode(); + return swhid.hashCode(); } @Override public String toString() { - return swhPID; + return swhid; } /** - * Converts PID to a compact binary representation. + * Converts SWHID to a compact binary representation. *

* The binary format is specified in the Python module - * swh.graph.pid:str_to_bytes . + * swh.graph.swhid:str_to_bytes . */ public byte[] toBytes() { byte[] bytes = new byte[22]; byte[] digest; bytes[0] = (byte) 1; // namespace version - bytes[1] = (byte) Node.Type.toInt(this.type); // PID type + bytes[1] = (byte) Node.Type.toInt(this.type); // SWHID type try { - digest = Hex.decodeHex(this.swhPID.substring(10)); // SHA1 hash + digest = Hex.decodeHex(this.swhid.substring(10)); // SHA1 hash System.arraycopy(digest, 0, bytes, 2, digest.length); } catch (DecoderException e) { - throw new IllegalArgumentException("invalid hex sequence in PID: " + this.swhPID); + throw new IllegalArgumentException("invalid hex sequence in SWHID: " + this.swhid); } return bytes; } /** - * Returns full PID as a string. + * Returns full SWHID as a string. * - * @return full PID string + * @return full SWHID string */ @JsonValue - public String getSwhPID() { - return swhPID; + public String getSWHID() { + return swhid; } /** - * Returns PID node type. + * Returns SWHID node type. * - * @return PID corresponding {@link Node.Type} + * @return SWHID corresponding {@link Node.Type} * @see org.softwareheritage.graph.Node.Type */ public Node.Type getType() { return type; } } diff --git a/java/src/main/java/org/softwareheritage/graph/SwhPath.java b/java/src/main/java/org/softwareheritage/graph/SwhPath.java index e0d1501..8693e02 100644 --- a/java/src/main/java/org/softwareheritage/graph/SwhPath.java +++ b/java/src/main/java/org/softwareheritage/graph/SwhPath.java @@ -1,122 +1,122 @@ package org.softwareheritage.graph; import com.fasterxml.jackson.annotation.JsonValue; import java.util.ArrayList; /** - * Wrapper class to store a list of {@link SwhPID}. + * Wrapper class to store a list of {@link SWHID}. * * @author The Software Heritage developers - * @see org.softwareheritage.graph.SwhPID + * @see SWHID */ public class SwhPath { - /** Internal list of {@link SwhPID} */ - ArrayList path; + /** Internal list of {@link SWHID} */ + ArrayList path; /** * Constructor. */ public SwhPath() { this.path = new ArrayList<>(); } /** * Constructor. * - * @param swhPIDs variable number of string PIDs to initialize this path with + * @param swhids variable number of string SWHIDs to initialize this path with */ - public SwhPath(String... swhPIDs) { + public SwhPath(String... swhids) { this(); - for (String swhPID : swhPIDs) { - add(new SwhPID(swhPID)); + for (String swhid : swhids) { + add(new SWHID(swhid)); } } /** * Constructor. * - * @param swhPIDs variable number of {@link SwhPID} to initialize this path with - * @see org.softwareheritage.graph.SwhPID + * @param swhids variable number of {@link SWHID} to initialize this path with + * @see SWHID */ - public SwhPath(SwhPID... swhPIDs) { + public SwhPath(SWHID... swhids) { this(); - for (SwhPID swhPID : swhPIDs) { - add(swhPID); + for (SWHID swhid : swhids) { + add(swhid); } } /** - * Returns this path as a list of {@link SwhPID}. + * Returns this path as a list of {@link SWHID}. * - * @return list of {@link SwhPID} constituting the path - * @see org.softwareheritage.graph.SwhPID + * @return list of {@link SWHID} constituting the path + * @see SWHID */ @JsonValue - public ArrayList getPath() { + public ArrayList getPath() { return path; } /** - * Adds a {@link SwhPID} to this path. + * Adds a {@link SWHID} to this path. * - * @param swhPID {@link SwhPID} to add to this path - * @see org.softwareheritage.graph.SwhPID + * @param swhid {@link SWHID} to add to this path + * @see SWHID */ - public void add(SwhPID swhPID) { - path.add(swhPID); + public void add(SWHID swhid) { + path.add(swhid); } /** - * Returns the {@link SwhPID} at the specified position in this path. + * Returns the {@link SWHID} at the specified position in this path. * - * @param index position of the {@link SwhPID} to return - * @return {@link SwhPID} at the specified position - * @see org.softwareheritage.graph.SwhPID + * @param index position of the {@link SWHID} to return + * @return {@link SWHID} at the specified position + * @see SWHID */ - public SwhPID get(int index) { + public SWHID get(int index) { return path.get(index); } /** * Returns the number of elements in this path. * * @return number of elements in this path */ public int size() { return path.size(); } @Override public boolean equals(Object otherObj) { if (otherObj == this) return true; if (!(otherObj instanceof SwhPath)) return false; SwhPath other = (SwhPath) otherObj; if (size() != other.size()) { return false; } for (int i = 0; i < size(); i++) { - SwhPID thisSwhPID = get(i); - SwhPID otherSwhPID = other.get(i); - if (!thisSwhPID.equals(otherSwhPID)) { + SWHID thisSWHID = get(i); + SWHID otherSWHID = other.get(i); + if (!thisSWHID.equals(otherSWHID)) { return false; } } return true; } @Override public String toString() { StringBuilder str = new StringBuilder(); - for (SwhPID swhPID : path) { - str.append(swhPID).append("/"); + for (SWHID swhid : path) { + str.append(swhid).append("/"); } return str.toString(); } } diff --git a/java/src/main/java/org/softwareheritage/graph/Traversal.java b/java/src/main/java/org/softwareheritage/graph/Traversal.java index 5c4902f..5a0b007 100644 --- a/java/src/main/java/org/softwareheritage/graph/Traversal.java +++ b/java/src/main/java/org/softwareheritage/graph/Traversal.java @@ -1,526 +1,525 @@ package org.softwareheritage.graph; import it.unimi.dsi.big.webgraph.LazyLongIterator; import org.softwareheritage.graph.server.Endpoint; import java.util.*; import java.util.function.Consumer; import java.util.function.LongConsumer; /** * 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. + * long ids, which are converted in the {@link Endpoint} higher-level class to {@link SWHID}. * * @author The Software Heritage developers * @see Endpoint */ public class Traversal { /** Graph used in the traversal */ Graph graph; /** Graph edge restriction */ AllowedEdges edges; /** Hash set storing if we have visited a node */ HashSet visited; /** Hash map storing parent node id for each nodes during a traversal */ Map parentNode; /** Number of edges accessed during traversal */ long nbEdgesAccessed; /** random number generator, for random walks */ Random rng; /** * 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); } if (direction.equals("backward")) { this.graph = graph.transpose(); } else { this.graph = graph; } this.edges = new AllowedEdges(graph, edgesFmt); this.visited = new HashSet<>(); this.parentNode = new HashMap<>(); this.nbEdgesAccessed = 0; this.rng = new Random(); } /** * Returns number of accessed edges during traversal. * * @return number of edges accessed in last traversal */ public long getNbEdgesAccessed() { return nbEdgesAccessed; } /** * Returns number of accessed nodes during traversal. * * @return number of nodes accessed in last traversal */ public long getNbNodesAccessed() { return this.visited.size(); } /** * Push version of {@link #leaves} will fire passed callback for each leaf. */ public void leavesVisitor(long srcNodeId, NodeIdConsumer cb) { Stack stack = new Stack<>(); this.nbEdgesAccessed = 0; stack.push(srcNodeId); visited.add(srcNodeId); while (!stack.isEmpty()) { long currentNodeId = stack.pop(); long neighborsCnt = 0; nbEdgesAccessed += graph.outdegree(currentNodeId); LazyLongIterator it = graph.successors(currentNodeId, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1; ) { neighborsCnt++; if (!visited.contains(neighborNodeId)) { stack.push(neighborNodeId); visited.add(neighborNodeId); } } if (neighborsCnt == 0) { cb.accept(currentNodeId); } } } /** * 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<>(); leavesVisitor(srcNodeId, nodeIds::add); return nodeIds; } /** * Push version of {@link #neighbors}: will fire passed callback on each * neighbor. */ public void neighborsVisitor(long srcNodeId, NodeIdConsumer cb) { this.nbEdgesAccessed = graph.outdegree(srcNodeId); 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). * * @param srcNodeId source node * @return list of node ids corresponding to the neighbors */ public ArrayList neighbors(long srcNodeId) { ArrayList nodeIds = new ArrayList<>(); neighborsVisitor(srcNodeId, nodeIds::add); return nodeIds; } /** * Push version of {@link #visitNodes}: will fire passed callback on each * visited node. */ public void visitNodesVisitor(long srcNodeId, NodeIdConsumer nodeCb, EdgeIdConsumer edgeCb) { Stack stack = new Stack<>(); this.nbEdgesAccessed = 0; stack.push(srcNodeId); visited.add(srcNodeId); while (!stack.isEmpty()) { long currentNodeId = stack.pop(); if (nodeCb != null) { nodeCb.accept(currentNodeId); } nbEdgesAccessed += graph.outdegree(currentNodeId); LazyLongIterator it = graph.successors(currentNodeId, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1; ) { if (edgeCb != null) { edgeCb.accept(currentNodeId, neighborNodeId); } if (!visited.contains(neighborNodeId)) { stack.push(neighborNodeId); visited.add(neighborNodeId); } } } } /** One-argument version to handle callbacks properly */ public void visitNodesVisitor(long srcNodeId, NodeIdConsumer cb) { visitNodesVisitor(srcNodeId, cb, null); } /** * 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<>(); visitNodesVisitor(srcNodeId, nodeIds::add); return nodeIds; } /** * Push version of {@link #visitPaths}: will fire passed callback on each * discovered (complete) path. */ public void visitPathsVisitor(long srcNodeId, PathConsumer cb) { Stack currentPath = new Stack<>(); this.nbEdgesAccessed = 0; visitPathsInternalVisitor(srcNodeId, currentPath, cb); } /** * 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<>(); visitPathsVisitor(srcNodeId, paths::add); return paths; } private void visitPathsInternalVisitor(long currentNodeId, Stack currentPath, PathConsumer cb) { currentPath.push(currentNodeId); long visitedNeighbors = 0; nbEdgesAccessed += graph.outdegree(currentNodeId); LazyLongIterator it = graph.successors(currentNodeId, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1; ) { visitPathsInternalVisitor(neighborNodeId, currentPath, cb); visitedNeighbors++; } if (visitedNeighbors == 0) { ArrayList path = new ArrayList<>(currentPath); cb.accept(path); } currentPath.pop(); } /** * Performs a graph traversal with backtracking, 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 visitOrder) { long dstNodeId; if (visitOrder.equals("dfs")) { dstNodeId = walkInternalDFS(srcNodeId, dst); } else if (visitOrder.equals("bfs")) { dstNodeId = walkInternalBFS(srcNodeId, dst); } else { throw new IllegalArgumentException("Unknown visit order: " + visitOrder); } if (dstNodeId == -1) { throw new IllegalArgumentException("Cannot find destination: " + dst); } return backtracking(srcNodeId, dstNodeId); } /** * Performs a random walk (picking a random successor at each step) 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 or an empty path to indicate * that no suitable path have been found */ public ArrayList randomWalk(long srcNodeId, T dst) { return randomWalk(srcNodeId, dst, 0); } /** * Performs a stubborn random walk (picking a random successor at each * step) from source to destination. The walk is "stubborn" in the sense * that it will not give up the first time if a satisfying target node is * found, but it will retry up to a limited amount of times. * * @param srcNodeId source node * @param dst destination (either a node or a node type) * @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 * that no suitable path have been found */ public ArrayList randomWalk(long srcNodeId, T dst, int retries) { long curNodeId = srcNodeId; ArrayList path = new ArrayList<>(); this.nbEdgesAccessed = 0; boolean found; if (retries < 0) { throw new IllegalArgumentException("Negative number of retries given: " + retries); } while (true) { path.add(curNodeId); LazyLongIterator successors = graph.successors(curNodeId, edges); curNodeId = randomPick(successors); if (curNodeId < 0) { found = false; break; } if (isDstNode(curNodeId, dst)) { path.add(curNodeId); found = true; break; } } if (found) { return path; } else if (retries > 0) { // try again return randomWalk(srcNodeId, dst, retries - 1); } else { // not found and no retries left path.clear(); return path; } } /** * Randomly choose an element from an iterator over Longs using reservoir * sampling * * @param elements iterator over selection domain * @return randomly chosen element or -1 if no suitable element was found */ private long randomPick(LazyLongIterator elements) { long curPick = -1; long seenCandidates = 0; for (long element; (element = elements.nextLong()) != -1; ) { seenCandidates++; if (Math.round(rng.nextFloat() * (seenCandidates - 1)) == 0) { curPick = element; } } return curPick; } /** * 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.nbEdgesAccessed = 0; stack.push(srcNodeId); visited.add(srcNodeId); while (!stack.isEmpty()) { long currentNodeId = stack.pop(); if (isDstNode(currentNodeId, dst)) { return currentNodeId; } nbEdgesAccessed += graph.outdegree(currentNodeId); LazyLongIterator it = graph.successors(currentNodeId, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1; ) { if (!visited.contains(neighborNodeId)) { stack.push(neighborNodeId); visited.add(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.nbEdgesAccessed = 0; queue.add(srcNodeId); visited.add(srcNodeId); while (!queue.isEmpty()) { long currentNodeId = queue.poll(); if (isDstNode(currentNodeId, dst)) { return currentNodeId; } nbEdgesAccessed += graph.outdegree(currentNodeId); LazyLongIterator it = graph.successors(currentNodeId, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1; ) { if (!visited.contains(neighborNodeId)) { queue.add(neighborNodeId); visited.add(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; } /** * 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) { Queue lhsStack = new ArrayDeque<>(); Queue rhsStack = new ArrayDeque<>(); HashSet lhsVisited = new HashSet<>(); HashSet rhsVisited = new HashSet<>(); lhsStack.add(lhsNode); rhsStack.add(rhsNode); lhsVisited.add(lhsNode); rhsVisited.add(rhsNode); this.nbEdgesAccessed = 0; Long curNode; while (!lhsStack.isEmpty() || !rhsStack.isEmpty()) { if (!lhsStack.isEmpty()) { curNode = lhsStack.poll(); nbEdgesAccessed += graph.outdegree(curNode); LazyLongIterator it = graph.successors(curNode, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1; ) { if (!lhsVisited.contains(neighborNodeId)) { if (rhsVisited.contains(neighborNodeId)) return neighborNodeId; lhsStack.add(neighborNodeId); lhsVisited.add(neighborNodeId); } } } if (!rhsStack.isEmpty()) { curNode = rhsStack.poll(); nbEdgesAccessed += graph.outdegree(curNode); LazyLongIterator it = graph.successors(curNode, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1; ) { if (!rhsVisited.contains(neighborNodeId)) { if (lhsVisited.contains(neighborNodeId)) return neighborNodeId; rhsStack.add(neighborNodeId); rhsVisited.add(neighborNodeId); } } } } return null; } public interface NodeIdConsumer extends LongConsumer { /** * Callback for incrementally receiving node identifiers during a graph * visit. */ void accept(long nodeId); } public interface EdgeIdConsumer { /** * Callback for incrementally receiving edge identifiers during a graph * visit. */ void accept(long srcId, long dstId); } public interface PathConsumer extends Consumer> { /** * Callback for incrementally receiving node paths (made of node * identifiers) during a graph visit. */ void accept(ArrayList path); } } diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java index 884dea2..7c3cef7 100644 --- a/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java +++ b/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java @@ -1,162 +1,162 @@ package org.softwareheritage.graph.benchmark; import com.martiansoftware.jsap.*; import org.softwareheritage.graph.Graph; -import org.softwareheritage.graph.SwhPID; +import org.softwareheritage.graph.SWHID; import org.softwareheritage.graph.benchmark.utils.Random; import org.softwareheritage.graph.benchmark.utils.Statistics; import org.softwareheritage.graph.server.Endpoint; import java.io.BufferedWriter; import java.io.FileWriter; import java.io.IOException; import java.io.Writer; import java.util.ArrayList; import java.util.StringJoiner; import java.util.function.Function; /** * Benchmark common utility functions. * * @author The Software Heritage developers */ public class Benchmark { /** CSV separator for log file */ final String CSV_SEPARATOR = ";"; /** Command line arguments */ public Args args; /** * Constructor. */ public Benchmark() { this.args = new Args(); } /** * Parses benchmark command line arguments. * * @param args command line arguments */ public void parseCommandLineArgs(String[] args) throws JSAPException { SimpleJSAP jsap = new SimpleJSAP(Benchmark.class.getName(), "Benchmark tool for Software Heritage use-cases scenarios.", new Parameter[]{ new UnflaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, JSAP.NOT_GREEDY, "The basename of the compressed graph."), new FlaggedOption("nbNodes", JSAP.INTEGER_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'n', "nb-nodes", "Number of random nodes used to do the benchmark."), new FlaggedOption("logFile", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'l', "log-file", "File name to output CSV format benchmark log."), new FlaggedOption("seed", JSAP.LONG_PARSER, JSAP.NO_DEFAULT, JSAP.NOT_REQUIRED, 's', "seed", "Random generator seed."), }); JSAPResult config = jsap.parse(args); if (jsap.messagePrinted()) { System.exit(1); } this.args.graphPath = config.getString("graphPath"); this.args.nbNodes = config.getInt("nbNodes"); this.args.logFile = config.getString("logFile"); this.args.random = config.contains("seed") ? new Random(config.getLong("seed")) : new Random(); } /** * Creates CSV file for log output. */ public void createCSVLogFile() throws IOException { try (Writer csvLog = new BufferedWriter(new FileWriter(args.logFile))) { StringJoiner csvHeader = new StringJoiner(CSV_SEPARATOR); csvHeader.add("use case name") - .add("SWH PID") + .add("SWHID") .add("number of edges accessed") .add("traversal timing") - .add("pid2node timing") - .add("node2pid timing"); + .add("swhid2node timing") + .add("node2swhid timing"); csvLog.write(csvHeader.toString() + "\n"); } } /** * Times a specific endpoint and outputs individual datapoints along with aggregated statistics. * * @param useCaseName benchmark use-case name * @param graph compressed graph used in the benchmark * @param nodeIds node ids to use as starting point for the endpoint traversal * @param operation endpoint function to benchmark * @param dstFmt destination formatted string as described in the API * @param algorithm traversal algorithm used in endpoint call (either "dfs" or "bfs") */ public void timeEndpoint(String useCaseName, Graph graph, long[] nodeIds, Function operation, String dstFmt, String algorithm) throws IOException { ArrayList timings = new ArrayList<>(); ArrayList timingsNormalized = new ArrayList<>(); ArrayList nbEdgesAccessed = new ArrayList<>(); final boolean append = true; try (Writer csvLog = new BufferedWriter(new FileWriter(args.logFile, append))) { for (long nodeId : nodeIds) { - SwhPID swhPID = graph.getSwhPID(nodeId); + SWHID swhid = graph.getSWHID(nodeId); Endpoint.Output output = (dstFmt == null) - ? operation.apply(new Endpoint.Input(swhPID)) - : operation.apply(new Endpoint.Input(swhPID, dstFmt, algorithm)); + ? operation.apply(new Endpoint.Input(swhid)) + : operation.apply(new Endpoint.Input(swhid, dstFmt, algorithm)); StringJoiner csvLine = new StringJoiner(CSV_SEPARATOR); csvLine.add(useCaseName) - .add(swhPID.toString()) + .add(swhid.toString()) .add(Long.toString(output.meta.nbEdgesAccessed)) .add(Double.toString(output.meta.timings.traversal)) - .add(Double.toString(output.meta.timings.pid2node)) - .add(Double.toString(output.meta.timings.node2pid)); + .add(Double.toString(output.meta.timings.swhid2node)) + .add(Double.toString(output.meta.timings.node2swhid)); csvLog.write(csvLine.toString() + "\n"); timings.add(output.meta.timings.traversal); nbEdgesAccessed.add((double) output.meta.nbEdgesAccessed); if (output.meta.nbEdgesAccessed != 0) { timingsNormalized.add(output.meta.timings.traversal / output.meta.nbEdgesAccessed); } } } System.out.println("\n" + useCaseName + " use-case:"); System.out.println("timings:"); Statistics stats = new Statistics(timings); stats.printAll(); System.out.println("timings normalized:"); Statistics statsNormalized = new Statistics(timingsNormalized); statsNormalized.printAll(); System.out.println("nb edges accessed:"); Statistics statsNbEdgesAccessed = new Statistics(nbEdgesAccessed); statsNbEdgesAccessed.printAll(); } /** * Same as {@link #timeEndpoint} but without destination or algorithm specified to endpoint call. */ public void timeEndpoint(String useCaseName, Graph graph, long[] nodeIds, Function operation) throws IOException { timeEndpoint(useCaseName, graph, nodeIds, operation, null, null); } /** * Input arguments. */ public class Args { /** Basename of the compressed graph */ public String graphPath; /** Number of random nodes to use for the benchmark */ public int nbNodes; /** File name for CSV format benchmark log */ public String logFile; /** Random generator */ public Random random; } } diff --git a/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java b/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java index 3fa9f1e..c7217c5 100644 --- a/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java +++ b/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java @@ -1,114 +1,114 @@ package org.softwareheritage.graph.maps; import org.softwareheritage.graph.Graph; -import org.softwareheritage.graph.SwhPID; +import org.softwareheritage.graph.SWHID; import java.io.IOException; /** - * Mapping between internal long node id and external SWH PID. + * Mapping between internal long node id and external SWHID. *

* Mappings in both directions are pre-computed and dumped on disk in the * {@link NodeMapBuilder} class, then they are loaded here using mmap(). * * @author The Software Heritage developers * @see NodeMapBuilder */ public class NodeIdMap { - /** Fixed length of full SWH PID */ - public static final int SWH_ID_LENGTH = 50; + /** Fixed length of full SWHID */ + public static final int SWHID_LENGTH = 50; /** Fixed length of long node id */ public static final int NODE_ID_LENGTH = 20; - /** Fixed length of binary SWH PID buffer */ - public static final int SWH_ID_BIN_SIZE = 22; + /** Fixed length of binary SWHID buffer */ + public static final int SWHID_BIN_SIZE = 22; /** Fixed length of binary node id buffer */ public static final int NODE_ID_BIN_SIZE = 8; /** Graph path and basename */ String graphPath; /** Number of ids to map */ long nbIds; - /** mmap()-ed PID_TO_NODE file */ + /** mmap()-ed SWHID_TO_NODE file */ MapFile swhToNodeMap; - /** mmap()-ed NODE_TO_PID file */ + /** mmap()-ed NODE_TO_SWHID file */ MapFile nodeToSwhMap; /** * Constructor. * * @param graphPath full graph path * @param nbNodes number of nodes in the graph */ public NodeIdMap(String graphPath, long nbNodes) throws IOException { this.graphPath = graphPath; this.nbIds = nbNodes; - this.swhToNodeMap = new MapFile(graphPath + Graph.PID_TO_NODE, SWH_ID_BIN_SIZE + NODE_ID_BIN_SIZE); - this.nodeToSwhMap = new MapFile(graphPath + Graph.NODE_TO_PID, SWH_ID_BIN_SIZE); + this.swhToNodeMap = new MapFile(graphPath + Graph.SWHID_TO_NODE, SWHID_BIN_SIZE + NODE_ID_BIN_SIZE); + this.nodeToSwhMap = new MapFile(graphPath + Graph.NODE_TO_SWHID, SWHID_BIN_SIZE); } /** - * Converts SWH PID to corresponding long node id. + * Converts SWHID to corresponding long node id. * - * @param swhPID node represented as a {@link SwhPID} + * @param swhid node represented as a {@link SWHID} * @return corresponding node as a long id - * @see org.softwareheritage.graph.SwhPID + * @see SWHID */ - public long getNodeId(SwhPID swhPID) { - // The file is sorted by swhPID, hence we can binary search on swhPID to get corresponding + public long getNodeId(SWHID swhid) { + // The file is sorted by swhid, hence we can binary search on swhid to get corresponding // nodeId long start = 0; long end = nbIds - 1; while (start <= end) { long lineNumber = (start + end) / 2L; byte[] buffer = swhToNodeMap.readAtLine(lineNumber); - byte[] pidBuffer = new byte[SWH_ID_BIN_SIZE]; + byte[] swhidBuffer = new byte[SWHID_BIN_SIZE]; byte[] nodeBuffer = new byte[NODE_ID_BIN_SIZE]; - System.arraycopy(buffer, 0, pidBuffer, 0, SWH_ID_BIN_SIZE); - System.arraycopy(buffer, SWH_ID_BIN_SIZE, nodeBuffer, 0, NODE_ID_BIN_SIZE); + System.arraycopy(buffer, 0, swhidBuffer, 0, SWHID_BIN_SIZE); + System.arraycopy(buffer, SWHID_BIN_SIZE, nodeBuffer, 0, NODE_ID_BIN_SIZE); - String currentSwhPID = SwhPID.fromBytes(pidBuffer).getSwhPID(); + String currentSWHID = SWHID.fromBytes(swhidBuffer).getSWHID(); long currentNodeId = java.nio.ByteBuffer.wrap(nodeBuffer).getLong(); - int cmp = currentSwhPID.compareTo(swhPID.toString()); + int cmp = currentSWHID.compareTo(swhid.toString()); if (cmp == 0) { return currentNodeId; } else if (cmp < 0) { start = lineNumber + 1; } else { end = lineNumber - 1; } } - throw new IllegalArgumentException("Unknown SWH PID: " + swhPID); + throw new IllegalArgumentException("Unknown SWHID: " + swhid); } /** - * Converts a node long id to corresponding SWH PID. + * Converts a node long id to corresponding SWHID. * * @param nodeId node as a long id - * @return corresponding node as a {@link SwhPID} - * @see org.softwareheritage.graph.SwhPID + * @return corresponding node as a {@link SWHID} + * @see SWHID */ - public SwhPID getSwhPID(long nodeId) { - // Each line in NODE_TO_PID is formatted as: swhPID - // The file is ordered by nodeId, meaning node0's swhPID is at line 0, hence we can read the - // nodeId-th line to get corresponding swhPID + public SWHID getSWHID(long nodeId) { + // Each line in NODE_TO_SWHID is formatted as: swhid + // The file is ordered by nodeId, meaning node0's swhid is at line 0, hence we can read the + // nodeId-th line to get corresponding swhid if (nodeId < 0 || nodeId >= nbIds) { throw new IllegalArgumentException("Node id " + nodeId + " should be between 0 and " + nbIds); } - return SwhPID.fromBytes(nodeToSwhMap.readAtLine(nodeId)); + return SWHID.fromBytes(nodeToSwhMap.readAtLine(nodeId)); } /** * Closes the mapping files. */ public void close() throws IOException { swhToNodeMap.close(); nodeToSwhMap.close(); } } diff --git a/java/src/main/java/org/softwareheritage/graph/maps/NodeMapBuilder.java b/java/src/main/java/org/softwareheritage/graph/maps/NodeMapBuilder.java index ea2e9bc..6d8e939 100644 --- a/java/src/main/java/org/softwareheritage/graph/maps/NodeMapBuilder.java +++ b/java/src/main/java/org/softwareheritage/graph/maps/NodeMapBuilder.java @@ -1,212 +1,212 @@ package org.softwareheritage.graph.maps; import it.unimi.dsi.bits.LongArrayBitVector; import it.unimi.dsi.fastutil.BigArrays; import it.unimi.dsi.fastutil.Size64; import it.unimi.dsi.fastutil.io.BinIO; import it.unimi.dsi.fastutil.longs.LongBigArrays; import it.unimi.dsi.fastutil.longs.LongBigList; import it.unimi.dsi.fastutil.objects.Object2LongFunction; import it.unimi.dsi.io.FastBufferedReader; import it.unimi.dsi.io.LineIterator; import it.unimi.dsi.logging.ProgressLogger; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.Node; -import org.softwareheritage.graph.SwhPID; +import org.softwareheritage.graph.SWHID; import java.io.*; import java.nio.charset.StandardCharsets; import java.util.Scanner; import java.util.concurrent.TimeUnit; /** * Create maps needed at runtime by the graph service, in particular: *

- * - SWH PID → WebGraph long node id - * - WebGraph long node id → SWH PID (converse of the former) + * - SWHID → WebGraph long node id + * - WebGraph long node id → SWHID (converse of the former) * - WebGraph long node id → SWH node type (enum) * * @author The Software Heritage developers */ public class NodeMapBuilder { final static String SORT_BUFFER_SIZE = "40%"; final static Logger logger = LoggerFactory.getLogger(NodeMapBuilder.class); /** * Main entrypoint. * * @param args command line arguments */ public static void main(String[] args) throws IOException { if (args.length != 2) { logger.error("Usage: COMPRESSED_GRAPH_BASE_NAME TEMP_DIR < NODES_CSV"); System.exit(1); } String graphPath = args[0]; String tmpDir = args[1]; logger.info("starting maps generation..."); precomputeNodeIdMap(graphPath, tmpDir); logger.info("maps generation completed"); } /** * Computes and dumps on disk mapping files. * * @param graphPath path of the compressed graph */ // Suppress warning for Object2LongFunction cast @SuppressWarnings("unchecked") static void precomputeNodeIdMap(String graphPath, String tmpDir) throws IOException { - ProgressLogger plPid2Node = new ProgressLogger(logger, 10, TimeUnit.SECONDS); - ProgressLogger plNode2Pid = new ProgressLogger(logger, 10, TimeUnit.SECONDS); - plPid2Node.itemsName = "pid→node"; - plNode2Pid.itemsName = "node→pid"; + ProgressLogger plSWHID2Node = new ProgressLogger(logger, 10, TimeUnit.SECONDS); + ProgressLogger plNode2SWHID = new ProgressLogger(logger, 10, TimeUnit.SECONDS); + plSWHID2Node.itemsName = "swhid→node"; + plNode2SWHID.itemsName = "node→swhid"; - // avg speed for pid→node is sometime skewed due to write to the sort + // avg speed for swhid→node is sometime skewed due to write to the sort // pipe hanging when sort is sorting; hence also desplay local speed - plPid2Node.displayLocalSpeed = true; + plSWHID2Node.displayLocalSpeed = true; - // first half of PID->node mapping: PID -> WebGraph MPH (long) + // first half of SWHID->node mapping: SWHID -> WebGraph MPH (long) Object2LongFunction mphMap = null; try { logger.info("loading MPH function..."); mphMap = (Object2LongFunction) BinIO.loadObject(graphPath + ".mph"); logger.info("MPH function loaded"); } catch (ClassNotFoundException e) { logger.error("unknown class object in .mph file: " + e); System.exit(2); } long nbIds = (mphMap instanceof Size64) ? ((Size64) mphMap).size64() : mphMap.size(); - plPid2Node.expectedUpdates = nbIds; - plNode2Pid.expectedUpdates = nbIds; + plSWHID2Node.expectedUpdates = nbIds; + plNode2SWHID.expectedUpdates = nbIds; - // second half of PID->node mapping: WebGraph MPH (long) -> BFS order (long) + // second half of SWHID->node mapping: WebGraph MPH (long) -> BFS order (long) long[][] bfsMap = LongBigArrays.newBigArray(nbIds); logger.info("loading BFS order file..."); long loaded = BinIO.loadLongs(graphPath + ".order", bfsMap); logger.info("BFS order file loaded"); if (loaded != nbIds) { logger.error("graph contains " + nbIds + " nodes, but read " + loaded); System.exit(2); } - // Create mapping SWH PID -> WebGraph node id, by sequentially reading + // Create mapping SWHID -> WebGraph node id, by sequentially reading // nodes, hashing them with MPH, and permuting according to BFS order FastBufferedReader buffer = new FastBufferedReader(new InputStreamReader(System.in, StandardCharsets.US_ASCII)); - LineIterator swhPIDIterator = new LineIterator(buffer); + LineIterator swhidIterator = new LineIterator(buffer); - // The WebGraph node id -> SWH PID mapping can be obtained from the - // PID->node one by numerically sorting on node id and sequentially - // writing obtained PIDs to a binary map. Delegates the sorting job to + // The WebGraph node id -> SWHID mapping can be obtained from the + // SWHID->node one by numerically sorting on node id and sequentially + // writing obtained SWHIDs to a binary map. Delegates the sorting job to // /usr/bin/sort via pipes ProcessBuilder processBuilder = new ProcessBuilder(); processBuilder.command("sort", "--numeric-sort", "--key", "2", "--buffer-size", SORT_BUFFER_SIZE, "--temporary-directory", tmpDir); Process sort = processBuilder.start(); BufferedOutputStream sort_stdin = new BufferedOutputStream(sort.getOutputStream()); BufferedInputStream sort_stdout = new BufferedInputStream(sort.getInputStream()); - // for the binary format of pidToNodeMap, see Python module swh.graph.pid:PidToIntMap - // for the binary format of nodeToPidMap, see Python module swh.graph.pid:IntToPidMap - try (DataOutputStream pidToNodeMap = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(graphPath + Graph.PID_TO_NODE))); - BufferedOutputStream nodeToPidMap = new BufferedOutputStream(new FileOutputStream(graphPath + Graph.NODE_TO_PID))) { + // for the binary format of swhidToNodeMap, see Python module swh.graph.swhid:SwhidToIntMap + // for the binary format of nodeToSwhidMap, see Python module swh.graph.swhid:IntToSwhidMap + try (DataOutputStream swhidToNodeMap = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(graphPath + Graph.SWHID_TO_NODE))); + BufferedOutputStream nodeToSwhidMap = new BufferedOutputStream(new FileOutputStream(graphPath + Graph.NODE_TO_SWHID))) { - // background handler for sort output, it will be fed PID/node - // pairs while pidToNodeMap is being filled, and will itself fill - // nodeToPidMap as soon as data from sort is ready - SortOutputHandler outputHandler = new SortOutputHandler(sort_stdout, nodeToPidMap, plNode2Pid); + // background handler for sort output, it will be fed SWHID/node + // pairs while swhidToNodeMap is being filled, and will itself fill + // nodeToSwhidMap as soon as data from sort is ready + SortOutputHandler outputHandler = new SortOutputHandler(sort_stdout, nodeToSwhidMap, plNode2SWHID); outputHandler.start(); // Type map from WebGraph node ID to SWH type. Used at runtime by // pure Java graph traversals to efficiently check edge // restrictions. final int log2NbTypes = (int) Math.ceil(Math.log(Node.Type.values().length) / Math.log(2)); final int nbBitsPerNodeType = log2NbTypes; LongArrayBitVector nodeTypesBitVector = LongArrayBitVector.ofLength(nbBitsPerNodeType * nbIds); LongBigList nodeTypesMap = nodeTypesBitVector.asLongBigList(nbBitsPerNodeType); - plPid2Node.start("filling pid2node map"); - for (long iNode = 0; iNode < nbIds && swhPIDIterator.hasNext(); iNode++) { - String strSwhPID = swhPIDIterator.next().toString(); - SwhPID swhPID = new SwhPID(strSwhPID); - byte[] swhPIDBin = swhPID.toBytes(); + plSWHID2Node.start("filling swhid2node map"); + for (long iNode = 0; iNode < nbIds && swhidIterator.hasNext(); iNode++) { + String swhidStr = swhidIterator.next().toString(); + SWHID swhid = new SWHID(swhidStr); + byte[] swhidBin = swhid.toBytes(); - long mphId = mphMap.getLong(strSwhPID); + long mphId = mphMap.getLong(swhidStr); long nodeId = BigArrays.get(bfsMap, mphId); - pidToNodeMap.write(swhPIDBin, 0, swhPIDBin.length); - pidToNodeMap.writeLong(nodeId); - sort_stdin.write((strSwhPID + "\t" + nodeId + "\n") + swhidToNodeMap.write(swhidBin, 0, swhidBin.length); + swhidToNodeMap.writeLong(nodeId); + sort_stdin.write((swhidStr + "\t" + nodeId + "\n") .getBytes(StandardCharsets.US_ASCII)); - nodeTypesMap.set(nodeId, swhPID.getType().ordinal()); - plPid2Node.lightUpdate(); + nodeTypesMap.set(nodeId, swhid.getType().ordinal()); + plSWHID2Node.lightUpdate(); } - plPid2Node.done(); + plSWHID2Node.done(); sort_stdin.close(); // write type map logger.info("storing type map"); BinIO.storeObject(nodeTypesMap, graphPath + Graph.NODE_TO_TYPE); logger.info("type map stored"); - // wait for nodeToPidMap filling + // wait for nodeToSwhidMap filling try { - logger.info("waiting for node2pid map..."); + logger.info("waiting for node2swhid map..."); int sortExitCode = sort.waitFor(); if (sortExitCode != 0) { logger.error("sort returned non-zero exit code: " + sortExitCode); System.exit(2); } outputHandler.join(); } catch (InterruptedException e) { logger.error("processing of sort output failed with: " + e); System.exit(2); } } } private static class SortOutputHandler extends Thread { private Scanner input; private OutputStream output; private ProgressLogger pl; SortOutputHandler(InputStream input, OutputStream output, ProgressLogger pl) { this.input = new Scanner(input, StandardCharsets.US_ASCII); this.output = output; this.pl = pl; } public void run() { boolean sortDone = false; - logger.info("node2pid: waiting for sort output..."); + logger.info("node2swhid: waiting for sort output..."); while (input.hasNextLine()) { if (!sortDone) { sortDone = true; - this.pl.start("filling node2pid map"); + this.pl.start("filling node2swhid map"); } - String line = input.nextLine(); // format: SWH_PID NODE_ID - SwhPID swhPID = new SwhPID(line.split("\\t")[0]); // get PID + String line = input.nextLine(); // format: SWHID NODE_ID + SWHID swhid = new SWHID(line.split("\\t")[0]); // get SWHID try { - output.write((byte[]) swhPID.toBytes()); + output.write((byte[]) swhid.toBytes()); } catch (IOException e) { - logger.error("writing to node->PID map failed with: " + e); + logger.error("writing to node->SWHID map failed with: " + e); } this.pl.lightUpdate(); } this.pl.done(); } } } diff --git a/java/src/main/java/org/softwareheritage/graph/server/App.java b/java/src/main/java/org/softwareheritage/graph/server/App.java index 78836b0..d061680 100644 --- a/java/src/main/java/org/softwareheritage/graph/server/App.java +++ b/java/src/main/java/org/softwareheritage/graph/server/App.java @@ -1,198 +1,198 @@ package org.softwareheritage.graph.server; import com.fasterxml.jackson.databind.ObjectMapper; import com.fasterxml.jackson.databind.PropertyNamingStrategy; import com.martiansoftware.jsap.*; import io.javalin.Javalin; import io.javalin.http.Context; import io.javalin.plugin.json.JavalinJackson; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.Stats; -import org.softwareheritage.graph.SwhPID; +import org.softwareheritage.graph.SWHID; import java.io.IOException; import java.util.List; import java.util.Map; /** * Web framework of the swh-graph server REST API. * * @author The Software Heritage developers */ public class App { /** * Main entrypoint. * * @param args command line arguments */ public static void main(String[] args) throws IOException, JSAPException { SimpleJSAP jsap = new SimpleJSAP(App.class.getName(), "Server to load and query a compressed graph representation of Software Heritage archive.", new Parameter[]{ new FlaggedOption("port", JSAP.INTEGER_PARSER, "5009", JSAP.NOT_REQUIRED, 'p', "port", "Binding port of the server."), new UnflaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, JSAP.NOT_GREEDY, "The basename of the compressed graph."), new Switch("timings", 't', "timings", "Show timings in API result metadata."), }); JSAPResult config = jsap.parse(args); if (jsap.messagePrinted()) { System.exit(1); } String graphPath = config.getString("graphPath"); int port = config.getInt("port"); boolean showTimings = config.getBoolean("timings"); startServer(graphPath, port, showTimings); } /** * Loads compressed graph and starts the web server to query it. * * @param graphPath basename of the compressed graph * @param port binding port of the server * @param showTimings true if timings should be in results metadata, false otherwise */ private static void startServer(String graphPath, int port, boolean showTimings) throws IOException { Graph graph = new Graph(graphPath); Stats stats = new Stats(graphPath); // Clean up on exit Runtime.getRuntime().addShutdownHook(new Thread() { public void run() { try { graph.cleanUp(); } catch (IOException e) { System.out.println("Could not clean up graph on exit: " + e); } } }); // Configure Jackson JSON to use snake case naming style ObjectMapper objectMapper = JavalinJackson.getObjectMapper(); objectMapper.setPropertyNamingStrategy(PropertyNamingStrategy.SNAKE_CASE); JavalinJackson.configure(objectMapper); Javalin app = Javalin.create().start(port); app.before("/stats/*", ctx -> { checkQueryStrings(ctx, ""); }); app.before("/leaves/*", ctx -> { checkQueryStrings(ctx, "direction|edges"); }); app.before("/neighbors/*", ctx -> { checkQueryStrings(ctx, "direction|edges"); }); app.before("/visit/*", ctx -> { checkQueryStrings(ctx, "direction|edges"); }); app.before("/walk/*", ctx -> { checkQueryStrings(ctx, "direction|edges|traversal"); }); app.get("/stats/", ctx -> { ctx.json(stats); }); // Graph traversal endpoints // By default the traversal is a forward DFS using all edges app.get("/leaves/:src", ctx -> { - SwhPID src = new SwhPID(ctx.pathParam("src")); + SWHID src = new SWHID(ctx.pathParam("src")); String direction = ctx.queryParam("direction", "forward"); String edgesFmt = ctx.queryParam("edges", "*"); Endpoint endpoint = new Endpoint(graph, direction, edgesFmt); Endpoint.Output output = endpoint.leaves(new Endpoint.Input(src)); ctx.json(formatEndpointOutput(output, showTimings)); }); app.get("/neighbors/:src", ctx -> { - SwhPID src = new SwhPID(ctx.pathParam("src")); + SWHID src = new SWHID(ctx.pathParam("src")); String direction = ctx.queryParam("direction", "forward"); String edgesFmt = ctx.queryParam("edges", "*"); Endpoint endpoint = new Endpoint(graph, direction, edgesFmt); Endpoint.Output output = endpoint.neighbors(new Endpoint.Input(src)); ctx.json(formatEndpointOutput(output, showTimings)); }); app.get("/visit/nodes/:src", ctx -> { - SwhPID src = new SwhPID(ctx.pathParam("src")); + SWHID src = new SWHID(ctx.pathParam("src")); String direction = ctx.queryParam("direction", "forward"); String edgesFmt = ctx.queryParam("edges", "*"); Endpoint endpoint = new Endpoint(graph, direction, edgesFmt); Endpoint.Output output = endpoint.visitNodes(new Endpoint.Input(src)); ctx.json(formatEndpointOutput(output, showTimings)); }); app.get("/visit/paths/:src", ctx -> { - SwhPID src = new SwhPID(ctx.pathParam("src")); + SWHID src = new SWHID(ctx.pathParam("src")); String direction = ctx.queryParam("direction", "forward"); String edgesFmt = ctx.queryParam("edges", "*"); Endpoint endpoint = new Endpoint(graph, direction, edgesFmt); Endpoint.Output output = endpoint.visitPaths(new Endpoint.Input(src)); ctx.json(formatEndpointOutput(output, showTimings)); }); app.get("/walk/:src/:dst", ctx -> { - SwhPID src = new SwhPID(ctx.pathParam("src")); + SWHID src = new SWHID(ctx.pathParam("src")); String dstFmt = ctx.pathParam("dst"); String direction = ctx.queryParam("direction", "forward"); String edgesFmt = ctx.queryParam("edges", "*"); String algorithm = ctx.queryParam("traversal", "dfs"); Endpoint endpoint = new Endpoint(graph, direction, edgesFmt); Endpoint.Output output = endpoint.walk(new Endpoint.Input(src, dstFmt, algorithm)); ctx.json(formatEndpointOutput(output, showTimings)); }); app.exception(IllegalArgumentException.class, (e, ctx) -> { ctx.status(400); ctx.result(e.getMessage()); }); } /** * Checks query strings names provided to the REST API. * * @param ctx Javalin HTTP request context * @param allowedFmt a regular expression describing allowed query strings names * @throws IllegalArgumentException unknown query string provided */ private static void checkQueryStrings(Context ctx, String allowedFmt) { Map> queryParamMap = ctx.queryParamMap(); for (String key : queryParamMap.keySet()) { if (!key.matches(allowedFmt)) { throw new IllegalArgumentException("Unknown query string: " + key); } } } /** * Formats endpoint result into final JSON for the REST API. *

* Removes unwanted information if necessary, such as timings (to prevent use of side channels * attacks). * * @param output endpoint operation output which needs formatting * @param showTimings true if timings should be in results metadata, false otherwise * @return final Object with desired JSON format */ private static Object formatEndpointOutput(Endpoint.Output output, boolean showTimings) { if (showTimings) { return output; } else { Map metaNoTimings = Map.of("nb_edges_accessed", output.meta.nbEdgesAccessed); Map outputNoTimings = Map.of("result", output.result, "meta", metaNoTimings); return outputNoTimings; } } } diff --git a/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java b/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java index 16c96e3..10b7860 100644 --- a/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java +++ b/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java @@ -1,308 +1,308 @@ package org.softwareheritage.graph.server; import org.softwareheritage.graph.*; import org.softwareheritage.graph.benchmark.utils.Timing; import java.util.ArrayList; /** * 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 The Software Heritage developers * @see Traversal */ public class Endpoint { /** 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. + * Converts a list of (internal) long node ids to a list of corresponding (external) SWHIDs. * * @param nodeIds the list of long node ids - * @return a list of corresponding SWH PIDs + * @return a list of corresponding SWHIDs */ - private ArrayList convertNodesToSwhPIDs(ArrayList nodeIds) { - ArrayList swhPIDs = new ArrayList<>(); + private ArrayList convertNodesToSWHIDs(ArrayList nodeIds) { + ArrayList swhids = new ArrayList<>(); for (long nodeId : nodeIds) { - swhPIDs.add(graph.getSwhPID(nodeId)); + swhids.add(graph.getSWHID(nodeId)); } - return swhPIDs; + return swhids; } /** * 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)); + path.add(graph.getSWHID(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) { + private ArrayList convertPathsToSWHIDs(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 + * @return the resulting list of {@link SWHID} from endpoint call and operation metadata + * @see SWHID * @see Traversal#leaves(long) */ public Output leaves(Input input) { - Output> output = new Output<>(); + Output> output = new Output<>(); long startTime; startTime = Timing.start(); long srcNodeId = graph.getNodeId(input.src); - output.meta.timings.pid2node = Timing.stop(startTime); + output.meta.timings.swhid2node = Timing.stop(startTime); startTime = Timing.start(); ArrayList nodeIds = traversal.leaves(srcNodeId); output.meta.timings.traversal = Timing.stop(startTime); output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed(); startTime = Timing.start(); - output.result = convertNodesToSwhPIDs(nodeIds); - output.meta.timings.node2pid = Timing.stop(startTime); + output.result = convertNodesToSWHIDs(nodeIds); + output.meta.timings.node2swhid = 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 + * @return the resulting list of {@link SWHID} from endpoint call and operation metadata + * @see SWHID * @see Traversal#neighbors(long) */ public Output neighbors(Input input) { - Output> output = new Output<>(); + Output> output = new Output<>(); long startTime; startTime = Timing.start(); long srcNodeId = graph.getNodeId(input.src); - output.meta.timings.pid2node = Timing.stop(startTime); + output.meta.timings.swhid2node = Timing.stop(startTime); startTime = Timing.start(); ArrayList nodeIds = traversal.neighbors(srcNodeId); output.meta.timings.traversal = Timing.stop(startTime); output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed(); startTime = Timing.start(); - output.result = convertNodesToSwhPIDs(nodeIds); - output.meta.timings.node2pid = Timing.stop(startTime); + output.result = convertNodesToSWHIDs(nodeIds); + output.meta.timings.node2swhid = 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 SWHID * @see org.softwareheritage.graph.SwhPath * @see 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); + output.meta.timings.swhid2node = Timing.stop(startTime); ArrayList nodeIds = new ArrayList(); - // Destination is either a SWH PID or a node type + // Destination is either a SWHID or a node type try { - SwhPID dstSwhPID = new SwhPID(input.dstFmt); - long dstNodeId = graph.getNodeId(dstSwhPID); + SWHID dstSWHID = new SWHID(input.dstFmt); + long dstNodeId = graph.getNodeId(dstSWHID); 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(); startTime = Timing.start(); output.result = convertNodesToSwhPath(nodeIds); - output.meta.timings.node2pid = Timing.stop(startTime); + output.meta.timings.node2swhid = 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 + * @return the resulting list of {@link SWHID} from endpoint call and operation metadata + * @see SWHID * @see Traversal#visitNodes(long) */ public Output visitNodes(Input input) { - Output> output = new Output<>(); + Output> output = new Output<>(); long startTime; startTime = Timing.start(); long srcNodeId = graph.getNodeId(input.src); - output.meta.timings.pid2node = Timing.stop(startTime); + output.meta.timings.swhid2node = Timing.stop(startTime); startTime = Timing.start(); ArrayList nodeIds = traversal.visitNodes(srcNodeId); output.meta.timings.traversal = Timing.stop(startTime); output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed(); startTime = Timing.start(); - output.result = convertNodesToSwhPIDs(nodeIds); - output.meta.timings.node2pid = Timing.stop(startTime); + output.result = convertNodesToSWHIDs(nodeIds); + output.meta.timings.node2swhid = 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 SWHID * @see org.softwareheritage.graph.SwhPath * @see 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); + output.meta.timings.swhid2node = Timing.stop(startTime); startTime = Timing.start(); ArrayList> paths = traversal.visitPaths(srcNodeId); output.meta.timings.traversal = Timing.stop(startTime); output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed(); startTime = Timing.start(); - output.result = convertPathsToSwhPIDs(paths); - output.meta.timings.node2pid = Timing.stop(startTime); + output.result = convertPathsToSWHIDs(paths); + output.meta.timings.node2swhid = Timing.stop(startTime); return output; } /** * 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; + /** Source node of endpoint call specified as a {@link SWHID} */ + public SWHID 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) { + public Input(SWHID src) { this.src = src; } - public Input(SwhPID src, String dstFmt, String algorithm) { + public Input(SWHID 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; + /** Time in seconds to convert input SWHID to node id */ + public double swhid2node; + /** Time in seconds to convert output node ids to SWHIDs */ + public double node2swhid; } } } } diff --git a/java/src/main/java/org/softwareheritage/graph/utils/ReadGraph.java b/java/src/main/java/org/softwareheritage/graph/utils/ReadGraph.java index 333bddb..5243d12 100644 --- a/java/src/main/java/org/softwareheritage/graph/utils/ReadGraph.java +++ b/java/src/main/java/org/softwareheritage/graph/utils/ReadGraph.java @@ -1,32 +1,32 @@ package org.softwareheritage.graph.utils; import it.unimi.dsi.big.webgraph.ImmutableGraph; import it.unimi.dsi.big.webgraph.NodeIterator; import org.softwareheritage.graph.maps.NodeIdMap; import java.io.IOException; public class ReadGraph { public static void main(String[] args) throws IOException { String graphPath = args[0]; ImmutableGraph graph = ImmutableGraph.load(graphPath); NodeIdMap nodeMap = new NodeIdMap(graphPath, graph.numNodes()); NodeIterator it = graph.nodeIterator(); while (it.hasNext()) { long srcNode = it.nextLong(); var s = it.successors(); long dstNode; while ((dstNode = s.nextLong()) >= 0) { System.out.format( "%s %s\n", - nodeMap.getSwhPID(srcNode), - nodeMap.getSwhPID(dstNode) + nodeMap.getSWHID(srcNode), + nodeMap.getSWHID(dstNode) ); } } } } diff --git a/java/src/main/java/org/softwareheritage/graph/utils/ReadLabelledGraph.java b/java/src/main/java/org/softwareheritage/graph/utils/ReadLabelledGraph.java index d44c6a1..10b4c20 100644 --- a/java/src/main/java/org/softwareheritage/graph/utils/ReadLabelledGraph.java +++ b/java/src/main/java/org/softwareheritage/graph/utils/ReadLabelledGraph.java @@ -1,48 +1,48 @@ package org.softwareheritage.graph.utils; import it.unimi.dsi.big.webgraph.labelling.ArcLabelledImmutableGraph; import it.unimi.dsi.big.webgraph.labelling.ArcLabelledNodeIterator; import it.unimi.dsi.big.webgraph.labelling.BitStreamArcLabelledImmutableGraph; import it.unimi.dsi.fastutil.io.BinIO; import it.unimi.dsi.util.PermutedFrontCodedStringList; import org.softwareheritage.graph.maps.NodeIdMap; import java.io.IOException; public class ReadLabelledGraph { public static void main(String[] args) throws IOException, ClassNotFoundException { String graphPath = args[0]; ArcLabelledImmutableGraph graph = BitStreamArcLabelledImmutableGraph.loadOffline(graphPath + "-labelled"); NodeIdMap nodeMap = new NodeIdMap(graphPath, graph.numNodes()); PermutedFrontCodedStringList labelMap = (PermutedFrontCodedStringList) BinIO.loadObject(graphPath + "-labels.fcl"); ArcLabelledNodeIterator it = graph.nodeIterator(); while (it.hasNext()) { long srcNode = it.nextLong(); ArcLabelledNodeIterator.LabelledArcIterator s = it.successors(); long dstNode; while ((dstNode = s.nextLong()) >= 0) { int[] labels = (int[]) s.label().get(); if (labels.length > 0) { for (int label : labels) { System.out.format( "%s %s %s\n", - nodeMap.getSwhPID(srcNode), - nodeMap.getSwhPID(dstNode), + nodeMap.getSWHID(srcNode), + nodeMap.getSWHID(dstNode), labelMap.get(label) ); } } else { System.out.format( "%s %s\n", - nodeMap.getSwhPID(srcNode), - nodeMap.getSwhPID(dstNode) + nodeMap.getSWHID(srcNode), + nodeMap.getSWHID(dstNode) ); } } } } } diff --git a/java/src/test/java/org/softwareheritage/graph/LeavesTest.java b/java/src/test/java/org/softwareheritage/graph/LeavesTest.java index e74774e..a24cb61 100644 --- a/java/src/test/java/org/softwareheritage/graph/LeavesTest.java +++ b/java/src/test/java/org/softwareheritage/graph/LeavesTest.java @@ -1,108 +1,108 @@ package org.softwareheritage.graph; import java.util.ArrayList; import org.junit.Test; import org.softwareheritage.graph.server.Endpoint; // Avoid warnings concerning Endpoint.Output.result manual cast @SuppressWarnings("unchecked") public class LeavesTest extends GraphTest { @Test public void forwardFromSnp() { Graph graph = getGraph(); - SwhPID src = new SwhPID("swh:1:snp:0000000000000000000000000000000000000020"); + SWHID src = new SWHID("swh:1:snp:0000000000000000000000000000000000000020"); Endpoint endpoint = new Endpoint(graph, "forward", "*"); - ArrayList expectedLeaves = new ArrayList<>(); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000001")); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000004")); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000005")); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000007")); + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000004")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000005")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007")); - ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result; + ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result; GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves); } @Test public void forwardFromRel() { Graph graph = getGraph(); - SwhPID src = new SwhPID("swh:1:rel:0000000000000000000000000000000000000019"); + SWHID src = new SWHID("swh:1:rel:0000000000000000000000000000000000000019"); Endpoint endpoint = new Endpoint(graph, "forward", "*"); - ArrayList expectedLeaves = new ArrayList<>(); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000015")); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000014")); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000001")); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000004")); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000005")); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000007")); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000011")); + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000015")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000014")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000004")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000005")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000011")); - ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result; + ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result; GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves); } @Test public void backwardFromLeaf() { Graph graph = getGraph(); Endpoint endpoint1 = new Endpoint(graph, "backward", "*"); - SwhPID src1 = new SwhPID("swh:1:cnt:0000000000000000000000000000000000000015"); - ArrayList expectedLeaves1 = new ArrayList<>(); - expectedLeaves1.add(new SwhPID("swh:1:rel:0000000000000000000000000000000000000019")); - ArrayList actualLeaves1 = (ArrayList) endpoint1.leaves(new Endpoint.Input(src1)).result; + SWHID src1 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000015"); + ArrayList expectedLeaves1 = new ArrayList<>(); + expectedLeaves1.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000019")); + ArrayList actualLeaves1 = (ArrayList) endpoint1.leaves(new Endpoint.Input(src1)).result; GraphTest.assertEqualsAnyOrder(expectedLeaves1, actualLeaves1); Endpoint endpoint2 = new Endpoint(graph, "backward", "*"); - SwhPID src2 = new SwhPID("swh:1:cnt:0000000000000000000000000000000000000004"); - ArrayList expectedLeaves2 = new ArrayList<>(); - expectedLeaves2.add(new SwhPID("swh:1:ori:0000000000000000000000000000000000000021")); - expectedLeaves2.add(new SwhPID("swh:1:rel:0000000000000000000000000000000000000019")); - ArrayList actualLeaves2 = (ArrayList) endpoint2.leaves(new Endpoint.Input(src2)).result; + SWHID src2 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000004"); + ArrayList expectedLeaves2 = new ArrayList<>(); + expectedLeaves2.add(new SWHID("swh:1:ori:0000000000000000000000000000000000000021")); + expectedLeaves2.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000019")); + ArrayList actualLeaves2 = (ArrayList) endpoint2.leaves(new Endpoint.Input(src2)).result; GraphTest.assertEqualsAnyOrder(expectedLeaves2, actualLeaves2); } @Test public void forwardRevToRevOnly() { Graph graph = getGraph(); - SwhPID src = new SwhPID("swh:1:rev:0000000000000000000000000000000000000018"); + SWHID src = new SWHID("swh:1:rev:0000000000000000000000000000000000000018"); Endpoint endpoint = new Endpoint(graph, "forward", "rev:rev"); - ArrayList expectedLeaves = new ArrayList<>(); - expectedLeaves.add(new SwhPID("swh:1:rev:0000000000000000000000000000000000000003")); + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000003")); - ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result; + ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result; GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves); } @Test public void forwardDirToAll() { Graph graph = getGraph(); - SwhPID src = new SwhPID("swh:1:dir:0000000000000000000000000000000000000008"); + SWHID src = new SWHID("swh:1:dir:0000000000000000000000000000000000000008"); Endpoint endpoint = new Endpoint(graph, "forward", "dir:*"); - ArrayList expectedLeaves = new ArrayList<>(); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000004")); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000005")); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000001")); - expectedLeaves.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000007")); + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000004")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000005")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007")); - ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result; + ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result; GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves); } @Test public void backwardCntToDirDirToDir() { Graph graph = getGraph(); - SwhPID src = new SwhPID("swh:1:cnt:0000000000000000000000000000000000000005"); + SWHID src = new SWHID("swh:1:cnt:0000000000000000000000000000000000000005"); Endpoint endpoint = new Endpoint(graph, "backward", "cnt:dir,dir:dir"); - ArrayList expectedLeaves = new ArrayList<>(); - expectedLeaves.add(new SwhPID("swh:1:dir:0000000000000000000000000000000000000012")); + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000012")); - ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result; + ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result; GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves); } } diff --git a/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java b/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java index 861c43c..b20bcb6 100644 --- a/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java +++ b/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java @@ -1,142 +1,142 @@ package org.softwareheritage.graph; import java.util.ArrayList; import org.junit.Test; import org.softwareheritage.graph.server.Endpoint; // Avoid warnings concerning Endpoint.Output.result manual cast @SuppressWarnings("unchecked") public class NeighborsTest extends GraphTest { @Test public void zeroNeighbor() { Graph graph = getGraph(); - ArrayList expectedNodes = new ArrayList<>(); + ArrayList expectedNodes = new ArrayList<>(); - SwhPID src1 = new SwhPID("swh:1:ori:0000000000000000000000000000000000000021"); + SWHID src1 = new SWHID("swh:1:ori:0000000000000000000000000000000000000021"); Endpoint endpoint1 = new Endpoint(graph, "backward", "*"); - ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result; + ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result; GraphTest.assertEqualsAnyOrder(expectedNodes, actuals1); - SwhPID src2 = new SwhPID("swh:1:cnt:0000000000000000000000000000000000000004"); + SWHID src2 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000004"); Endpoint endpoint2 = new Endpoint(graph, "forward", "*"); - ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result; + ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result; GraphTest.assertEqualsAnyOrder(expectedNodes, actuals2); - SwhPID src3 = new SwhPID("swh:1:cnt:0000000000000000000000000000000000000015"); + SWHID src3 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000015"); Endpoint endpoint3 = new Endpoint(graph, "forward", "*"); - ArrayList actuals3 = (ArrayList) endpoint3.neighbors(new Endpoint.Input(src3)).result; + ArrayList actuals3 = (ArrayList) endpoint3.neighbors(new Endpoint.Input(src3)).result; GraphTest.assertEqualsAnyOrder(expectedNodes, actuals3); - SwhPID src4 = new SwhPID("swh:1:rel:0000000000000000000000000000000000000019"); + SWHID src4 = new SWHID("swh:1:rel:0000000000000000000000000000000000000019"); Endpoint endpoint4 = new Endpoint(graph, "backward", "*"); - ArrayList actuals4 = (ArrayList) endpoint4.neighbors(new Endpoint.Input(src4)).result; + ArrayList actuals4 = (ArrayList) endpoint4.neighbors(new Endpoint.Input(src4)).result; GraphTest.assertEqualsAnyOrder(expectedNodes, actuals4); - SwhPID src5 = new SwhPID("swh:1:dir:0000000000000000000000000000000000000008"); + SWHID src5 = new SWHID("swh:1:dir:0000000000000000000000000000000000000008"); Endpoint endpoint5 = new Endpoint(graph, "forward", "snp:*,rev:*,rel:*"); - ArrayList actuals5 = (ArrayList) endpoint5.neighbors(new Endpoint.Input(src5)).result; + ArrayList actuals5 = (ArrayList) endpoint5.neighbors(new Endpoint.Input(src5)).result; GraphTest.assertEqualsAnyOrder(expectedNodes, actuals5); } @Test public void oneNeighbor() { Graph graph = getGraph(); - SwhPID src1 = new SwhPID("swh:1:rev:0000000000000000000000000000000000000003"); + SWHID src1 = new SWHID("swh:1:rev:0000000000000000000000000000000000000003"); Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); - ArrayList expectedNodes1 = new ArrayList<>(); - expectedNodes1.add(new SwhPID("swh:1:dir:0000000000000000000000000000000000000002")); - ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result; + ArrayList expectedNodes1 = new ArrayList<>(); + expectedNodes1.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000002")); + ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result; GraphTest.assertEqualsAnyOrder(expectedNodes1, actuals1); - SwhPID src2 = new SwhPID("swh:1:dir:0000000000000000000000000000000000000017"); + SWHID src2 = new SWHID("swh:1:dir:0000000000000000000000000000000000000017"); Endpoint endpoint2 = new Endpoint(graph, "forward", "dir:cnt"); - ArrayList expectedNodes2 = new ArrayList<>(); - expectedNodes2.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000014")); - ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result; + ArrayList expectedNodes2 = new ArrayList<>(); + expectedNodes2.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000014")); + ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result; GraphTest.assertEqualsAnyOrder(expectedNodes2, actuals2); - SwhPID src3 = new SwhPID("swh:1:dir:0000000000000000000000000000000000000012"); + SWHID src3 = new SWHID("swh:1:dir:0000000000000000000000000000000000000012"); Endpoint endpoint3 = new Endpoint(graph, "backward", "*"); - ArrayList expectedNodes3 = new ArrayList<>(); - expectedNodes3.add(new SwhPID("swh:1:rev:0000000000000000000000000000000000000013")); - ArrayList actuals3 = (ArrayList) endpoint3.neighbors(new Endpoint.Input(src3)).result; + ArrayList expectedNodes3 = new ArrayList<>(); + expectedNodes3.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000013")); + ArrayList actuals3 = (ArrayList) endpoint3.neighbors(new Endpoint.Input(src3)).result; GraphTest.assertEqualsAnyOrder(expectedNodes3, actuals3); - SwhPID src4 = new SwhPID("swh:1:rev:0000000000000000000000000000000000000009"); + SWHID src4 = new SWHID("swh:1:rev:0000000000000000000000000000000000000009"); Endpoint endpoint4 = new Endpoint(graph, "backward", "rev:rev"); - ArrayList expectedNodes4 = new ArrayList<>(); - expectedNodes4.add(new SwhPID("swh:1:rev:0000000000000000000000000000000000000013")); - ArrayList actuals4 = (ArrayList) endpoint4.neighbors(new Endpoint.Input(src4)).result; + ArrayList expectedNodes4 = new ArrayList<>(); + expectedNodes4.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000013")); + ArrayList actuals4 = (ArrayList) endpoint4.neighbors(new Endpoint.Input(src4)).result; GraphTest.assertEqualsAnyOrder(expectedNodes4, actuals4); - SwhPID src5 = new SwhPID("swh:1:snp:0000000000000000000000000000000000000020"); + SWHID src5 = new SWHID("swh:1:snp:0000000000000000000000000000000000000020"); Endpoint endpoint5 = new Endpoint(graph, "backward", "*"); - ArrayList expectedNodes5 = new ArrayList<>(); - expectedNodes5.add(new SwhPID("swh:1:ori:0000000000000000000000000000000000000021")); - ArrayList actuals5 = (ArrayList) endpoint5.neighbors(new Endpoint.Input(src5)).result; + ArrayList expectedNodes5 = new ArrayList<>(); + expectedNodes5.add(new SWHID("swh:1:ori:0000000000000000000000000000000000000021")); + ArrayList actuals5 = (ArrayList) endpoint5.neighbors(new Endpoint.Input(src5)).result; GraphTest.assertEqualsAnyOrder(expectedNodes5, actuals5); } @Test public void twoNeighbors() { Graph graph = getGraph(); - SwhPID src1 = new SwhPID("swh:1:snp:0000000000000000000000000000000000000020"); + SWHID src1 = new SWHID("swh:1:snp:0000000000000000000000000000000000000020"); Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); - ArrayList expectedNodes1 = new ArrayList<>(); - expectedNodes1.add(new SwhPID("swh:1:rel:0000000000000000000000000000000000000010")); - expectedNodes1.add(new SwhPID("swh:1:rev:0000000000000000000000000000000000000009")); - ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result; + ArrayList expectedNodes1 = new ArrayList<>(); + expectedNodes1.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000010")); + expectedNodes1.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000009")); + ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result; GraphTest.assertEqualsAnyOrder(expectedNodes1, actuals1); - SwhPID src2 = new SwhPID("swh:1:dir:0000000000000000000000000000000000000008"); + SWHID src2 = new SWHID("swh:1:dir:0000000000000000000000000000000000000008"); Endpoint endpoint2 = new Endpoint(graph, "forward", "dir:cnt"); - ArrayList expectedNodes2 = new ArrayList<>(); - expectedNodes2.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000001")); - expectedNodes2.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000007")); - ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result; + ArrayList expectedNodes2 = new ArrayList<>(); + expectedNodes2.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedNodes2.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007")); + ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result; GraphTest.assertEqualsAnyOrder(expectedNodes2, actuals2); - SwhPID src3 = new SwhPID("swh:1:cnt:0000000000000000000000000000000000000001"); + SWHID src3 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000001"); Endpoint endpoint3 = new Endpoint(graph, "backward", "*"); - ArrayList expectedNodes3 = new ArrayList<>(); - expectedNodes3.add(new SwhPID("swh:1:dir:0000000000000000000000000000000000000008")); - expectedNodes3.add(new SwhPID("swh:1:dir:0000000000000000000000000000000000000002")); - ArrayList actuals3 = (ArrayList) endpoint3.neighbors(new Endpoint.Input(src3)).result; + ArrayList expectedNodes3 = new ArrayList<>(); + expectedNodes3.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000008")); + expectedNodes3.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000002")); + ArrayList actuals3 = (ArrayList) endpoint3.neighbors(new Endpoint.Input(src3)).result; GraphTest.assertEqualsAnyOrder(expectedNodes3, actuals3); - SwhPID src4 = new SwhPID("swh:1:rev:0000000000000000000000000000000000000009"); + SWHID src4 = new SWHID("swh:1:rev:0000000000000000000000000000000000000009"); Endpoint endpoint4 = new Endpoint(graph, "backward", "rev:snp,rev:rel"); - ArrayList expectedNodes4 = new ArrayList<>(); - expectedNodes4.add(new SwhPID("swh:1:snp:0000000000000000000000000000000000000020")); - expectedNodes4.add(new SwhPID("swh:1:rel:0000000000000000000000000000000000000010")); - ArrayList actuals4 = (ArrayList) endpoint4.neighbors(new Endpoint.Input(src4)).result; + ArrayList expectedNodes4 = new ArrayList<>(); + expectedNodes4.add(new SWHID("swh:1:snp:0000000000000000000000000000000000000020")); + expectedNodes4.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000010")); + ArrayList actuals4 = (ArrayList) endpoint4.neighbors(new Endpoint.Input(src4)).result; GraphTest.assertEqualsAnyOrder(expectedNodes4, actuals4); } @Test public void threeNeighbors() { Graph graph = getGraph(); - SwhPID src1 = new SwhPID("swh:1:dir:0000000000000000000000000000000000000008"); + SWHID src1 = new SWHID("swh:1:dir:0000000000000000000000000000000000000008"); Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); - ArrayList expectedNodes1 = new ArrayList<>(); - expectedNodes1.add(new SwhPID("swh:1:dir:0000000000000000000000000000000000000006")); - expectedNodes1.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000001")); - expectedNodes1.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000007")); - ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result; + ArrayList expectedNodes1 = new ArrayList<>(); + expectedNodes1.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000006")); + expectedNodes1.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedNodes1.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007")); + ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result; GraphTest.assertEqualsAnyOrder(expectedNodes1, actuals1); - SwhPID src2 = new SwhPID("swh:1:rev:0000000000000000000000000000000000000009"); + SWHID src2 = new SWHID("swh:1:rev:0000000000000000000000000000000000000009"); Endpoint endpoint2 = new Endpoint(graph, "backward", "*"); - ArrayList expectedNodes2 = new ArrayList<>(); - expectedNodes2.add(new SwhPID("swh:1:snp:0000000000000000000000000000000000000020")); - expectedNodes2.add(new SwhPID("swh:1:rel:0000000000000000000000000000000000000010")); - expectedNodes2.add(new SwhPID("swh:1:rev:0000000000000000000000000000000000000013")); - ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result; + ArrayList expectedNodes2 = new ArrayList<>(); + expectedNodes2.add(new SWHID("swh:1:snp:0000000000000000000000000000000000000020")); + expectedNodes2.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000010")); + expectedNodes2.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000013")); + ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result; GraphTest.assertEqualsAnyOrder(expectedNodes2, actuals2); } } diff --git a/java/src/test/java/org/softwareheritage/graph/VisitTest.java b/java/src/test/java/org/softwareheritage/graph/VisitTest.java index 9ac4008..11fc97c 100644 --- a/java/src/test/java/org/softwareheritage/graph/VisitTest.java +++ b/java/src/test/java/org/softwareheritage/graph/VisitTest.java @@ -1,543 +1,543 @@ package org.softwareheritage.graph; import java.util.ArrayList; import java.util.Set; import java.util.HashSet; import org.junit.Test; import org.softwareheritage.graph.server.Endpoint; // Avoid warnings concerning Endpoint.Output.result manual cast @SuppressWarnings("unchecked") public class VisitTest extends GraphTest { - private void assertSameNodesFromPaths(ArrayList paths, ArrayList nodes) { - Set expectedNodes = new HashSet(); + private void assertSameNodesFromPaths(ArrayList paths, ArrayList nodes) { + Set expectedNodes = new HashSet(); for (SwhPath path : paths) { - for (SwhPID node : path.getPath()) { + for (SWHID node : path.getPath()) { expectedNodes.add(node); } } GraphTest.assertEqualsAnyOrder(expectedNodes, nodes); } @Test public void forwardFromRoot() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:ori:0000000000000000000000000000000000000021"); + SWHID swhid = new SWHID("swh:1:ori:0000000000000000000000000000000000000021"); Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); - ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhPID)).result; + ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; Endpoint endpoint2 = new Endpoint(graph, "forward", "*"); - ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhPID)).result; + ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result; ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:ori:0000000000000000000000000000000000000021", "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000007" )); expectedPaths.add( new SwhPath( "swh:1:ori:0000000000000000000000000000000000000021", "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000001" )); expectedPaths.add( new SwhPath( "swh:1:ori:0000000000000000000000000000000000000021", "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000004" )); expectedPaths.add( new SwhPath( "swh:1:ori:0000000000000000000000000000000000000021", "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000005" )); expectedPaths.add( new SwhPath( "swh:1:ori:0000000000000000000000000000000000000021", "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:cnt:0000000000000000000000000000000000000001" )); expectedPaths.add( new SwhPath( "swh:1:ori:0000000000000000000000000000000000000021", "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000007" )); expectedPaths.add( new SwhPath( "swh:1:ori:0000000000000000000000000000000000000021", "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000001" )); expectedPaths.add( new SwhPath( "swh:1:ori:0000000000000000000000000000000000000021", "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000004" )); expectedPaths.add( new SwhPath( "swh:1:ori:0000000000000000000000000000000000000021", "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000005" )); expectedPaths.add( new SwhPath( "swh:1:ori:0000000000000000000000000000000000000021", "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:cnt:0000000000000000000000000000000000000001" )); GraphTest.assertEqualsAnyOrder(expectedPaths, paths); assertSameNodesFromPaths(expectedPaths, nodes); } @Test public void forwardFromMiddle() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:dir:0000000000000000000000000000000000000012"); + SWHID swhid = new SWHID("swh:1:dir:0000000000000000000000000000000000000012"); Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); - ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhPID)).result; + ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; Endpoint endpoint2 = new Endpoint(graph, "forward", "*"); - ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhPID)).result; + ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result; ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000012", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000007" )); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000012", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000001" )); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000012", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000004" )); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000012", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000005" )); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000012", "swh:1:cnt:0000000000000000000000000000000000000011" )); GraphTest.assertEqualsAnyOrder(expectedPaths, paths); assertSameNodesFromPaths(expectedPaths, nodes); } @Test public void forwardFromLeaf() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:cnt:0000000000000000000000000000000000000004"); + SWHID swhid = new SWHID("swh:1:cnt:0000000000000000000000000000000000000004"); Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); - ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhPID)).result; + ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; Endpoint endpoint2 = new Endpoint(graph, "forward", "*"); - ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhPID)).result; + ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result; ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000004" )); GraphTest.assertEqualsAnyOrder(expectedPaths, paths); assertSameNodesFromPaths(expectedPaths, nodes); } @Test public void backwardFromRoot() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:ori:0000000000000000000000000000000000000021"); + SWHID swhid = new SWHID("swh:1:ori:0000000000000000000000000000000000000021"); Endpoint endpoint1 = new Endpoint(graph, "backward", "*"); - ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhPID)).result; + ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; Endpoint endpoint2 = new Endpoint(graph, "backward", "*"); - ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhPID)).result; + ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result; ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:ori:0000000000000000000000000000000000000021" )); GraphTest.assertEqualsAnyOrder(expectedPaths, paths); assertSameNodesFromPaths(expectedPaths, nodes); } @Test public void backwardFromMiddle() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:dir:0000000000000000000000000000000000000012"); + SWHID swhid = new SWHID("swh:1:dir:0000000000000000000000000000000000000012"); Endpoint endpoint1 = new Endpoint(graph, "backward", "*"); - ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhPID)).result; + ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; Endpoint endpoint2 = new Endpoint(graph, "backward", "*"); - ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhPID)).result; + ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result; ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:dir:0000000000000000000000000000000000000012", "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:rev:0000000000000000000000000000000000000018", "swh:1:rel:0000000000000000000000000000000000000019" )); GraphTest.assertEqualsAnyOrder(expectedPaths, paths); assertSameNodesFromPaths(expectedPaths, nodes); } @Test public void backwardFromLeaf() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:cnt:0000000000000000000000000000000000000004"); + SWHID swhid = new SWHID("swh:1:cnt:0000000000000000000000000000000000000004"); Endpoint endpoint1 = new Endpoint(graph, "backward", "*"); - ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhPID)).result; + ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; Endpoint endpoint2 = new Endpoint(graph, "backward", "*"); - ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhPID)).result; + ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result; ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000004", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000012", "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:rev:0000000000000000000000000000000000000018", "swh:1:rel:0000000000000000000000000000000000000019" )); expectedPaths.add( new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000004", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:rev:0000000000000000000000000000000000000018", "swh:1:rel:0000000000000000000000000000000000000019" )); expectedPaths.add( new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000004", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:ori:0000000000000000000000000000000000000021" )); expectedPaths.add( new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000004", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:ori:0000000000000000000000000000000000000021" )); GraphTest.assertEqualsAnyOrder(expectedPaths, paths); assertSameNodesFromPaths(expectedPaths, nodes); } @Test public void forwardSnpToRev() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:snp:0000000000000000000000000000000000000020"); + SWHID swhid = new SWHID("swh:1:snp:0000000000000000000000000000000000000020"); Endpoint endpoint1 = new Endpoint(graph, "forward", "snp:rev"); - ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhPID)).result; + ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; Endpoint endpoint2 = new Endpoint(graph, "forward", "snp:rev"); - ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhPID)).result; + ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result; ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rev:0000000000000000000000000000000000000009" )); GraphTest.assertEqualsAnyOrder(expectedPaths, paths); assertSameNodesFromPaths(expectedPaths, nodes); } @Test public void forwardRelToRevRevToRev() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:rel:0000000000000000000000000000000000000010"); + SWHID swhid = new SWHID("swh:1:rel:0000000000000000000000000000000000000010"); Endpoint endpoint1 = new Endpoint(graph, "forward", "rel:rev,rev:rev"); - ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhPID)).result; + ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; Endpoint endpoint2 = new Endpoint(graph, "forward", "rel:rev,rev:rev"); - ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhPID)).result; + ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result; ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000003" )); GraphTest.assertEqualsAnyOrder(expectedPaths, paths); assertSameNodesFromPaths(expectedPaths, nodes); } @Test public void forwardRevToAllDirToAll() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:rev:0000000000000000000000000000000000000013"); + SWHID swhid = new SWHID("swh:1:rev:0000000000000000000000000000000000000013"); Endpoint endpoint1 = new Endpoint(graph, "forward", "rev:*,dir:*"); - ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhPID)).result; + ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; Endpoint endpoint2 = new Endpoint(graph, "forward", "rev:*,dir:*"); - ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhPID)).result; + ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result; ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000005" )); expectedPaths.add( new SwhPath( "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:dir:0000000000000000000000000000000000000012", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000005" )); expectedPaths.add( new SwhPath( "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000004" )); expectedPaths.add( new SwhPath( "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:dir:0000000000000000000000000000000000000012", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000004" )); expectedPaths.add( new SwhPath( "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000007" )); expectedPaths.add( new SwhPath( "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:dir:0000000000000000000000000000000000000012", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000007" )); expectedPaths.add( new SwhPath( "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:dir:0000000000000000000000000000000000000012", "swh:1:cnt:0000000000000000000000000000000000000011" )); expectedPaths.add( new SwhPath( "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:cnt:0000000000000000000000000000000000000001" )); expectedPaths.add( new SwhPath( "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000001" )); expectedPaths.add( new SwhPath( "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:dir:0000000000000000000000000000000000000012", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000001" )); GraphTest.assertEqualsAnyOrder(expectedPaths, paths); assertSameNodesFromPaths(expectedPaths, nodes); } @Test public void forwardSnpToAllRevToAll() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:snp:0000000000000000000000000000000000000020"); + SWHID swhid = new SWHID("swh:1:snp:0000000000000000000000000000000000000020"); Endpoint endpoint1 = new Endpoint(graph, "forward", "snp:*,rev:*"); - ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhPID)).result; + ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; Endpoint endpoint2 = new Endpoint(graph, "forward", "snp:*,rev:*"); - ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhPID)).result; + ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result; ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:dir:0000000000000000000000000000000000000002" )); expectedPaths.add( new SwhPath( "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008" )); expectedPaths.add( new SwhPath( "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rel:0000000000000000000000000000000000000010" )); GraphTest.assertEqualsAnyOrder(expectedPaths, paths); assertSameNodesFromPaths(expectedPaths, nodes); } @Test public void forwardNoEdges() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:snp:0000000000000000000000000000000000000020"); + SWHID swhid = new SWHID("swh:1:snp:0000000000000000000000000000000000000020"); Endpoint endpoint1 = new Endpoint(graph, "forward", ""); - ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhPID)).result; + ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; Endpoint endpoint2 = new Endpoint(graph, "forward", ""); - ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhPID)).result; + ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result; ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:snp:0000000000000000000000000000000000000020" )); GraphTest.assertEqualsAnyOrder(expectedPaths, paths); assertSameNodesFromPaths(expectedPaths, nodes); } @Test public void backwardRevToRevRevToRel() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:rev:0000000000000000000000000000000000000003"); + SWHID swhid = new SWHID("swh:1:rev:0000000000000000000000000000000000000003"); Endpoint endpoint1 = new Endpoint(graph, "backward", "rev:rev,rev:rel"); - ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhPID)).result; + ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; Endpoint endpoint2 = new Endpoint(graph, "backward", "rev:rev,rev:rel"); - ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhPID)).result; + ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result; ArrayList expectedPaths = new ArrayList(); expectedPaths.add( new SwhPath( "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:rev:0000000000000000000000000000000000000018", "swh:1:rel:0000000000000000000000000000000000000019" )); expectedPaths.add( new SwhPath( "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rel:0000000000000000000000000000000000000010" )); GraphTest.assertEqualsAnyOrder(expectedPaths, paths); assertSameNodesFromPaths(expectedPaths, nodes); } @Test public void forwardFromRootNodesOnly() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:ori:0000000000000000000000000000000000000021"); + SWHID swhid = new SWHID("swh:1:ori:0000000000000000000000000000000000000021"); Endpoint endpoint = new Endpoint(graph, "forward", "*"); - ArrayList nodes = (ArrayList) endpoint.visitNodes(new Endpoint.Input(swhPID)).result; - - ArrayList expectedNodes = new ArrayList(); - expectedNodes.add(new SwhPID("swh:1:ori:0000000000000000000000000000000000000021")); - expectedNodes.add(new SwhPID("swh:1:snp:0000000000000000000000000000000000000020")); - expectedNodes.add(new SwhPID("swh:1:rel:0000000000000000000000000000000000000010")); - expectedNodes.add(new SwhPID("swh:1:rev:0000000000000000000000000000000000000009")); - expectedNodes.add(new SwhPID("swh:1:rev:0000000000000000000000000000000000000003")); - expectedNodes.add(new SwhPID("swh:1:dir:0000000000000000000000000000000000000002")); - expectedNodes.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000001")); - expectedNodes.add(new SwhPID("swh:1:dir:0000000000000000000000000000000000000008")); - expectedNodes.add(new SwhPID("swh:1:dir:0000000000000000000000000000000000000006")); - expectedNodes.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000004")); - expectedNodes.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000005")); - expectedNodes.add(new SwhPID("swh:1:cnt:0000000000000000000000000000000000000007")); + ArrayList nodes = (ArrayList) endpoint.visitNodes(new Endpoint.Input(swhid)).result; + + ArrayList expectedNodes = new ArrayList(); + expectedNodes.add(new SWHID("swh:1:ori:0000000000000000000000000000000000000021")); + expectedNodes.add(new SWHID("swh:1:snp:0000000000000000000000000000000000000020")); + expectedNodes.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000010")); + expectedNodes.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000009")); + expectedNodes.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000003")); + expectedNodes.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000002")); + expectedNodes.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedNodes.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000008")); + expectedNodes.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000006")); + expectedNodes.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000004")); + expectedNodes.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000005")); + expectedNodes.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007")); GraphTest.assertEqualsAnyOrder(expectedNodes, nodes); } @Test public void backwardRevToAllNodesOnly() { Graph graph = getGraph(); - SwhPID swhPID = new SwhPID("swh:1:rev:0000000000000000000000000000000000000003"); + SWHID swhid = new SWHID("swh:1:rev:0000000000000000000000000000000000000003"); Endpoint endpoint = new Endpoint(graph, "backward", "rev:*"); - ArrayList nodes = (ArrayList) endpoint.visitNodes(new Endpoint.Input(swhPID)).result; - - ArrayList expectedNodes = new ArrayList(); - expectedNodes.add(new SwhPID("swh:1:rev:0000000000000000000000000000000000000003")); - expectedNodes.add(new SwhPID("swh:1:rev:0000000000000000000000000000000000000009")); - expectedNodes.add(new SwhPID("swh:1:snp:0000000000000000000000000000000000000020")); - expectedNodes.add(new SwhPID("swh:1:rel:0000000000000000000000000000000000000010")); - expectedNodes.add(new SwhPID("swh:1:rev:0000000000000000000000000000000000000013")); - expectedNodes.add(new SwhPID("swh:1:rev:0000000000000000000000000000000000000018")); - expectedNodes.add(new SwhPID("swh:1:rel:0000000000000000000000000000000000000019")); + ArrayList nodes = (ArrayList) endpoint.visitNodes(new Endpoint.Input(swhid)).result; + + ArrayList expectedNodes = new ArrayList(); + expectedNodes.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000003")); + expectedNodes.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000009")); + expectedNodes.add(new SWHID("swh:1:snp:0000000000000000000000000000000000000020")); + expectedNodes.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000010")); + expectedNodes.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000013")); + expectedNodes.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000018")); + expectedNodes.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000019")); GraphTest.assertEqualsAnyOrder(expectedNodes, nodes); } } diff --git a/java/src/test/java/org/softwareheritage/graph/WalkTest.java b/java/src/test/java/org/softwareheritage/graph/WalkTest.java index 54a3b3b..f575a66 100644 --- a/java/src/test/java/org/softwareheritage/graph/WalkTest.java +++ b/java/src/test/java/org/softwareheritage/graph/WalkTest.java @@ -1,234 +1,234 @@ package org.softwareheritage.graph; import java.util.Arrays; import java.util.List; import org.junit.Assert; import org.junit.Test; import org.softwareheritage.graph.server.Endpoint; public class WalkTest extends GraphTest { @Test public void forwardRootToLeaf() { Graph graph = getGraph(); - SwhPID src = new SwhPID("swh:1:snp:0000000000000000000000000000000000000020"); + SWHID src = new SWHID("swh:1:snp:0000000000000000000000000000000000000020"); String dstFmt = "swh:1:cnt:0000000000000000000000000000000000000005"; SwhPath solution1 = new SwhPath( "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000005" ); SwhPath solution2 = new SwhPath( "swh:1:snp:0000000000000000000000000000000000000020", "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000005" ); Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result; Endpoint endpoint2 = new Endpoint(graph, "forward", "*"); SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result; List possibleSolutions = Arrays.asList(solution1, solution2); Assert.assertTrue(possibleSolutions.contains(dfsPath)); Assert.assertTrue(possibleSolutions.contains(bfsPath)); } @Test public void forwardLeafToLeaf() { Graph graph = getGraph(); - SwhPID src = new SwhPID("swh:1:cnt:0000000000000000000000000000000000000007"); + SWHID src = new SWHID("swh:1:cnt:0000000000000000000000000000000000000007"); String dstFmt = "cnt"; SwhPath expectedPath = new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000007" ); Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result; Endpoint endpoint2 = new Endpoint(graph, "forward", "*"); SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result; Assert.assertEquals(dfsPath, expectedPath); Assert.assertEquals(bfsPath, expectedPath); } @Test public void forwardRevToRev() { Graph graph = getGraph(); - SwhPID src = new SwhPID("swh:1:rev:0000000000000000000000000000000000000018"); + SWHID src = new SWHID("swh:1:rev:0000000000000000000000000000000000000018"); String dstFmt = "swh:1:rev:0000000000000000000000000000000000000003"; SwhPath expectedPath = new SwhPath( "swh:1:rev:0000000000000000000000000000000000000018", "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000003" ); Endpoint endpoint1 = new Endpoint(graph, "forward", "rev:rev"); SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result; Endpoint endpoint2 = new Endpoint(graph, "forward", "rev:rev"); SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result; Assert.assertEquals(dfsPath, expectedPath); Assert.assertEquals(bfsPath, expectedPath); } @Test public void backwardRevToRev() { Graph graph = getGraph(); - SwhPID src = new SwhPID("swh:1:rev:0000000000000000000000000000000000000003"); + SWHID src = new SWHID("swh:1:rev:0000000000000000000000000000000000000003"); String dstFmt = "swh:1:rev:0000000000000000000000000000000000000018"; SwhPath expectedPath = new SwhPath( "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000013", "swh:1:rev:0000000000000000000000000000000000000018" ); Endpoint endpoint1 = new Endpoint(graph, "backward", "rev:rev"); SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result; Endpoint endpoint2 = new Endpoint(graph, "backward", "rev:rev"); SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result; Assert.assertEquals(dfsPath, expectedPath); Assert.assertEquals(bfsPath, expectedPath); } @Test public void backwardCntToFirstSnp() { Graph graph = getGraph(); - SwhPID src = new SwhPID("swh:1:cnt:0000000000000000000000000000000000000001"); + SWHID src = new SWHID("swh:1:cnt:0000000000000000000000000000000000000001"); String dstFmt = "snp"; SwhPath solution1 = new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000001", "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:snp:0000000000000000000000000000000000000020" ); SwhPath solution2 = new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000001", "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:snp:0000000000000000000000000000000000000020" ); SwhPath solution3 = new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000001", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:snp:0000000000000000000000000000000000000020" ); SwhPath solution4 = new SwhPath( "swh:1:cnt:0000000000000000000000000000000000000001", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rel:0000000000000000000000000000000000000010", "swh:1:snp:0000000000000000000000000000000000000020" ); Endpoint endpoint1 = new Endpoint(graph, "backward", "*"); SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result; Endpoint endpoint2 = new Endpoint(graph, "backward", "*"); SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result; List possibleSolutions = Arrays.asList(solution1, solution2, solution3, solution4); Assert.assertTrue(possibleSolutions.contains(dfsPath)); Assert.assertTrue(possibleSolutions.contains(bfsPath)); } @Test public void forwardRevToFirstCnt() { Graph graph = getGraph(); - SwhPID src = new SwhPID("swh:1:rev:0000000000000000000000000000000000000009"); + SWHID src = new SWHID("swh:1:rev:0000000000000000000000000000000000000009"); String dstFmt = "cnt"; SwhPath solution1 = new SwhPath( "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000007" ); SwhPath solution2 = new SwhPath( "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000005" ); SwhPath solution3 = new SwhPath( "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:dir:0000000000000000000000000000000000000006", "swh:1:cnt:0000000000000000000000000000000000000004" ); SwhPath solution4 = new SwhPath( "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:dir:0000000000000000000000000000000000000008", "swh:1:cnt:0000000000000000000000000000000000000001" ); SwhPath solution5 = new SwhPath( "swh:1:rev:0000000000000000000000000000000000000009", "swh:1:rev:0000000000000000000000000000000000000003", "swh:1:dir:0000000000000000000000000000000000000002", "swh:1:cnt:0000000000000000000000000000000000000001" ); Endpoint endpoint1 = new Endpoint(graph, "forward", "rev:*,dir:*"); SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result; Endpoint endpoint2 = new Endpoint(graph, "forward", "rev:*,dir:*"); SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result; List possibleSolutions = Arrays.asList(solution1, solution2, solution3, solution4, solution5); Assert.assertTrue(possibleSolutions.contains(dfsPath)); Assert.assertTrue(possibleSolutions.contains(bfsPath)); } @Test public void backwardDirToFirstRel() { Graph graph = getGraph(); - SwhPID src = new SwhPID("swh:1:dir:0000000000000000000000000000000000000016"); + SWHID src = new SWHID("swh:1:dir:0000000000000000000000000000000000000016"); String dstFmt = "rel"; SwhPath expectedPath = new SwhPath( "swh:1:dir:0000000000000000000000000000000000000016", "swh:1:dir:0000000000000000000000000000000000000017", "swh:1:rev:0000000000000000000000000000000000000018", "swh:1:rel:0000000000000000000000000000000000000019" ); Endpoint endpoint1 = new Endpoint(graph, "backward", "dir:dir,dir:rev,rev:*"); SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result; Endpoint endpoint2 = new Endpoint(graph, "backward", "dir:dir,dir:rev,rev:*"); SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result; Assert.assertEquals(dfsPath, expectedPath); Assert.assertEquals(bfsPath, expectedPath); } }