nodeTypes = Arrays.asList(Node.Type.values());
- types.addAll(nodeTypes);
- } else {
- types.add(Node.Type.fromStr(strFmtType));
- }
-
- return types;
- }
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/SWHID.java b/java/src/main/java/org/softwareheritage/graph/SWHID.java
--- a/java/src/main/java/org/softwareheritage/graph/SWHID.java
+++ b/java/src/main/java/org/softwareheritage/graph/SWHID.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2019 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph;
import com.fasterxml.jackson.annotation.JsonValue;
@@ -19,7 +26,7 @@
/** Full SWHID as a string */
String swhid;
/** SWHID node type */
- Node.Type type;
+ SwhType type;
/**
* Constructor.
@@ -34,7 +41,7 @@
if (parts.length != 4 || !parts[0].equals("swh") || !parts[1].equals("1")) {
throw new IllegalArgumentException("malformed SWHID: " + swhid);
}
- this.type = Node.Type.fromStr(parts[2]);
+ this.type = SwhType.fromStr(parts[2]);
if (!parts[3].matches("[0-9a-f]{" + HASH_LENGTH + "}")) {
throw new IllegalArgumentException("malformed SWHID: " + swhid);
}
@@ -49,7 +56,7 @@
byte[] digest = new byte[20];
System.arraycopy(input, 2, digest, 0, digest.length);
- String swhidStr = String.format("swh:%d:%s:%s", input[0], Node.Type.fromInt(input[1]).toString().toLowerCase(),
+ String swhidStr = String.format("swh:%d:%s:%s", input[0], SwhType.fromInt(input[1]).toString().toLowerCase(),
Hex.encodeHexString(digest));
return new SWHID(swhidStr);
}
@@ -85,7 +92,7 @@
byte[] digest;
bytes[0] = (byte) 1; // namespace version
- bytes[1] = (byte) Node.Type.toInt(this.type); // SWHID type
+ bytes[1] = (byte) SwhType.toInt(this.type); // SWHID type
try {
digest = Hex.decodeHex(this.swhid.substring(10)); // SHA1 hash
System.arraycopy(digest, 0, bytes, 2, digest.length);
@@ -109,10 +116,10 @@
/**
* Returns SWHID node type.
*
- * @return SWHID corresponding {@link Node.Type}
- * @see org.softwareheritage.graph.Node.Type
+ * @return SWHID corresponding {@link SwhType}
+ * @see SwhType
*/
- public Node.Type getType() {
+ public SwhType getType() {
return type;
}
}
diff --git a/java/src/main/java/org/softwareheritage/graph/Stats.java b/java/src/main/java/org/softwareheritage/graph/Stats.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/Stats.java
+++ /dev/null
@@ -1,67 +0,0 @@
-package org.softwareheritage.graph;
-
-import java.io.FileInputStream;
-import java.io.IOException;
-import java.util.Properties;
-
-/**
- * Statistics on the compressed graph.
- *
- * These statistics are not computed but directly read from
- * WebGraph generated .stats and .properties files.
- *
- * @author The Software Heritage developers
- */
-
-public class Stats {
- public Counts counts;
- public Ratios ratios;
- public Degree indegree;
- public Degree outdegree;
- /**
- * Constructor.
- *
- * @param graphPath path and basename of compressed graph
- */
- public Stats(String graphPath) throws IOException {
- Properties properties = new Properties();
- properties.load(new FileInputStream(graphPath + ".properties"));
- properties.load(new FileInputStream(graphPath + ".stats"));
-
- this.counts = new Counts();
- this.ratios = new Ratios();
- this.indegree = new Degree();
- this.outdegree = new Degree();
-
- this.counts.nodes = Long.parseLong(properties.getProperty("nodes"));
- this.counts.edges = Long.parseLong(properties.getProperty("arcs"));
- this.ratios.compression = Double.parseDouble(properties.getProperty("compratio"));
- this.ratios.bitsPerNode = Double.parseDouble(properties.getProperty("bitspernode"));
- this.ratios.bitsPerEdge = Double.parseDouble(properties.getProperty("bitsperlink"));
- this.ratios.avgLocality = Double.parseDouble(properties.getProperty("avglocality"));
- this.indegree.min = Long.parseLong(properties.getProperty("minindegree"));
- this.indegree.max = Long.parseLong(properties.getProperty("maxindegree"));
- this.indegree.avg = Double.parseDouble(properties.getProperty("avgindegree"));
- this.outdegree.min = Long.parseLong(properties.getProperty("minoutdegree"));
- this.outdegree.max = Long.parseLong(properties.getProperty("maxoutdegree"));
- this.outdegree.avg = Double.parseDouble(properties.getProperty("avgoutdegree"));
- }
-
- public static class Counts {
- public long nodes;
- public long edges;
- }
-
- public static class Ratios {
- public double compression;
- public double bitsPerNode;
- public double bitsPerEdge;
- public double avgLocality;
- }
-
- public static class Degree {
- public long min;
- public long max;
- public double avg;
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/Subgraph.java b/java/src/main/java/org/softwareheritage/graph/Subgraph.java
--- a/java/src/main/java/org/softwareheritage/graph/Subgraph.java
+++ b/java/src/main/java/org/softwareheritage/graph/Subgraph.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2020 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph;
import it.unimi.dsi.big.webgraph.ImmutableGraph;
@@ -216,9 +223,9 @@
*
* @param nodeId node specified as a long id
* @return corresponding node type
- * @see Node.Type
+ * @see SwhType
*/
- public Node.Type getNodeType(long nodeId) {
+ public SwhType getNodeType(long nodeId) {
return underlyingGraph.getNodeType(nodeId);
}
}
diff --git a/java/src/main/java/org/softwareheritage/graph/SwhBidirectionalGraph.java b/java/src/main/java/org/softwareheritage/graph/SwhBidirectionalGraph.java
--- a/java/src/main/java/org/softwareheritage/graph/SwhBidirectionalGraph.java
+++ b/java/src/main/java/org/softwareheritage/graph/SwhBidirectionalGraph.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2021-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph;
import it.unimi.dsi.big.webgraph.labelling.ArcLabelledNodeIterator;
@@ -64,8 +71,8 @@
private SwhBidirectionalGraph(BidirectionalImmutableGraph graph, SwhGraphProperties properties) {
super(graph.forward, graph.backward);
- this.forwardGraph = (SwhUnidirectionalGraph) graph.forward;
- this.backwardGraph = (SwhUnidirectionalGraph) graph.backward;
+ this.forwardGraph = new SwhUnidirectionalGraph(graph.forward, properties);
+ this.backwardGraph = new SwhUnidirectionalGraph(graph.backward, properties);
this.properties = properties;
}
@@ -132,7 +139,7 @@
@Override
public SwhBidirectionalGraph copy() {
- return new SwhBidirectionalGraph(forwardGraph, backwardGraph, this.properties);
+ return new SwhBidirectionalGraph(forwardGraph.copy(), backwardGraph.copy(), this.properties);
}
@Override
diff --git a/java/src/main/java/org/softwareheritage/graph/SwhGraph.java b/java/src/main/java/org/softwareheritage/graph/SwhGraph.java
--- a/java/src/main/java/org/softwareheritage/graph/SwhGraph.java
+++ b/java/src/main/java/org/softwareheritage/graph/SwhGraph.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2021-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph;
import java.io.IOException;
@@ -38,7 +45,7 @@
}
/** @see SwhGraphProperties#getNodeType(long) */
- default Node.Type getNodeType(long nodeId) {
+ default SwhType getNodeType(long nodeId) {
return getProperties().getNodeType(nodeId);
}
@@ -113,12 +120,12 @@
}
/** @see SwhGraphProperties#getMessage(long) */
- default byte[] getMessage(long nodeId) throws IOException {
+ default byte[] getMessage(long nodeId) {
return getProperties().getMessage(nodeId);
}
/** @see SwhGraphProperties#getUrl(long) */
- default String getUrl(long nodeId) throws IOException {
+ default String getUrl(long nodeId) {
return getProperties().getUrl(nodeId);
}
@@ -128,7 +135,7 @@
}
/** @see SwhGraphProperties#getTagName(long) */
- default byte[] getTagName(long nodeId) throws IOException {
+ default byte[] getTagName(long nodeId) {
return getProperties().getTagName(nodeId);
}
diff --git a/java/src/main/java/org/softwareheritage/graph/SwhGraphProperties.java b/java/src/main/java/org/softwareheritage/graph/SwhGraphProperties.java
--- a/java/src/main/java/org/softwareheritage/graph/SwhGraphProperties.java
+++ b/java/src/main/java/org/softwareheritage/graph/SwhGraphProperties.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2021-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph;
import it.unimi.dsi.big.util.MappedFrontCodedStringBigList;
@@ -69,7 +76,6 @@
* Cleans up resources after use.
*/
public void close() throws IOException {
- nodeIdMap.close();
edgeLabelNames.close();
}
@@ -105,9 +111,9 @@
*
* @param nodeId node specified as a long id
* @return corresponding node type
- * @see Node.Type
+ * @see SwhType
*/
- public Node.Type getNodeType(long nodeId) {
+ public SwhType getNodeType(long nodeId) {
return nodeTypesMap.getType(nodeId);
}
@@ -267,7 +273,7 @@
}
/** Get the message of the given revision or release node */
- public byte[] getMessage(long nodeId) throws IOException {
+ public byte[] getMessage(long nodeId) {
if (messageBuffer == null || messageOffsets == null) {
throw new IllegalStateException("Messages not loaded");
}
@@ -279,7 +285,7 @@
}
/** Get the URL of the given origin node */
- public String getUrl(long nodeId) throws IOException {
+ public String getUrl(long nodeId) {
byte[] url = getMessage(nodeId);
return (url != null) ? new String(url) : null;
}
@@ -291,7 +297,7 @@
}
/** Get the name of the given release node */
- public byte[] getTagName(long nodeId) throws IOException {
+ public byte[] getTagName(long nodeId) {
if (tagNameBuffer == null || tagNameOffsets == null) {
throw new IllegalStateException("Tag names not loaded");
}
diff --git a/java/src/main/java/org/softwareheritage/graph/SwhPath.java b/java/src/main/java/org/softwareheritage/graph/SwhPath.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/SwhPath.java
+++ /dev/null
@@ -1,122 +0,0 @@
-package org.softwareheritage.graph;
-
-import com.fasterxml.jackson.annotation.JsonValue;
-
-import java.util.ArrayList;
-
-/**
- * Wrapper class to store a list of {@link SWHID}.
- *
- * @author The Software Heritage developers
- * @see SWHID
- */
-
-public class SwhPath {
- /** Internal list of {@link SWHID} */
- ArrayList path;
-
- /**
- * Constructor.
- */
- public SwhPath() {
- this.path = new ArrayList<>();
- }
-
- /**
- * Constructor.
- *
- * @param swhids variable number of string SWHIDs to initialize this path with
- */
- public SwhPath(String... swhids) {
- this();
- for (String swhid : swhids) {
- add(new SWHID(swhid));
- }
- }
-
- /**
- * Constructor.
- *
- * @param swhids variable number of {@link SWHID} to initialize this path with
- * @see SWHID
- */
- public SwhPath(SWHID... swhids) {
- this();
- for (SWHID swhid : swhids) {
- add(swhid);
- }
- }
-
- /**
- * Returns this path as a list of {@link SWHID}.
- *
- * @return list of {@link SWHID} constituting the path
- * @see SWHID
- */
- @JsonValue
- public ArrayList getPath() {
- return path;
- }
-
- /**
- * Adds a {@link SWHID} to this path.
- *
- * @param swhid {@link SWHID} to add to this path
- * @see SWHID
- */
- public void add(SWHID swhid) {
- path.add(swhid);
- }
-
- /**
- * Returns the {@link SWHID} at the specified position in this path.
- *
- * @param index position of the {@link SWHID} to return
- * @return {@link SWHID} at the specified position
- * @see SWHID
- */
- 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++) {
- 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 (SWHID swhid : path) {
- str.append(swhid).append("/");
- }
- return str.toString();
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/SwhType.java b/java/src/main/java/org/softwareheritage/graph/SwhType.java
new file mode 100644
--- /dev/null
+++ b/java/src/main/java/org/softwareheritage/graph/SwhType.java
@@ -0,0 +1,140 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
+package org.softwareheritage.graph;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+/**
+ * Software Heritage graph node types, as described in the
+ * data model.
+ */
+public enum SwhType {
+ /** Content node */
+ CNT,
+ /** Directory node */
+ DIR,
+ /** Origin node */
+ ORI,
+ /** Release node */
+ REL,
+ /** Revision node */
+ REV,
+ /** Snapshot node */
+ SNP;
+
+ /**
+ * Converts integer to corresponding SWH node type.
+ *
+ * @param intType node type represented as an integer
+ * @return the corresponding {@link SwhType} value
+ * @see SwhType
+ */
+ public static SwhType fromInt(int intType) {
+ switch (intType) {
+ case 0:
+ return CNT;
+ case 1:
+ return DIR;
+ case 2:
+ return ORI;
+ case 3:
+ return REL;
+ case 4:
+ return REV;
+ case 5:
+ return SNP;
+ }
+ return null;
+ }
+
+ /**
+ * Converts node types to the corresponding int value
+ *
+ * @param type node type as an enum
+ * @return the corresponding int value
+ */
+ public static int toInt(SwhType type) {
+ switch (type) {
+ case CNT:
+ return 0;
+ case DIR:
+ return 1;
+ case ORI:
+ return 2;
+ case REL:
+ return 3;
+ case REV:
+ return 4;
+ case SNP:
+ return 5;
+ }
+ throw new IllegalArgumentException("Unknown node type: " + type);
+ }
+
+ /**
+ * Converts string to corresponding SWH node type.
+ *
+ * @param strType node type represented as a string
+ * @return the corresponding {@link SwhType} value
+ * @see SwhType
+ */
+ public static SwhType fromStr(String strType) {
+ if (!strType.matches("cnt|dir|ori|rel|rev|snp")) {
+ throw new IllegalArgumentException("Unknown node type: " + strType);
+ }
+ return SwhType.valueOf(strType.toUpperCase());
+ }
+
+ /**
+ * Converts byte array name to the int code of the corresponding SWH node type. Used for
+ * performance-critical deserialization.
+ *
+ * @param name node type represented as a byte array (e.g. b"cnt")
+ * @return the ordinal value of the corresponding {@link SwhType}
+ * @see SwhType
+ */
+ public static int byteNameToInt(byte[] name) {
+ if (Arrays.equals(name, "cnt".getBytes())) {
+ return 0;
+ } else if (Arrays.equals(name, "dir".getBytes())) {
+ return 1;
+ } else if (Arrays.equals(name, "ori".getBytes())) {
+ return 2;
+ } else if (Arrays.equals(name, "rel".getBytes())) {
+ return 3;
+ } else if (Arrays.equals(name, "rev".getBytes())) {
+ return 4;
+ } else if (Arrays.equals(name, "snp".getBytes())) {
+ return 5;
+ } else
+ return -1;
+ }
+
+ /**
+ * Parses SWH node type possible values from formatted string (see the
+ * API syntax).
+ *
+ * @param strFmtType node types represented as a formatted string
+ * @return a list containing the {@link SwhType} values
+ * @see SwhType
+ */
+ public static ArrayList parse(String strFmtType) {
+ ArrayList types = new ArrayList<>();
+
+ if (strFmtType.equals("*")) {
+ List nodeTypes = Arrays.asList(SwhType.values());
+ types.addAll(nodeTypes);
+ } else {
+ types.add(SwhType.fromStr(strFmtType));
+ }
+
+ return types;
+ }
+}
diff --git a/java/src/main/java/org/softwareheritage/graph/SwhUnidirectionalGraph.java b/java/src/main/java/org/softwareheritage/graph/SwhUnidirectionalGraph.java
--- a/java/src/main/java/org/softwareheritage/graph/SwhUnidirectionalGraph.java
+++ b/java/src/main/java/org/softwareheritage/graph/SwhUnidirectionalGraph.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2019-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph;
import it.unimi.dsi.big.webgraph.ImmutableGraph;
@@ -34,7 +41,7 @@
/** Property data of the graph (id/type mappings etc.) */
public SwhGraphProperties properties;
- protected SwhUnidirectionalGraph(ImmutableGraph graph, SwhGraphProperties properties) {
+ public SwhUnidirectionalGraph(ImmutableGraph graph, SwhGraphProperties properties) {
this.graph = graph;
this.properties = properties;
}
diff --git a/java/src/main/java/org/softwareheritage/graph/Traversal.java b/java/src/main/java/org/softwareheritage/graph/Traversal.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/Traversal.java
+++ /dev/null
@@ -1,614 +0,0 @@
-package org.softwareheritage.graph;
-
-import java.util.ArrayDeque;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.LinkedList;
-import java.util.Map;
-import java.util.Queue;
-import java.util.Random;
-import java.util.Stack;
-import java.util.function.Consumer;
-import java.util.function.LongConsumer;
-
-import org.softwareheritage.graph.server.Endpoint;
-
-import it.unimi.dsi.big.webgraph.LazyLongIterator;
-
-/**
- * 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 {@link SWHID}.
- *
- * @author The Software Heritage developers
- * @see Endpoint
- */
-
-public class Traversal {
- /** Graph used in the traversal */
- SwhBidirectionalGraph graph;
- /** Type filter on the returned nodes */
- AllowedNodes nodesFilter;
- /** Restrictions on which edges can be traversed */
- AllowedEdges edgesRestrictions;
-
- /** 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;
-
- /** The anti Dos limit of edges traversed while a visit */
- long maxEdges;
-
- /** 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(SwhBidirectionalGraph graph, String direction, String edgesFmt) {
- this(graph, direction, edgesFmt, 0);
- }
-
- public Traversal(SwhBidirectionalGraph graph, String direction, String edgesFmt, long maxEdges) {
- this(graph, direction, edgesFmt, maxEdges, "*");
- }
-
- public Traversal(SwhBidirectionalGraph graph, String direction, String edgesFmt, long maxEdges,
- String returnTypes) {
- 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.nodesFilter = new AllowedNodes(returnTypes);
- this.edgesRestrictions = new AllowedEdges(edgesFmt);
-
- this.visited = new HashSet<>();
- this.parentNode = new HashMap<>();
- this.nbEdgesAccessed = 0;
- this.maxEdges = maxEdges;
- 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();
- }
-
- /**
- * Returns lazy iterator of successors of a node while following a specific set of edge types.
- *
- * @param g input graph
- * @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 static LazyLongIterator filterSuccessors(SwhBidirectionalGraph g, long nodeId, AllowedEdges allowedEdges) {
- if (allowedEdges.restrictedTo == null) {
- // All edges are allowed, bypass edge check
- return g.successors(nodeId);
- } else {
- LazyLongIterator allSuccessors = g.successors(nodeId);
- return new LazyLongIterator() {
- @Override
- public long nextLong() {
- long neighbor;
- while ((neighbor = allSuccessors.nextLong()) != -1) {
- if (allowedEdges.isAllowed(g.getNodeType(nodeId), g.getNodeType(neighbor))) {
- return neighbor;
- }
- }
- return -1;
- }
-
- @Override
- public long skip(final long n) {
- long i;
- for (i = 0; i < n && nextLong() != -1; i++)
- ;
- return i;
- }
- };
- }
- }
-
- private LazyLongIterator filterSuccessors(long nodeId, AllowedEdges allowedEdges) {
- return filterSuccessors(graph, nodeId, allowedEdges);
- }
-
- /**
- * 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);
- if (this.maxEdges > 0) {
- if (nbEdgesAccessed >= this.maxEdges) {
- break;
- }
- }
- LazyLongIterator it = filterSuccessors(currentNodeId, edgesRestrictions);
- for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
- neighborsCnt++;
- if (!visited.contains(neighborNodeId)) {
- stack.push(neighborNodeId);
- visited.add(neighborNodeId);
- }
- }
-
- if (neighborsCnt == 0) {
- if (nodesFilter.isAllowed(graph.getNodeType(currentNodeId))) {
- 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);
- if (this.maxEdges > 0) {
- if (nbEdgesAccessed >= this.maxEdges) {
- return;
- }
- }
- LazyLongIterator it = filterSuccessors(srcNodeId, edgesRestrictions);
- for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
- if (nodesFilter.isAllowed(graph.getNodeType(neighborNodeId))) {
- 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) {
- if (nodesFilter.isAllowed(graph.getNodeType(currentNodeId))) {
- nodeCb.accept(currentNodeId);
- }
- }
- nbEdgesAccessed += graph.outdegree(currentNodeId);
- if (this.maxEdges > 0) {
- if (nbEdgesAccessed >= this.maxEdges) {
- break;
- }
- }
- LazyLongIterator it = filterSuccessors(currentNodeId, edgesRestrictions);
- for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
- if (edgeCb != null) {
- if (nodesFilter.isAllowed(graph.getNodeType(currentNodeId))) {
- 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);
- if (this.maxEdges > 0) {
- if (nbEdgesAccessed >= this.maxEdges) {
- currentPath.pop();
- return;
- }
- }
- LazyLongIterator it = filterSuccessors(currentNodeId, edgesRestrictions);
- 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 = filterSuccessors(curNodeId, edgesRestrictions);
- 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 = filterSuccessors(currentNodeId, edgesRestrictions);
- 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 = filterSuccessors(currentNodeId, edgesRestrictions);
- 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 = filterSuccessors(curNode, edgesRestrictions);
- 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 = filterSuccessors(curNode, edgesRestrictions);
- 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/AccessEdge.java b/java/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java
+++ /dev/null
@@ -1,45 +0,0 @@
-package org.softwareheritage.graph.benchmark;
-
-import com.martiansoftware.jsap.JSAPException;
-import it.unimi.dsi.big.webgraph.LazyLongIterator;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.benchmark.utils.Statistics;
-import org.softwareheritage.graph.benchmark.utils.Timing;
-
-import java.io.IOException;
-import java.util.ArrayList;
-
-/**
- * Benchmark to time edge access time.
- *
- * @author The Software Heritage developers
- */
-
-public class AccessEdge {
- /**
- * Main entrypoint.
- *
- * @param args command line arguments
- */
- public static void main(String[] args) throws IOException, JSAPException {
- Benchmark bench = new Benchmark();
- bench.parseCommandLineArgs(args);
-
- SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(bench.args.graphPath);
-
- long[] nodeIds = bench.args.random.generateNodeIds(graph, bench.args.nbNodes);
-
- ArrayList timings = new ArrayList<>();
- for (long nodeId : nodeIds) {
- long startTime = Timing.start();
- LazyLongIterator neighbors = graph.successors(nodeId);
- long firstNeighbor = neighbors.nextLong();
- double duration = Timing.stop(startTime);
- timings.add(duration);
- }
-
- System.out.println("Used " + bench.args.nbNodes + " random edges (results are in seconds):");
- Statistics stats = new Statistics(timings);
- stats.printAll();
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java b/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java
+++ /dev/null
@@ -1,107 +0,0 @@
-package org.softwareheritage.graph.benchmark;
-
-import com.google.common.primitives.Longs;
-import com.martiansoftware.jsap.*;
-import it.unimi.dsi.big.webgraph.ImmutableGraph;
-import it.unimi.dsi.big.webgraph.LazyLongIterator;
-import it.unimi.dsi.bits.LongArrayBitVector;
-import it.unimi.dsi.fastutil.Arrays;
-import it.unimi.dsi.io.ByteDiskQueue;
-import it.unimi.dsi.logging.ProgressLogger;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-
-import java.io.File;
-import java.io.IOException;
-
-public class BFS {
- private final static Logger LOGGER = LoggerFactory.getLogger(BFS.class);
- private final ImmutableGraph graph;
-
- public BFS(ImmutableGraph graph) {
- this.graph = graph;
- }
-
- private static JSAPResult parse_args(String[] args) {
- JSAPResult config = null;
- try {
- SimpleJSAP jsap = new SimpleJSAP(BFS.class.getName(), "",
- new Parameter[]{
- new FlaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'g',
- "graph", "Basename of the compressed graph"),
-
- new FlaggedOption("useTransposed", JSAP.BOOLEAN_PARSER, "false", JSAP.NOT_REQUIRED, 'T',
- "transposed", "Use transposed graph (default: false)"),});
-
- config = jsap.parse(args);
- if (jsap.messagePrinted()) {
- System.exit(1);
- }
- } catch (JSAPException e) {
- e.printStackTrace();
- }
- return config;
- }
-
- public static void main(String[] args) throws IOException {
- JSAPResult config = parse_args(args);
- String graphPath = config.getString("graphPath");
- boolean useTransposed = config.getBoolean("useTransposed");
-
- System.err.println("Loading graph " + graphPath + " ...");
- SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(graphPath);
- System.err.println("Graph loaded.");
-
- if (useTransposed)
- graph = graph.transpose();
-
- BFS bfs = new BFS(graph);
- bfs.bfsperm();
- }
-
- // Partly inlined from it.unimi.dsi.law.big.graph.BFS
- private void bfsperm() throws IOException {
- final long n = graph.numNodes();
- // Allow enough memory to behave like in-memory queue
- int bufferSize = (int) Math.min(Arrays.MAX_ARRAY_SIZE & ~0x7, 8L * n);
-
- // Use a disk based queue to store BFS frontier
- final File queueFile = File.createTempFile(BFS.class.getSimpleName(), "queue");
- final ByteDiskQueue queue = ByteDiskQueue.createNew(queueFile, bufferSize, true);
- final byte[] byteBuf = new byte[Long.BYTES];
- // WARNING: no 64-bit version of this data-structure, but it can support
- // indices up to 2^37
- final LongArrayBitVector visited = LongArrayBitVector.ofLength(n);
- final ProgressLogger pl = new ProgressLogger(LOGGER);
- pl.expectedUpdates = n;
- pl.itemsName = "nodes";
- pl.start("Starting breadth-first visit...");
-
- for (long i = 0; i < n; i++) {
- if (visited.getBoolean(i))
- continue;
- queue.enqueue(Longs.toByteArray(i));
- visited.set(i);
-
- while (!queue.isEmpty()) {
- queue.dequeue(byteBuf);
- final long currentNode = Longs.fromByteArray(byteBuf);
-
- final LazyLongIterator iterator = graph.successors(currentNode);
- long succ;
- while ((succ = iterator.nextLong()) != -1) {
- if (!visited.getBoolean(succ)) {
- visited.set(succ);
- queue.enqueue(Longs.toByteArray(succ));
- }
- }
-
- pl.update();
- }
- }
-
- pl.done();
- queue.close();
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java
+++ /dev/null
@@ -1,154 +0,0 @@
-package org.softwareheritage.graph.benchmark;
-
-import com.martiansoftware.jsap.*;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-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("SWHID").add("number of edges accessed").add("traversal 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, SwhBidirectionalGraph 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) {
- SWHID swhid = graph.getSWHID(nodeId);
-
- Endpoint.Output output = (dstFmt == null)
- ? operation.apply(new Endpoint.Input(swhid))
- : operation.apply(new Endpoint.Input(swhid, dstFmt, algorithm));
-
- StringJoiner csvLine = new StringJoiner(CSV_SEPARATOR);
- csvLine.add(useCaseName).add(swhid.toString()).add(Long.toString(output.meta.nbEdgesAccessed))
- .add(Double.toString(output.meta.timings.traversal))
- .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, SwhBidirectionalGraph 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/benchmark/Browsing.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Browsing.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/Browsing.java
+++ /dev/null
@@ -1,42 +0,0 @@
-package org.softwareheritage.graph.benchmark;
-
-import com.martiansoftware.jsap.JSAPException;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
-import org.softwareheritage.graph.server.Endpoint;
-
-import java.io.IOException;
-
-/**
- * Benchmark Software Heritage
- * browsing
- * use-cases scenarios.
- *
- * @author The Software Heritage developers
- */
-
-public class Browsing {
- /**
- * Main entrypoint.
- *
- * @param args command line arguments
- */
- public static void main(String[] args) throws IOException, JSAPException {
- Benchmark bench = new Benchmark();
- bench.parseCommandLineArgs(args);
-
- SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(bench.args.graphPath);
-
- long[] dirNodeIds = bench.args.random.generateNodeIdsOfType(graph, bench.args.nbNodes, Node.Type.DIR);
- long[] revNodeIds = bench.args.random.generateNodeIdsOfType(graph, bench.args.nbNodes, Node.Type.REV);
-
- Endpoint dirEndpoint = new Endpoint(graph, "forward", "dir:cnt,dir:dir");
- Endpoint revEndpoint = new Endpoint(graph, "forward", "rev:rev");
-
- System.out.println("Used " + bench.args.nbNodes + " random nodes (results are in seconds):");
- bench.createCSVLogFile();
- bench.timeEndpoint("ls", graph, dirNodeIds, dirEndpoint::neighbors);
- bench.timeEndpoint("ls -R", graph, dirNodeIds, dirEndpoint::visitPaths);
- bench.timeEndpoint("git log", graph, revNodeIds, revEndpoint::visitNodes);
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Provenance.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Provenance.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/Provenance.java
+++ /dev/null
@@ -1,45 +0,0 @@
-package org.softwareheritage.graph.benchmark;
-
-import com.martiansoftware.jsap.JSAPException;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.server.Endpoint;
-
-import java.io.IOException;
-
-/**
- * Benchmark Software Heritage
- * provenance
- * use-cases scenarios.
- *
- * @author The Software Heritage developers
- */
-
-public class Provenance {
- /**
- * Main entrypoint.
- *
- * @param args command line arguments
- */
- public static void main(String[] args) throws IOException, JSAPException {
- Benchmark bench = new Benchmark();
- bench.parseCommandLineArgs(args);
-
- SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(bench.args.graphPath);
-
- long[] nodeIds = bench.args.random.generateNodeIds(graph, bench.args.nbNodes);
-
- Endpoint commitProvenanceEndpoint = new Endpoint(graph, "backward", "dir:dir,cnt:dir,dir:rev");
- Endpoint originProvenanceEndpoint = new Endpoint(graph, "backward", "*");
-
- System.out.println("Used " + bench.args.nbNodes + " random nodes (results are in seconds):");
- bench.createCSVLogFile();
-
- bench.timeEndpoint("commit provenance (dfs)", graph, nodeIds, commitProvenanceEndpoint::walk, "rev", "dfs");
- bench.timeEndpoint("commit provenance (bfs)", graph, nodeIds, commitProvenanceEndpoint::walk, "rev", "bfs");
- bench.timeEndpoint("complete commit provenance", graph, nodeIds, commitProvenanceEndpoint::leaves);
-
- bench.timeEndpoint("origin provenance (dfs)", graph, nodeIds, originProvenanceEndpoint::walk, "ori", "dfs");
- bench.timeEndpoint("origin provenance (bfs)", graph, nodeIds, originProvenanceEndpoint::walk, "ori", "bfs");
- bench.timeEndpoint("complete origin provenance", graph, nodeIds, originProvenanceEndpoint::leaves);
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Vault.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Vault.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/Vault.java
+++ /dev/null
@@ -1,37 +0,0 @@
-package org.softwareheritage.graph.benchmark;
-
-import com.martiansoftware.jsap.JSAPException;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.server.Endpoint;
-
-import java.io.IOException;
-
-/**
- * Benchmark Software Heritage
- * vault use-case
- * scenario.
- *
- * @author The Software Heritage developers
- */
-
-public class Vault {
- /**
- * Main entrypoint.
- *
- * @param args command line arguments
- */
- public static void main(String[] args) throws IOException, JSAPException {
- Benchmark bench = new Benchmark();
- bench.parseCommandLineArgs(args);
-
- SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(bench.args.graphPath);
-
- long[] nodeIds = bench.args.random.generateNodeIds(graph, bench.args.nbNodes);
-
- Endpoint endpoint = new Endpoint(graph, "forward", "*");
-
- System.out.println("Used " + bench.args.nbNodes + " random nodes (results are in seconds):");
- bench.createCSVLogFile();
- bench.timeEndpoint("git bundle", graph, nodeIds, endpoint::visitNodes);
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Random.java b/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Random.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Random.java
+++ /dev/null
@@ -1,67 +0,0 @@
-package org.softwareheritage.graph.benchmark.utils;
-
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
-
-import java.util.PrimitiveIterator;
-
-/**
- * Random related utility class.
- *
- * @author The Software Heritage developers
- */
-
-public class Random {
- /** Internal pseudorandom generator */
- java.util.Random random;
-
- /**
- * Constructor.
- */
- public Random() {
- this.random = new java.util.Random();
- }
-
- /**
- * Constructor.
- *
- * @param seed random generator seed
- */
- public Random(long seed) {
- this.random = new java.util.Random(seed);
- }
-
- /**
- * Generates random node ids.
- *
- * @param graph graph used to pick node ids
- * @param nbNodes number of node ids to generate
- * @return an array of random node ids
- */
- public long[] generateNodeIds(SwhBidirectionalGraph graph, int nbNodes) {
- return random.longs(nbNodes, 0, graph.numNodes()).toArray();
- }
-
- /**
- * Generates random node ids with a specific type.
- *
- * @param graph graph used to pick node ids
- * @param nbNodes number of node ids to generate
- * @param expectedType specific node type to pick
- * @return an array of random node ids
- */
- public long[] generateNodeIdsOfType(SwhBidirectionalGraph graph, int nbNodes, Node.Type expectedType) {
- PrimitiveIterator.OfLong nodes = random.longs(0, graph.numNodes()).iterator();
- long[] nodeIds = new long[nbNodes];
-
- long nextId;
- for (int i = 0; i < nbNodes; i++) {
- do {
- nextId = nodes.nextLong();
- } while (graph.getNodeType(nextId) != expectedType);
- nodeIds[i] = nextId;
- }
-
- return nodeIds;
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Statistics.java b/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Statistics.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Statistics.java
+++ /dev/null
@@ -1,104 +0,0 @@
-package org.softwareheritage.graph.benchmark.utils;
-
-import java.util.ArrayList;
-import java.util.Collections;
-
-/**
- * Compute various statistics on a list of values.
- *
- * @author The Software Heritage developers
- */
-
-public class Statistics {
- /** Input values */
- ArrayList values;
-
- /**
- * Constructor.
- *
- * @param values input values
- */
- public Statistics(ArrayList values) {
- this.values = values;
- }
-
- /**
- * Returns the minimum value.
- *
- * @return minimum value
- */
- public double getMin() {
- double min = Double.POSITIVE_INFINITY;
- for (double v : values) {
- min = Math.min(min, v);
- }
- return min;
- }
-
- /**
- * Returns the maximum value.
- *
- * @return maximum value
- */
- public double getMax() {
- double max = Double.NEGATIVE_INFINITY;
- for (double v : values) {
- max = Math.max(max, v);
- }
- return max;
- }
-
- /**
- * Computes the average.
- *
- * @return average value
- */
- public double getAverage() {
- double sum = 0;
- for (double v : values) {
- sum += v;
- }
- return sum / (double) values.size();
- }
-
- /**
- * Returns the median value.
- *
- * @return median value
- */
- public double getMedian() {
- Collections.sort(values);
- int length = values.size();
- if (length % 2 == 0) {
- return (values.get(length / 2) + values.get(length / 2 - 1)) / 2;
- } else {
- return values.get(length / 2);
- }
- }
-
- /**
- * Computes the standard deviation.
- *
- * @return standard deviation value
- */
- public double getStandardDeviation() {
- double average = getAverage();
- double variance = 0;
- for (double v : values) {
- variance += (v - average) * (v - average);
- }
- variance /= (double) values.size();
- return Math.sqrt(variance);
- }
-
- /**
- * Computes and prints all statistical values.
- */
- public void printAll() {
- System.out.println("min value: " + getMin());
- System.out.println("max value: " + getMax());
- System.out.println("average: " + getAverage());
- System.out.println("median: " + getMedian());
- System.out.println("standard deviation: " + getStandardDeviation());
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Timing.java b/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Timing.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Timing.java
+++ /dev/null
@@ -1,30 +0,0 @@
-package org.softwareheritage.graph.benchmark.utils;
-
-/**
- * Time measurement utility class.
- *
- * @author The Software Heritage developers
- */
-
-public class Timing {
- /**
- * Returns measurement starting timestamp.
- *
- * @return timestamp used for time measurement
- */
- public static long start() {
- return System.nanoTime();
- }
-
- /**
- * Ends timing measurement and returns total duration in seconds.
- *
- * @param startTime measurement starting timestamp
- * @return time in seconds elapsed since starting point
- */
- public static double stop(long startTime) {
- long endTime = System.nanoTime();
- double duration = (double) (endTime - startTime) / 1_000_000_000;
- return duration;
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/compress/CSVEdgeDataset.java b/java/src/main/java/org/softwareheritage/graph/compress/CSVEdgeDataset.java
--- a/java/src/main/java/org/softwareheritage/graph/compress/CSVEdgeDataset.java
+++ b/java/src/main/java/org/softwareheritage/graph/compress/CSVEdgeDataset.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.compress;
import com.github.luben.zstd.ZstdInputStream;
diff --git a/java/src/main/java/org/softwareheritage/graph/compress/ComposePermutations.java b/java/src/main/java/org/softwareheritage/graph/compress/ComposePermutations.java
--- a/java/src/main/java/org/softwareheritage/graph/compress/ComposePermutations.java
+++ b/java/src/main/java/org/softwareheritage/graph/compress/ComposePermutations.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2021-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.compress;
import com.martiansoftware.jsap.*;
diff --git a/java/src/main/java/org/softwareheritage/graph/compress/ExtractNodes.java b/java/src/main/java/org/softwareheritage/graph/compress/ExtractNodes.java
--- a/java/src/main/java/org/softwareheritage/graph/compress/ExtractNodes.java
+++ b/java/src/main/java/org/softwareheritage/graph/compress/ExtractNodes.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.compress;
import com.github.luben.zstd.ZstdOutputStream;
@@ -5,7 +12,7 @@
import it.unimi.dsi.logging.ProgressLogger;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import org.softwareheritage.graph.Node;
+import org.softwareheritage.graph.SwhType;
import org.softwareheritage.graph.utils.Sort;
import java.io.*;
@@ -119,7 +126,7 @@
throws IOException, InterruptedException {
// Read the dataset and write the nodes and labels to the sorting processes
AtomicLong edgeCount = new AtomicLong(0);
- AtomicLongArray edgeCountByType = new AtomicLongArray(Node.Type.values().length * Node.Type.values().length);
+ AtomicLongArray edgeCountByType = new AtomicLongArray(SwhType.values().length * SwhType.values().length);
int numThreads = Runtime.getRuntime().availableProcessors();
ForkJoinPool forkJoinPool = new ForkJoinPool(numThreads);
@@ -177,10 +184,10 @@
// Extract type of src and dst from their SWHID: swh:1:XXX
byte[] srcTypeBytes = Arrays.copyOfRange(src, 6, 6 + 3);
byte[] dstTypeBytes = Arrays.copyOfRange(dst, 6, 6 + 3);
- int srcType = Node.Type.byteNameToInt(srcTypeBytes);
- int dstType = Node.Type.byteNameToInt(dstTypeBytes);
+ int srcType = SwhType.byteNameToInt(srcTypeBytes);
+ int dstType = SwhType.byteNameToInt(dstTypeBytes);
if (srcType != -1 && dstType != -1) {
- edgeCountByType.incrementAndGet(srcType * Node.Type.values().length + dstType);
+ edgeCountByType.incrementAndGet(srcType * SwhType.values().length + dstType);
} else {
System.err.println("Invalid edge type: " + new String(srcTypeBytes) + " -> "
+ new String(dstTypeBytes));
@@ -259,10 +266,10 @@
nodesOutputThread.join();
labelsOutputThread.join();
- long[][] edgeCountByTypeArray = new long[Node.Type.values().length][Node.Type.values().length];
+ long[][] edgeCountByTypeArray = new long[SwhType.values().length][SwhType.values().length];
for (int i = 0; i < edgeCountByTypeArray.length; i++) {
for (int j = 0; j < edgeCountByTypeArray[i].length; j++) {
- edgeCountByTypeArray[i][j] = edgeCountByType.get(i * Node.Type.values().length + j);
+ edgeCountByTypeArray[i][j] = edgeCountByType.get(i * SwhType.values().length + j);
}
}
@@ -289,9 +296,9 @@
PrintWriter nodeTypesCountWriter = new PrintWriter(basename + ".edges.stats.txt");
TreeMap edgeTypeCountsMap = new TreeMap<>();
- for (Node.Type src : Node.Type.values()) {
- for (Node.Type dst : Node.Type.values()) {
- long cnt = edgeTypeCounts[Node.Type.toInt(src)][Node.Type.toInt(dst)];
+ for (SwhType src : SwhType.values()) {
+ for (SwhType dst : SwhType.values()) {
+ long cnt = edgeTypeCounts[SwhType.toInt(src)][SwhType.toInt(dst)];
if (cnt > 0)
edgeTypeCountsMap.put(src.toString().toLowerCase() + ":" + dst.toString().toLowerCase(), cnt);
}
@@ -309,8 +316,8 @@
PrintWriter nodeTypesCountWriter = new PrintWriter(basename + ".nodes.stats.txt");
TreeMap nodeTypeCountsMap = new TreeMap<>();
- for (Node.Type v : Node.Type.values()) {
- nodeTypeCountsMap.put(v.toString().toLowerCase(), nodeTypeCounts[Node.Type.toInt(v)]);
+ for (SwhType v : SwhType.values()) {
+ nodeTypeCountsMap.put(v.toString().toLowerCase(), nodeTypeCounts[SwhType.toInt(v)]);
}
for (Map.Entry entry : nodeTypeCountsMap.entrySet()) {
nodeTypesCountWriter.println(entry.getKey() + " " + entry.getValue());
@@ -329,7 +336,7 @@
private final OutputStream nodesOutputStream;
private long nodeCount = 0;
- private final long[] nodeTypeCounts = new long[Node.Type.values().length];
+ private final long[] nodeTypeCounts = new long[SwhType.values().length];
NodesOutputThread(InputStream sortedNodesStream, OutputStream nodesOutputStream) {
this.sortedNodesStream = sortedNodesStream;
@@ -347,8 +354,8 @@
nodesOutputStream.write('\n');
nodeCount++;
try {
- Node.Type nodeType = Node.Type.fromStr(line.split(":")[2]);
- nodeTypeCounts[Node.Type.toInt(nodeType)]++;
+ SwhType nodeType = SwhType.fromStr(line.split(":")[2]);
+ nodeTypeCounts[SwhType.toInt(nodeType)]++;
} catch (ArrayIndexOutOfBoundsException e) {
System.err.println("Error parsing SWHID: " + line);
System.exit(1);
diff --git a/java/src/main/java/org/softwareheritage/graph/compress/ExtractPersons.java b/java/src/main/java/org/softwareheritage/graph/compress/ExtractPersons.java
--- a/java/src/main/java/org/softwareheritage/graph/compress/ExtractPersons.java
+++ b/java/src/main/java/org/softwareheritage/graph/compress/ExtractPersons.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.compress;
import com.github.luben.zstd.ZstdOutputStream;
diff --git a/java/src/main/java/org/softwareheritage/graph/compress/GraphDataset.java b/java/src/main/java/org/softwareheritage/graph/compress/GraphDataset.java
--- a/java/src/main/java/org/softwareheritage/graph/compress/GraphDataset.java
+++ b/java/src/main/java/org/softwareheritage/graph/compress/GraphDataset.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.compress;
import java.io.IOException;
diff --git a/java/src/main/java/org/softwareheritage/graph/compress/LabelMapBuilder.java b/java/src/main/java/org/softwareheritage/graph/compress/LabelMapBuilder.java
--- a/java/src/main/java/org/softwareheritage/graph/compress/LabelMapBuilder.java
+++ b/java/src/main/java/org/softwareheritage/graph/compress/LabelMapBuilder.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2020-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.compress;
import com.martiansoftware.jsap.*;
diff --git a/java/src/main/java/org/softwareheritage/graph/compress/NodeMapBuilder.java b/java/src/main/java/org/softwareheritage/graph/compress/NodeMapBuilder.java
--- a/java/src/main/java/org/softwareheritage/graph/compress/NodeMapBuilder.java
+++ b/java/src/main/java/org/softwareheritage/graph/compress/NodeMapBuilder.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2019-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.compress;
import com.github.luben.zstd.ZstdInputStream;
@@ -13,8 +20,8 @@
import it.unimi.dsi.logging.ProgressLogger;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import org.softwareheritage.graph.Node;
import org.softwareheritage.graph.SWHID;
+import org.softwareheritage.graph.SwhType;
import org.softwareheritage.graph.maps.NodeIdMap;
import org.softwareheritage.graph.maps.NodeTypesMap;
@@ -119,7 +126,7 @@
* Type map from WebGraph node ID to SWH type. Used at runtime by pure Java graph traversals to
* efficiently check edge restrictions.
*/
- final int nbBitsPerNodeType = (int) Math.ceil(Math.log(Node.Type.values().length) / Math.log(2));
+ final int nbBitsPerNodeType = (int) Math.ceil(Math.log(SwhType.values().length) / Math.log(2));
LongArrayBitVector nodeTypesBitVector = LongArrayBitVector.ofLength(nbBitsPerNodeType * nbIds);
LongBigList nodeTypesMap = nodeTypesBitVector.asLongBigList(nbBitsPerNodeType);
diff --git a/java/src/main/java/org/softwareheritage/graph/compress/ORCGraphDataset.java b/java/src/main/java/org/softwareheritage/graph/compress/ORCGraphDataset.java
--- a/java/src/main/java/org/softwareheritage/graph/compress/ORCGraphDataset.java
+++ b/java/src/main/java/org/softwareheritage/graph/compress/ORCGraphDataset.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.compress;
import com.github.luben.zstd.ZstdOutputStream;
diff --git a/java/src/main/java/org/softwareheritage/graph/compress/ScatteredArcsORCGraph.java b/java/src/main/java/org/softwareheritage/graph/compress/ScatteredArcsORCGraph.java
--- a/java/src/main/java/org/softwareheritage/graph/compress/ScatteredArcsORCGraph.java
+++ b/java/src/main/java/org/softwareheritage/graph/compress/ScatteredArcsORCGraph.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.compress;
import java.io.File;
diff --git a/java/src/main/java/org/softwareheritage/graph/compress/WriteNodeProperties.java b/java/src/main/java/org/softwareheritage/graph/compress/WriteNodeProperties.java
--- a/java/src/main/java/org/softwareheritage/graph/compress/WriteNodeProperties.java
+++ b/java/src/main/java/org/softwareheritage/graph/compress/WriteNodeProperties.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.compress;
import com.martiansoftware.jsap.*;
diff --git a/java/src/main/java/org/softwareheritage/graph/experiments/forks/FindCommonAncestor.java b/java/src/main/java/org/softwareheritage/graph/experiments/forks/FindCommonAncestor.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/experiments/forks/FindCommonAncestor.java
+++ /dev/null
@@ -1,62 +0,0 @@
-package org.softwareheritage.graph.experiments.forks;
-
-import com.martiansoftware.jsap.*;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Traversal;
-
-import java.io.IOException;
-import java.util.Scanner;
-
-public class FindCommonAncestor {
- private SwhBidirectionalGraph graph;
-
- private void load_graph(String graphBasename) throws IOException {
- System.err.println("Loading graph " + graphBasename + " ...");
- this.graph = SwhBidirectionalGraph.loadMapped(graphBasename);
- System.err.println("Graph loaded.");
- }
-
- private static JSAPResult parse_args(String[] args) {
- JSAPResult config = null;
- try {
- SimpleJSAP jsap = new SimpleJSAP(FindCommonAncestor.class.getName(), "",
- new Parameter[]{
- new FlaggedOption("edgesFmt", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'e',
- "edges", "Edges constraints"),
- new FlaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'g',
- "graph", "Basename of the compressed graph"),});
-
- config = jsap.parse(args);
- if (jsap.messagePrinted()) {
- System.exit(1);
- }
- } catch (JSAPException e) {
- e.printStackTrace();
- }
- return config;
- }
-
- public static void main(String[] args) {
- JSAPResult config = parse_args(args);
-
- String graphPath = config.getString("graphPath");
- String edgesFmt = config.getString("edgesFmt");
-
- FindCommonAncestor fca = new FindCommonAncestor();
- try {
- fca.load_graph(graphPath);
- } catch (IOException e) {
- System.out.println("Could not load graph: " + e);
- System.exit(2);
- }
-
- Scanner input = new Scanner(System.in);
- while (input.hasNextLong()) {
- long lhsNode = input.nextLong();
- long rhsNode = input.nextLong();
-
- Traversal t = new Traversal(fca.graph.symmetrize(), "forward", edgesFmt);
- System.out.println(t.findCommonDescendant(lhsNode, rhsNode));
- }
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/experiments/forks/FindPath.java b/java/src/main/java/org/softwareheritage/graph/experiments/forks/FindPath.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/experiments/forks/FindPath.java
+++ /dev/null
@@ -1,123 +0,0 @@
-package org.softwareheritage.graph.experiments.forks;
-
-import com.martiansoftware.jsap.*;
-import it.unimi.dsi.big.webgraph.LazyLongIterator;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
-
-import java.io.IOException;
-import java.util.*;
-
-public class FindPath {
- private SwhBidirectionalGraph graph;
- private Long emptySnapshot;
-
- private void load_graph(String graphBasename) throws IOException {
- System.err.println("Loading graph " + graphBasename + " ...");
- this.graph = SwhBidirectionalGraph.loadMapped(graphBasename).symmetrize();
- System.err.println("Graph loaded.");
- this.emptySnapshot = null;
- }
-
- private static JSAPResult parse_args(String[] args) {
- JSAPResult config = null;
- try {
- SimpleJSAP jsap = new SimpleJSAP(FindPath.class.getName(), "",
- new Parameter[]{new FlaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED,
- 'g', "graph", "Basename of the compressed graph"),});
-
- config = jsap.parse(args);
- if (jsap.messagePrinted()) {
- System.exit(1);
- }
- } catch (JSAPException e) {
- e.printStackTrace();
- }
- return config;
- }
-
- private boolean nodeIsEmptySnapshot(Long node) {
- if (this.emptySnapshot == null && this.graph.getNodeType(node) == Node.Type.SNP
- && this.graph.outdegree(node) == 0) {
- System.err.println("Found empty snapshot: " + node);
- this.emptySnapshot = node;
- }
- return node.equals(this.emptySnapshot);
- }
-
- private Boolean shouldVisit(Long node) {
- Node.Type nt = this.graph.getNodeType(node);
- if (nt != Node.Type.REV && nt != Node.Type.REL && nt != Node.Type.SNP && nt != Node.Type.ORI) {
- return false;
- }
- if (this.nodeIsEmptySnapshot(node))
- return false;
- return true;
- }
-
- private ArrayList findPath(Long src, Long dst) {
- HashSet visited = new HashSet<>();
- Queue queue = new ArrayDeque<>();
- Map parentNode = new HashMap<>();
-
- queue.add(src);
- visited.add(src);
-
- while (!queue.isEmpty()) {
- long currentNode = queue.poll();
-
- final LazyLongIterator iterator = graph.successors(currentNode);
- long succ;
- while ((succ = iterator.nextLong()) != -1) {
- if (!shouldVisit(succ) || visited.contains(succ))
- continue;
- visited.add(succ);
- queue.add(succ);
- parentNode.put(succ, currentNode);
-
- if (succ == dst) {
- ArrayList path = new ArrayList<>();
- long n = dst;
- while (n != src) {
- path.add(n);
- n = parentNode.get(n);
- }
- path.add(src);
- Collections.reverse(path);
- return path;
- }
- }
- }
- return null;
- }
-
- public static void main(String[] args) {
- JSAPResult config = parse_args(args);
-
- String graphPath = config.getString("graphPath");
-
- FindPath fpath = new FindPath();
- try {
- fpath.load_graph(graphPath);
- } catch (IOException e) {
- System.out.println("Could not load graph: " + e);
- System.exit(2);
- }
-
- Scanner input = new Scanner(System.in);
- while (input.hasNextLong()) {
- long lhsNode = input.nextLong();
- long rhsNode = input.nextLong();
-
- ArrayList path = fpath.findPath(lhsNode, rhsNode);
- if (path != null) {
- for (Long n : path) {
- System.out.format("%d ", n);
- }
- System.out.println();
- } else {
- System.out.println("null");
- }
- }
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/experiments/forks/ForkCC.java b/java/src/main/java/org/softwareheritage/graph/experiments/forks/ForkCC.java
--- a/java/src/main/java/org/softwareheritage/graph/experiments/forks/ForkCC.java
+++ b/java/src/main/java/org/softwareheritage/graph/experiments/forks/ForkCC.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2019 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.experiments.forks;
import com.google.common.primitives.Longs;
@@ -8,7 +15,7 @@
import it.unimi.dsi.io.ByteDiskQueue;
import it.unimi.dsi.logging.ProgressLogger;
import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
+import org.softwareheritage.graph.SwhType;
import java.io.File;
import java.io.FileNotFoundException;
@@ -81,7 +88,7 @@
}
private boolean nodeIsEmptySnapshot(Long node) {
- if (this.emptySnapshot == null && this.graph.getNodeType(node) == Node.Type.SNP
+ if (this.emptySnapshot == null && this.graph.getNodeType(node) == SwhType.SNP
&& this.graph.outdegree(node) == 0) {
System.err.println("Found empty snapshot: " + node);
this.emptySnapshot = node;
@@ -90,11 +97,11 @@
}
private Boolean shouldVisit(Long node) {
- Node.Type nt = this.graph.getNodeType(node);
- if (nt == Node.Type.CNT) {
+ SwhType nt = this.graph.getNodeType(node);
+ if (nt == SwhType.CNT) {
return false;
}
- if (nt == Node.Type.DIR && !includeRootDir)
+ if (nt == SwhType.DIR && !includeRootDir)
return false;
if (this.nodeIsEmptySnapshot(node))
return false;
@@ -122,7 +129,7 @@
ArrayList> components = new ArrayList<>();
for (long i = 0; i < n; i++) {
- if (!shouldVisit(i) || this.graph.getNodeType(i) == Node.Type.DIR)
+ if (!shouldVisit(i) || this.graph.getNodeType(i) == SwhType.DIR)
continue;
ArrayList component = new ArrayList<>();
@@ -133,8 +140,8 @@
while (!queue.isEmpty()) {
queue.dequeue(byteBuf);
final long currentNode = Longs.fromByteArray(byteBuf);
- Node.Type cur_nt = this.graph.getNodeType(currentNode);
- if (cur_nt == Node.Type.ORI && (this.whitelist == null || this.whitelist.getBoolean(currentNode))) {
+ SwhType cur_nt = this.graph.getNodeType(currentNode);
+ if (cur_nt == SwhType.ORI && (this.whitelist == null || this.whitelist.getBoolean(currentNode))) {
// TODO: add a check that the origin has >=1 non-empty snapshot
component.add(currentNode);
}
@@ -144,7 +151,7 @@
while ((succ = iterator.nextLong()) != -1) {
if (!shouldVisit(succ))
continue;
- if (this.graph.getNodeType(succ) == Node.Type.DIR && cur_nt != Node.Type.REV)
+ if (this.graph.getNodeType(succ) == SwhType.DIR && cur_nt != SwhType.REV)
continue;
visited.set(succ);
queue.enqueue(Longs.toByteArray(succ));
diff --git a/java/src/main/java/org/softwareheritage/graph/experiments/forks/ForkCliques.java b/java/src/main/java/org/softwareheritage/graph/experiments/forks/ForkCliques.java
--- a/java/src/main/java/org/softwareheritage/graph/experiments/forks/ForkCliques.java
+++ b/java/src/main/java/org/softwareheritage/graph/experiments/forks/ForkCliques.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2020 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.experiments.forks;
import ch.qos.logback.classic.Level;
@@ -9,7 +16,7 @@
import it.unimi.dsi.logging.ProgressLogger;
import org.slf4j.LoggerFactory;
import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
+import org.softwareheritage.graph.SwhType;
import java.io.File;
import java.io.FileNotFoundException;
@@ -65,10 +72,10 @@
long succ;
while ((succ = iterator.nextLong()) != -1) {
if (!seen.contains(succ)) {
- Node.Type nt = this.graph.getNodeType(succ);
- if (nt == Node.Type.DIR || nt == Node.Type.CNT)
+ SwhType nt = this.graph.getNodeType(succ);
+ if (nt == SwhType.DIR || nt == SwhType.CNT)
continue;
- if (nt == Node.Type.ORI && (this.whitelist == null || this.whitelist.getBoolean(succ))) {
+ if (nt == SwhType.ORI && (this.whitelist == null || this.whitelist.getBoolean(succ))) {
res.add(succ);
} else {
stack.push(succ);
@@ -83,13 +90,13 @@
}
private boolean isBaseRevision(Long node) {
- if (this.graph.getNodeType(node) != Node.Type.REV)
+ if (this.graph.getNodeType(node) != SwhType.REV)
return false;
final LazyLongIterator iterator = this.graph.successors(node);
long succ;
while ((succ = iterator.nextLong()) != -1) {
- if (this.graph.getNodeType(succ) == Node.Type.REV)
+ if (this.graph.getNodeType(succ) == SwhType.REV)
return false;
}
return true;
diff --git a/java/src/main/java/org/softwareheritage/graph/experiments/forks/ListEmptyOrigins.java b/java/src/main/java/org/softwareheritage/graph/experiments/forks/ListEmptyOrigins.java
--- a/java/src/main/java/org/softwareheritage/graph/experiments/forks/ListEmptyOrigins.java
+++ b/java/src/main/java/org/softwareheritage/graph/experiments/forks/ListEmptyOrigins.java
@@ -1,10 +1,17 @@
+/*
+ * Copyright (c) 2019 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.experiments.forks;
import com.martiansoftware.jsap.*;
import it.unimi.dsi.big.webgraph.ImmutableGraph;
import it.unimi.dsi.big.webgraph.LazyLongIterator;
import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
+import org.softwareheritage.graph.SwhType;
import java.io.IOException;
import java.util.ArrayList;
@@ -56,7 +63,7 @@
private boolean nodeIsEmptySnapshot(Long node) {
System.err.println(this.graph.getNodeType(node) + " " + this.graph.outdegree(node) + " " + node);
- if (this.emptySnapshot == null && this.graph.getNodeType(node) == Node.Type.SNP
+ if (this.emptySnapshot == null && this.graph.getNodeType(node) == SwhType.SNP
&& this.graph.outdegree(node) == 0) {
System.err.println("Found empty snapshot: " + node);
this.emptySnapshot = node;
@@ -68,8 +75,8 @@
final long n = graph.numNodes();
ArrayList bad = new ArrayList<>();
for (long i = 0; i < n; i++) {
- Node.Type nt = this.graph.getNodeType(i);
- if (nt != Node.Type.ORI)
+ SwhType nt = this.graph.getNodeType(i);
+ if (nt != SwhType.ORI)
continue;
final LazyLongIterator iterator = graph.successors(i);
diff --git a/java/src/main/java/org/softwareheritage/graph/experiments/multiplicationfactor/GenDistribution.java b/java/src/main/java/org/softwareheritage/graph/experiments/multiplicationfactor/GenDistribution.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/experiments/multiplicationfactor/GenDistribution.java
+++ /dev/null
@@ -1,130 +0,0 @@
-package org.softwareheritage.graph.experiments.multiplicationfactor;
-
-import com.martiansoftware.jsap.*;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
-import org.softwareheritage.graph.Traversal;
-import org.softwareheritage.graph.benchmark.utils.Timing;
-
-import java.io.IOException;
-import java.util.Scanner;
-import java.util.concurrent.ArrayBlockingQueue;
-import java.util.concurrent.ExecutorService;
-import java.util.concurrent.Executors;
-
-public class GenDistribution {
- private SwhBidirectionalGraph graph;
-
- private static JSAPResult parse_args(String[] args) {
- JSAPResult config = null;
- try {
- SimpleJSAP jsap = new SimpleJSAP(GenDistribution.class.getName(), "",
- new Parameter[]{
- new FlaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'g',
- "graph", "Basename of the compressed graph"),
- new FlaggedOption("srcType", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 's',
- "srctype", "Source node type"),
- new FlaggedOption("dstType", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'd',
- "dsttype", "Destination node type"),
- new FlaggedOption("edgesFmt", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'e',
- "edges", "Edges constraints"),
-
- new FlaggedOption("numThreads", JSAP.INTEGER_PARSER, "128", JSAP.NOT_REQUIRED, 't',
- "numthreads", "Number of threads"),});
-
- config = jsap.parse(args);
- if (jsap.messagePrinted()) {
- System.exit(1);
- }
- } catch (JSAPException e) {
- e.printStackTrace();
- }
- return config;
- }
-
- public static void main(String[] args) {
- JSAPResult config = parse_args(args);
-
- String graphPath = config.getString("graphPath");
- Node.Type srcType = Node.Type.fromStr(config.getString("srcType"));
- Node.Type dstType = Node.Type.fromStr(config.getString("dstType"));
- String edgesFmt = config.getString("edgesFmt");
- int numThreads = config.getInt("numThreads");
-
- GenDistribution tp = new GenDistribution();
- try {
- tp.load_graph(graphPath);
- } catch (IOException e) {
- System.out.println("Could not load graph: " + e);
- System.exit(2);
- }
-
- final long END_OF_QUEUE = -1L;
-
- ArrayBlockingQueue queue = new ArrayBlockingQueue<>(numThreads);
- ExecutorService service = Executors.newFixedThreadPool(numThreads + 1);
-
- service.submit(() -> {
- try {
- Scanner input = new Scanner(System.in);
- while (input.hasNextLong()) {
- long node = input.nextLong();
- if (tp.graph.getNodeType(node) == srcType) {
- queue.put(node);
- }
- }
- } catch (InterruptedException e) {
- e.printStackTrace();
- } finally {
- for (int i = 0; i < numThreads; ++i) {
- try {
- queue.put(END_OF_QUEUE);
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- }
- });
-
- for (int i = 0; i < numThreads; ++i) {
- service.submit(() -> {
- SwhBidirectionalGraph thread_graph = tp.graph.copy();
- long startTime;
- double totalTime;
-
- while (true) {
- Long node = null;
- try {
- node = queue.take();
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- if (node == null || node == END_OF_QUEUE) {
- return;
- }
-
- Traversal t = new Traversal(thread_graph, "backward", edgesFmt);
- int[] count = {0};
-
- startTime = Timing.start();
- t.visitNodesVisitor(node, (curnode) -> {
- if (tp.graph.getNodeType(curnode) == dstType) {
- count[0]++;
- }
- });
- totalTime = Timing.stop(startTime);
- System.out.format("%d %d %d %d %f\n", node, count[0], t.getNbNodesAccessed(),
- t.getNbEdgesAccessed(), totalTime);
- }
- });
- }
-
- service.shutdown();
- }
-
- private void load_graph(String graphBasename) throws IOException {
- System.err.println("Loading graph " + graphBasename + " ...");
- this.graph = SwhBidirectionalGraph.loadMapped(graphBasename);
- System.err.println("Graph loaded.");
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/experiments/topology/AveragePaths.java b/java/src/main/java/org/softwareheritage/graph/experiments/topology/AveragePaths.java
--- a/java/src/main/java/org/softwareheritage/graph/experiments/topology/AveragePaths.java
+++ b/java/src/main/java/org/softwareheritage/graph/experiments/topology/AveragePaths.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2020 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.experiments.topology;
import com.martiansoftware.jsap.*;
diff --git a/java/src/main/java/org/softwareheritage/graph/experiments/topology/ClusteringCoefficient.java b/java/src/main/java/org/softwareheritage/graph/experiments/topology/ClusteringCoefficient.java
--- a/java/src/main/java/org/softwareheritage/graph/experiments/topology/ClusteringCoefficient.java
+++ b/java/src/main/java/org/softwareheritage/graph/experiments/topology/ClusteringCoefficient.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2020 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.experiments.topology;
import com.martiansoftware.jsap.*;
@@ -9,7 +16,7 @@
import it.unimi.dsi.logging.ProgressLogger;
import it.unimi.dsi.util.XoRoShiRo128PlusRandom;
import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
+import org.softwareheritage.graph.SwhType;
import java.io.*;
import java.util.*;
@@ -132,7 +139,7 @@
if (d < 2) {
return;
}
- Node.Type nodeType = graph.getNodeType(node);
+ SwhType nodeType = graph.getNodeType(node);
HashSet neighborhood = new HashSet<>();
long succ;
@@ -148,26 +155,25 @@
long triangles_orisnp = 0;
for (Long neighbor : neighborhood) {
- Node.Type neighborNodeType = graph.getNodeType(neighbor);
+ SwhType neighborNodeType = graph.getNodeType(neighbor);
final LazyLongIterator it = graph.successors(neighbor);
while ((succ = it.nextLong()) != -1) {
if (neighborhood.contains(succ)) {
- Node.Type succNodeType = graph.getNodeType(succ);
+ SwhType succNodeType = graph.getNodeType(succ);
triangles_full++;
- if ((nodeType == Node.Type.DIR || nodeType == Node.Type.CNT)
- && (neighborNodeType == Node.Type.DIR || neighborNodeType == Node.Type.CNT)
- && (succNodeType == Node.Type.DIR || succNodeType == Node.Type.CNT)) {
+ if ((nodeType == SwhType.DIR || nodeType == SwhType.CNT)
+ && (neighborNodeType == SwhType.DIR || neighborNodeType == SwhType.CNT)
+ && (succNodeType == SwhType.DIR || succNodeType == SwhType.CNT)) {
triangles_dircnt++;
- } else if ((nodeType == Node.Type.REV || nodeType == Node.Type.REL)
- && (neighborNodeType == Node.Type.REV || neighborNodeType == Node.Type.REL)
- && (succNodeType == Node.Type.REV || succNodeType == Node.Type.REL)) {
+ } else if ((nodeType == SwhType.REV || nodeType == SwhType.REL)
+ && (neighborNodeType == SwhType.REV || neighborNodeType == SwhType.REL)
+ && (succNodeType == SwhType.REV || succNodeType == SwhType.REL)) {
triangles_revrel++;
- if (nodeType == Node.Type.REV && neighborNodeType == Node.Type.REV
- && succNodeType == Node.Type.REV)
+ if (nodeType == SwhType.REV && neighborNodeType == SwhType.REV && succNodeType == SwhType.REV)
triangles_rev++;
- } else if ((nodeType == Node.Type.ORI || nodeType == Node.Type.SNP)
- && (neighborNodeType == Node.Type.ORI || neighborNodeType == Node.Type.SNP)
- && (succNodeType == Node.Type.ORI || succNodeType == Node.Type.SNP)) {
+ } else if ((nodeType == SwhType.ORI || nodeType == SwhType.SNP)
+ && (neighborNodeType == SwhType.ORI || neighborNodeType == SwhType.SNP)
+ && (succNodeType == SwhType.ORI || succNodeType == SwhType.SNP)) {
triangles_orisnp++;
}
}
diff --git a/java/src/main/java/org/softwareheritage/graph/experiments/topology/ConnectedComponents.java b/java/src/main/java/org/softwareheritage/graph/experiments/topology/ConnectedComponents.java
--- a/java/src/main/java/org/softwareheritage/graph/experiments/topology/ConnectedComponents.java
+++ b/java/src/main/java/org/softwareheritage/graph/experiments/topology/ConnectedComponents.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2020 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.experiments.topology;
import com.google.common.primitives.Longs;
@@ -7,10 +14,7 @@
import it.unimi.dsi.fastutil.Arrays;
import it.unimi.dsi.io.ByteDiskQueue;
import it.unimi.dsi.logging.ProgressLogger;
-import org.softwareheritage.graph.AllowedNodes;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
-import org.softwareheritage.graph.Subgraph;
+import org.softwareheritage.graph.*;
import java.io.File;
import java.io.FileWriter;
@@ -94,7 +98,7 @@
final long currentNode = Longs.fromByteArray(byteBuf);
// component.add(currentNode);
- if (!byOrigin || graph.getNodeType(currentNode) == Node.Type.ORI)
+ if (!byOrigin || graph.getNodeType(currentNode) == SwhType.ORI)
componentNodes += 1;
final LazyLongIterator iterator = graph.successors(currentNode);
diff --git a/java/src/main/java/org/softwareheritage/graph/experiments/topology/InOutDegree.java b/java/src/main/java/org/softwareheritage/graph/experiments/topology/InOutDegree.java
--- a/java/src/main/java/org/softwareheritage/graph/experiments/topology/InOutDegree.java
+++ b/java/src/main/java/org/softwareheritage/graph/experiments/topology/InOutDegree.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2020 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.experiments.topology;
import java.io.File;
@@ -16,27 +23,27 @@
import it.unimi.dsi.logging.ProgressLogger;
import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
+import org.softwareheritage.graph.SwhType;
public class InOutDegree {
private InOutDegree() {
}
- private static final int NODE_ARRAY_SIZE = Node.Type.values().length + 1;
- private static final int TYPE_ALL = Node.Type.values().length;
- private static final int TYPE_CNT = Node.Type.toInt(Node.Type.CNT);
- private static final int TYPE_DIR = Node.Type.toInt(Node.Type.DIR);
- private static final int TYPE_REV = Node.Type.toInt(Node.Type.REV);
- private static final int TYPE_REL = Node.Type.toInt(Node.Type.REL);
- private static final int TYPE_SNP = Node.Type.toInt(Node.Type.SNP);
- private static final int TYPE_ORI = Node.Type.toInt(Node.Type.ORI);
+ private static final int NODE_ARRAY_SIZE = SwhType.values().length + 1;
+ private static final int TYPE_ALL = SwhType.values().length;
+ private static final int TYPE_CNT = SwhType.toInt(SwhType.CNT);
+ private static final int TYPE_DIR = SwhType.toInt(SwhType.DIR);
+ private static final int TYPE_REV = SwhType.toInt(SwhType.REV);
+ private static final int TYPE_REL = SwhType.toInt(SwhType.REL);
+ private static final int TYPE_SNP = SwhType.toInt(SwhType.SNP);
+ private static final int TYPE_ORI = SwhType.toInt(SwhType.ORI);
public static long[] outdegreeTypes(final SwhBidirectionalGraph graph, long node) {
long[] out = new long[NODE_ARRAY_SIZE];
var successors = graph.successors(node);
long neighbor;
while ((neighbor = successors.nextLong()) != -1) {
- out[Node.Type.toInt(graph.getNodeType(neighbor))]++;
+ out[SwhType.toInt(graph.getNodeType(neighbor))]++;
out[TYPE_ALL]++;
}
return out;
diff --git a/java/src/main/java/org/softwareheritage/graph/experiments/topology/SubdatasetSizeFunction.java b/java/src/main/java/org/softwareheritage/graph/experiments/topology/SubdatasetSizeFunction.java
--- a/java/src/main/java/org/softwareheritage/graph/experiments/topology/SubdatasetSizeFunction.java
+++ b/java/src/main/java/org/softwareheritage/graph/experiments/topology/SubdatasetSizeFunction.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2020 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.experiments.topology;
import com.google.common.primitives.Longs;
@@ -12,7 +19,7 @@
import it.unimi.dsi.logging.ProgressLogger;
import it.unimi.dsi.util.XoRoShiRo128PlusRandom;
import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
+import org.softwareheritage.graph.SwhType;
import org.softwareheritage.graph.experiments.forks.ForkCC;
import java.io.*;
@@ -45,7 +52,7 @@
pl.start("Running traversal starting from origins...");
for (long j = 0; j < n; ++j) {
long i = BigArrays.get(randomPerm, j);
- if (visited.getBoolean(i) || graph.getNodeType(i) != Node.Type.ORI) {
+ if (visited.getBoolean(i) || graph.getNodeType(i) != SwhType.ORI) {
continue;
}
visitedOrigins++;
@@ -57,7 +64,7 @@
final long currentNode = Longs.fromByteArray(byteBuf);
visitedNodes++;
- if (graph.getNodeType(currentNode) == Node.Type.CNT)
+ if (graph.getNodeType(currentNode) == SwhType.CNT)
visitedContents++;
final LazyLongIterator iterator = graph.successors(currentNode);
diff --git a/java/src/main/java/org/softwareheritage/graph/labels/DirEntry.java b/java/src/main/java/org/softwareheritage/graph/labels/DirEntry.java
--- a/java/src/main/java/org/softwareheritage/graph/labels/DirEntry.java
+++ b/java/src/main/java/org/softwareheritage/graph/labels/DirEntry.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2021-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.labels;
/**
diff --git a/java/src/main/java/org/softwareheritage/graph/labels/SwhLabel.java b/java/src/main/java/org/softwareheritage/graph/labels/SwhLabel.java
--- a/java/src/main/java/org/softwareheritage/graph/labels/SwhLabel.java
+++ b/java/src/main/java/org/softwareheritage/graph/labels/SwhLabel.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2021-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.labels;
import it.unimi.dsi.big.webgraph.labelling.AbstractLabel;
diff --git a/java/src/main/java/org/softwareheritage/graph/maps/MapFile.java b/java/src/main/java/org/softwareheritage/graph/maps/MapFile.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/maps/MapFile.java
+++ /dev/null
@@ -1,66 +0,0 @@
-package org.softwareheritage.graph.maps;
-
-import it.unimi.dsi.io.ByteBufferInputStream;
-
-import java.io.File;
-import java.io.IOException;
-import java.io.RandomAccessFile;
-import java.nio.channels.FileChannel;
-
-/**
- * Wrapper class around very big mmap()-ed file.
- *
- * Java has a limit for mmap()-ed files because of unsupported 64-bit indexing. The
- * dsiutils ByteBufferInputStream is used to overcome
- * this Java limit.
- *
- * @author The Software Heritage developers
- */
-
-public class MapFile {
- /** Memory-mapped file buffer */
- ByteBufferInputStream bufferMap;
- /** Fixed line length of the mmap()-ed file */
- int lineLength;
-
- /**
- * Constructor.
- *
- * @param path file path to mmap()
- * @param lineLength fixed length of a line in the file
- */
- public MapFile(String path, int lineLength) throws IOException {
- this.bufferMap = null;
- this.lineLength = lineLength;
-
- try (RandomAccessFile mapFile = new RandomAccessFile(new File(path), "r")) {
- FileChannel fileChannel = mapFile.getChannel();
- bufferMap = ByteBufferInputStream.map(fileChannel, FileChannel.MapMode.READ_ONLY);
- }
- }
-
- /**
- * Returns a specific line in the file.
- *
- * @param lineIndex line number in the file
- * @return the line at the specified position
- */
- public byte[] readAtLine(long lineIndex) {
- byte[] buffer = new byte[lineLength];
- long position = lineIndex * (long) lineLength;
- bufferMap.position(position);
- bufferMap.read(buffer, 0, lineLength);
- return buffer;
- }
-
- public long size() {
- return bufferMap.length() / (long) lineLength;
- }
-
- /**
- * Closes the mmap()-ed file.
- */
- public void close() throws IOException {
- bufferMap.close();
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java b/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java
--- a/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java
+++ b/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java
@@ -1,17 +1,25 @@
+/*
+ * Copyright (c) 2019-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.maps;
import it.unimi.dsi.fastutil.Size64;
+import it.unimi.dsi.fastutil.bytes.ByteBigList;
+import it.unimi.dsi.fastutil.bytes.ByteMappedBigList;
import it.unimi.dsi.fastutil.io.BinIO;
import it.unimi.dsi.fastutil.longs.LongBigList;
+import it.unimi.dsi.fastutil.longs.LongMappedBigList;
import it.unimi.dsi.fastutil.objects.Object2LongFunction;
-import it.unimi.dsi.util.ByteBufferLongBigList;
import org.softwareheritage.graph.SWHID;
import org.softwareheritage.graph.compress.NodeMapBuilder;
import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
-import java.nio.channels.FileChannel;
import java.nio.charset.StandardCharsets;
/**
@@ -38,7 +46,7 @@
String graphPath;
/** mmap()-ed NODE_TO_SWHID file */
- MapFile nodeToSwhMap;
+ ByteBigList nodeToSwhMap;
/** Minimal perfect hash (MPH) function SWHID -> initial order */
Object2LongFunction mph;
@@ -54,14 +62,14 @@
this.graphPath = graphPath;
// node -> SWHID
- this.nodeToSwhMap = new MapFile(graphPath + NODE_TO_SWHID, SWHID_BIN_SIZE);
+ try (RandomAccessFile raf = new RandomAccessFile(graphPath + NODE_TO_SWHID, "r")) {
+ this.nodeToSwhMap = ByteMappedBigList.map(raf.getChannel());
+ }
// SWHID -> node
this.mph = loadMph(graphPath + ".mph");
-
try (RandomAccessFile mapFile = new RandomAccessFile(new File(graphPath + ".order"), "r")) {
- FileChannel fileChannel = mapFile.getChannel();
- this.orderMap = ByteBufferLongBigList.map(fileChannel);
+ this.orderMap = LongMappedBigList.map(mapFile.getChannel());
}
}
@@ -95,6 +103,7 @@
return legacyFunction.getLong(new String(bi, StandardCharsets.UTF_8));
}
+ @SuppressWarnings("deprecation")
@Override
public int size() {
return legacyFunction.size();
@@ -169,23 +178,19 @@
* 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 >= nodeToSwhMap.size()) {
- throw new IllegalArgumentException("Node id " + nodeId + " should be between 0 and " + nodeToSwhMap.size());
+ if (nodeId < 0 || nodeId >= nodeToSwhMap.size64()) {
+ throw new IllegalArgumentException(
+ "Node id " + nodeId + " should be between 0 and " + nodeToSwhMap.size64());
}
- return SWHID.fromBytes(nodeToSwhMap.readAtLine(nodeId));
- }
-
- /**
- * Closes the mapping files.
- */
- public void close() throws IOException {
- nodeToSwhMap.close();
+ byte[] swhid = new byte[SWHID_BIN_SIZE];
+ nodeToSwhMap.getElements(nodeId * SWHID_BIN_SIZE, swhid, 0, SWHID_BIN_SIZE);
+ return SWHID.fromBytes(swhid);
}
/** Return the number of nodes in the map. */
@Override
public long size64() {
- return nodeToSwhMap.size();
+ return nodeToSwhMap.size64();
}
}
diff --git a/java/src/main/java/org/softwareheritage/graph/maps/NodeTypesMap.java b/java/src/main/java/org/softwareheritage/graph/maps/NodeTypesMap.java
--- a/java/src/main/java/org/softwareheritage/graph/maps/NodeTypesMap.java
+++ b/java/src/main/java/org/softwareheritage/graph/maps/NodeTypesMap.java
@@ -1,8 +1,15 @@
+/*
+ * Copyright (c) 2019-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.maps;
import it.unimi.dsi.fastutil.io.BinIO;
import it.unimi.dsi.fastutil.longs.LongBigList;
-import org.softwareheritage.graph.Node;
+import org.softwareheritage.graph.SwhType;
import java.io.IOException;
@@ -14,7 +21,7 @@
* {@link org.softwareheritage.graph.compress.NodeMapBuilder} class, then it is loaded in-memory
* here using fastutil LongBigList. To be
* space-efficient, the mapping is stored as a bitmap using minimum number of bits per
- * {@link Node.Type}.
+ * {@link SwhType}.
*
* @author The Software Heritage developers
*/
@@ -45,11 +52,11 @@
* Returns node type from a node long id.
*
* @param nodeId node as a long id
- * @return corresponding {@link Node.Type} value
- * @see org.softwareheritage.graph.Node.Type
+ * @return corresponding {@link SwhType} value
+ * @see SwhType
*/
- public Node.Type getType(long nodeId) {
+ public SwhType getType(long nodeId) {
long type = nodeTypesMap.getLong(nodeId);
- return Node.Type.fromInt((int) type);
+ return SwhType.fromInt((int) type);
}
}
diff --git a/java/src/main/java/org/softwareheritage/graph/rpc/GraphServer.java b/java/src/main/java/org/softwareheritage/graph/rpc/GraphServer.java
new file mode 100644
--- /dev/null
+++ b/java/src/main/java/org/softwareheritage/graph/rpc/GraphServer.java
@@ -0,0 +1,300 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
+package org.softwareheritage.graph.rpc;
+
+import com.google.protobuf.FieldMask;
+import com.martiansoftware.jsap.*;
+import io.grpc.Server;
+import io.grpc.Status;
+import io.grpc.netty.shaded.io.grpc.netty.NettyServerBuilder;
+import io.grpc.netty.shaded.io.netty.channel.ChannelOption;
+import io.grpc.stub.StreamObserver;
+import io.grpc.protobuf.services.ProtoReflectionService;
+import it.unimi.dsi.logging.ProgressLogger;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+import org.softwareheritage.graph.SWHID;
+import org.softwareheritage.graph.SwhBidirectionalGraph;
+import org.softwareheritage.graph.compress.LabelMapBuilder;
+
+import java.io.FileInputStream;
+import java.io.IOException;
+import java.util.Properties;
+import java.util.concurrent.Executors;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicLong;
+
+/**
+ * Server that manages startup/shutdown of a {@code Greeter} server.
+ */
+public class GraphServer {
+ private final static Logger logger = LoggerFactory.getLogger(GraphServer.class);
+
+ private final SwhBidirectionalGraph graph;
+ private final int port;
+ private final int threads;
+ private Server server;
+
+ /**
+ * @param graphBasename the basename of the SWH graph to load
+ * @param port the port on which the GRPC server will listen
+ * @param threads the number of threads to use in the server threadpool
+ */
+ public GraphServer(String graphBasename, int port, int threads) throws IOException {
+ this.graph = loadGraph(graphBasename);
+ this.port = port;
+ this.threads = threads;
+ }
+
+ /** Load a graph and all its properties. */
+ public static SwhBidirectionalGraph loadGraph(String basename) throws IOException {
+ SwhBidirectionalGraph g = SwhBidirectionalGraph.loadLabelledMapped(basename, new ProgressLogger(logger));
+ g.loadContentLength();
+ g.loadContentIsSkipped();
+ g.loadPersonIds();
+ g.loadAuthorTimestamps();
+ g.loadCommitterTimestamps();
+ g.loadMessages();
+ g.loadTagNames();
+ g.loadLabelNames();
+ return g;
+ }
+
+ /** Start the RPC server. */
+ private void start() throws IOException {
+ server = NettyServerBuilder.forPort(port).withChildOption(ChannelOption.SO_REUSEADDR, true)
+ .executor(Executors.newFixedThreadPool(threads)).addService(new TraversalService(graph))
+ .addService(ProtoReflectionService.newInstance()).build().start();
+ logger.info("Server started, listening on " + port);
+ Runtime.getRuntime().addShutdownHook(new Thread(() -> {
+ try {
+ GraphServer.this.stop();
+ } catch (InterruptedException e) {
+ e.printStackTrace(System.err);
+ }
+ }));
+ }
+
+ private void stop() throws InterruptedException {
+ if (server != null) {
+ server.shutdown().awaitTermination(30, TimeUnit.SECONDS);
+ }
+ }
+
+ /**
+ * Await termination on the main thread since the grpc library uses daemon threads.
+ */
+ private void blockUntilShutdown() throws InterruptedException {
+ if (server != null) {
+ server.awaitTermination();
+ }
+ }
+
+ private static JSAPResult parseArgs(String[] args) {
+ JSAPResult config = null;
+ try {
+ SimpleJSAP jsap = new SimpleJSAP(LabelMapBuilder.class.getName(), "",
+ new Parameter[]{
+ new FlaggedOption("port", JSAP.INTEGER_PARSER, "50091", JSAP.NOT_REQUIRED, 'p', "port",
+ "The port on which the server should listen."),
+ new FlaggedOption("threads", JSAP.INTEGER_PARSER, "0", JSAP.NOT_REQUIRED, 't', "threads",
+ "The number of concurrent threads. 0 = number of cores."),
+ new UnflaggedOption("graphBasename", JSAP.STRING_PARSER, JSAP.REQUIRED,
+ "Basename of the output graph")});
+
+ config = jsap.parse(args);
+ if (jsap.messagePrinted()) {
+ System.exit(1);
+ }
+ } catch (JSAPException e) {
+ e.printStackTrace();
+ }
+ return config;
+ }
+
+ /** Main launches the server from the command line. */
+ public static void main(String[] args) throws IOException, InterruptedException {
+ JSAPResult config = parseArgs(args);
+ String graphBasename = config.getString("graphBasename");
+ int port = config.getInt("port");
+ int threads = config.getInt("threads");
+ if (threads == 0) {
+ threads = Runtime.getRuntime().availableProcessors();
+ }
+
+ final GraphServer server = new GraphServer(graphBasename, port, threads);
+ server.start();
+ server.blockUntilShutdown();
+ }
+
+ /** Implementation of the Traversal service, which contains all the graph querying endpoints. */
+ static class TraversalService extends TraversalServiceGrpc.TraversalServiceImplBase {
+ SwhBidirectionalGraph graph;
+
+ public TraversalService(SwhBidirectionalGraph graph) {
+ this.graph = graph;
+ }
+
+ /** Return various statistics on the overall graph. */
+ @Override
+ public void stats(StatsRequest request, StreamObserver responseObserver) {
+ StatsResponse.Builder response = StatsResponse.newBuilder();
+ response.setNumNodes(graph.numNodes());
+ response.setNumEdges(graph.numArcs());
+
+ Properties properties = new Properties();
+ try {
+ properties.load(new FileInputStream(graph.getPath() + ".properties"));
+ properties.load(new FileInputStream(graph.getPath() + ".stats"));
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ response.setCompressionRatio(Double.parseDouble(properties.getProperty("compratio")));
+ response.setBitsPerNode(Double.parseDouble(properties.getProperty("bitspernode")));
+ response.setBitsPerEdge(Double.parseDouble(properties.getProperty("bitsperlink")));
+ response.setAvgLocality(Double.parseDouble(properties.getProperty("avglocality")));
+ response.setIndegreeMin(Long.parseLong(properties.getProperty("minindegree")));
+ response.setIndegreeMax(Long.parseLong(properties.getProperty("maxindegree")));
+ response.setIndegreeAvg(Double.parseDouble(properties.getProperty("avgindegree")));
+ response.setOutdegreeMin(Long.parseLong(properties.getProperty("minoutdegree")));
+ response.setOutdegreeMax(Long.parseLong(properties.getProperty("maxoutdegree")));
+ response.setOutdegreeAvg(Double.parseDouble(properties.getProperty("avgoutdegree")));
+ responseObserver.onNext(response.build());
+ responseObserver.onCompleted();
+ }
+
+ /** Return a single node and its properties. */
+ @Override
+ public void getNode(GetNodeRequest request, StreamObserver responseObserver) {
+ SwhBidirectionalGraph g = graph.copy();
+ long nodeId;
+ try {
+ nodeId = g.getNodeId(new SWHID(request.getSwhid()));
+ } catch (IllegalArgumentException e) {
+ responseObserver
+ .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException());
+ return;
+ }
+ Node.Builder builder = Node.newBuilder();
+ NodePropertyBuilder.buildNodeProperties(g.getForwardGraph(), request.hasMask() ? request.getMask() : null,
+ builder, nodeId);
+ responseObserver.onNext(builder.build());
+ responseObserver.onCompleted();
+ }
+
+ /** Perform a BFS traversal from a set of source nodes and stream the nodes encountered. */
+ @Override
+ public void traverse(TraversalRequest request, StreamObserver responseObserver) {
+ SwhBidirectionalGraph g = graph.copy();
+ Traversal.SimpleTraversal t;
+ try {
+ t = new Traversal.SimpleTraversal(g, request, responseObserver::onNext);
+ } catch (IllegalArgumentException e) {
+ responseObserver
+ .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException());
+ return;
+ }
+ t.visit();
+ responseObserver.onCompleted();
+ }
+
+ /**
+ * Find the shortest path between a set of source nodes and a node that matches a given criteria
+ * using a BFS.
+ */
+ @Override
+ public void findPathTo(FindPathToRequest request, StreamObserver responseObserver) {
+ SwhBidirectionalGraph g = graph.copy();
+ Traversal.FindPathTo t;
+ try {
+ t = new Traversal.FindPathTo(g, request);
+ } catch (IllegalArgumentException e) {
+ responseObserver
+ .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException());
+ return;
+ }
+ t.visit();
+ Path path = t.getPath();
+ if (path == null) {
+ responseObserver.onError(Status.NOT_FOUND.asException());
+ } else {
+ responseObserver.onNext(path);
+ responseObserver.onCompleted();
+ }
+ }
+
+ /**
+ * Find the shortest path between a set of source nodes and a set of destination nodes using a
+ * bidirectional BFS.
+ */
+ @Override
+ public void findPathBetween(FindPathBetweenRequest request, StreamObserver responseObserver) {
+ SwhBidirectionalGraph g = graph.copy();
+ Traversal.FindPathBetween t;
+ try {
+ t = new Traversal.FindPathBetween(g, request);
+ } catch (IllegalArgumentException e) {
+ responseObserver
+ .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException());
+ return;
+ }
+ t.visit();
+ Path path = t.getPath();
+ if (path == null) {
+ responseObserver.onError(Status.NOT_FOUND.asException());
+ } else {
+ responseObserver.onNext(path);
+ responseObserver.onCompleted();
+ }
+ }
+
+ /** Return the number of nodes traversed by a BFS traversal. */
+ @Override
+ public void countNodes(TraversalRequest request, StreamObserver responseObserver) {
+ AtomicLong count = new AtomicLong(0);
+ SwhBidirectionalGraph g = graph.copy();
+ TraversalRequest fixedReq = TraversalRequest.newBuilder(request)
+ // Ignore return fields, just count nodes
+ .setMask(FieldMask.getDefaultInstance()).build();
+ Traversal.SimpleTraversal t;
+ try {
+ t = new Traversal.SimpleTraversal(g, fixedReq, n -> count.incrementAndGet());
+ } catch (IllegalArgumentException e) {
+ responseObserver
+ .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException());
+ return;
+ }
+ t.visit();
+ CountResponse response = CountResponse.newBuilder().setCount(count.get()).build();
+ responseObserver.onNext(response);
+ responseObserver.onCompleted();
+ }
+
+ /** Return the number of edges traversed by a BFS traversal. */
+ @Override
+ public void countEdges(TraversalRequest request, StreamObserver responseObserver) {
+ AtomicLong count = new AtomicLong(0);
+ SwhBidirectionalGraph g = graph.copy();
+ TraversalRequest fixedReq = TraversalRequest.newBuilder(request)
+ // Force return empty successors to count the edges
+ .setMask(FieldMask.newBuilder().addPaths("num_successors").build()).build();
+ Traversal.SimpleTraversal t;
+ try {
+ t = new Traversal.SimpleTraversal(g, fixedReq, n -> count.addAndGet(n.getNumSuccessors()));
+ } catch (IllegalArgumentException e) {
+ responseObserver
+ .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException());
+ return;
+ }
+ t.visit();
+ CountResponse response = CountResponse.newBuilder().setCount(count.get()).build();
+ responseObserver.onNext(response);
+ responseObserver.onCompleted();
+ }
+ }
+}
diff --git a/java/src/main/java/org/softwareheritage/graph/rpc/NodePropertyBuilder.java b/java/src/main/java/org/softwareheritage/graph/rpc/NodePropertyBuilder.java
new file mode 100644
--- /dev/null
+++ b/java/src/main/java/org/softwareheritage/graph/rpc/NodePropertyBuilder.java
@@ -0,0 +1,210 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
+package org.softwareheritage.graph.rpc;
+
+import com.google.protobuf.ByteString;
+import com.google.protobuf.FieldMask;
+import com.google.protobuf.util.FieldMaskUtil;
+import it.unimi.dsi.big.webgraph.labelling.Label;
+import org.softwareheritage.graph.SwhUnidirectionalGraph;
+import org.softwareheritage.graph.labels.DirEntry;
+
+import java.util.*;
+
+/**
+ * NodePropertyBuilder is a helper class to enrich {@link Node} messages with node and edge
+ * properties. It is used by {@link GraphServer.TraversalService} to build the response messages or
+ * streams. Because property access is disk-based and slow, particular care is taken to avoid
+ * loading unnecessary properties. We use a FieldMask object to check which properties are requested
+ * by the client, and only load these.
+ */
+public class NodePropertyBuilder {
+ /**
+ * NodeDataMask caches a FieldMask into a more efficient representation (booleans). This avoids the
+ * need of parsing the FieldMask for each node in the stream.
+ */
+ public static class NodeDataMask {
+ public boolean swhid;
+ public boolean successor;
+ public boolean successorSwhid;
+ public boolean successorLabel;
+ public boolean numSuccessors;
+ public boolean cntLength;
+ public boolean cntIsSkipped;
+ public boolean revAuthor;
+ public boolean revAuthorDate;
+ public boolean revAuthorDateOffset;
+ public boolean revCommitter;
+ public boolean revCommitterDate;
+ public boolean revCommitterDateOffset;
+ public boolean revMessage;
+ public boolean relAuthor;
+ public boolean relAuthorDate;
+ public boolean relAuthorDateOffset;
+ public boolean relName;
+ public boolean relMessage;
+ public boolean oriUrl;
+
+ public NodeDataMask(FieldMask mask) {
+ Set allowedFields = null;
+ if (mask != null) {
+ mask = FieldMaskUtil.normalize(mask);
+ allowedFields = new HashSet<>(mask.getPathsList());
+ }
+ this.swhid = allowedFields == null || allowedFields.contains("swhid");
+ this.successorSwhid = allowedFields == null || allowedFields.contains("successor")
+ || allowedFields.contains("successor.swhid");
+ this.successorLabel = allowedFields == null || allowedFields.contains("successor")
+ || allowedFields.contains("successor.label");
+ this.successor = this.successorSwhid || this.successorLabel;
+ this.numSuccessors = allowedFields == null || allowedFields.contains("num_successors");
+ this.cntLength = allowedFields == null || allowedFields.contains("cnt.length");
+ this.cntIsSkipped = allowedFields == null || allowedFields.contains("cnt.is_skipped");
+ this.revAuthor = allowedFields == null || allowedFields.contains("rev.author");
+ this.revAuthorDate = allowedFields == null || allowedFields.contains("rev.author_date");
+ this.revAuthorDateOffset = allowedFields == null || allowedFields.contains("rev.author_date_offset");
+ this.revCommitter = allowedFields == null || allowedFields.contains("rev.committer");
+ this.revCommitterDate = allowedFields == null || allowedFields.contains("rev.committer_date");
+ this.revCommitterDateOffset = allowedFields == null || allowedFields.contains("rev.committer_date_offset");
+ this.revMessage = allowedFields == null || allowedFields.contains("rev.message");
+ this.relAuthor = allowedFields == null || allowedFields.contains("rel.author");
+ this.relAuthorDate = allowedFields == null || allowedFields.contains("rel.author_date");
+ this.relAuthorDateOffset = allowedFields == null || allowedFields.contains("rel.author_date_offset");
+ this.relName = allowedFields == null || allowedFields.contains("rel.name");
+ this.relMessage = allowedFields == null || allowedFields.contains("rel.message");
+ this.oriUrl = allowedFields == null || allowedFields.contains("ori.url");
+ }
+ }
+
+ /** Enrich a Node message with node properties requested in the NodeDataMask. */
+ public static void buildNodeProperties(SwhUnidirectionalGraph graph, NodeDataMask mask, Node.Builder nodeBuilder,
+ long node) {
+ if (mask.swhid) {
+ nodeBuilder.setSwhid(graph.getSWHID(node).toString());
+ }
+
+ switch (graph.getNodeType(node)) {
+ case CNT:
+ ContentData.Builder cntBuilder = ContentData.newBuilder();
+ if (mask.cntLength) {
+ cntBuilder.setLength(graph.getContentLength(node));
+ }
+ if (mask.cntIsSkipped) {
+ cntBuilder.setIsSkipped(graph.isContentSkipped(node));
+ }
+ nodeBuilder.setCnt(cntBuilder.build());
+ break;
+ case REV:
+ RevisionData.Builder revBuilder = RevisionData.newBuilder();
+ if (mask.revAuthor) {
+ revBuilder.setAuthor(graph.getAuthorId(node));
+ }
+ if (mask.revAuthorDate) {
+ revBuilder.setAuthorDate(graph.getAuthorTimestamp(node));
+ }
+ if (mask.revAuthorDateOffset) {
+ revBuilder.setAuthorDateOffset(graph.getAuthorTimestampOffset(node));
+ }
+ if (mask.revCommitter) {
+ revBuilder.setCommitter(graph.getCommitterId(node));
+ }
+ if (mask.revCommitterDate) {
+ revBuilder.setCommitterDate(graph.getCommitterTimestamp(node));
+ }
+ if (mask.revCommitterDateOffset) {
+ revBuilder.setCommitterDateOffset(graph.getCommitterTimestampOffset(node));
+ }
+ if (mask.revMessage) {
+ byte[] msg = graph.getMessage(node);
+ if (msg != null) {
+ revBuilder.setMessage(ByteString.copyFrom(msg));
+ }
+ }
+ nodeBuilder.setRev(revBuilder.build());
+ break;
+ case REL:
+ ReleaseData.Builder relBuilder = ReleaseData.newBuilder();
+ if (mask.relAuthor) {
+ relBuilder.setAuthor(graph.getAuthorId(node));
+ }
+ if (mask.relAuthorDate) {
+ relBuilder.setAuthorDate(graph.getAuthorTimestamp(node));
+ }
+ if (mask.relAuthorDateOffset) {
+ relBuilder.setAuthorDateOffset(graph.getAuthorTimestampOffset(node));
+ }
+ if (mask.relName) {
+ byte[] msg = graph.getMessage(node);
+ if (msg != null) {
+ relBuilder.setMessage(ByteString.copyFrom(msg));
+ }
+ }
+ if (mask.relMessage) {
+ byte[] msg = graph.getMessage(node);
+ if (msg != null) {
+ relBuilder.setMessage(ByteString.copyFrom(msg));
+ }
+ }
+ nodeBuilder.setRel(relBuilder.build());
+ break;
+ case ORI:
+ OriginData.Builder oriBuilder = OriginData.newBuilder();
+ if (mask.oriUrl) {
+ String url = graph.getUrl(node);
+ if (url != null) {
+ oriBuilder.setUrl(url);
+ }
+ }
+ nodeBuilder.setOri(oriBuilder.build());
+ }
+ }
+
+ /** Enrich a Node message with node properties requested in the FieldMask. */
+ public static void buildNodeProperties(SwhUnidirectionalGraph graph, FieldMask mask, Node.Builder nodeBuilder,
+ long node) {
+ NodeDataMask nodeMask = new NodeDataMask(mask);
+ buildNodeProperties(graph, nodeMask, nodeBuilder, node);
+ }
+
+ /**
+ * Enrich a Node message with edge properties requested in the NodeDataMask, for a specific edge.
+ */
+ public static void buildSuccessorProperties(SwhUnidirectionalGraph graph, NodeDataMask mask,
+ Node.Builder nodeBuilder, long src, long dst, Label label) {
+ if (nodeBuilder != null) {
+ Successor.Builder successorBuilder = Successor.newBuilder();
+ if (mask.successorSwhid) {
+ successorBuilder.setSwhid(graph.getSWHID(dst).toString());
+ }
+ if (mask.successorLabel) {
+ DirEntry[] entries = (DirEntry[]) label.get();
+ for (DirEntry entry : entries) {
+ EdgeLabel.Builder builder = EdgeLabel.newBuilder();
+ builder.setName(ByteString.copyFrom(graph.getLabelName(entry.filenameId)));
+ builder.setPermission(entry.permission);
+ successorBuilder.addLabel(builder.build());
+ }
+ }
+ Successor successor = successorBuilder.build();
+ if (successor != Successor.getDefaultInstance()) {
+ nodeBuilder.addSuccessor(successor);
+ }
+
+ if (mask.numSuccessors) {
+ nodeBuilder.setNumSuccessors(nodeBuilder.getNumSuccessors() + 1);
+ }
+ }
+ }
+
+ /** Enrich a Node message with edge properties requested in the FieldMask, for a specific edge. */
+ public static void buildSuccessorProperties(SwhUnidirectionalGraph graph, FieldMask mask, Node.Builder nodeBuilder,
+ long src, long dst, Label label) {
+ NodeDataMask nodeMask = new NodeDataMask(mask);
+ buildSuccessorProperties(graph, nodeMask, nodeBuilder, src, dst, label);
+ }
+}
diff --git a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java
new file mode 100644
--- /dev/null
+++ b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java
@@ -0,0 +1,533 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
+package org.softwareheritage.graph.rpc;
+
+import it.unimi.dsi.big.webgraph.labelling.ArcLabelledNodeIterator;
+import it.unimi.dsi.big.webgraph.labelling.Label;
+import org.softwareheritage.graph.*;
+
+import java.util.*;
+
+/** Traversal contains all the algorithms used for graph traversals */
+public class Traversal {
+ /**
+ * Wrapper around g.successors(), only follows edges that are allowed by the given
+ * {@link AllowedEdges} object.
+ */
+ private static ArcLabelledNodeIterator.LabelledArcIterator filterLabelledSuccessors(SwhUnidirectionalGraph g,
+ long nodeId, AllowedEdges allowedEdges) {
+ if (allowedEdges.restrictedTo == null) {
+ // All edges are allowed, bypass edge check
+ return g.labelledSuccessors(nodeId);
+ } else {
+ ArcLabelledNodeIterator.LabelledArcIterator allSuccessors = g.labelledSuccessors(nodeId);
+ return new ArcLabelledNodeIterator.LabelledArcIterator() {
+ @Override
+ public Label label() {
+ return allSuccessors.label();
+ }
+
+ @Override
+ public long nextLong() {
+ long neighbor;
+ while ((neighbor = allSuccessors.nextLong()) != -1) {
+ if (allowedEdges.isAllowed(g.getNodeType(nodeId), g.getNodeType(neighbor))) {
+ return neighbor;
+ }
+ }
+ return -1;
+ }
+
+ @Override
+ public long skip(final long n) {
+ long i = 0;
+ while (i < n && nextLong() != -1)
+ i++;
+ return i;
+ }
+ };
+ }
+ }
+
+ /** Helper class to check that a given node is "valid" for some given {@link NodeFilter} */
+ private static class NodeFilterChecker {
+ private final SwhUnidirectionalGraph g;
+ private final NodeFilter filter;
+ private final AllowedNodes allowedNodes;
+
+ private NodeFilterChecker(SwhUnidirectionalGraph graph, NodeFilter filter) {
+ this.g = graph;
+ this.filter = filter;
+ this.allowedNodes = new AllowedNodes(filter.hasTypes() ? filter.getTypes() : "*");
+ }
+
+ public boolean allowed(long nodeId) {
+ if (filter == null) {
+ return true;
+ }
+ if (!this.allowedNodes.isAllowed(g.getNodeType(nodeId))) {
+ return false;
+ }
+
+ return true;
+ }
+ }
+
+ /** Returns the unidirectional graph from a bidirectional graph and a {@link GraphDirection}. */
+ public static SwhUnidirectionalGraph getDirectedGraph(SwhBidirectionalGraph g, GraphDirection direction) {
+ switch (direction) {
+ case FORWARD:
+ return g.getForwardGraph();
+ case BACKWARD:
+ return g.getBackwardGraph();
+ /*
+ * TODO: add support for BOTH case BOTH: return new SwhUnidirectionalGraph(g.symmetrize(),
+ * g.getProperties());
+ */
+ default :
+ throw new IllegalArgumentException("Unknown direction: " + direction);
+ }
+ }
+
+ /** Returns the opposite of a given {@link GraphDirection} (equivalent to a graph transposition). */
+ public static GraphDirection reverseDirection(GraphDirection direction) {
+ switch (direction) {
+ case FORWARD:
+ return GraphDirection.BACKWARD;
+ case BACKWARD:
+ return GraphDirection.FORWARD;
+ /*
+ * TODO: add support for BOTH case BOTH: return GraphDirection.BOTH;
+ */
+ default :
+ throw new IllegalArgumentException("Unknown direction: " + direction);
+ }
+ }
+
+ /** Dummy exception to short-circuit and interrupt a graph traversal. */
+ static class StopTraversalException extends RuntimeException {
+ }
+
+ /** Generic BFS traversal algorithm. */
+ static class BFSVisitor {
+ /** The graph to traverse. */
+ protected final SwhUnidirectionalGraph g;
+ /** Depth of the node currently being visited */
+ protected long depth = 0;
+ /**
+ * Number of traversal successors (i.e., successors that will be considered by the traversal) of the
+ * node currently being visited
+ */
+ protected long traversalSuccessors = 0;
+ /** Number of edges accessed since the beginning of the traversal */
+ protected long edgesAccessed = 0;
+
+ /**
+ * Map from a node ID to its parent node ID. The key set can be used as the set of all visited
+ * nodes.
+ */
+ protected HashMap parents = new HashMap<>();
+ /** Queue of nodes to visit (also called "frontier", "open set", "wavefront" etc.) */
+ protected ArrayDeque queue = new ArrayDeque<>();
+ /** If > 0, the maximum depth of the traversal. */
+ private long maxDepth = -1;
+ /** If > 0, the maximum number of edges to traverse. */
+ private long maxEdges = -1;
+
+ BFSVisitor(SwhUnidirectionalGraph g) {
+ this.g = g;
+ }
+
+ /** Add a new source node to the initial queue. */
+ public void addSource(long nodeId) {
+ queue.add(nodeId);
+ parents.put(nodeId, -1L);
+ }
+
+ /** Set the maximum depth of the traversal. */
+ public void setMaxDepth(long depth) {
+ maxDepth = depth;
+ }
+
+ /** Set the maximum number of edges to traverse. */
+ public void setMaxEdges(long edges) {
+ maxEdges = edges;
+ }
+
+ /** Setup the visit counters and depth sentinel. */
+ public void visitSetup() {
+ edgesAccessed = 0;
+ depth = 0;
+ queue.add(-1L); // depth sentinel
+ }
+
+ /** Perform the visit */
+ public void visit() {
+ visitSetup();
+ while (!queue.isEmpty()) {
+ visitStep();
+ }
+ }
+
+ /** Single "step" of a visit. Advance the frontier of exactly one node. */
+ public void visitStep() {
+ try {
+ assert !queue.isEmpty();
+ long curr = queue.poll();
+ if (curr == -1L) {
+ ++depth;
+ if (!queue.isEmpty()) {
+ queue.add(-1L);
+ visitStep();
+ }
+ return;
+ }
+ if (maxDepth >= 0 && depth > maxDepth) {
+ throw new StopTraversalException();
+ }
+ edgesAccessed += g.outdegree(curr);
+ if (maxEdges >= 0 && edgesAccessed > maxEdges) {
+ throw new StopTraversalException();
+ }
+ visitNode(curr);
+ } catch (StopTraversalException e) {
+ // Traversal is over, clear the to-do queue.
+ queue.clear();
+ }
+ }
+
+ /**
+ * Get the successors of a node. Override this function if you want to filter which successors are
+ * considered during the traversal.
+ */
+ protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) {
+ return g.labelledSuccessors(nodeId);
+ }
+
+ /** Visit a node. Override to do additional processing on the node. */
+ protected void visitNode(long node) {
+ ArcLabelledNodeIterator.LabelledArcIterator it = getSuccessors(node);
+ traversalSuccessors = 0;
+ for (long succ; (succ = it.nextLong()) != -1;) {
+ traversalSuccessors++;
+ visitEdge(node, succ, it.label());
+ }
+ }
+
+ /** Visit an edge. Override to do additional processing on the edge. */
+ protected void visitEdge(long src, long dst, Label label) {
+ if (!parents.containsKey(dst)) {
+ queue.add(dst);
+ parents.put(dst, src);
+ }
+ }
+ }
+
+ /**
+ * SimpleTraversal is used by the Traverse endpoint. It extends BFSVisitor with additional
+ * processing, notably related to graph properties and filters.
+ */
+ static class SimpleTraversal extends BFSVisitor {
+ private final NodeFilterChecker nodeReturnChecker;
+ private final AllowedEdges allowedEdges;
+ private final TraversalRequest request;
+ private final NodePropertyBuilder.NodeDataMask nodeDataMask;
+ private final NodeObserver nodeObserver;
+
+ private Node.Builder nodeBuilder;
+
+ SimpleTraversal(SwhBidirectionalGraph bidirectionalGraph, TraversalRequest request, NodeObserver nodeObserver) {
+ super(getDirectedGraph(bidirectionalGraph, request.getDirection()));
+ this.request = request;
+ this.nodeObserver = nodeObserver;
+ this.nodeReturnChecker = new NodeFilterChecker(g, request.getReturnNodes());
+ this.nodeDataMask = new NodePropertyBuilder.NodeDataMask(request.hasMask() ? request.getMask() : null);
+ this.allowedEdges = new AllowedEdges(request.hasEdges() ? request.getEdges() : "*");
+ request.getSrcList().forEach(srcSwhid -> {
+ long srcNodeId = g.getNodeId(new SWHID(srcSwhid));
+ addSource(srcNodeId);
+ });
+ if (request.hasMaxDepth()) {
+ setMaxDepth(request.getMaxDepth());
+ }
+ if (request.hasMaxEdges()) {
+ setMaxEdges(request.getMaxEdges());
+ }
+ }
+
+ @Override
+ protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) {
+ return filterLabelledSuccessors(g, nodeId, allowedEdges);
+ }
+
+ @Override
+ public void visitNode(long node) {
+ nodeBuilder = null;
+ if (nodeReturnChecker.allowed(node) && (!request.hasMinDepth() || depth >= request.getMinDepth())) {
+ nodeBuilder = Node.newBuilder();
+ NodePropertyBuilder.buildNodeProperties(g, nodeDataMask, nodeBuilder, node);
+ }
+ super.visitNode(node);
+ if (request.getReturnNodes().hasMinTraversalSuccessors()
+ && traversalSuccessors < request.getReturnNodes().getMinTraversalSuccessors()
+ || request.getReturnNodes().hasMaxTraversalSuccessors()
+ && traversalSuccessors > request.getReturnNodes().getMaxTraversalSuccessors()) {
+ nodeBuilder = null;
+ }
+ if (nodeBuilder != null) {
+ nodeObserver.onNext(nodeBuilder.build());
+ }
+ }
+
+ @Override
+ protected void visitEdge(long src, long dst, Label label) {
+ super.visitEdge(src, dst, label);
+ NodePropertyBuilder.buildSuccessorProperties(g, nodeDataMask, nodeBuilder, src, dst, label);
+ }
+ }
+
+ /**
+ * FindPathTo searches for a path from a source node to a node matching a given criteria It extends
+ * BFSVisitor with additional processing, and makes the traversal stop as soon as a node matching
+ * the given criteria is found.
+ */
+ static class FindPathTo extends BFSVisitor {
+ private final AllowedEdges allowedEdges;
+ private final FindPathToRequest request;
+ private final NodePropertyBuilder.NodeDataMask nodeDataMask;
+ private final NodeFilterChecker targetChecker;
+ private Long targetNode = null;
+
+ FindPathTo(SwhBidirectionalGraph bidirectionalGraph, FindPathToRequest request) {
+ super(getDirectedGraph(bidirectionalGraph, request.getDirection()));
+ this.request = request;
+ this.targetChecker = new NodeFilterChecker(g, request.getTarget());
+ this.nodeDataMask = new NodePropertyBuilder.NodeDataMask(request.hasMask() ? request.getMask() : null);
+ this.allowedEdges = new AllowedEdges(request.hasEdges() ? request.getEdges() : "*");
+ if (request.hasMaxDepth()) {
+ setMaxDepth(request.getMaxDepth());
+ }
+ if (request.hasMaxEdges()) {
+ setMaxEdges(request.getMaxEdges());
+ }
+ request.getSrcList().forEach(srcSwhid -> {
+ long srcNodeId = g.getNodeId(new SWHID(srcSwhid));
+ addSource(srcNodeId);
+ });
+ }
+
+ @Override
+ protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) {
+ return filterLabelledSuccessors(g, nodeId, allowedEdges);
+ }
+
+ @Override
+ public void visitNode(long node) {
+ if (targetChecker.allowed(node)) {
+ targetNode = node;
+ throw new StopTraversalException();
+ }
+ super.visitNode(node);
+ }
+
+ /**
+ * Once the visit has been performed and a matching node has been found, return the shortest path
+ * from the source set to that node. To do so, we need to backtrack the parents of the node until we
+ * find one of the source nodes (whose parent is -1).
+ */
+ public Path getPath() {
+ if (targetNode == null) {
+ return null; // No path found.
+ }
+
+ /* Backtrack from targetNode to a source node */
+ long curNode = targetNode;
+ ArrayList path = new ArrayList<>();
+ while (curNode != -1) {
+ path.add(curNode);
+ curNode = parents.get(curNode);
+ }
+ Collections.reverse(path);
+
+ /* Enrich path with node properties */
+ Path.Builder pathBuilder = Path.newBuilder();
+ for (long nodeId : path) {
+ Node.Builder nodeBuilder = Node.newBuilder();
+ NodePropertyBuilder.buildNodeProperties(g, nodeDataMask, nodeBuilder, nodeId);
+ pathBuilder.addNode(nodeBuilder.build());
+ }
+ return pathBuilder.build();
+ }
+ }
+
+ /**
+ * FindPathBetween searches for a shortest path between a set of source nodes and a set of
+ * destination nodes.
+ *
+ * It does so by performing a *bidirectional breadth-first search*, i.e., two parallel breadth-first
+ * searches, one from the source set ("src-BFS") and one from the destination set ("dst-BFS"), until
+ * both searches find a common node that joins their visited sets. This node is called the "midpoint
+ * node". The path returned is the path src -> ... -> midpoint -> ... -> dst, which is always a
+ * shortest path between src and dst.
+ *
+ * The graph direction of both BFS can be configured separately. By default, the dst-BFS will use
+ * the graph in the opposite direction than the src-BFS (if direction = FORWARD, by default
+ * direction_reverse = BACKWARD, and vice-versa). The default behavior is thus to search for a
+ * shortest path between two nodes in a given direction. However, one can also specify FORWARD or
+ * BACKWARD for *both* the src-BFS and the dst-BFS. This will search for a common descendant or a
+ * common ancestor between the two sets, respectively. These will be the midpoints of the returned
+ * path.
+ */
+ static class FindPathBetween extends BFSVisitor {
+ private final FindPathBetweenRequest request;
+ private final NodePropertyBuilder.NodeDataMask nodeDataMask;
+ private final AllowedEdges allowedEdgesSrc;
+ private final AllowedEdges allowedEdgesDst;
+
+ private final BFSVisitor srcVisitor;
+ private final BFSVisitor dstVisitor;
+ private Long middleNode = null;
+
+ FindPathBetween(SwhBidirectionalGraph bidirectionalGraph, FindPathBetweenRequest request) {
+ super(getDirectedGraph(bidirectionalGraph, request.getDirection()));
+ this.request = request;
+ this.nodeDataMask = new NodePropertyBuilder.NodeDataMask(request.hasMask() ? request.getMask() : null);
+
+ GraphDirection direction = request.getDirection();
+ // if direction_reverse is not specified, use the opposite direction of direction
+ GraphDirection directionReverse = request.hasDirectionReverse()
+ ? request.getDirectionReverse()
+ : reverseDirection(request.getDirection());
+ SwhUnidirectionalGraph srcGraph = getDirectedGraph(bidirectionalGraph, direction);
+ SwhUnidirectionalGraph dstGraph = getDirectedGraph(bidirectionalGraph, directionReverse);
+
+ this.allowedEdgesSrc = new AllowedEdges(request.hasEdges() ? request.getEdges() : "*");
+ /*
+ * If edges_reverse is not specified: - If `edges` is not specified either, defaults to "*" - If
+ * direction == direction_reverse, defaults to `edges` - If direction != direction_reverse, defaults
+ * to the reverse of `edges` (e.g. "rev:dir" becomes "dir:rev").
+ */
+ this.allowedEdgesDst = request.hasEdgesReverse()
+ ? new AllowedEdges(request.getEdgesReverse())
+ : (request.hasEdges()
+ ? (direction == directionReverse
+ ? new AllowedEdges(request.getEdges())
+ : new AllowedEdges(request.getEdges()).reverse())
+ : new AllowedEdges("*"));
+
+ /*
+ * Source sub-visitor. Aborts as soon as it finds a node already visited by the destination
+ * sub-visitor.
+ */
+ this.srcVisitor = new BFSVisitor(srcGraph) {
+ @Override
+ protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) {
+ return filterLabelledSuccessors(g, nodeId, allowedEdgesSrc);
+ }
+
+ @Override
+ public void visitNode(long node) {
+ if (dstVisitor.parents.containsKey(node)) {
+ middleNode = node;
+ throw new StopTraversalException();
+ }
+ super.visitNode(node);
+ }
+ };
+
+ /*
+ * Destination sub-visitor. Aborts as soon as it finds a node already visited by the source
+ * sub-visitor.
+ */
+ this.dstVisitor = new BFSVisitor(dstGraph) {
+ @Override
+ protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) {
+ return filterLabelledSuccessors(g, nodeId, allowedEdgesDst);
+ }
+
+ @Override
+ public void visitNode(long node) {
+ if (srcVisitor.parents.containsKey(node)) {
+ middleNode = node;
+ throw new StopTraversalException();
+ }
+ super.visitNode(node);
+ }
+ };
+ if (request.hasMaxDepth()) {
+ this.srcVisitor.setMaxDepth(request.getMaxDepth());
+ this.dstVisitor.setMaxDepth(request.getMaxDepth());
+ }
+ if (request.hasMaxEdges()) {
+ this.srcVisitor.setMaxEdges(request.getMaxEdges());
+ this.dstVisitor.setMaxEdges(request.getMaxEdges());
+ }
+ request.getSrcList().forEach(srcSwhid -> {
+ long srcNodeId = g.getNodeId(new SWHID(srcSwhid));
+ srcVisitor.addSource(srcNodeId);
+ });
+ request.getDstList().forEach(srcSwhid -> {
+ long srcNodeId = g.getNodeId(new SWHID(srcSwhid));
+ dstVisitor.addSource(srcNodeId);
+ });
+ }
+
+ @Override
+ public void visit() {
+ /*
+ * Bidirectional BFS: maintain two sub-visitors, and alternately run a visit step in each of them.
+ */
+ srcVisitor.visitSetup();
+ dstVisitor.visitSetup();
+ while (!srcVisitor.queue.isEmpty() || !dstVisitor.queue.isEmpty()) {
+ if (!srcVisitor.queue.isEmpty()) {
+ srcVisitor.visitStep();
+ }
+ if (!dstVisitor.queue.isEmpty()) {
+ dstVisitor.visitStep();
+ }
+ }
+ }
+
+ public Path getPath() {
+ if (middleNode == null) {
+ return null; // No path found.
+ }
+ Path.Builder pathBuilder = Path.newBuilder();
+ ArrayList path = new ArrayList<>();
+
+ /* First section of the path: src -> midpoint */
+ long curNode = middleNode;
+ while (curNode != -1) {
+ path.add(curNode);
+ curNode = srcVisitor.parents.get(curNode);
+ }
+ pathBuilder.setMidpointIndex(path.size() - 1);
+ Collections.reverse(path);
+
+ /* Second section of the path: midpoint -> dst */
+ curNode = dstVisitor.parents.get(middleNode);
+ while (curNode != -1) {
+ path.add(curNode);
+ curNode = dstVisitor.parents.get(curNode);
+ }
+
+ /* Enrich path with node properties */
+ for (long nodeId : path) {
+ Node.Builder nodeBuilder = Node.newBuilder();
+ NodePropertyBuilder.buildNodeProperties(g, nodeDataMask, nodeBuilder, nodeId);
+ pathBuilder.addNode(nodeBuilder.build());
+ }
+ return pathBuilder.build();
+ }
+ }
+
+ public interface NodeObserver {
+ void onNext(Node nodeId);
+ }
+}
diff --git a/java/src/main/java/org/softwareheritage/graph/server/App.java b/java/src/main/java/org/softwareheritage/graph/server/App.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/server/App.java
+++ /dev/null
@@ -1,196 +0,0 @@
-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.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Stats;
-import org.softwareheritage.graph.SWHID;
-
-import java.io.IOException;
-import java.util.List;
-import java.util.Map;
-
-/**
- * Web framework of the swh-graph server RPC 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 {
- SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(graphPath);
- Stats stats = new Stats(graphPath);
-
- // Clean up on exit
- Runtime.getRuntime().addShutdownHook(new Thread() {
- public void run() {
- try {
- graph.close();
- } 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 -> {
- 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 -> {
- 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 -> {
- 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 -> {
- 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 -> {
- 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 RPC 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 RPC 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
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java
+++ /dev/null
@@ -1,309 +0,0 @@
-package org.softwareheritage.graph.server;
-
-import org.softwareheritage.graph.*;
-import org.softwareheritage.graph.benchmark.utils.Timing;
-
-import java.util.ArrayList;
-
-/**
- * RPC 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 */
- SwhBidirectionalGraph 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(SwhBidirectionalGraph 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) SWHIDs.
- *
- * @param nodeIds the list of long node ids
- * @return a list of corresponding SWHIDs
- */
- private ArrayList convertNodesToSWHIDs(ArrayList nodeIds) {
- ArrayList swhids = new ArrayList<>();
- for (long nodeId : nodeIds) {
- swhids.add(graph.getSWHID(nodeId));
- }
- 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.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 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 SWHID} from endpoint call and operation metadata
- * @see SWHID
- * @see Traversal#leaves(long)
- */
- public Output leaves(Input input) {
- Output> output = new Output<>();
- long startTime;
-
- startTime = Timing.start();
- long srcNodeId = graph.getNodeId(input.src);
- output.meta.timings.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 = 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 SWHID} from endpoint call and operation metadata
- * @see SWHID
- * @see Traversal#neighbors(long)
- */
- public Output neighbors(Input input) {
- Output> output = new Output<>();
- long startTime;
-
- startTime = Timing.start();
- long srcNodeId = graph.getNodeId(input.src);
- output.meta.timings.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 = 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 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.swhid2node = Timing.stop(startTime);
-
- ArrayList nodeIds = new ArrayList();
-
- // Destination is either a SWHID or a node type
- try {
- 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.node2swhid = Timing.stop(startTime);
-
- return output;
- }
-
- /**
- * VisitNodes endpoint wrapper.
- *
- * @param input input parameters for the underlying endpoint call
- * @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<>();
- long startTime;
-
- startTime = Timing.start();
- long srcNodeId = graph.getNodeId(input.src);
- 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 = 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 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.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 = 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 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(SWHID src) {
- this.src = src;
- }
-
- 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 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/DumpProperties.java b/java/src/main/java/org/softwareheritage/graph/utils/DumpProperties.java
--- a/java/src/main/java/org/softwareheritage/graph/utils/DumpProperties.java
+++ b/java/src/main/java/org/softwareheritage/graph/utils/DumpProperties.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.utils;
import it.unimi.dsi.big.webgraph.labelling.ArcLabelledNodeIterator;
diff --git a/java/src/main/java/org/softwareheritage/graph/utils/ExportSubdataset.java b/java/src/main/java/org/softwareheritage/graph/utils/ExportSubdataset.java
--- a/java/src/main/java/org/softwareheritage/graph/utils/ExportSubdataset.java
+++ b/java/src/main/java/org/softwareheritage/graph/utils/ExportSubdataset.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2021 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.utils;
import com.google.common.primitives.Longs;
diff --git a/java/src/main/java/org/softwareheritage/graph/utils/FindEarliestRevision.java b/java/src/main/java/org/softwareheritage/graph/utils/FindEarliestRevision.java
--- a/java/src/main/java/org/softwareheritage/graph/utils/FindEarliestRevision.java
+++ b/java/src/main/java/org/softwareheritage/graph/utils/FindEarliestRevision.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2021 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.utils;
import it.unimi.dsi.big.webgraph.LazyLongIterator;
@@ -76,7 +83,7 @@
long minTimestamp = Long.MAX_VALUE;
while (!stack.isEmpty()) {
long currentNodeId = stack.pop();
- if (graph.getNodeType(currentNodeId) == Node.Type.REV) {
+ if (graph.getNodeType(currentNodeId) == SwhType.REV) {
long committerTs = graph.getCommitterTimestamp(currentNodeId);
if (committerTs < minTimestamp) {
minRevId = currentNodeId;
@@ -84,8 +91,11 @@
}
}
- LazyLongIterator it = Traversal.filterSuccessors(graph, currentNodeId, edges);
+ LazyLongIterator it = graph.successors(currentNodeId);
for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) {
+ if (!edges.isAllowed(graph.getNodeType(currentNodeId), graph.getNodeType(neighborNodeId))) {
+ continue;
+ }
if (!visited.contains(neighborNodeId)) {
stack.push(neighborNodeId);
visited.add(neighborNodeId);
diff --git a/java/src/main/java/org/softwareheritage/graph/utils/ForkJoinBigQuickSort2.java b/java/src/main/java/org/softwareheritage/graph/utils/ForkJoinBigQuickSort2.java
--- a/java/src/main/java/org/softwareheritage/graph/utils/ForkJoinBigQuickSort2.java
+++ b/java/src/main/java/org/softwareheritage/graph/utils/ForkJoinBigQuickSort2.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.utils;
import it.unimi.dsi.fastutil.BigArrays;
diff --git a/java/src/main/java/org/softwareheritage/graph/utils/ForkJoinQuickSort3.java b/java/src/main/java/org/softwareheritage/graph/utils/ForkJoinQuickSort3.java
--- a/java/src/main/java/org/softwareheritage/graph/utils/ForkJoinQuickSort3.java
+++ b/java/src/main/java/org/softwareheritage/graph/utils/ForkJoinQuickSort3.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.utils;
import java.util.concurrent.ForkJoinPool;
diff --git a/java/src/main/java/org/softwareheritage/graph/utils/MPHTranslate.java b/java/src/main/java/org/softwareheritage/graph/utils/MPHTranslate.java
--- a/java/src/main/java/org/softwareheritage/graph/utils/MPHTranslate.java
+++ b/java/src/main/java/org/softwareheritage/graph/utils/MPHTranslate.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2020 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.utils;
import com.martiansoftware.jsap.*;
diff --git a/java/src/main/java/org/softwareheritage/graph/utils/ReadGraph.java b/java/src/main/java/org/softwareheritage/graph/utils/ReadGraph.java
--- a/java/src/main/java/org/softwareheritage/graph/utils/ReadGraph.java
+++ b/java/src/main/java/org/softwareheritage/graph/utils/ReadGraph.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2020-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.utils;
import it.unimi.dsi.big.webgraph.NodeIterator;
diff --git a/java/src/main/java/org/softwareheritage/graph/utils/ReadLabelledGraph.java b/java/src/main/java/org/softwareheritage/graph/utils/ReadLabelledGraph.java
--- a/java/src/main/java/org/softwareheritage/graph/utils/ReadLabelledGraph.java
+++ b/java/src/main/java/org/softwareheritage/graph/utils/ReadLabelledGraph.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2020-2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.utils;
import it.unimi.dsi.big.webgraph.labelling.ArcLabelledNodeIterator;
diff --git a/java/src/main/java/org/softwareheritage/graph/utils/Sort.java b/java/src/main/java/org/softwareheritage/graph/utils/Sort.java
--- a/java/src/main/java/org/softwareheritage/graph/utils/Sort.java
+++ b/java/src/main/java/org/softwareheritage/graph/utils/Sort.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.utils;
import java.io.IOException;
diff --git a/java/src/main/proto b/java/src/main/proto
new file mode 120000
--- /dev/null
+++ b/java/src/main/proto
@@ -0,0 +1 @@
+../../../proto
\ No newline at end of file
diff --git a/java/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java b/java/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java
--- a/java/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph;
import org.junit.jupiter.api.Assertions;
@@ -7,10 +14,10 @@
public class AllowedEdgesTest extends GraphTest {
static class EdgeType {
- Node.Type src;
- Node.Type dst;
+ SwhType src;
+ SwhType dst;
- public EdgeType(Node.Type src, Node.Type dst) {
+ public EdgeType(SwhType src, SwhType dst) {
this.src = src;
this.dst = dst;
}
@@ -28,9 +35,9 @@
}
void assertEdgeRestriction(AllowedEdges edges, ArrayList expectedAllowed) {
- Node.Type[] nodeTypes = Node.Type.values();
- for (Node.Type src : nodeTypes) {
- for (Node.Type dst : nodeTypes) {
+ SwhType[] nodeTypes = SwhType.values();
+ for (SwhType src : nodeTypes) {
+ for (SwhType dst : nodeTypes) {
EdgeType edge = new EdgeType(src, dst);
boolean isAllowed = edges.isAllowed(src, dst);
boolean isExpected = false;
@@ -50,8 +57,8 @@
public void dirToDirDirToCntEdges() {
AllowedEdges edges = new AllowedEdges("dir:dir,dir:cnt");
ArrayList expected = new ArrayList<>();
- expected.add(new EdgeType(Node.Type.DIR, Node.Type.DIR));
- expected.add(new EdgeType(Node.Type.DIR, Node.Type.CNT));
+ expected.add(new EdgeType(SwhType.DIR, SwhType.DIR));
+ expected.add(new EdgeType(SwhType.DIR, SwhType.CNT));
assertEdgeRestriction(edges, expected);
}
@@ -59,9 +66,9 @@
public void relToRevRevToRevRevToDirEdges() {
AllowedEdges edges = new AllowedEdges("rel:rev,rev:rev,rev:dir");
ArrayList expected = new ArrayList<>();
- expected.add(new EdgeType(Node.Type.REL, Node.Type.REV));
- expected.add(new EdgeType(Node.Type.REV, Node.Type.REV));
- expected.add(new EdgeType(Node.Type.REV, Node.Type.DIR));
+ expected.add(new EdgeType(SwhType.REL, SwhType.REV));
+ expected.add(new EdgeType(SwhType.REV, SwhType.REV));
+ expected.add(new EdgeType(SwhType.REV, SwhType.DIR));
assertEdgeRestriction(edges, expected);
}
@@ -69,10 +76,10 @@
public void revToAllDirToDirEdges() {
AllowedEdges edges = new AllowedEdges("rev:*,dir:dir");
ArrayList expected = new ArrayList<>();
- for (Node.Type dst : Node.Type.values()) {
- expected.add(new EdgeType(Node.Type.REV, dst));
+ for (SwhType dst : SwhType.values()) {
+ expected.add(new EdgeType(SwhType.REV, dst));
}
- expected.add(new EdgeType(Node.Type.DIR, Node.Type.DIR));
+ expected.add(new EdgeType(SwhType.DIR, SwhType.DIR));
assertEdgeRestriction(edges, expected);
}
@@ -80,8 +87,8 @@
public void allToCntEdges() {
AllowedEdges edges = new AllowedEdges("*:cnt");
ArrayList expected = new ArrayList<>();
- for (Node.Type src : Node.Type.values()) {
- expected.add(new EdgeType(src, Node.Type.CNT));
+ for (SwhType src : SwhType.values()) {
+ expected.add(new EdgeType(src, SwhType.CNT));
}
assertEdgeRestriction(edges, expected);
}
@@ -90,8 +97,8 @@
public void allEdges() {
AllowedEdges edges = new AllowedEdges("*:*");
ArrayList expected = new ArrayList<>();
- for (Node.Type src : Node.Type.values()) {
- for (Node.Type dst : Node.Type.values()) {
+ for (SwhType src : SwhType.values()) {
+ for (SwhType dst : SwhType.values()) {
expected.add(new EdgeType(src, dst));
}
}
diff --git a/java/src/test/java/org/softwareheritage/graph/AllowedNodesTest.java b/java/src/test/java/org/softwareheritage/graph/AllowedNodesTest.java
--- a/java/src/test/java/org/softwareheritage/graph/AllowedNodesTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/AllowedNodesTest.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph;
import org.junit.jupiter.api.Assertions;
@@ -6,9 +13,9 @@
import java.util.Set;
public class AllowedNodesTest extends GraphTest {
- void assertNodeRestriction(AllowedNodes nodes, Set expectedAllowed) {
- Node.Type[] nodeTypes = Node.Type.values();
- for (Node.Type t : nodeTypes) {
+ void assertNodeRestriction(AllowedNodes nodes, Set expectedAllowed) {
+ SwhType[] nodeTypes = SwhType.values();
+ for (SwhType t : nodeTypes) {
boolean isAllowed = nodes.isAllowed(t);
boolean isExpected = expectedAllowed.contains(t);
Assertions.assertEquals(isAllowed, isExpected, "Node type: " + t);
@@ -18,36 +25,35 @@
@Test
public void dirCntNodes() {
AllowedNodes edges = new AllowedNodes("dir,cnt");
- Set expected = Set.of(Node.Type.DIR, Node.Type.CNT);
+ Set expected = Set.of(SwhType.DIR, SwhType.CNT);
assertNodeRestriction(edges, expected);
}
@Test
public void revDirNodes() {
AllowedNodes edges = new AllowedNodes("rev,dir");
- Set expected = Set.of(Node.Type.DIR, Node.Type.REV);
+ Set expected = Set.of(SwhType.DIR, SwhType.REV);
assertNodeRestriction(edges, expected);
}
@Test
public void relSnpCntNodes() {
AllowedNodes edges = new AllowedNodes("rel,snp,cnt");
- Set expected = Set.of(Node.Type.REL, Node.Type.SNP, Node.Type.CNT);
+ Set expected = Set.of(SwhType.REL, SwhType.SNP, SwhType.CNT);
assertNodeRestriction(edges, expected);
}
@Test
public void allNodes() {
AllowedNodes edges = new AllowedNodes("*");
- Set expected = Set.of(Node.Type.REL, Node.Type.SNP, Node.Type.CNT, Node.Type.DIR, Node.Type.REV,
- Node.Type.ORI);
+ Set expected = Set.of(SwhType.REL, SwhType.SNP, SwhType.CNT, SwhType.DIR, SwhType.REV, SwhType.ORI);
assertNodeRestriction(edges, expected);
}
@Test
public void noNodes() {
AllowedNodes edges = new AllowedNodes("");
- Set expected = Set.of();
+ Set expected = Set.of();
assertNodeRestriction(edges, expected);
}
}
diff --git a/java/src/test/java/org/softwareheritage/graph/GraphTest.java b/java/src/test/java/org/softwareheritage/graph/GraphTest.java
--- a/java/src/test/java/org/softwareheritage/graph/GraphTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/GraphTest.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph;
import java.io.FileInputStream;
@@ -6,15 +13,15 @@
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Collection;
+import java.util.Comparator;
import java.util.Iterator;
import com.github.luben.zstd.ZstdInputStream;
import it.unimi.dsi.big.webgraph.LazyLongIterator;
import it.unimi.dsi.big.webgraph.LazyLongIterators;
-import org.hamcrest.MatcherAssert;
import org.junit.jupiter.api.BeforeAll;
-import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder;
+import static org.junit.Assert.assertEquals;
public class GraphTest {
static SwhBidirectionalGraph graph;
@@ -23,11 +30,14 @@
@BeforeAll
public static void setUp() throws IOException {
- Path graphPath = Paths.get("..", "swh", "graph", "tests", "dataset", "compressed", "example");
- graph = SwhBidirectionalGraph.loadMapped(graphPath.toString());
+ graph = SwhBidirectionalGraph.loadLabelled(getGraphPath().toString());
+ }
+
+ public static Path getGraphPath() {
+ return Paths.get("..", "swh", "graph", "tests", "dataset", "compressed", "example");
}
- public SwhBidirectionalGraph getGraph() {
+ public static SwhBidirectionalGraph getGraph() {
return graph;
}
@@ -35,8 +45,12 @@
return new SWHID(String.format("swh:1:%s:%040d", type, num));
}
- public static void assertEqualsAnyOrder(Collection expecteds, Collection actuals) {
- MatcherAssert.assertThat(expecteds, containsInAnyOrder(actuals.toArray()));
+ public static void assertEqualsAnyOrder(Collection expected, Collection actual) {
+ ArrayList expectedList = new ArrayList<>(expected);
+ ArrayList actualList = new ArrayList<>(actual);
+ expectedList.sort(Comparator.comparing(Object::toString));
+ actualList.sort(Comparator.comparing(Object::toString));
+ assertEquals(expectedList, actualList);
}
public static ArrayList lazyLongIteratorToList(LazyLongIterator input) {
diff --git a/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java b/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java
deleted file mode 100644
--- a/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java
+++ /dev/null
@@ -1,141 +0,0 @@
-package org.softwareheritage.graph;
-
-import java.util.ArrayList;
-
-import org.junit.jupiter.api.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() {
- SwhBidirectionalGraph graph = getGraph();
- ArrayList expectedNodes = new ArrayList<>();
-
- SWHID src1 = new SWHID(TEST_ORIGIN_ID);
- Endpoint endpoint1 = new Endpoint(graph, "backward", "*");
- ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes, actuals1);
-
- SWHID src2 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000004");
- Endpoint endpoint2 = new Endpoint(graph, "forward", "*");
- ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes, actuals2);
-
- SWHID src3 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000015");
- Endpoint endpoint3 = new Endpoint(graph, "forward", "*");
- ArrayList actuals3 = (ArrayList) endpoint3.neighbors(new Endpoint.Input(src3)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes, actuals3);
-
- SWHID src4 = new SWHID("swh:1:rel:0000000000000000000000000000000000000019");
- Endpoint endpoint4 = new Endpoint(graph, "backward", "*");
- ArrayList actuals4 = (ArrayList) endpoint4.neighbors(new Endpoint.Input(src4)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes, actuals4);
-
- 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;
- GraphTest.assertEqualsAnyOrder(expectedNodes, actuals5);
- }
-
- @Test
- public void oneNeighbor() {
- SwhBidirectionalGraph graph = getGraph();
-
- SWHID src1 = new SWHID("swh:1:rev:0000000000000000000000000000000000000003");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- 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);
-
- SWHID src2 = new SWHID("swh:1:dir:0000000000000000000000000000000000000017");
- Endpoint endpoint2 = new Endpoint(graph, "forward", "dir:cnt");
- 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);
-
- SWHID src3 = new SWHID("swh:1:dir:0000000000000000000000000000000000000012");
- Endpoint endpoint3 = new Endpoint(graph, "backward", "*");
- 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);
-
- SWHID src4 = new SWHID("swh:1:rev:0000000000000000000000000000000000000009");
- Endpoint endpoint4 = new Endpoint(graph, "backward", "rev:rev");
- 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);
-
- SWHID src5 = new SWHID("swh:1:snp:0000000000000000000000000000000000000020");
- Endpoint endpoint5 = new Endpoint(graph, "backward", "*");
- ArrayList expectedNodes5 = new ArrayList<>();
- expectedNodes5.add(new SWHID(TEST_ORIGIN_ID));
- ArrayList actuals5 = (ArrayList) endpoint5.neighbors(new Endpoint.Input(src5)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes5, actuals5);
- }
-
- @Test
- public void twoNeighbors() {
- SwhBidirectionalGraph graph = getGraph();
-
- SWHID src1 = new SWHID("swh:1:snp:0000000000000000000000000000000000000020");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- 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);
-
- SWHID src2 = new SWHID("swh:1:dir:0000000000000000000000000000000000000008");
- Endpoint endpoint2 = new Endpoint(graph, "forward", "dir:cnt");
- 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);
-
- SWHID src3 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000001");
- Endpoint endpoint3 = new Endpoint(graph, "backward", "*");
- 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);
-
- 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 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() {
- SwhBidirectionalGraph graph = getGraph();
-
- SWHID src1 = new SWHID("swh:1:dir:0000000000000000000000000000000000000008");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- 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);
-
- SWHID src2 = new SWHID("swh:1:rev:0000000000000000000000000000000000000009");
- Endpoint endpoint2 = new Endpoint(graph, "backward", "*");
- 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/SubgraphTest.java b/java/src/test/java/org/softwareheritage/graph/SubgraphTest.java
--- a/java/src/test/java/org/softwareheritage/graph/SubgraphTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/SubgraphTest.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph;
import java.util.*;
diff --git a/java/src/test/java/org/softwareheritage/graph/VisitTest.java b/java/src/test/java/org/softwareheritage/graph/VisitTest.java
deleted file mode 100644
--- a/java/src/test/java/org/softwareheritage/graph/VisitTest.java
+++ /dev/null
@@ -1,408 +0,0 @@
-package org.softwareheritage.graph;
-
-import java.util.ArrayList;
-import java.util.Set;
-import java.util.HashSet;
-
-import org.junit.jupiter.api.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();
- for (SwhPath path : paths) {
- expectedNodes.addAll(path.getPath());
- }
- GraphTest.assertEqualsAnyOrder(expectedNodes, nodes);
- }
-
- @Test
- public void forwardFromRoot() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID(TEST_ORIGIN_ID);
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "*");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000007"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000001"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000004"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000005"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rev:0000000000000000000000000000000000000003",
- "swh:1:dir:0000000000000000000000000000000000000002",
- "swh:1:cnt:0000000000000000000000000000000000000001"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rel:0000000000000000000000000000000000000010",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000007"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rel:0000000000000000000000000000000000000010",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000001"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "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(TEST_ORIGIN_ID, "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(TEST_ORIGIN_ID, "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() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:dir:0000000000000000000000000000000000000012");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "*");
- 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() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:cnt:0000000000000000000000000000000000000004");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "*");
- 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() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID(TEST_ORIGIN_ID);
- Endpoint endpoint1 = new Endpoint(graph, "backward", "*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "backward", "*");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void backwardFromMiddle() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:dir:0000000000000000000000000000000000000012");
- Endpoint endpoint1 = new Endpoint(graph, "backward", "*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "backward", "*");
- 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() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:cnt:0000000000000000000000000000000000000004");
- Endpoint endpoint1 = new Endpoint(graph, "backward", "*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "backward", "*");
- 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", TEST_ORIGIN_ID));
- 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", TEST_ORIGIN_ID));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void forwardSnpToRev() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:snp:0000000000000000000000000000000000000020");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "snp:rev");
- 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(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() {
- SwhBidirectionalGraph graph = getGraph();
- 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(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "rel:rev,rev:rev");
- 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() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:rev:0000000000000000000000000000000000000013");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "rev:*,dir:*");
- 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(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() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:snp:0000000000000000000000000000000000000020");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "snp:*,rev:*");
- 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(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() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:snp:0000000000000000000000000000000000000020");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "");
- 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() {
- SwhBidirectionalGraph graph = getGraph();
- 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(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "backward", "rev:rev,rev:rel");
- 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() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID(TEST_ORIGIN_ID);
- Endpoint endpoint = new Endpoint(graph, "forward", "*");
- ArrayList nodes = (ArrayList) endpoint.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedNodes = new ArrayList();
- expectedNodes.add(new SWHID(TEST_ORIGIN_ID));
- 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() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:rev:0000000000000000000000000000000000000003");
- Endpoint endpoint = new Endpoint(graph, "backward", "rev:*");
- 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
deleted file mode 100644
--- a/java/src/test/java/org/softwareheritage/graph/WalkTest.java
+++ /dev/null
@@ -1,187 +0,0 @@
-package org.softwareheritage.graph;
-
-import java.util.Arrays;
-import java.util.List;
-
-import org.junit.jupiter.api.Assertions;
-import org.junit.jupiter.api.Test;
-import org.softwareheritage.graph.server.Endpoint;
-
-public class WalkTest extends GraphTest {
- @Test
- public void forwardRootToLeaf() {
- SwhBidirectionalGraph graph = getGraph();
- 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);
- Assertions.assertTrue(possibleSolutions.contains(dfsPath));
- Assertions.assertTrue(possibleSolutions.contains(bfsPath));
- }
-
- @Test
- public void forwardLeafToLeaf() {
- SwhBidirectionalGraph graph = getGraph();
- 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;
-
- Assertions.assertEquals(dfsPath, expectedPath);
- Assertions.assertEquals(bfsPath, expectedPath);
- }
-
- @Test
- public void forwardRevToRev() {
- SwhBidirectionalGraph graph = getGraph();
- 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;
-
- Assertions.assertEquals(dfsPath, expectedPath);
- Assertions.assertEquals(bfsPath, expectedPath);
- }
-
- @Test
- public void backwardRevToRev() {
- SwhBidirectionalGraph graph = getGraph();
- 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;
-
- Assertions.assertEquals(dfsPath, expectedPath);
- Assertions.assertEquals(bfsPath, expectedPath);
- }
-
- @Test
- public void backwardCntToFirstSnp() {
- SwhBidirectionalGraph graph = getGraph();
- 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);
- Assertions.assertTrue(possibleSolutions.contains(dfsPath));
- Assertions.assertTrue(possibleSolutions.contains(bfsPath));
- }
-
- @Test
- public void forwardRevToFirstCnt() {
- SwhBidirectionalGraph graph = getGraph();
- 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);
- Assertions.assertTrue(possibleSolutions.contains(dfsPath));
- Assertions.assertTrue(possibleSolutions.contains(bfsPath));
- }
-
- @Test
- public void backwardDirToFirstRel() {
- SwhBidirectionalGraph graph = getGraph();
- 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;
-
- Assertions.assertEquals(dfsPath, expectedPath);
- Assertions.assertEquals(bfsPath, expectedPath);
- }
-}
diff --git a/java/src/test/java/org/softwareheritage/graph/compress/ExtractNodesTest.java b/java/src/test/java/org/softwareheritage/graph/compress/ExtractNodesTest.java
--- a/java/src/test/java/org/softwareheritage/graph/compress/ExtractNodesTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/compress/ExtractNodesTest.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.compress;
import org.apache.commons.codec.digest.DigestUtils;
@@ -5,7 +12,7 @@
import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.io.TempDir;
import org.softwareheritage.graph.GraphTest;
-import org.softwareheritage.graph.Node;
+import org.softwareheritage.graph.SwhType;
import java.io.IOException;
import java.nio.file.Files;
@@ -24,7 +31,7 @@
@Override
public void readEdges(NodeCallback nodeCb, EdgeCallback edgeCb) throws IOException {
// For each node type, write nodes {1..4} as present in the graph
- for (Node.Type type : Node.Type.values()) {
+ for (SwhType type : SwhType.values()) {
for (int i = 1; i <= 4; i++) {
byte[] node = f(type.toString().toLowerCase(), i);
nodeCb.onNode(node);
@@ -82,7 +89,7 @@
// Build ordered set of expected node IDs
TreeSet expectedNodes = new TreeSet<>();
- for (Node.Type type : Node.Type.values()) {
+ for (SwhType type : SwhType.values()) {
for (int i = 1; i <= 4; i++) {
byte[] node = f(type.toString().toLowerCase(), i);
expectedNodes.add(new String(node));
diff --git a/java/src/test/java/org/softwareheritage/graph/compress/ExtractPersonsTest.java b/java/src/test/java/org/softwareheritage/graph/compress/ExtractPersonsTest.java
--- a/java/src/test/java/org/softwareheritage/graph/compress/ExtractPersonsTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/compress/ExtractPersonsTest.java
@@ -1,3 +1,10 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
package org.softwareheritage.graph.compress;
import org.junit.jupiter.api.Assertions;
diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/CountEdgesTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/CountEdgesTest.java
new file mode 100644
--- /dev/null
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/CountEdgesTest.java
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
+package org.softwareheritage.graph.rpc;
+
+import com.google.protobuf.FieldMask;
+import io.grpc.Status;
+import io.grpc.StatusRuntimeException;
+import org.junit.jupiter.api.Test;
+import org.softwareheritage.graph.SWHID;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+public class CountEdgesTest extends TraversalServiceTest {
+ private TraversalRequest.Builder getTraversalRequestBuilder(SWHID src) {
+ return TraversalRequest.newBuilder().addSrc(src.toString());
+ }
+
+ @Test
+ public void testSwhidErrors() {
+ StatusRuntimeException thrown;
+ thrown = assertThrows(StatusRuntimeException.class, () -> client
+ .countEdges(TraversalRequest.newBuilder().addSrc(fakeSWHID("cnt", 404).toString()).build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.countEdges(
+ TraversalRequest.newBuilder().addSrc("swh:1:lol:0000000000000000000000000000000000000001").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.countEdges(
+ TraversalRequest.newBuilder().addSrc("swh:1:cnt:000000000000000000000000000000000000000z").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ @Test
+ public void forwardFromRoot() {
+ CountResponse actual = client.countEdges(getTraversalRequestBuilder(new SWHID(TEST_ORIGIN_ID)).build());
+ assertEquals(13, actual.getCount());
+ }
+
+ @Test
+ public void forwardFromMiddle() {
+ CountResponse actual = client.countEdges(getTraversalRequestBuilder(fakeSWHID("dir", 12)).build());
+ assertEquals(7, actual.getCount());
+ }
+
+ @Test
+ public void forwardRelRev() {
+ CountResponse actual = client
+ .countEdges(getTraversalRequestBuilder(fakeSWHID("rel", 10)).setEdges("rel:rev,rev:rev").build());
+ assertEquals(2, actual.getCount());
+ }
+
+ @Test
+ public void backwardFromMiddle() {
+ CountResponse actual = client.countEdges(
+ getTraversalRequestBuilder(fakeSWHID("dir", 12)).setDirection(GraphDirection.BACKWARD).build());
+ assertEquals(3, actual.getCount());
+ }
+
+ @Test
+ public void backwardFromLeaf() {
+ CountResponse actual = client.countEdges(
+ getTraversalRequestBuilder(fakeSWHID("cnt", 4)).setDirection(GraphDirection.BACKWARD).build());
+ assertEquals(12, actual.getCount());
+ }
+
+ @Test
+ public void backwardRevToRevRevToRel() {
+ CountResponse actual = client.countEdges(getTraversalRequestBuilder(fakeSWHID("rev", 3))
+ .setEdges("rev:rev,rev:rel").setDirection(GraphDirection.BACKWARD).build());
+ assertEquals(5, actual.getCount());
+ }
+
+ @Test
+ public void testWithEmptyMask() {
+ CountResponse actual = client.countEdges(
+ getTraversalRequestBuilder(fakeSWHID("dir", 12)).setMask(FieldMask.getDefaultInstance()).build());
+ assertEquals(7, actual.getCount());
+ }
+}
diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/CountNodesTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/CountNodesTest.java
new file mode 100644
--- /dev/null
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/CountNodesTest.java
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
+package org.softwareheritage.graph.rpc;
+
+import com.google.protobuf.FieldMask;
+import io.grpc.Status;
+import io.grpc.StatusRuntimeException;
+import org.junit.jupiter.api.Test;
+import org.softwareheritage.graph.SWHID;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+public class CountNodesTest extends TraversalServiceTest {
+ private TraversalRequest.Builder getTraversalRequestBuilder(SWHID src) {
+ return TraversalRequest.newBuilder().addSrc(src.toString());
+ }
+
+ @Test
+ public void testSwhidErrors() {
+ StatusRuntimeException thrown;
+ thrown = assertThrows(StatusRuntimeException.class, () -> client
+ .countNodes(TraversalRequest.newBuilder().addSrc(fakeSWHID("cnt", 404).toString()).build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.countNodes(
+ TraversalRequest.newBuilder().addSrc("swh:1:lol:0000000000000000000000000000000000000001").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.countNodes(
+ TraversalRequest.newBuilder().addSrc("swh:1:cnt:000000000000000000000000000000000000000z").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ @Test
+ public void forwardFromRoot() {
+ CountResponse actual = client.countNodes(getTraversalRequestBuilder(new SWHID(TEST_ORIGIN_ID)).build());
+ assertEquals(12, actual.getCount());
+ }
+
+ @Test
+ public void forwardFromMiddle() {
+ CountResponse actual = client.countNodes(getTraversalRequestBuilder(fakeSWHID("dir", 12)).build());
+ assertEquals(8, actual.getCount());
+ }
+
+ @Test
+ public void forwardRelRev() {
+ CountResponse actual = client
+ .countNodes(getTraversalRequestBuilder(fakeSWHID("rel", 10)).setEdges("rel:rev,rev:rev").build());
+ assertEquals(3, actual.getCount());
+ }
+
+ @Test
+ public void backwardFromMiddle() {
+ CountResponse actual = client.countNodes(
+ getTraversalRequestBuilder(fakeSWHID("dir", 12)).setDirection(GraphDirection.BACKWARD).build());
+ assertEquals(4, actual.getCount());
+ }
+
+ @Test
+ public void backwardFromLeaf() {
+ CountResponse actual = client.countNodes(
+ getTraversalRequestBuilder(fakeSWHID("cnt", 4)).setDirection(GraphDirection.BACKWARD).build());
+ assertEquals(11, actual.getCount());
+ }
+
+ @Test
+ public void backwardRevToRevRevToRel() {
+ CountResponse actual = client.countNodes(getTraversalRequestBuilder(fakeSWHID("rev", 3))
+ .setEdges("rev:rev,rev:rel").setDirection(GraphDirection.BACKWARD).build());
+ assertEquals(6, actual.getCount());
+ }
+
+ @Test
+ public void testWithEmptyMask() {
+ CountResponse actual = client.countNodes(
+ getTraversalRequestBuilder(fakeSWHID("dir", 12)).setMask(FieldMask.getDefaultInstance()).build());
+ assertEquals(8, actual.getCount());
+ }
+}
diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java
new file mode 100644
--- /dev/null
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java
@@ -0,0 +1,210 @@
+/*
+ * Copyright (c) 2022 The Software Heritage developers
+ * See the AUTHORS file at the top-level directory of this distribution
+ * License: GNU General Public License version 3, or any later version
+ * See top-level LICENSE file for more information
+ */
+
+package org.softwareheritage.graph.rpc;
+
+import io.grpc.Status;
+import io.grpc.StatusRuntimeException;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+import org.softwareheritage.graph.SWHID;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+public class FindPathBetweenTest extends TraversalServiceTest {
+ private FindPathBetweenRequest.Builder getRequestBuilder(SWHID src, SWHID dst) {
+ return FindPathBetweenRequest.newBuilder().addSrc(src.toString()).addDst(dst.toString());
+ }
+
+ @Test
+ public void testSwhidErrors() {
+ StatusRuntimeException thrown;
+ thrown = assertThrows(StatusRuntimeException.class, () -> client
+ .findPathBetween(FindPathBetweenRequest.newBuilder().addSrc(fakeSWHID("cnt", 404).toString()).build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest
+ .newBuilder().addSrc("swh:1:lol:0000000000000000000000000000000000000001").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest
+ .newBuilder().addSrc("swh:1:cnt:000000000000000000000000000000000000000z").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class,
+ () -> client.findPathBetween(FindPathBetweenRequest.newBuilder().addSrc(TEST_ORIGIN_ID)
+ .addDst("swh:1:cnt:000000000000000000000000000000000000000z").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ @Test
+ public void testEdgeErrors() {
+ StatusRuntimeException thrown;
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest
+ .newBuilder().addSrc(TEST_ORIGIN_ID).addDst(TEST_ORIGIN_ID).setEdges("batracien:reptile").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ // Test path between ori 1 and cnt 4 (forward graph)
+ @Test
+ public void forwardRootToLeaf() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(new SWHID(TEST_ORIGIN_ID), fakeSWHID("cnt", 4)).build()));
+ List expected = List.of(new SWHID(TEST_ORIGIN_ID), fakeSWHID("snp", 20), fakeSWHID("rev", 9),
+ fakeSWHID("dir", 8), fakeSWHID("dir", 6), fakeSWHID("cnt", 4));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Test path between rev 18 and rev 3 (forward graph)
+ @Test
+ public void forwardRevToRev() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(fakeSWHID("rev", 18), fakeSWHID("rev", 3)).build()));
+ List expected = List.of(fakeSWHID("rev", 18), fakeSWHID("rev", 13), fakeSWHID("rev", 9),
+ fakeSWHID("rev", 3));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Test path between rev 3 and rev 18 (backward graph)
+ @Test
+ public void backwardRevToRev() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(fakeSWHID("rev", 3), fakeSWHID("rev", 18))
+ .setDirection(GraphDirection.BACKWARD).build()));
+ List expected = List.of(fakeSWHID("rev", 3), fakeSWHID("rev", 9), fakeSWHID("rev", 13),
+ fakeSWHID("rev", 18));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Test path between cnt 4 and itself (forward graph)
+ @Test
+ public void forwardCntToItself() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("cnt", 4)).build()));
+ List expected = List.of(fakeSWHID("cnt", 4));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Start from ori and rel 19 and find cnt 14 or cnt 7 (forward graph)
+ @Test
+ public void forwardMultipleSourcesDest() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 14))
+ .addSrc(TEST_ORIGIN_ID).addDst(fakeSWHID("cnt", 7).toString()).build()));
+ List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17),
+ fakeSWHID("cnt", 14));
+ }
+
+ // Start from cnt 4 and cnt 11 and find rev 13 or rev 9 (backward graph)
+ @Test
+ public void backwardMultipleSourcesDest() {
+ ArrayList actual = getSWHIDs(client.findPathBetween(
+ getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("rev", 13)).setDirection(GraphDirection.BACKWARD)
+ .addSrc(fakeSWHID("cnt", 11).toString()).addDst(fakeSWHID("rev", 9).toString()).build()));
+ List expected = List.of(fakeSWHID("cnt", 11), fakeSWHID("dir", 12), fakeSWHID("rev", 13));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Start from all directories and find the origin (backward graph)
+ @Test
+ public void backwardMultipleSourcesAllDirToOri() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(fakeSWHID("dir", 2), new SWHID(TEST_ORIGIN_ID))
+ .addSrc(fakeSWHID("dir", 6).toString()).addSrc(fakeSWHID("dir", 8).toString())
+ .addSrc(fakeSWHID("dir", 12).toString()).addSrc(fakeSWHID("dir", 16).toString())
+ .addSrc(fakeSWHID("dir", 17).toString()).setDirection(GraphDirection.BACKWARD).build()));
+ List expected = List.of(fakeSWHID("dir", 8), fakeSWHID("rev", 9), fakeSWHID("snp", 20),
+ new SWHID(TEST_ORIGIN_ID));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Start from cnt 4 and find any rev (backward graph)
+ @Test
+ public void backwardCntToAnyRev() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("rev", 3))
+ .addDst(fakeSWHID("rev", 9).toString()).addDst(fakeSWHID("rev", 13).toString())
+ .addDst(fakeSWHID("rev", 18).toString()).setDirection(GraphDirection.BACKWARD).build()));
+ List expected = List.of(fakeSWHID("cnt", 4), fakeSWHID("dir", 6), fakeSWHID("dir", 8),
+ fakeSWHID("rev", 9));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Impossible path between rev 9 and cnt 14
+ @Test
+ public void forwardImpossiblePath() {
+ StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> {
+ client.findPathBetween(getRequestBuilder(fakeSWHID("rev", 9), fakeSWHID("cnt", 14)).build());
+ });
+ Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode());
+
+ // Reverse direction
+ thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> {
+ client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 14), fakeSWHID("rev", 9))
+ .setDirection(GraphDirection.BACKWARD).build());
+ });
+ Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode());
+ }
+
+ // Common ancestor between cnt 4 and cnt 15 : rev 18
+ @Test
+ public void commonAncestorBackwardBackward() {
+ Path p = client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("cnt", 15))
+ .setDirection(GraphDirection.BACKWARD).setDirectionReverse(GraphDirection.BACKWARD).build());
+ ArrayList actual = getSWHIDs(p);
+ SWHID expected = fakeSWHID("rev", 18);
+ Assertions.assertEquals(expected, actual.get(p.getMidpointIndex()));
+ }
+
+ // Common descendant between rev 13 and rev 3 : cnt 1 (with rev:dir,dir:dir,dir:cnt)
+ @Test
+ public void commonDescendantForwardForward() {
+ Path p = client.findPathBetween(
+ getRequestBuilder(fakeSWHID("rev", 13), fakeSWHID("rev", 3)).setDirection(GraphDirection.FORWARD)
+ .setDirectionReverse(GraphDirection.FORWARD).setEdges("rev:dir,dir:dir,dir:cnt").build());
+ ArrayList