diff --git a/java/pom.xml b/java/pom.xml --- a/java/pom.xml +++ b/java/pom.xml @@ -28,6 +28,16 @@ 5.7.0 test + + org.junit.vintage + junit-vintage-engine + 5.7.0 + + + junit + junit + 4.12 + org.junit.jupiter junit-jupiter-engine @@ -260,15 +270,72 @@ - - - - + + maven-source-plugin + 2.1.1 + + + bundle-sources + package + + jar-no-fork + test-jar-no-fork + + + + org.apache.maven.plugins maven-javadoc-plugin - 3.1.1 + 3.3.1 + + + resource-bundles + package + + + resource-bundle + + + test-resource-bundle + + + false + + + + javadoc-jar + package + + jar + + + + + true + + it.unimi.dsi:webgraph-big:* + + + https://webgraph.di.unimi.it/docs-big/ + https://dsiutils.di.unimi.it/docs/ + https://fastutil.di.unimi.it/docs/ + https://law.di.unimi.it/software/law-docs/ + + + + implSpec + a + Implementation Requirements: + + + implNote + a + Implementation Note: + + + - + diff --git a/java/src/main/java/org/softwareheritage/graph/BidirectionalImmutableGraph.java b/java/src/main/java/org/softwareheritage/graph/BidirectionalImmutableGraph.java --- a/java/src/main/java/org/softwareheritage/graph/BidirectionalImmutableGraph.java +++ b/java/src/main/java/org/softwareheritage/graph/BidirectionalImmutableGraph.java @@ -21,7 +21,7 @@ * @param forwardGraph The graph in the forward direction * @param backwardGraph The graph in the backward direction */ - protected BidirectionalImmutableGraph(ImmutableGraph forwardGraph, ImmutableGraph backwardGraph) { + public BidirectionalImmutableGraph(ImmutableGraph forwardGraph, ImmutableGraph backwardGraph) { this.forwardGraph = forwardGraph; this.backwardGraph = backwardGraph; } diff --git a/java/src/main/java/org/softwareheritage/graph/Entry.java b/java/src/main/java/org/softwareheritage/graph/Entry.java --- a/java/src/main/java/org/softwareheritage/graph/Entry.java +++ b/java/src/main/java/org/softwareheritage/graph/Entry.java @@ -7,15 +7,15 @@ import com.fasterxml.jackson.databind.PropertyNamingStrategy; public class Entry { - private Graph graph; + private SwhBidirectionalGraph graph; public void load_graph(String graphBasename) throws IOException { System.err.println("Loading graph " + graphBasename + " ..."); - this.graph = Graph.loadMapped(graphBasename); + this.graph = SwhBidirectionalGraph.loadMapped(graphBasename); System.err.println("Graph loaded."); } - public Graph get_graph() { + public SwhBidirectionalGraph get_graph() { return graph.copy(); } @@ -69,11 +69,11 @@ } public class QueryHandler { - Graph graph; + SwhBidirectionalGraph graph; BufferedWriter out; String clientFIFO; - public QueryHandler(Graph graph, String clientFIFO) { + public QueryHandler(SwhBidirectionalGraph graph, String clientFIFO) { this.graph = graph; this.clientFIFO = clientFIFO; this.out = null; diff --git a/java/src/main/java/org/softwareheritage/graph/Graph.java b/java/src/main/java/org/softwareheritage/graph/Graph.java deleted file mode 100644 --- a/java/src/main/java/org/softwareheritage/graph/Graph.java +++ /dev/null @@ -1,304 +0,0 @@ -package org.softwareheritage.graph; - -import it.unimi.dsi.big.webgraph.ImmutableGraph; -import it.unimi.dsi.big.webgraph.LazyLongIterator; -import it.unimi.dsi.logging.ProgressLogger; -import org.softwareheritage.graph.maps.NodeIdMap; -import org.softwareheritage.graph.maps.NodeTypesMap; - -import java.io.IOException; - -/** - * Main class storing the compressed graph and node id mappings. - *

- * The compressed graph is stored using the WebGraph - * ecosystem. Additional mappings are necessary because Software Heritage uses string based persistent - * identifiers (SWHID) while WebGraph uses integers internally. These two mappings (long id - * ↔ SWHID) are used for the input (users refer to the graph using SWHID) and the output - * (convert back to SWHID for users results). However, since graph traversal can be restricted - * depending on the node type (see {@link AllowedEdges}), a long id → node type map is stored - * as well to avoid a full SWHID lookup. - * - * @author The Software Heritage developers - * @see org.softwareheritage.graph.AllowedEdges - * @see org.softwareheritage.graph.maps.NodeIdMap - * @see org.softwareheritage.graph.maps.NodeTypesMap - */ - -public class Graph extends ImmutableGraph { - /** - * Bidirectional graph containing two compressed {@link it.unimi.dsi.big.webgraph.BVGraph} one for - * each direction - */ - BidirectionalImmutableGraph graph; - - /** Path and basename of the compressed graph */ - String path; - /** Mapping long id ↔ SWHIDs */ - NodeIdMap nodeIdMap; - /** Mapping long id → node types */ - NodeTypesMap nodeTypesMap; - - /** - * Constructor. - * - * @param path path and basename of the compressed graph to load - */ - - private Graph(String path) throws IOException { - loadInternal(path, null, LoadMethod.MAPPED); - } - - /** - * Loading mechanisms - */ - - enum LoadMethod { - MEMORY, MAPPED, OFFLINE, - } - - protected Graph loadInternal(String path, ProgressLogger pl, LoadMethod method) throws IOException { - this.path = path; - ImmutableGraph direct = null; - ImmutableGraph transposed = null; - if (method == LoadMethod.MEMORY) { - direct = ImmutableGraph.load(path, pl); - transposed = ImmutableGraph.load(path + "-transposed", pl); - } else if (method == LoadMethod.MAPPED) { - direct = ImmutableGraph.load(path, pl); - transposed = ImmutableGraph.loadMapped(path + "-transposed", pl); - } else if (method == LoadMethod.OFFLINE) { - direct = ImmutableGraph.loadOffline(path, pl); - transposed = ImmutableGraph.loadOffline(path + "-transposed", pl); - } - this.graph = new BidirectionalImmutableGraph(direct, transposed); - this.nodeTypesMap = new NodeTypesMap(path); - this.nodeIdMap = new NodeIdMap(path, numNodes()); - return this; - } - - protected Graph() { - } - - public static Graph load(String path, ProgressLogger pl) throws IOException { - return new Graph().loadInternal(path, pl, LoadMethod.MEMORY); - } - - public static Graph loadMapped(String path, ProgressLogger pl) throws IOException { - return new Graph().loadInternal(path, pl, LoadMethod.MAPPED); - } - - public static Graph loadOffline(String path, ProgressLogger pl) throws IOException { - return new Graph().loadInternal(path, null, LoadMethod.OFFLINE); - } - - public static Graph load(String path) throws IOException { - return new Graph().loadInternal(path, null, LoadMethod.MEMORY); - } - - public static Graph loadMapped(String path) throws IOException { - return new Graph().loadInternal(path, null, LoadMethod.MAPPED); - } - - public static Graph loadOffline(String path) throws IOException { - return new Graph().loadInternal(path, null, LoadMethod.OFFLINE); - } - - /** - * Constructor used for copy() - */ - protected Graph(BidirectionalImmutableGraph graph, String path, NodeIdMap nodeIdMap, NodeTypesMap nodeTypesMap) { - this.graph = graph; - this.path = path; - this.nodeIdMap = nodeIdMap; - this.nodeTypesMap = nodeTypesMap; - } - - /** - * Return a flyweight copy of the graph. - */ - @Override - public Graph copy() { - return new Graph(this.graph.copy(), this.path, this.nodeIdMap, this.nodeTypesMap); - } - - @Override - public boolean randomAccess() { - return graph.randomAccess(); - } - - /** - * Return a transposed version of the graph. - */ - public Graph transpose() { - return new Graph(this.graph.transpose(), this.path, this.nodeIdMap, this.nodeTypesMap); - } - - /** - * Return a symmetric version of the graph. - */ - public Graph symmetrize() { - return new Graph(this.graph.symmetrize(), this.path, this.nodeIdMap, this.nodeTypesMap); - } - - /** - * Cleans up graph resources after use. - */ - public void cleanUp() throws IOException { - nodeIdMap.close(); - } - - /** - * Returns number of nodes in the graph. - * - * @return number of nodes in the graph - */ - @Override - public long numNodes() { - return graph.numNodes(); - } - - /** - * Returns number of edges in the graph. - * - * @return number of edges in the graph - */ - @Override - public long numArcs() { - return graph.numArcs(); - } - - /** - * Returns lazy iterator of successors of a node. - * - * @param nodeId node specified as a long id - * @return lazy iterator of successors of the node, specified as a - * WebGraph LazyLongIterator - */ - @Override - public LazyLongIterator successors(long nodeId) { - return graph.successors(nodeId); - } - - /** - * Returns lazy iterator of successors of a node while following a specific set of edge types. - * - * @param nodeId node specified as a long id - * @param allowedEdges the specification of which edges can be traversed - * @return lazy iterator of successors of the node, specified as a - * WebGraph LazyLongIterator - */ - public LazyLongIterator successors(long nodeId, AllowedEdges allowedEdges) { - if (allowedEdges.restrictedTo == null) { - // All edges are allowed, bypass edge check - return this.successors(nodeId); - } else { - LazyLongIterator allSuccessors = this.successors(nodeId); - Graph thisGraph = this; - return new LazyLongIterator() { - @Override - public long nextLong() { - long neighbor; - while ((neighbor = allSuccessors.nextLong()) != -1) { - if (allowedEdges.isAllowed(thisGraph.getNodeType(nodeId), thisGraph.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; - } - }; - } - } - - /** - * Returns the outdegree of a node. - * - * @param nodeId node specified as a long id - * @return outdegree of a node - */ - @Override - public long outdegree(long nodeId) { - return graph.outdegree(nodeId); - } - - /** - * Returns lazy iterator of predecessors of a node. - * - * @param nodeId node specified as a long id - * @return lazy iterator of predecessors of the node, specified as a - * WebGraph LazyLongIterator - */ - public LazyLongIterator predecessors(long nodeId) { - return graph.predecessors(nodeId); - } - - /** - * Returns the indegree of a node. - * - * @param nodeId node specified as a long id - * @return indegree of a node - */ - public long indegree(long nodeId) { - return graph.indegree(nodeId); - } - - /** - * Returns the underlying BidirectionalImmutableGraph. - * - * @return WebGraph ImmutableGraph - */ - public ImmutableGraph getGraph() { - return this.graph; - } - - /** - * Returns the graph full path. - * - * @return graph full path - */ - public String getPath() { - return path; - } - - /** - * Converts {@link SWHID} node to long. - * - * @param swhid node specified as a {@link SWHID} - * @return internal long node id - * @see SWHID - */ - public long getNodeId(SWHID swhid) { - return nodeIdMap.getNodeId(swhid); - } - - /** - * Converts long id node to {@link SWHID}. - * - * @param nodeId node specified as a long id - * @return external SWHID - * @see SWHID - */ - public SWHID getSWHID(long nodeId) { - return nodeIdMap.getSWHID(nodeId); - } - - /** - * Returns node type. - * - * @param nodeId node specified as a long id - * @return corresponding node type - * @see org.softwareheritage.graph.Node.Type - */ - public Node.Type getNodeType(long nodeId) { - return nodeTypesMap.getType(nodeId); - } -} diff --git a/java/src/main/java/org/softwareheritage/graph/NodesFiltering.java b/java/src/main/java/org/softwareheritage/graph/NodesFiltering.java --- a/java/src/main/java/org/softwareheritage/graph/NodesFiltering.java +++ b/java/src/main/java/org/softwareheritage/graph/NodesFiltering.java @@ -3,7 +3,7 @@ import java.util.ArrayList; /** - *

NodesFiltering

+ * NodesFiltering *

* class that manages the filtering of nodes that have been returned after a visit of the graph. * parameterized by a string that represents either no filtering (*) or a set of node types. @@ -95,7 +95,7 @@ * * */ - public ArrayList filterByNodeTypes(ArrayList nodeIds, Graph g) { + public ArrayList filterByNodeTypes(ArrayList nodeIds, SwhBidirectionalGraph g) { ArrayList filteredNodes = new ArrayList(); for (Long node : nodeIds) { if (this.typeIsAllowed(g.getNodeType(node))) { 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 @@ -7,7 +7,7 @@ import java.util.NoSuchElementException; public class Subgraph extends ImmutableGraph { - private final Graph underlyingGraph; + private final SwhBidirectionalGraph underlyingGraph; public final AllowedNodes allowedNodeTypes; private long nodeCount = -1; @@ -16,7 +16,7 @@ * Constructor. * */ - public Subgraph(Graph underlyingGraph, AllowedNodes allowedNodeTypes) { + public Subgraph(SwhBidirectionalGraph underlyingGraph, AllowedNodes allowedNodeTypes) { this.underlyingGraph = underlyingGraph.copy(); this.allowedNodeTypes = allowedNodeTypes; } diff --git a/java/src/main/java/org/softwareheritage/graph/SwhBidirectionalGraph.java b/java/src/main/java/org/softwareheritage/graph/SwhBidirectionalGraph.java new file mode 100644 --- /dev/null +++ b/java/src/main/java/org/softwareheritage/graph/SwhBidirectionalGraph.java @@ -0,0 +1,166 @@ +package org.softwareheritage.graph; + +import it.unimi.dsi.big.webgraph.labelling.ArcLabelledNodeIterator; +import it.unimi.dsi.logging.ProgressLogger; + +import java.io.IOException; +import java.io.InputStream; + +/** + * Class representing the compressed Software Heritage graph in both directions (forward and + * backward). + * + * This class uses the {@link BidirectionalImmutableGraph} class internally to implement the + * backward equivalent of graph operations ({@link SwhBidirectionalGraph#indegree(long)}, + * {@link SwhBidirectionalGraph#predecessors(long)}, etc.) by holding a reference to two + * {@link SwhUnidirectionalGraph} (a forward graph and a backward graph). + * + * Both graphs share their graph properties in memory by storing references to the same + * {@link SwhGraphProperties} object. + * + * @author The Software Heritage developers + * @see SwhUnidirectionalGraph + */ + +public class SwhBidirectionalGraph extends BidirectionalImmutableGraph implements SwhGraph { + /** Property data of the graph (id/type mappings etc.) */ + private final SwhGraphProperties properties; + + private final SwhUnidirectionalGraph forwardGraph; + private final SwhUnidirectionalGraph backwardGraph; + + public SwhBidirectionalGraph(SwhUnidirectionalGraph forwardGraph, SwhUnidirectionalGraph backwardGraph, + SwhGraphProperties properties) { + super(forwardGraph, backwardGraph); + this.forwardGraph = forwardGraph; + this.backwardGraph = backwardGraph; + this.properties = properties; + } + + private SwhBidirectionalGraph(BidirectionalImmutableGraph graph, SwhGraphProperties properties) { + super(graph.getForwardGraph(), graph.getBackwardGraph()); + this.forwardGraph = (SwhUnidirectionalGraph) graph.getForwardGraph(); + this.backwardGraph = (SwhUnidirectionalGraph) graph.getBackwardGraph(); + this.properties = properties; + } + + public static SwhBidirectionalGraph load(LoadMethod method, String path, InputStream is, ProgressLogger pl) + throws IOException { + SwhUnidirectionalGraph forward = SwhUnidirectionalGraph.loadGraphOnly(method, path, is, pl); + SwhUnidirectionalGraph backward = SwhUnidirectionalGraph.loadGraphOnly(method, path + "-transposed", is, pl); + SwhGraphProperties properties = SwhGraphProperties.load(path); + forward.setProperties(properties); + backward.setProperties(properties); + return new SwhBidirectionalGraph(forward, backward, properties); + } + + public static SwhBidirectionalGraph loadLabelled(LoadMethod method, String path, InputStream is, ProgressLogger pl) + throws IOException { + SwhUnidirectionalGraph forward = SwhUnidirectionalGraph.loadLabelledGraphOnly(method, path, is, pl); + SwhUnidirectionalGraph backward = SwhUnidirectionalGraph.loadLabelledGraphOnly(method, path + "-transposed", is, + pl); + SwhGraphProperties properties = SwhGraphProperties.load(path); + forward.setProperties(properties); + backward.setProperties(properties); + return new SwhBidirectionalGraph(forward, backward, properties); + } + + // loadXXX methods from ImmutableGraph + public static SwhBidirectionalGraph load(String path, ProgressLogger pl) throws IOException { + return load(LoadMethod.STANDARD, path, null, pl); + } + public static SwhBidirectionalGraph load(String path) throws IOException { + return load(LoadMethod.STANDARD, path, null, null); + } + public static SwhBidirectionalGraph loadMapped(String path, ProgressLogger pl) throws IOException { + return load(LoadMethod.MAPPED, path, null, pl); + } + public static SwhBidirectionalGraph loadMapped(String path) throws IOException { + return load(LoadMethod.MAPPED, path, null, null); + } + public static SwhBidirectionalGraph loadOffline(String path, ProgressLogger pl) throws IOException { + return load(LoadMethod.OFFLINE, path, null, pl); + } + public static SwhBidirectionalGraph loadOffline(String path) throws IOException { + return load(LoadMethod.OFFLINE, path, null, null); + } + + // Labelled versions of the loadXXX methods from ImmutableGraph + public static SwhBidirectionalGraph loadLabelled(String path, ProgressLogger pl) throws IOException { + return loadLabelled(LoadMethod.STANDARD, path, null, pl); + } + public static SwhBidirectionalGraph loadLabelled(String path) throws IOException { + return loadLabelled(LoadMethod.STANDARD, path, null, null); + } + public static SwhBidirectionalGraph loadLabelledMapped(String path, ProgressLogger pl) throws IOException { + return loadLabelled(LoadMethod.MAPPED, path, null, pl); + } + public static SwhBidirectionalGraph loadLabelledMapped(String path) throws IOException { + return loadLabelled(LoadMethod.MAPPED, path, null, null); + } + public static SwhBidirectionalGraph loadLabelledOffline(String path, ProgressLogger pl) throws IOException { + return loadLabelled(LoadMethod.OFFLINE, path, null, pl); + } + public static SwhBidirectionalGraph loadLabelledOffline(String path) throws IOException { + return loadLabelled(LoadMethod.OFFLINE, path, null, null); + } + + @Override + public SwhBidirectionalGraph copy() { + return new SwhBidirectionalGraph(forwardGraph, backwardGraph, this.properties); + } + + @Override + public SwhBidirectionalGraph transpose() { + return new SwhBidirectionalGraph(super.transpose(), this.properties); + } + + @Override + public SwhBidirectionalGraph symmetrize() { + return new SwhBidirectionalGraph(super.symmetrize(), this.properties); + } + + public SwhUnidirectionalGraph getForwardGraph() { + return this.forwardGraph; + } + + public SwhUnidirectionalGraph getBackwardGraph() { + return this.backwardGraph; + } + + /** + * Returns a *labelled* lazy iterator over the successors of a given node. The iteration terminates + * when -1 is returned. + */ + public ArcLabelledNodeIterator.LabelledArcIterator labelledSuccessors(long x) { + return forwardGraph.labelledSuccessors(x); + } + + /** + * Returns a *labelled* lazy iterator over the predecessors of a given node. The iteration + * terminates when -1 is returned. + */ + public ArcLabelledNodeIterator.LabelledArcIterator labelledPredecessors(long x) { + return backwardGraph.labelledSuccessors(x); + } + + public void close() throws IOException { + this.properties.close(); + } + + public String getPath() { + return properties.getPath(); + } + + public long getNodeId(SWHID swhid) { + return properties.getNodeId(swhid); + } + + public SWHID getSWHID(long nodeId) { + return properties.getSWHID(nodeId); + } + + public Node.Type getNodeType(long nodeId) { + return properties.getNodeType(nodeId); + } +} diff --git a/java/src/main/java/org/softwareheritage/graph/SwhGraph.java b/java/src/main/java/org/softwareheritage/graph/SwhGraph.java new file mode 100644 --- /dev/null +++ b/java/src/main/java/org/softwareheritage/graph/SwhGraph.java @@ -0,0 +1,47 @@ +package org.softwareheritage.graph; + +import java.io.IOException; + +/** + * Common interface for SWH graph classes. + */ +public interface SwhGraph { + /** + * Cleans up graph resources after use. + */ + void close() throws IOException; + + /** + * Converts {@link SWHID} node to long. + * + * @param swhid node specified as a {@link SWHID} + * @return internal long node id + * @see SWHID + */ + long getNodeId(SWHID swhid); + + /** + * Converts long id node to {@link SWHID}. + * + * @param nodeId node specified as a long id + * @return external SWHID + * @see SWHID + */ + SWHID getSWHID(long nodeId); + + /** + * Returns node type. + * + * @param nodeId node specified as a long id + * @return corresponding node type + * @see Node.Type + */ + Node.Type getNodeType(long nodeId); + + /** + * Returns the graph full path. + * + * @return graph full path + */ + String getPath(); +} diff --git a/java/src/main/java/org/softwareheritage/graph/SwhGraphProperties.java b/java/src/main/java/org/softwareheritage/graph/SwhGraphProperties.java new file mode 100644 --- /dev/null +++ b/java/src/main/java/org/softwareheritage/graph/SwhGraphProperties.java @@ -0,0 +1,85 @@ +package org.softwareheritage.graph; + +import org.softwareheritage.graph.maps.NodeIdMap; +import org.softwareheritage.graph.maps.NodeTypesMap; + +import java.io.IOException; + +/** + * This objects contains SWH graph properties such as node labels. + * + * Some property mappings are necessary because Software Heritage uses string based persistent + * identifiers (SWHID) while WebGraph uses integers internally. + * + * The two node ID mappings (long id ↔ SWHID) are used for the input (users refer to the graph + * using SWHID) and the output (convert back to SWHID for users results). + * + * Since graph traversal can be restricted depending on the node type (see {@link AllowedEdges}), a + * long id → node type map is stored as well to avoid a full SWHID lookup. + * + * @see NodeIdMap + * @see NodeTypesMap + */ +public class SwhGraphProperties { + /** Path and basename of the compressed graph */ + String path; + /** Mapping long id ↔ SWHIDs */ + NodeIdMap nodeIdMap; + /** Mapping long id → node types */ + NodeTypesMap nodeTypesMap; + + protected SwhGraphProperties(String path, NodeIdMap nodeIdMap, NodeTypesMap nodeTypesMap) { + this.path = path; + this.nodeIdMap = nodeIdMap; + this.nodeTypesMap = nodeTypesMap; + } + + public static SwhGraphProperties load(String path) throws IOException { + return new SwhGraphProperties(path, new NodeIdMap(path), new NodeTypesMap(path)); + } + + /** + * Cleans up graph resources after use. + */ + public void close() throws IOException { + this.nodeIdMap.close(); + } + + public String getPath() { + return path; + } + + /** + * Converts {@link SWHID} node to long. + * + * @param swhid node specified as a {@link SWHID} + * @return internal long node id + * @see SWHID + */ + public long getNodeId(SWHID swhid) { + return nodeIdMap.getNodeId(swhid); + } + + /** + * Converts long id node to {@link SWHID}. + * + * @param nodeId node specified as a long id + * @return external SWHID + * @see SWHID + */ + public SWHID getSWHID(long nodeId) { + return nodeIdMap.getSWHID(nodeId); + } + + /** + * Returns node type. + * + * @param nodeId node specified as a long id + * @return corresponding node type + * @see Node.Type + */ + public Node.Type getNodeType(long nodeId) { + return nodeTypesMap.getType(nodeId); + } +} diff --git a/java/src/main/java/org/softwareheritage/graph/SwhUnidirectionalGraph.java b/java/src/main/java/org/softwareheritage/graph/SwhUnidirectionalGraph.java new file mode 100644 --- /dev/null +++ b/java/src/main/java/org/softwareheritage/graph/SwhUnidirectionalGraph.java @@ -0,0 +1,221 @@ +package org.softwareheritage.graph; + +import it.unimi.dsi.big.webgraph.ImmutableGraph; +import it.unimi.dsi.big.webgraph.LazyLongIterator; +import it.unimi.dsi.big.webgraph.labelling.ArcLabelledNodeIterator; +import it.unimi.dsi.big.webgraph.labelling.BitStreamArcLabelledImmutableGraph; +import it.unimi.dsi.logging.ProgressLogger; +import it.unimi.dsi.big.webgraph.labelling.ArcLabelledImmutableGraph; + +import java.io.IOException; +import java.io.InputStream; + +/** + * Class representing the compressed Software Heritage graph in a single direction. + *

+ * The compressed graph is stored using the WebGraph + * framework. This class contains an {@link ImmutableGraph} representing the graph itself, as well + * as a reference to the object containing the graph properties (e.g. node labels). Optionally, + * arc labels (properties stored on the graph edges) can also be loaded with the + * loadLabelled...() function family. + * + * @author The Software Heritage developers + * @see SwhGraphProperties + * @see SwhUnidirectionalGraph + */ + +public class SwhUnidirectionalGraph extends ImmutableGraph implements SwhGraph { + /** Underlying ImmutableGraph */ + private final ImmutableGraph graph; + + /** Labelled ImmutableGraph, null if labels are not loaded */ + private ArcLabelledImmutableGraph labelledGraph; + + /** Property data of the graph (id/type mappings etc.) */ + private SwhGraphProperties properties; + + protected SwhUnidirectionalGraph(ImmutableGraph graph, SwhGraphProperties properties) { + this.graph = graph; + this.properties = properties; + } + + protected SwhUnidirectionalGraph(ArcLabelledImmutableGraph graph, SwhGraphProperties properties) { + this.graph = graph; + this.labelledGraph = graph; + this.properties = properties; + } + + /** + * Load the (unlabelled) graph only, without the SWH properties. + */ + public static SwhUnidirectionalGraph loadGraphOnly(LoadMethod method, String path, InputStream is, + ProgressLogger pl) throws IOException { + return new SwhUnidirectionalGraph(ImmutableGraph.load(method, path, is, pl), null); + } + + /** + * Load the labelled graph only, without the SWH properties. + */ + public static SwhUnidirectionalGraph loadLabelledGraphOnly(LoadMethod method, String path, InputStream is, + ProgressLogger pl) throws IOException { + BitStreamArcLabelledImmutableGraph g = (BitStreamArcLabelledImmutableGraph) BitStreamArcLabelledImmutableGraph + .load(method, path, is, pl); + return new SwhUnidirectionalGraph(g, null); + } + + /** + * Load the SWH properties of the graph from a given path. + */ + public void loadProperties(String path) throws IOException { + properties = SwhGraphProperties.load(path); + } + + /** + * Setter for the SWH graph properties. + * + * @param properties The {@link SwhGraphProperties} object containing the graph properties + */ + public void setProperties(SwhGraphProperties properties) { + this.properties = properties; + } + + /** + * Load the unlabelled graph and its SWH properties. + */ + public static SwhUnidirectionalGraph load(LoadMethod method, String path, InputStream is, ProgressLogger pl) + throws IOException { + SwhUnidirectionalGraph g = loadGraphOnly(method, path, is, pl); + g.loadProperties(path); + return g; + } + + /** + * Load the labelled graph and its SWH properties. + */ + public static SwhUnidirectionalGraph loadLabelled(LoadMethod method, String path, InputStream is, ProgressLogger pl) + throws IOException { + SwhUnidirectionalGraph g = loadLabelledGraphOnly(method, path, is, pl); + g.loadProperties(path); + return g; + } + + // loadXXX methods of ImmutableGraph + public static SwhUnidirectionalGraph load(String path, ProgressLogger pl) throws IOException { + return load(LoadMethod.STANDARD, path, null, pl); + } + public static SwhUnidirectionalGraph load(String path) throws IOException { + return load(LoadMethod.STANDARD, path, null, null); + } + public static SwhUnidirectionalGraph loadMapped(String path, ProgressLogger pl) throws IOException { + return load(LoadMethod.MAPPED, path, null, pl); + } + public static SwhUnidirectionalGraph loadMapped(String path) throws IOException { + return load(LoadMethod.MAPPED, path, null, null); + } + public static SwhUnidirectionalGraph loadOffline(String path, ProgressLogger pl) throws IOException { + return load(LoadMethod.OFFLINE, path, null, pl); + } + public static SwhUnidirectionalGraph loadOffline(String path) throws IOException { + return load(LoadMethod.OFFLINE, path, null, null); + } + + // Labelled versions of the loadXXX methods from ImmutableGraph + public static SwhUnidirectionalGraph loadLabelled(String path, ProgressLogger pl) throws IOException { + return loadLabelled(LoadMethod.STANDARD, path, null, pl); + } + public static SwhUnidirectionalGraph loadLabelled(String path) throws IOException { + return loadLabelled(LoadMethod.STANDARD, path, null, null); + } + public static SwhUnidirectionalGraph loadLabelledMapped(String path, ProgressLogger pl) throws IOException { + return loadLabelled(LoadMethod.MAPPED, path, null, pl); + } + public static SwhUnidirectionalGraph loadLabelledMapped(String path) throws IOException { + return loadLabelled(LoadMethod.MAPPED, path, null, null); + } + public static SwhUnidirectionalGraph loadLabelledOffline(String path, ProgressLogger pl) throws IOException { + return loadLabelled(LoadMethod.OFFLINE, path, null, pl); + } + public static SwhUnidirectionalGraph loadLabelledOffline(String path) throws IOException { + return loadLabelled(LoadMethod.OFFLINE, path, null, null); + } + + @Override + public SwhUnidirectionalGraph copy() { + return new SwhUnidirectionalGraph(this.graph.copy(), this.properties); + } + + @Override + public boolean randomAccess() { + return graph.randomAccess(); + } + + public void close() throws IOException { + this.properties.close(); + } + + @Override + public long numNodes() { + return graph.numNodes(); + } + + @Override + public long numArcs() { + return graph.numArcs(); + } + + @Override + public LazyLongIterator successors(long nodeId) { + return graph.successors(nodeId); + } + + /** + * Returns a labelled node iterator for scanning the graph sequentially, starting from the + * first node. + */ + public ArcLabelledNodeIterator labelledNodeIterator() { + if (labelledGraph == null) { + throw new RuntimeException("Calling labelledNodeIterator() but labels were not loaded."); + } + return labelledGraph.nodeIterator(); + } + + /** + * Returns a labelled node iterator for scanning the graph sequentially, starting from a + * given node. + */ + public ArcLabelledNodeIterator labelledNodeIterator(long from) { + if (labelledGraph == null) { + throw new RuntimeException("Calling labelledNodeIterator() but labels were not loaded."); + } + return labelledGraph.nodeIterator(from); + } + + /** + * Returns a labelled lazy iterator over the successors of a given node. The iteration + * terminates when -1 is returned. + */ + public ArcLabelledNodeIterator.LabelledArcIterator labelledSuccessors(long x) { + if (labelledGraph == null) { + throw new RuntimeException("Calling labelledNodeIterator() but labels were not loaded."); + } + return labelledGraph.successors(x); + } + + @Override + public long outdegree(long nodeId) { + return graph.outdegree(nodeId); + } + + public String getPath() { + return properties.getPath(); + } + public long getNodeId(SWHID swhid) { + return properties.getNodeId(swhid); + } + public SWHID getSWHID(long nodeId) { + return properties.getSWHID(nodeId); + } + public Node.Type getNodeType(long nodeId) { + return properties.getNodeType(nodeId); + } +} diff --git a/java/src/main/java/org/softwareheritage/graph/Traversal.java b/java/src/main/java/org/softwareheritage/graph/Traversal.java --- a/java/src/main/java/org/softwareheritage/graph/Traversal.java +++ b/java/src/main/java/org/softwareheritage/graph/Traversal.java @@ -29,8 +29,8 @@ public class Traversal { /** Graph used in the traversal */ - Graph graph; - /** Graph edge restriction */ + SwhBidirectionalGraph graph; + /** Graph edge restrictions */ AllowedEdges edges; /** Hash set storing if we have visited a node */ @@ -58,15 +58,16 @@ * edges */ - public Traversal(Graph graph, String direction, String edgesFmt) { + public Traversal(SwhBidirectionalGraph graph, String direction, String edgesFmt) { this(graph, direction, edgesFmt, 0); } - public Traversal(Graph graph, String direction, String edgesFmt, long maxEdges) { + public Traversal(SwhBidirectionalGraph graph, String direction, String edgesFmt, long maxEdges) { this(graph, direction, edgesFmt, maxEdges, "*"); } - public Traversal(Graph graph, String direction, String edgesFmt, long maxEdges, String returnTypes) { + public Traversal(SwhBidirectionalGraph graph, String direction, String edgesFmt, long maxEdges, + String returnTypes) { if (!direction.matches("forward|backward")) { throw new IllegalArgumentException("Unknown traversal direction: " + direction); } @@ -109,6 +110,48 @@ 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. */ @@ -129,7 +172,7 @@ break; } } - LazyLongIterator it = graph.successors(currentNodeId, edges); + LazyLongIterator it = filterSuccessors(currentNodeId, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { neighborsCnt++; if (!visited.contains(neighborNodeId)) { @@ -169,7 +212,7 @@ return; } } - LazyLongIterator it = graph.successors(srcNodeId, edges); + LazyLongIterator it = filterSuccessors(srcNodeId, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { cb.accept(neighborNodeId); } @@ -211,7 +254,7 @@ break; } } - LazyLongIterator it = graph.successors(currentNodeId, edges); + LazyLongIterator it = filterSuccessors(currentNodeId, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { if (edgeCb != null) { edgeCb.accept(currentNodeId, neighborNodeId); @@ -278,7 +321,7 @@ return; } } - LazyLongIterator it = graph.successors(currentNodeId, edges); + LazyLongIterator it = filterSuccessors(currentNodeId, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { visitPathsInternalVisitor(neighborNodeId, currentPath, cb); visitedNeighbors++; @@ -352,7 +395,7 @@ while (true) { path.add(curNodeId); - LazyLongIterator successors = graph.successors(curNodeId, edges); + LazyLongIterator successors = filterSuccessors(curNodeId, edges); curNodeId = randomPick(successors); if (curNodeId < 0) { found = false; @@ -419,7 +462,7 @@ } nbEdgesAccessed += graph.outdegree(currentNodeId); - LazyLongIterator it = graph.successors(currentNodeId, edges); + LazyLongIterator it = filterSuccessors(currentNodeId, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { if (!visited.contains(neighborNodeId)) { stack.push(neighborNodeId); @@ -453,7 +496,7 @@ } nbEdgesAccessed += graph.outdegree(currentNodeId); - LazyLongIterator it = graph.successors(currentNodeId, edges); + LazyLongIterator it = filterSuccessors(currentNodeId, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { if (!visited.contains(neighborNodeId)) { queue.add(neighborNodeId); @@ -528,7 +571,7 @@ if (!lhsStack.isEmpty()) { curNode = lhsStack.poll(); nbEdgesAccessed += graph.outdegree(curNode); - LazyLongIterator it = graph.successors(curNode, edges); + LazyLongIterator it = filterSuccessors(curNode, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { if (!lhsVisited.contains(neighborNodeId)) { if (rhsVisited.contains(neighborNodeId)) @@ -542,7 +585,7 @@ if (!rhsStack.isEmpty()) { curNode = rhsStack.poll(); nbEdgesAccessed += graph.outdegree(curNode); - LazyLongIterator it = graph.successors(curNode, edges); + LazyLongIterator it = filterSuccessors(curNode, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { if (!rhsVisited.contains(neighborNodeId)) { if (lhsVisited.contains(neighborNodeId)) diff --git a/java/src/main/java/org/softwareheritage/graph/algo/TopologicalTraversal.java b/java/src/main/java/org/softwareheritage/graph/algo/TopologicalTraversal.java --- a/java/src/main/java/org/softwareheritage/graph/algo/TopologicalTraversal.java +++ b/java/src/main/java/org/softwareheritage/graph/algo/TopologicalTraversal.java @@ -8,7 +8,7 @@ import it.unimi.dsi.fastutil.longs.LongBigArrays; import it.unimi.dsi.io.ByteDiskQueue; import it.unimi.dsi.logging.ProgressLogger; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Traversal; import org.softwareheritage.graph.experiments.forks.ForkCC; @@ -16,7 +16,7 @@ import java.io.IOException; public class TopologicalTraversal { - public static void run(final Graph graph, Traversal.NodeIdConsumer cb) throws IOException { + public static void run(final SwhBidirectionalGraph graph, Traversal.NodeIdConsumer cb) throws IOException { final long[][] indegree = LongBigArrays.newBigArray(graph.numNodes()); final ProgressLogger pl = new ProgressLogger(); diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java b/java/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java --- a/java/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java +++ b/java/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java @@ -2,7 +2,7 @@ import com.martiansoftware.jsap.JSAPException; import it.unimi.dsi.big.webgraph.LazyLongIterator; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.benchmark.utils.Statistics; import org.softwareheritage.graph.benchmark.utils.Timing; @@ -25,7 +25,7 @@ Benchmark bench = new Benchmark(); bench.parseCommandLineArgs(args); - Graph graph = Graph.loadMapped(bench.args.graphPath); + SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(bench.args.graphPath); long[] nodeIds = bench.args.random.generateNodeIds(graph, bench.args.nbNodes); diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java b/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java --- a/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java +++ b/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java @@ -10,7 +10,7 @@ import it.unimi.dsi.logging.ProgressLogger; import org.slf4j.Logger; import org.slf4j.LoggerFactory; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import java.io.File; import java.io.IOException; @@ -50,7 +50,7 @@ boolean useTransposed = config.getBoolean("useTransposed"); System.err.println("Loading graph " + graphPath + " ..."); - Graph graph = Graph.loadMapped(graphPath); + SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(graphPath); System.err.println("Graph loaded."); if (useTransposed) diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java --- a/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java +++ b/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java @@ -1,7 +1,7 @@ package org.softwareheritage.graph.benchmark; import com.martiansoftware.jsap.*; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.SWHID; import org.softwareheritage.graph.benchmark.utils.Random; import org.softwareheritage.graph.benchmark.utils.Statistics; @@ -85,7 +85,7 @@ * API * @param algorithm traversal algorithm used in endpoint call (either "dfs" or "bfs") */ - public void timeEndpoint(String useCaseName, Graph graph, long[] nodeIds, + 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<>(); @@ -133,7 +133,7 @@ /** * Same as {@link #timeEndpoint} but without destination or algorithm specified to endpoint call. */ - public void timeEndpoint(String useCaseName, Graph graph, long[] nodeIds, + public void timeEndpoint(String useCaseName, SwhBidirectionalGraph graph, long[] nodeIds, Function operation) throws IOException { timeEndpoint(useCaseName, graph, nodeIds, operation, null, null); } diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Browsing.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Browsing.java --- a/java/src/main/java/org/softwareheritage/graph/benchmark/Browsing.java +++ b/java/src/main/java/org/softwareheritage/graph/benchmark/Browsing.java @@ -1,7 +1,7 @@ package org.softwareheritage.graph.benchmark; import com.martiansoftware.jsap.JSAPException; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Node; import org.softwareheritage.graph.server.Endpoint; @@ -25,7 +25,7 @@ Benchmark bench = new Benchmark(); bench.parseCommandLineArgs(args); - Graph graph = Graph.loadMapped(bench.args.graphPath); + 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); diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Provenance.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Provenance.java --- a/java/src/main/java/org/softwareheritage/graph/benchmark/Provenance.java +++ b/java/src/main/java/org/softwareheritage/graph/benchmark/Provenance.java @@ -1,7 +1,7 @@ package org.softwareheritage.graph.benchmark; import com.martiansoftware.jsap.JSAPException; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.server.Endpoint; import java.io.IOException; @@ -24,7 +24,7 @@ Benchmark bench = new Benchmark(); bench.parseCommandLineArgs(args); - Graph graph = Graph.loadMapped(bench.args.graphPath); + SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(bench.args.graphPath); long[] nodeIds = bench.args.random.generateNodeIds(graph, bench.args.nbNodes); diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Vault.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Vault.java --- a/java/src/main/java/org/softwareheritage/graph/benchmark/Vault.java +++ b/java/src/main/java/org/softwareheritage/graph/benchmark/Vault.java @@ -1,7 +1,7 @@ package org.softwareheritage.graph.benchmark; import com.martiansoftware.jsap.JSAPException; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.server.Endpoint; import java.io.IOException; @@ -24,7 +24,7 @@ Benchmark bench = new Benchmark(); bench.parseCommandLineArgs(args); - Graph graph = Graph.loadMapped(bench.args.graphPath); + SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(bench.args.graphPath); long[] nodeIds = bench.args.random.generateNodeIds(graph, bench.args.nbNodes); 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 --- a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Random.java +++ b/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Random.java @@ -1,6 +1,6 @@ package org.softwareheritage.graph.benchmark.utils; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Node; import java.util.PrimitiveIterator; @@ -38,7 +38,7 @@ * @param nbNodes number of node ids to generate * @return an array of random node ids */ - public long[] generateNodeIds(Graph graph, int nbNodes) { + public long[] generateNodeIds(SwhBidirectionalGraph graph, int nbNodes) { return random.longs(nbNodes, 0, graph.numNodes()).toArray(); } @@ -50,7 +50,7 @@ * @param expectedType specific node type to pick * @return an array of random node ids */ - public long[] generateNodeIdsOfType(Graph graph, int nbNodes, Node.Type expectedType) { + public long[] generateNodeIdsOfType(SwhBidirectionalGraph graph, int nbNodes, Node.Type expectedType) { PrimitiveIterator.OfLong nodes = random.longs(0, graph.numNodes()).iterator(); long[] nodeIds = new long[nbNodes]; 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 --- a/java/src/main/java/org/softwareheritage/graph/experiments/forks/FindCommonAncestor.java +++ b/java/src/main/java/org/softwareheritage/graph/experiments/forks/FindCommonAncestor.java @@ -1,18 +1,18 @@ package org.softwareheritage.graph.experiments.forks; import com.martiansoftware.jsap.*; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Traversal; import java.io.IOException; import java.util.Scanner; public class FindCommonAncestor { - private Graph graph; + private SwhBidirectionalGraph graph; private void load_graph(String graphBasename) throws IOException { System.err.println("Loading graph " + graphBasename + " ..."); - this.graph = Graph.loadMapped(graphBasename); + this.graph = SwhBidirectionalGraph.loadMapped(graphBasename); System.err.println("Graph loaded."); } 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 --- a/java/src/main/java/org/softwareheritage/graph/experiments/forks/FindPath.java +++ b/java/src/main/java/org/softwareheritage/graph/experiments/forks/FindPath.java @@ -2,19 +2,19 @@ import com.martiansoftware.jsap.*; import it.unimi.dsi.big.webgraph.LazyLongIterator; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Node; import java.io.IOException; import java.util.*; public class FindPath { - private Graph graph; + private SwhBidirectionalGraph graph; private Long emptySnapshot; private void load_graph(String graphBasename) throws IOException { System.err.println("Loading graph " + graphBasename + " ..."); - this.graph = Graph.loadMapped(graphBasename).symmetrize(); + this.graph = SwhBidirectionalGraph.loadMapped(graphBasename).symmetrize(); System.err.println("Graph loaded."); this.emptySnapshot = 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 @@ -7,7 +7,7 @@ import it.unimi.dsi.fastutil.Arrays; import it.unimi.dsi.io.ByteDiskQueue; import it.unimi.dsi.logging.ProgressLogger; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Node; import java.io.File; @@ -17,7 +17,7 @@ public class ForkCC { public Boolean includeRootDir; - private Graph graph; + private SwhBidirectionalGraph graph; private Long emptySnapshot; private LongArrayBitVector visited; private LongArrayBitVector whitelist; @@ -72,7 +72,7 @@ private void load_graph(String graphBasename) throws IOException { System.err.println("Loading graph " + graphBasename + " ..."); - this.graph = Graph.loadMapped(graphBasename).symmetrize(); + this.graph = SwhBidirectionalGraph.loadMapped(graphBasename).symmetrize(); System.err.println("Graph loaded."); this.emptySnapshot = null; this.whitelist = null; 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 @@ -8,7 +8,7 @@ import it.unimi.dsi.bits.LongArrayBitVector; import it.unimi.dsi.logging.ProgressLogger; import org.slf4j.LoggerFactory; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Node; import java.io.File; @@ -19,12 +19,12 @@ import java.util.*; public class ForkCliques { - private Graph graph; + private SwhBidirectionalGraph graph; private LongArrayBitVector whitelist; private void load_graph(String graphBasename) throws IOException { System.err.println("Loading graph " + graphBasename + " ..."); - this.graph = Graph.loadMapped(graphBasename); + this.graph = SwhBidirectionalGraph.loadMapped(graphBasename); System.err.println("Graph loaded."); this.whitelist = null; } 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 @@ -3,14 +3,14 @@ import com.martiansoftware.jsap.*; import it.unimi.dsi.big.webgraph.ImmutableGraph; import it.unimi.dsi.big.webgraph.LazyLongIterator; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Node; import java.io.IOException; import java.util.ArrayList; public class ListEmptyOrigins { - private Graph graph; + private SwhBidirectionalGraph graph; private Long emptySnapshot; private static JSAPResult parse_args(String[] args) { @@ -49,7 +49,7 @@ private void load_graph(String graphBasename) throws IOException { System.err.println("Loading graph " + graphBasename + " ..."); - this.graph = Graph.loadMapped(graphBasename); + this.graph = SwhBidirectionalGraph.loadMapped(graphBasename); System.err.println("Graph loaded."); this.emptySnapshot = null; } 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 --- a/java/src/main/java/org/softwareheritage/graph/experiments/multiplicationfactor/GenDistribution.java +++ b/java/src/main/java/org/softwareheritage/graph/experiments/multiplicationfactor/GenDistribution.java @@ -1,7 +1,7 @@ package org.softwareheritage.graph.experiments.multiplicationfactor; import com.martiansoftware.jsap.*; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Node; import org.softwareheritage.graph.Traversal; import org.softwareheritage.graph.benchmark.utils.Timing; @@ -13,7 +13,7 @@ import java.util.concurrent.Executors; public class GenDistribution { - private Graph graph; + private SwhBidirectionalGraph graph; private static JSAPResult parse_args(String[] args) { JSAPResult config = null; @@ -88,7 +88,7 @@ for (int i = 0; i < numThreads; ++i) { service.submit(() -> { - Graph thread_graph = tp.graph.copy(); + SwhBidirectionalGraph thread_graph = tp.graph.copy(); long startTime; double totalTime; @@ -124,7 +124,7 @@ private void load_graph(String graphBasename) throws IOException { System.err.println("Loading graph " + graphBasename + " ..."); - this.graph = Graph.loadMapped(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 @@ -17,14 +17,14 @@ import java.util.concurrent.*; public class AveragePaths { - private final Graph graph; + private final SwhBidirectionalGraph graph; private final Subgraph subgraph; private final ConcurrentHashMap result; private final String outdir; public AveragePaths(String graphBasename, String allowedNodes, String outdir) throws IOException { System.err.println("Loading graph " + graphBasename + " ..."); - this.graph = Graph.loadMapped(graphBasename); + this.graph = SwhBidirectionalGraph.loadMapped(graphBasename); this.subgraph = new Subgraph(this.graph, new AllowedNodes(allowedNodes)); this.outdir = outdir; System.err.println("Graph loaded."); @@ -64,7 +64,7 @@ service.submit(() -> { try { - Graph thread_graph = graph.copy(); + SwhBidirectionalGraph thread_graph = graph.copy(); Subgraph thread_subgraph = subgraph.copy(); long[][] randomPerm = Util.identity(thread_graph.numNodes()); 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 @@ -8,7 +8,7 @@ import it.unimi.dsi.fastutil.longs.LongBigArrays; import it.unimi.dsi.logging.ProgressLogger; import it.unimi.dsi.util.XoRoShiRo128PlusRandom; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Node; import java.io.*; @@ -16,7 +16,7 @@ import java.util.concurrent.*; public class ClusteringCoefficient { - private final Graph graph; + private final SwhBidirectionalGraph graph; private final String outdirPath; private final ConcurrentHashMap result_full; private final ConcurrentHashMap result_dircnt; @@ -27,7 +27,7 @@ public ClusteringCoefficient(String graphBasename, String outdirPath) throws IOException { this.outdirPath = outdirPath; System.err.println("Loading graph " + graphBasename + " ..."); - Graph directedGraph = Graph.loadMapped(graphBasename); + SwhBidirectionalGraph directedGraph = SwhBidirectionalGraph.loadMapped(graphBasename); this.graph = directedGraph.symmetrize(); System.err.println("Graph loaded."); @@ -68,7 +68,7 @@ service.submit(() -> { try { - Graph thread_graph = graph.copy(); + SwhBidirectionalGraph thread_graph = graph.copy(); long[][] randomPerm = Util.identity(thread_graph.numNodes()); LongBigArrays.shuffle(randomPerm, new XoRoShiRo128PlusRandom()); @@ -103,7 +103,7 @@ for (int i = 0; i < numThreads; ++i) { service.submit(() -> { try { - Graph thread_graph = graph.copy(); + SwhBidirectionalGraph thread_graph = graph.copy(); while (true) { Long node = null; try { @@ -127,7 +127,7 @@ service.awaitTermination(365, TimeUnit.DAYS); } - private void computeAt(Graph graph, long node) { + private void computeAt(SwhBidirectionalGraph graph, long node) { long d = graph.outdegree(node); if (d < 2) { return; 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 @@ -8,7 +8,7 @@ import it.unimi.dsi.io.ByteDiskQueue; import it.unimi.dsi.logging.ProgressLogger; import org.softwareheritage.graph.AllowedNodes; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Node; import org.softwareheritage.graph.Subgraph; @@ -23,7 +23,7 @@ private void load_graph(String graphBasename, String nodeTypes) throws IOException { System.err.println("Loading graph " + graphBasename + " ..."); - var underlyingGraph = Graph.loadMapped(graphBasename); + var underlyingGraph = SwhBidirectionalGraph.loadMapped(graphBasename); var underlyingGraphSym = underlyingGraph.symmetrize(); graph = new Subgraph(underlyingGraphSym, new AllowedNodes(nodeTypes)); System.err.println("Graph loaded."); 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 @@ -15,7 +15,7 @@ import com.martiansoftware.jsap.UnflaggedOption; import it.unimi.dsi.logging.ProgressLogger; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Node; public class InOutDegree { @@ -31,7 +31,7 @@ private static final int TYPE_SNP = Node.Type.toInt(Node.Type.SNP); private static final int TYPE_ORI = Node.Type.toInt(Node.Type.ORI); - public static long[] outdegreeTypes(final Graph graph, long node) { + public static long[] outdegreeTypes(final SwhBidirectionalGraph graph, long node) { long[] out = new long[NODE_ARRAY_SIZE]; var successors = graph.successors(node); long neighbor; @@ -42,7 +42,7 @@ return out; } - public static long[] indegreeTypes(final Graph graph, long node) { + public static long[] indegreeTypes(final SwhBidirectionalGraph graph, long node) { return outdegreeTypes(graph.transpose(), node); } @@ -55,7 +55,7 @@ f.close(); } - public static void run(final Graph graph, String resultsDir) throws IOException { + public static void run(final SwhBidirectionalGraph graph, String resultsDir) throws IOException { // Per-type var cnt_in_dir = new HashMap(); var dir_in_dir = new HashMap(); @@ -233,7 +233,7 @@ final ProgressLogger pl = new ProgressLogger(); - Graph graph = Graph.loadMapped(basename); + SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(basename); run(graph, resultsDir); } } 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 @@ -11,7 +11,7 @@ import it.unimi.dsi.io.ByteDiskQueue; import it.unimi.dsi.logging.ProgressLogger; import it.unimi.dsi.util.XoRoShiRo128PlusRandom; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Node; import org.softwareheritage.graph.experiments.forks.ForkCC; @@ -22,7 +22,7 @@ private SubdatasetSizeFunction() { } - public static void run(final Graph graph) throws IOException { + public static void run(final SwhBidirectionalGraph graph) throws IOException { final ProgressLogger pl = new ProgressLogger(); pl.itemsName = "nodes"; pl.expectedUpdates = graph.numNodes(); @@ -92,7 +92,7 @@ final String basename = jsapResult.getString("basename"); - Graph graph = Graph.loadMapped(basename); + SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(basename); run(graph); } } diff --git a/java/src/main/java/org/softwareheritage/graph/maps/LabelMapBuilder.java b/java/src/main/java/org/softwareheritage/graph/maps/LabelMapBuilder.java --- a/java/src/main/java/org/softwareheritage/graph/maps/LabelMapBuilder.java +++ b/java/src/main/java/org/softwareheritage/graph/maps/LabelMapBuilder.java @@ -61,7 +61,7 @@ numArcs = graph.numArcs(); numNodes = graph.numNodes(); - nodeIdMap = new NodeIdMap(graphPath, numNodes); + nodeIdMap = new NodeIdMap(graphPath); filenameMph = NodeIdMap.loadMph(graphPath + "-labels.mph"); numFilenames = getMPHSize(filenameMph); diff --git a/java/src/main/java/org/softwareheritage/graph/maps/MapFile.java b/java/src/main/java/org/softwareheritage/graph/maps/MapFile.java --- a/java/src/main/java/org/softwareheritage/graph/maps/MapFile.java +++ b/java/src/main/java/org/softwareheritage/graph/maps/MapFile.java @@ -53,6 +53,10 @@ return buffer; } + public long size() { + return bufferMap.length() / (long) lineLength; + } + /** * Closes the mmap()-ed file. */ 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 @@ -33,8 +33,6 @@ /** Graph path and basename */ String graphPath; - /** Number of ids to map */ - long nbIds; /** mmap()-ed NODE_TO_SWHID file */ MapFile nodeToSwhMap; @@ -50,11 +48,9 @@ * Constructor. * * @param graphPath full graph path - * @param nbNodes number of nodes in the graph */ - public NodeIdMap(String graphPath, long nbNodes) throws IOException { + public NodeIdMap(String graphPath) throws IOException { this.graphPath = graphPath; - this.nbIds = nbNodes; // node -> SWHID this.nodeToSwhMap = new MapFile(graphPath + NODE_TO_SWHID, SWHID_BIN_SIZE); @@ -169,8 +165,8 @@ * Each line in NODE_TO_SWHID is formatted as: swhid The file is ordered by nodeId, meaning node0's * swhid is at line 0, hence we can read the nodeId-th line to get corresponding swhid */ - if (nodeId < 0 || nodeId >= nbIds) { - throw new IllegalArgumentException("Node id " + nodeId + " should be between 0 and " + nbIds); + if (nodeId < 0 || nodeId >= nodeToSwhMap.size()) { + throw new IllegalArgumentException("Node id " + nodeId + " should be between 0 and " + nodeToSwhMap.size()); } return SWHID.fromBytes(nodeToSwhMap.readAtLine(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 --- a/java/src/main/java/org/softwareheritage/graph/server/App.java +++ b/java/src/main/java/org/softwareheritage/graph/server/App.java @@ -6,7 +6,7 @@ import io.javalin.Javalin; import io.javalin.http.Context; import io.javalin.plugin.json.JavalinJackson; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.Stats; import org.softwareheritage.graph.SWHID; @@ -56,14 +56,14 @@ * @param showTimings true if timings should be in results metadata, false otherwise */ private static void startServer(String graphPath, int port, boolean showTimings) throws IOException { - Graph graph = Graph.loadMapped(graphPath); + SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(graphPath); Stats stats = new Stats(graphPath); // Clean up on exit Runtime.getRuntime().addShutdownHook(new Thread() { public void run() { try { - graph.cleanUp(); + graph.close(); } catch (IOException e) { System.out.println("Could not clean up graph on exit: " + e); } diff --git a/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java b/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java --- a/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java +++ b/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java @@ -18,7 +18,7 @@ public class Endpoint { /** Graph where traversal endpoint is performed */ - Graph graph; + SwhBidirectionalGraph graph; /** Internal traversal API */ Traversal traversal; @@ -31,7 +31,7 @@ * "https://docs.softwareheritage.org/devel/swh-graph/api.html#terminology">allowed * edges */ - public Endpoint(Graph graph, String direction, String edgesFmt) { + public Endpoint(SwhBidirectionalGraph graph, String direction, String edgesFmt) { this.graph = graph; this.traversal = new Traversal(graph, direction, edgesFmt); } 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 @@ -8,7 +8,7 @@ import it.unimi.dsi.io.ByteDiskQueue; import it.unimi.dsi.io.FastBufferedReader; import it.unimi.dsi.io.LineIterator; -import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.SwhBidirectionalGraph; import org.softwareheritage.graph.SWHID; import org.softwareheritage.graph.experiments.topology.ConnectedComponents; import org.softwareheritage.graph.maps.NodeIdMap; @@ -22,7 +22,7 @@ public static void main(String[] args) throws IOException, ClassNotFoundException { System.err.print("Loading everything..."); String graphPath = args[0]; - Graph graph = Graph.loadMapped(graphPath); + SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(graphPath); Object2LongFunction mphMap = NodeIdMap.loadMph(graphPath + ".mph"); System.err.println(" done."); 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 @@ -3,10 +3,7 @@ import it.unimi.dsi.big.webgraph.LazyLongIterator; import it.unimi.dsi.fastutil.BigArrays; import it.unimi.dsi.fastutil.io.BinIO; -import org.softwareheritage.graph.AllowedEdges; -import org.softwareheritage.graph.Graph; -import org.softwareheritage.graph.Node; -import org.softwareheritage.graph.SWHID; +import org.softwareheritage.graph.*; import java.io.IOException; import java.time.Duration; @@ -36,7 +33,7 @@ System.err.println("loading transposed graph..."); ts = System.nanoTime(); - Graph graph = Graph.loadMapped(graphPath).transpose(); + SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(graphPath).transpose(); elapsed = Duration.ofNanos(System.nanoTime() - ts); System.err.println(String.format("transposed graph loaded (duration: %s).", elapsed)); @@ -89,7 +86,7 @@ } } - LazyLongIterator it = graph.successors(currentNodeId, edges); + LazyLongIterator it = Traversal.filterSuccessors(graph, currentNodeId, edges); for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { if (!visited.contains(neighborNodeId)) { stack.push(neighborNodeId); 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 @@ -11,7 +11,7 @@ String graphPath = args[0]; ImmutableGraph graph = ImmutableGraph.load(graphPath); - NodeIdMap nodeMap = new NodeIdMap(graphPath, graph.numNodes()); + NodeIdMap nodeMap = new NodeIdMap(graphPath); NodeIterator it = graph.nodeIterator(); while (it.hasNext()) { 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 @@ -15,7 +15,7 @@ String graphPath = args[0]; ArcLabelledImmutableGraph graph = BitStreamArcLabelledImmutableGraph.loadOffline(graphPath + "-labelled"); - NodeIdMap nodeMap = new NodeIdMap(graphPath, graph.numNodes()); + NodeIdMap nodeMap = new NodeIdMap(graphPath); FrontCodedStringBigList filenameMap = (FrontCodedStringBigList) BinIO.loadObject(graphPath + "-labels.fcl"); ArcLabelledNodeIterator it = graph.nodeIterator(); 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 @@ -15,15 +15,15 @@ import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder; public class GraphTest { - static Graph graph; + static SwhBidirectionalGraph graph; @BeforeAll public static void setUp() throws IOException { Path graphPath = Paths.get("..", "swh", "graph", "tests", "dataset", "output", "example"); - graph = Graph.loadMapped(graphPath.toString()); + graph = SwhBidirectionalGraph.loadMapped(graphPath.toString()); } - public Graph getGraph() { + public SwhBidirectionalGraph getGraph() { return graph; } diff --git a/java/src/test/java/org/softwareheritage/graph/LeavesTest.java b/java/src/test/java/org/softwareheritage/graph/LeavesTest.java --- a/java/src/test/java/org/softwareheritage/graph/LeavesTest.java +++ b/java/src/test/java/org/softwareheritage/graph/LeavesTest.java @@ -10,7 +10,7 @@ public class LeavesTest extends GraphTest { @Test public void forwardFromSnp() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src = new SWHID("swh:1:snp:0000000000000000000000000000000000000020"); Endpoint endpoint = new Endpoint(graph, "forward", "*"); @@ -26,7 +26,7 @@ @Test public void forwardFromRel() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src = new SWHID("swh:1:rel:0000000000000000000000000000000000000019"); Endpoint endpoint = new Endpoint(graph, "forward", "*"); @@ -45,7 +45,7 @@ @Test public void backwardFromLeaf() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); Endpoint endpoint1 = new Endpoint(graph, "backward", "*"); SWHID src1 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000015"); @@ -65,7 +65,7 @@ @Test public void forwardRevToRevOnly() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src = new SWHID("swh:1:rev:0000000000000000000000000000000000000018"); Endpoint endpoint = new Endpoint(graph, "forward", "rev:rev"); @@ -78,7 +78,7 @@ @Test public void forwardDirToAll() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src = new SWHID("swh:1:dir:0000000000000000000000000000000000000008"); Endpoint endpoint = new Endpoint(graph, "forward", "dir:*"); @@ -94,7 +94,7 @@ @Test public void backwardCntToDirDirToDir() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src = new SWHID("swh:1:cnt:0000000000000000000000000000000000000005"); Endpoint endpoint = new Endpoint(graph, "backward", "cnt:dir,dir:dir"); diff --git a/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java b/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java --- a/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java +++ b/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java @@ -10,7 +10,7 @@ public class NeighborsTest extends GraphTest { @Test public void zeroNeighbor() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); ArrayList expectedNodes = new ArrayList<>(); SWHID src1 = new SWHID("swh:1:ori:0000000000000000000000000000000000000021"); @@ -41,7 +41,7 @@ @Test public void oneNeighbor() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src1 = new SWHID("swh:1:rev:0000000000000000000000000000000000000003"); Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); @@ -81,7 +81,7 @@ @Test public void twoNeighbors() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src1 = new SWHID("swh:1:snp:0000000000000000000000000000000000000020"); Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); @@ -118,7 +118,7 @@ @Test public void threeNeighbors() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src1 = new SWHID("swh:1:dir:0000000000000000000000000000000000000008"); Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); 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 @@ -8,7 +8,7 @@ public class SubgraphTest extends GraphTest { @Test public void noFilter() { - Graph g = getGraph(); + SwhBidirectionalGraph g = getGraph(); Subgraph sg = new Subgraph(g, new AllowedNodes("*")); for (long i = 0; i < g.numNodes(); ++i) { @@ -18,7 +18,7 @@ @Test public void missingNode() { - Graph g = getGraph(); + SwhBidirectionalGraph g = getGraph(); Subgraph sg = new Subgraph(g, new AllowedNodes("dir,ori")); SWHID rev1 = fakeSWHID("rev", 18); @@ -32,7 +32,7 @@ @Test public void outdegreeOnlyDirOri() { - Graph g = getGraph(); + SwhBidirectionalGraph g = getGraph(); Subgraph sg = new Subgraph(g, new AllowedNodes("dir,ori")); SWHID dir1 = fakeSWHID("dir", 17); @@ -50,7 +50,7 @@ @Test public void successorsOnlyDirOri() { - Graph g = getGraph(); + SwhBidirectionalGraph g = getGraph(); Subgraph sg = new Subgraph(g, new AllowedNodes("dir,ori")); SWHID dir1 = fakeSWHID("dir", 17); @@ -66,7 +66,7 @@ @Test public void nodeIteratorOnlyOriDir() { - Graph g = getGraph(); + SwhBidirectionalGraph g = getGraph(); Subgraph sg = new Subgraph(g, new AllowedNodes("dir,ori")); ArrayList nodeList = new ArrayList<>(); Iterator nodeIt = sg.nodeIterator(); diff --git a/java/src/test/java/org/softwareheritage/graph/VisitTest.java b/java/src/test/java/org/softwareheritage/graph/VisitTest.java --- a/java/src/test/java/org/softwareheritage/graph/VisitTest.java +++ b/java/src/test/java/org/softwareheritage/graph/VisitTest.java @@ -20,7 +20,7 @@ @Test public void forwardFromRoot() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID swhid = new SWHID("swh:1:ori:0000000000000000000000000000000000000021"); Endpoint endpoint1 = new Endpoint(graph, "forward", "*"); ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; @@ -96,7 +96,7 @@ @Test public void forwardFromMiddle() { - Graph graph = getGraph(); + 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; @@ -127,7 +127,7 @@ @Test public void forwardFromLeaf() { - Graph graph = getGraph(); + 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; @@ -143,7 +143,7 @@ @Test public void backwardFromRoot() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID swhid = new SWHID("swh:1:ori:0000000000000000000000000000000000000021"); Endpoint endpoint1 = new Endpoint(graph, "backward", "*"); ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result; @@ -159,7 +159,7 @@ @Test public void backwardFromMiddle() { - Graph graph = getGraph(); + 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; @@ -178,7 +178,7 @@ @Test public void backwardFromLeaf() { - Graph graph = getGraph(); + 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; @@ -220,7 +220,7 @@ @Test public void forwardSnpToRev() { - Graph graph = getGraph(); + 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; @@ -237,7 +237,7 @@ @Test public void forwardRelToRevRevToRev() { - Graph graph = getGraph(); + 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; @@ -255,7 +255,7 @@ @Test public void forwardRevToAllDirToAll() { - Graph graph = getGraph(); + 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; @@ -314,7 +314,7 @@ @Test public void forwardSnpToAllRevToAll() { - Graph graph = getGraph(); + 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; @@ -338,7 +338,7 @@ @Test public void forwardNoEdges() { - Graph graph = getGraph(); + 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; @@ -354,7 +354,7 @@ @Test public void backwardRevToRevRevToRel() { - Graph graph = getGraph(); + 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; @@ -377,7 +377,7 @@ @Test public void forwardFromRootNodesOnly() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID swhid = new SWHID("swh:1:ori:0000000000000000000000000000000000000021"); Endpoint endpoint = new Endpoint(graph, "forward", "*"); ArrayList nodes = (ArrayList) endpoint.visitNodes(new Endpoint.Input(swhid)).result; @@ -401,7 +401,7 @@ @Test public void backwardRevToAllNodesOnly() { - Graph graph = getGraph(); + 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; diff --git a/java/src/test/java/org/softwareheritage/graph/WalkTest.java b/java/src/test/java/org/softwareheritage/graph/WalkTest.java --- a/java/src/test/java/org/softwareheritage/graph/WalkTest.java +++ b/java/src/test/java/org/softwareheritage/graph/WalkTest.java @@ -10,7 +10,7 @@ public class WalkTest extends GraphTest { @Test public void forwardRootToLeaf() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src = new SWHID("swh:1:snp:0000000000000000000000000000000000000020"); String dstFmt = "swh:1:cnt:0000000000000000000000000000000000000005"; @@ -38,7 +38,7 @@ @Test public void forwardLeafToLeaf() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src = new SWHID("swh:1:cnt:0000000000000000000000000000000000000007"); String dstFmt = "cnt"; @@ -55,7 +55,7 @@ @Test public void forwardRevToRev() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src = new SWHID("swh:1:rev:0000000000000000000000000000000000000018"); String dstFmt = "swh:1:rev:0000000000000000000000000000000000000003"; @@ -75,7 +75,7 @@ @Test public void backwardRevToRev() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src = new SWHID("swh:1:rev:0000000000000000000000000000000000000003"); String dstFmt = "swh:1:rev:0000000000000000000000000000000000000018"; @@ -95,7 +95,7 @@ @Test public void backwardCntToFirstSnp() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src = new SWHID("swh:1:cnt:0000000000000000000000000000000000000001"); String dstFmt = "snp"; @@ -132,7 +132,7 @@ @Test public void forwardRevToFirstCnt() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src = new SWHID("swh:1:rev:0000000000000000000000000000000000000009"); String dstFmt = "cnt"; @@ -167,7 +167,7 @@ @Test public void backwardDirToFirstRel() { - Graph graph = getGraph(); + SwhBidirectionalGraph graph = getGraph(); SWHID src = new SWHID("swh:1:dir:0000000000000000000000000000000000000016"); String dstFmt = "rel";