diff --git a/java/README.md b/java/README.md --- a/java/README.md +++ b/java/README.md @@ -15,7 +15,7 @@ ```bash $ java -cp target/swh-graph-*.jar \ - org.softwareheritage.graph.App \ + org.softwareheritage.graph.server.App \ ``` @@ -44,7 +44,7 @@ $ mvn compile assembly:single # Dump mapping files $ java -cp target/swh-graph-*.jar \ - org.softwareheritage.graph.backend.MapBuilder \ + org.softwareheritage.graph.maps.MapBuilder \ src/swh/graph/tests/dataset/example.nodes.csv.gz \ src/swh/graph/tests/dataset/output/example ``` diff --git a/java/pom.xml b/java/pom.xml --- a/java/pom.xml +++ b/java/pom.xml @@ -101,6 +101,11 @@ commons-codec 1.11 + + it.unimi.dsi + dsiutils + 2.6.2 + @@ -159,7 +164,7 @@ - org.softwareheritage.graph.App + org.softwareheritage.graph.server.App 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,10 +7,6 @@ import com.fasterxml.jackson.databind.ObjectMapper; import com.fasterxml.jackson.databind.PropertyNamingStrategy; -import org.softwareheritage.graph.algo.NodeIdConsumer; - -import org.softwareheritage.graph.algo.Stats; -import org.softwareheritage.graph.algo.Traversal; public class Entry { private Graph graph; @@ -39,11 +35,11 @@ } private interface NodeCountVisitor { - void accept(long nodeId, NodeIdConsumer consumer); + void accept(long nodeId, Traversal.NodeIdConsumer consumer); } private int count_visitor(NodeCountVisitor f, long srcNodeId) { - int count[] = { 0 }; + int[] count = { 0 }; f.accept(srcNodeId, (node) -> { count[0]++; }); return count[0]; } diff --git a/java/src/main/java/org/softwareheritage/graph/Graph.java b/java/src/main/java/org/softwareheritage/graph/Graph.java --- a/java/src/main/java/org/softwareheritage/graph/Graph.java +++ b/java/src/main/java/org/softwareheritage/graph/Graph.java @@ -2,14 +2,10 @@ import java.io.IOException; -import it.unimi.dsi.big.webgraph.BVGraph; -import it.unimi.dsi.lang.FlyweightPrototype; -import it.unimi.dsi.big.webgraph.LazyLongIterator; +import it.unimi.dsi.big.webgraph.*; -import org.softwareheritage.graph.Node; -import org.softwareheritage.graph.SwhPID; -import org.softwareheritage.graph.backend.NodeIdMap; -import org.softwareheritage.graph.backend.NodeTypesMap; +import org.softwareheritage.graph.maps.NodeIdMap; +import org.softwareheritage.graph.maps.NodeTypesMap; /** * Main class storing the compressed graph and node id mappings. @@ -25,11 +21,11 @@ * * @author The Software Heritage developers * @see org.softwareheritage.graph.AllowedEdges - * @see org.softwareheritage.graph.backend.NodeIdMap - * @see org.softwareheritage.graph.backend.NodeTypesMap + * @see org.softwareheritage.graph.maps.NodeIdMap + * @see org.softwareheritage.graph.maps.NodeTypesMap */ -public class Graph implements FlyweightPrototype { +public class Graph extends ImmutableGraph { /** File extension for the SWH PID to long node id map */ public static final String PID_TO_NODE = ".pid2node.bin"; /** File extension for the long node id to SWH PID map */ @@ -38,9 +34,9 @@ public static final String NODE_TO_TYPE = ".node2type.map"; /** Compressed graph stored as a {@link it.unimi.dsi.big.webgraph.BVGraph} */ - BVGraph graph; + ImmutableGraph graph; /** Transposed compressed graph (used for backward traversals) */ - BVGraph graphTransposed; + ImmutableGraph graphTransposed; /** Path and basename of the compressed graph */ String path; /** Mapping long id ↔ SWH PIDs */ @@ -54,90 +50,63 @@ * @param path path and basename of the compressed graph to load */ public Graph(String path) throws IOException { + this.path = path; this.graph = BVGraph.loadMapped(path); this.graphTransposed = BVGraph.loadMapped(path + "-transposed"); - this.path = path; this.nodeTypesMap = new NodeTypesMap(path); - - // TODO: we don't need to load the nodeIdMap now that all the - // translation between ints and PIDs is happening on the Python side. - // However, some parts of the code still depend on this, so it's - // commented out while we decide on what to do with it. - this.nodeIdMap = null; // new NodeIdMap(path, getNbNodes()); + this.nodeIdMap = new NodeIdMap(path, numNodes()); } - // Protected empty constructor to implement copy() - protected Graph() { } + protected Graph(ImmutableGraph graph, ImmutableGraph graphTransposed, + String path, NodeIdMap nodeIdMap, NodeTypesMap nodeTypesMap) { + this.graph = graph; + this.graphTransposed = graphTransposed; + this.path = path; + this.nodeIdMap = nodeIdMap; + this.nodeTypesMap = nodeTypesMap; + } /** * Return a flyweight copy of the graph. */ @Override public Graph copy() { - final Graph ng = new Graph(); - ng.graph = this.graph.copy(); - ng.graphTransposed = this.graphTransposed.copy(); - ng.path = path; - ng.nodeIdMap = this.nodeIdMap; - ng.nodeTypesMap = this.nodeTypesMap; - return ng; + return new Graph(this.graph.copy(), this.graphTransposed.copy(), this.path, this.nodeIdMap, this.nodeTypesMap); } - /** - * Cleans up graph resources after use. - */ - public void cleanUp() throws IOException { - nodeIdMap.close(); + @Override + public boolean randomAccess() { + return graph.randomAccess() && graphTransposed.randomAccess(); } /** - * Returns the graph full path. - * - * @return graph full path + * Return a transposed version of the graph. */ - public String getPath() { - return path; + public Graph transpose() { + return new Graph(this.graphTransposed, this.graph, this.path, this.nodeIdMap, this.nodeTypesMap); } /** - * Converts {@link SwhPID} node to long. - * - * @param swhPID node specified as a {@link SwhPID} - * @return internal long node id - * @see org.softwareheritage.graph.SwhPID + * Return a symmetric version of the graph. */ - public long getNodeId(SwhPID swhPID) { - return nodeIdMap.getNodeId(swhPID); + public Graph symmetrize() { + ImmutableGraph symmetric = Transform.union(graph, graphTransposed); + return new Graph(symmetric, symmetric, this.path, this.nodeIdMap, this.nodeTypesMap); } /** - * Converts long id node to {@link SwhPID}. - * - * @param nodeId node specified as a long id - * @return external SWH PID - * @see org.softwareheritage.graph.SwhPID - */ - public SwhPID getSwhPID(long nodeId) { - return nodeIdMap.getSwhPID(nodeId); - } - - /** - * Returns node type. - * - * @param nodeId node specified as a long id - * @return corresponding node type - * @see org.softwareheritage.graph.Node.Type + * Cleans up graph resources after use. */ - public Node.Type getNodeType(long nodeId) { - return nodeTypesMap.getType(nodeId); + public void cleanUp() throws IOException { + nodeIdMap.close(); } - /** * Returns number of nodes in the graph. * * @return number of nodes in the graph */ - public long getNbNodes() { + @Override + public long numNodes() { return graph.numNodes(); } @@ -146,7 +115,8 @@ * * @return number of edges in the graph */ - public long getNbEdges() { + @Override + public long numArcs() { return graph.numArcs(); } @@ -157,16 +127,54 @@ * @return lazy iterator of successors of the node, specified as a WebGraph LazyLongIterator */ + @Override public LazyLongIterator successors(long nodeId) { return graph.successors(nodeId); } + /** + * Returns lazy iterator of successors of a node while following a specific set of edge types. + * + * @param nodeId node specified as a long id + * @param allowedEdges the specification of which edges can be traversed + * @return lazy iterator of successors of the node, specified as a WebGraph LazyLongIterator + */ + public LazyLongIterator successors(long nodeId, AllowedEdges allowedEdges) { + if (allowedEdges.restrictedTo == null) { + // All edges are allowed, bypass edge check + return this.successors(nodeId); + } else { + LazyLongIterator allSuccessors = this.successors(nodeId); + return new LazyLongIterator() { + @Override + public long nextLong() { + long neighbor; + while ((neighbor = allSuccessors.nextLong()) != -1) { + if (allowedEdges.isAllowed(nodeId, neighbor)) { + return neighbor; + } + } + return -1; + } + + @Override + public long skip(final long n) { + long i; + for (i = 0; i < n && nextLong() != -1; i++); + return i; + } + }; + } + } + /** * Returns the outdegree of a node. * * @param nodeId node specified as a long id * @return outdegree of a node */ + @Override public long outdegree(long nodeId) { return graph.outdegree(nodeId); } @@ -179,7 +187,7 @@ * href="http://webgraph.di.unimi.it/">WebGraph LazyLongIterator */ public LazyLongIterator predecessors(long nodeId) { - return graphTransposed.successors(nodeId); + return this.transpose().successors(nodeId); } /** @@ -189,39 +197,57 @@ * @return indegree of a node */ public long indegree(long nodeId) { - return graphTransposed.outdegree(nodeId); + return this.transpose().outdegree(nodeId); } /** - * Returns the degree of a node, depending on graph orientation. + * Returns the underlying BVGraph. * - * @param nodeId node specified as a long id - * @param useTransposed boolean value to use transposed graph - * @return degree of a node + * @return WebGraph BVGraph + */ + public ImmutableGraph getGraph() { + return this.graph; + } + + /** + * Returns the graph full path. + * + * @return graph full path */ - public long degree(long nodeId, boolean useTransposed) { - return (useTransposed) ? indegree(nodeId) : outdegree(nodeId); + public String getPath() { + return path; } /** - * Returns the neighbors of a node (as a lazy iterator), depending on graph orientation. + * Converts {@link SwhPID} node to long. + * + * @param swhPID node specified as a {@link SwhPID} + * @return internal long node id + * @see org.softwareheritage.graph.SwhPID + */ + public long getNodeId(SwhPID swhPID) { + return nodeIdMap.getNodeId(swhPID); + } + + /** + * Converts long id node to {@link SwhPID}. * * @param nodeId node specified as a long id - * @param useTransposed boolean value to use transposed graph - * @return lazy iterator of neighbors of the node, specified as a WebGraph LazyLongIterator + * @return external SWH PID + * @see org.softwareheritage.graph.SwhPID */ - public LazyLongIterator neighbors(long nodeId, boolean useTransposed) { - return (useTransposed) ? predecessors(nodeId) : successors(nodeId); + public SwhPID getSwhPID(long nodeId) { + return nodeIdMap.getSwhPID(nodeId); } /** - * Returns the underlying BVGraph. + * Returns node type. * - * @param useTransposed boolean value to use transposed graph - * @return WebGraph BVGraph + * @param nodeId node specified as a long id + * @return corresponding node type + * @see org.softwareheritage.graph.Node.Type */ - public BVGraph getBVGraph(boolean useTransposed) { - return (useTransposed) ? this.graphTransposed : this.graph; + public Node.Type getNodeType(long nodeId) { + return nodeTypesMap.getType(nodeId); } } diff --git a/java/src/main/java/org/softwareheritage/graph/Neighbors.java b/java/src/main/java/org/softwareheritage/graph/Neighbors.java deleted file mode 100644 --- a/java/src/main/java/org/softwareheritage/graph/Neighbors.java +++ /dev/null @@ -1,84 +0,0 @@ -package org.softwareheritage.graph; - -import java.util.Iterator; - -import it.unimi.dsi.big.webgraph.LazyLongIterator; - -import org.softwareheritage.graph.AllowedEdges; -import org.softwareheritage.graph.Graph; - -/** - * Iterator class to go over a node neighbors in the graph. - *

- * Wrapper iterator class to easily deal with {@link AllowedEdges} during traversals. - * - * @author The Software Heritage developers - * @see org.softwareheritage.graph.AllowedEdges - */ - -public class Neighbors implements Iterable { - /** Graph used to explore neighbors */ - Graph graph; - /** Boolean to specify the use of the transposed graph */ - boolean useTransposed; - /** Graph edge restriction */ - AllowedEdges edges; - /** Source node from which neighbors will be listed */ - long srcNodeId; - - /** - * Constructor. - * - * @param graph graph used to explore neighbors - * @param useTransposed boolean value to use transposed graph - * @param edges edges allowed to be used in the graph - * @param srcNodeId source node from where to list neighbors - */ - public Neighbors(Graph graph, boolean useTransposed, AllowedEdges edges, long srcNodeId) { - this.graph = graph; - this.useTransposed = useTransposed; - this.edges = edges; - this.srcNodeId = srcNodeId; - } - - @Override - public Iterator iterator() { - return new NeighborsIterator(); - } - - /** - * Inner class for {@link Neighbors} iterator. - * - * @author The Software Heritage developers - */ - - public class NeighborsIterator implements Iterator { - LazyLongIterator neighbors; - long nextNeighborId; - - public NeighborsIterator() { - this.neighbors = graph.neighbors(srcNodeId, useTransposed); - this.nextNeighborId = -1; - } - - public boolean hasNext() { - // Case 1: no edge restriction, bypass type checks and skip to next neighbor - if (edges.restrictedTo == null) { - nextNeighborId = neighbors.nextLong(); - return (nextNeighborId != -1); - } - - // Case 2: edge restriction, look ahead for next neighbor - while ((nextNeighborId = neighbors.nextLong()) != -1) { - if (edges.isAllowed(srcNodeId, nextNeighborId)) { - return true; - } - } - return false; - } - - public Long next() { - return nextNeighborId; - } - } -} diff --git a/java/src/main/java/org/softwareheritage/graph/algo/Stats.java b/java/src/main/java/org/softwareheritage/graph/Stats.java rename from java/src/main/java/org/softwareheritage/graph/algo/Stats.java rename to java/src/main/java/org/softwareheritage/graph/Stats.java --- a/java/src/main/java/org/softwareheritage/graph/algo/Stats.java +++ b/java/src/main/java/org/softwareheritage/graph/Stats.java @@ -1,4 +1,4 @@ -package org.softwareheritage.graph.algo; +package org.softwareheritage.graph; import java.io.FileInputStream; import java.io.IOException; @@ -14,19 +14,19 @@ */ public class Stats { - public class Counts { + public static class Counts { public long nodes; public long edges; } - public class Ratios { + public static class Ratios { public double compression; public double bitsPerNode; public double bitsPerEdge; public double avgLocality; } - public class Degree { + public static class Degree { public long min; public long max; public double avg; diff --git a/java/src/main/java/org/softwareheritage/graph/SwhPath.java b/java/src/main/java/org/softwareheritage/graph/SwhPath.java --- a/java/src/main/java/org/softwareheritage/graph/SwhPath.java +++ b/java/src/main/java/org/softwareheritage/graph/SwhPath.java @@ -1,10 +1,8 @@ package org.softwareheritage.graph; -import java.util.ArrayList; - import com.fasterxml.jackson.annotation.JsonValue; -import org.softwareheritage.graph.SwhPID; +import java.util.ArrayList; /** * Wrapper class to store a list of {@link SwhPID}. @@ -21,7 +19,7 @@ * Constructor. */ public SwhPath() { - this.path = new ArrayList(); + this.path = new ArrayList<>(); } /** @@ -115,10 +113,10 @@ @Override public String toString() { - String str = new String(); + StringBuilder str = new StringBuilder(); for (SwhPID swhPID : path) { - str += swhPID + "/"; + str.append(swhPID).append("/"); } - return str; + return str.toString(); } } diff --git a/java/src/main/java/org/softwareheritage/graph/algo/Traversal.java b/java/src/main/java/org/softwareheritage/graph/Traversal.java rename from java/src/main/java/org/softwareheritage/graph/algo/Traversal.java rename to java/src/main/java/org/softwareheritage/graph/Traversal.java --- a/java/src/main/java/org/softwareheritage/graph/algo/Traversal.java +++ b/java/src/main/java/org/softwareheritage/graph/Traversal.java @@ -1,14 +1,11 @@ -package org.softwareheritage.graph.algo; +package org.softwareheritage.graph; import java.util.*; +import java.util.function.Consumer; +import java.util.function.LongConsumer; -import it.unimi.dsi.bits.LongArrayBitVector; - -import org.softwareheritage.graph.AllowedEdges; -import org.softwareheritage.graph.Endpoint; -import org.softwareheritage.graph.Graph; -import org.softwareheritage.graph.Neighbors; -import org.softwareheritage.graph.Node; +import it.unimi.dsi.big.webgraph.LazyLongIterator; +import org.softwareheritage.graph.server.Endpoint; /** * Traversal algorithms on the compressed graph. @@ -18,14 +15,12 @@ * PID. * * @author The Software Heritage developers - * @see org.softwareheritage.graph.Endpoint + * @see Endpoint */ public class Traversal { /** Graph used in the traversal */ Graph graph; - /** Boolean to specify the use of the transposed graph */ - boolean useTransposed; /** Graph edge restriction */ AllowedEdges edges; @@ -39,6 +34,8 @@ /** random number generator, for random walks */ Random rng; + + /** * Constructor. * @@ -52,11 +49,13 @@ throw new IllegalArgumentException("Unknown traversal direction: " + direction); } - this.graph = graph; - this.useTransposed = (direction.equals("backward")); + if (direction.equals("backward")) { + this.graph = graph.transpose(); + } else { + this.graph = graph; + } this.edges = new AllowedEdges(graph, edgesFmt); - long nbNodes = graph.getNbNodes(); this.visited = new HashSet<>(); this.parentNode = new HashMap<>(); this.nbEdgesAccessed = 0; @@ -82,10 +81,10 @@ } /** - * Push version of {@link leaves}: will fire passed callback for each leaf. + * Push version of {@link #leaves} will fire passed callback for each leaf. */ public void leavesVisitor(long srcNodeId, NodeIdConsumer cb) { - Stack stack = new Stack(); + Stack stack = new Stack<>(); this.nbEdgesAccessed = 0; stack.push(srcNodeId); @@ -95,8 +94,9 @@ long currentNodeId = stack.pop(); long neighborsCnt = 0; - nbEdgesAccessed += graph.degree(currentNodeId, useTransposed); - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { + nbEdgesAccessed += graph.outdegree(currentNodeId); + LazyLongIterator it = graph.successors(currentNodeId, edges); + for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { neighborsCnt++; if (!visited.contains(neighborNodeId)) { stack.push(neighborNodeId); @@ -117,18 +117,19 @@ * @return list of node ids corresponding to the leaves */ public ArrayList leaves(long srcNodeId) { - ArrayList nodeIds = new ArrayList(); - leavesVisitor(srcNodeId, (nodeId) -> nodeIds.add(nodeId)); + ArrayList nodeIds = new ArrayList<>(); + leavesVisitor(srcNodeId, nodeIds::add); return nodeIds; } /** - * Push version of {@link neighbors}: will fire passed callback on each + * Push version of {@link #neighbors}: will fire passed callback on each * neighbor. */ public void neighborsVisitor(long srcNodeId, NodeIdConsumer cb) { - this.nbEdgesAccessed = graph.degree(srcNodeId, useTransposed); - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, srcNodeId)) { + this.nbEdgesAccessed = graph.outdegree(srcNodeId); + LazyLongIterator it = graph.successors(srcNodeId, edges); + for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { cb.accept(neighborNodeId); } } @@ -140,17 +141,17 @@ * @return list of node ids corresponding to the neighbors */ public ArrayList neighbors(long srcNodeId) { - ArrayList nodeIds = new ArrayList(); - neighborsVisitor(srcNodeId, (nodeId) -> nodeIds.add(nodeId)); + ArrayList nodeIds = new ArrayList<>(); + neighborsVisitor(srcNodeId, nodeIds::add); return nodeIds; } /** - * Push version of {@link visitNodes}: will fire passed callback on each + * Push version of {@link #visitNodes}: will fire passed callback on each * visited node. */ public void visitNodesVisitor(long srcNodeId, NodeIdConsumer nodeCb, EdgeIdConsumer edgeCb) { - Stack stack = new Stack(); + Stack stack = new Stack<>(); this.nbEdgesAccessed = 0; stack.push(srcNodeId); @@ -162,8 +163,9 @@ nodeCb.accept(currentNodeId); } - nbEdgesAccessed += graph.degree(currentNodeId, useTransposed); - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { + nbEdgesAccessed += graph.outdegree(currentNodeId); + LazyLongIterator it = graph.successors(currentNodeId, edges); + for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { if (edgeCb != null) { edgeCb.accept(currentNodeId, neighborNodeId); } @@ -187,17 +189,17 @@ * @return list of explored node ids */ public ArrayList visitNodes(long srcNodeId) { - ArrayList nodeIds = new ArrayList(); - visitNodesVisitor(srcNodeId, (nodeId) -> nodeIds.add(nodeId)); + ArrayList nodeIds = new ArrayList<>(); + visitNodesVisitor(srcNodeId, nodeIds::add); return nodeIds; } /** - * Push version of {@link visitPaths}: will fire passed callback on each + * Push version of {@link #visitPaths}: will fire passed callback on each * discovered (complete) path. */ public void visitPathsVisitor(long srcNodeId, PathConsumer cb) { - Stack currentPath = new Stack(); + Stack currentPath = new Stack<>(); this.nbEdgesAccessed = 0; visitPathsInternalVisitor(srcNodeId, currentPath, cb); } @@ -210,7 +212,7 @@ */ public ArrayList> visitPaths(long srcNodeId) { ArrayList> paths = new ArrayList<>(); - visitPathsVisitor(srcNodeId, (path) -> paths.add(path)); + visitPathsVisitor(srcNodeId, paths::add); return paths; } @@ -220,17 +222,15 @@ currentPath.push(currentNodeId); long visitedNeighbors = 0; - nbEdgesAccessed += graph.degree(currentNodeId, useTransposed); - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { + nbEdgesAccessed += graph.outdegree(currentNodeId); + LazyLongIterator it = graph.successors(currentNodeId, edges); + for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { visitPathsInternalVisitor(neighborNodeId, currentPath, cb); visitedNeighbors++; } if (visitedNeighbors == 0) { - ArrayList path = new ArrayList(); - for (long nodeId : currentPath) { - path.add(nodeId); - } + ArrayList path = new ArrayList<>(currentPath); cb.accept(path); } @@ -246,7 +246,7 @@ * @return found path as a list of node ids */ public ArrayList walk(long srcNodeId, T dst, String visitOrder) { - long dstNodeId = -1; + long dstNodeId; if (visitOrder.equals("dfs")) { dstNodeId = walkInternalDFS(srcNodeId, dst); } else if (visitOrder.equals("bfs")) { @@ -259,8 +259,7 @@ throw new IllegalArgumentException("Cannot find destination: " + dst); } - ArrayList nodeIds = backtracking(srcNodeId, dstNodeId); - return nodeIds; + return backtracking(srcNodeId, dstNodeId); } /** @@ -290,7 +289,7 @@ */ public ArrayList randomWalk(long srcNodeId, T dst, int retries) { long curNodeId = srcNodeId; - ArrayList path = new ArrayList(); + ArrayList path = new ArrayList<>(); this.nbEdgesAccessed = 0; boolean found; @@ -300,8 +299,8 @@ while (true) { path.add(curNodeId); - Neighbors neighbors = new Neighbors(graph, useTransposed, edges, curNodeId); - curNodeId = randomPick(neighbors.iterator()); + LazyLongIterator successors = graph.successors(curNodeId, edges); + curNodeId = randomPick(successors); if (curNodeId < 0) { found = false; break; @@ -330,14 +329,14 @@ * @param elements iterator over selection domain * @return randomly chosen element or -1 if no suitable element was found */ - private long randomPick(Iterator elements) { + private long randomPick(LazyLongIterator elements) { long curPick = -1; long seenCandidates = 0; - while (elements.hasNext()) { + for (long element; (element = elements.nextLong()) != -1;) { seenCandidates++; if (Math.round(rng.nextFloat() * (seenCandidates - 1)) == 0) { - curPick = elements.next(); + curPick = element; } } @@ -352,7 +351,7 @@ * @return final destination node or -1 if no path found */ private long walkInternalDFS(long srcNodeId, T dst) { - Stack stack = new Stack(); + Stack stack = new Stack<>(); this.nbEdgesAccessed = 0; stack.push(srcNodeId); @@ -364,8 +363,9 @@ return currentNodeId; } - nbEdgesAccessed += graph.degree(currentNodeId, useTransposed); - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { + nbEdgesAccessed += graph.outdegree(currentNodeId); + LazyLongIterator it = graph.successors(currentNodeId, edges); + for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { if (!visited.contains(neighborNodeId)) { stack.push(neighborNodeId); visited.add(neighborNodeId); @@ -385,7 +385,7 @@ * @return final destination node or -1 if no path found */ private long walkInternalBFS(long srcNodeId, T dst) { - Queue queue = new LinkedList(); + Queue queue = new LinkedList<>(); this.nbEdgesAccessed = 0; queue.add(srcNodeId); @@ -397,8 +397,9 @@ return currentNodeId; } - nbEdgesAccessed += graph.degree(currentNodeId, useTransposed); - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, currentNodeId)) { + nbEdgesAccessed += graph.outdegree(currentNodeId); + LazyLongIterator it = graph.successors(currentNodeId, edges); + for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { if (!visited.contains(neighborNodeId)) { queue.add(neighborNodeId); visited.add(neighborNodeId); @@ -437,7 +438,7 @@ * @return the found path, as a list of node ids */ private ArrayList backtracking(long srcNodeId, long dstNodeId) { - ArrayList path = new ArrayList(); + ArrayList path = new ArrayList<>(); long currentNodeId = dstNodeId; while (currentNodeId != srcNodeId) { path.add(currentNodeId); @@ -448,6 +449,13 @@ 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<>(); @@ -464,8 +472,9 @@ while (!lhsStack.isEmpty() || !rhsStack.isEmpty()) { if (!lhsStack.isEmpty()) { curNode = lhsStack.poll(); - nbEdgesAccessed += graph.degree(curNode, useTransposed); - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, curNode)) { + nbEdgesAccessed += graph.outdegree(curNode); + LazyLongIterator it = graph.successors(curNode, edges); + for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { if (!lhsVisited.contains(neighborNodeId)) { if (rhsVisited.contains(neighborNodeId)) return neighborNodeId; @@ -477,8 +486,9 @@ if (!rhsStack.isEmpty()) { curNode = rhsStack.poll(); - nbEdgesAccessed += graph.degree(curNode, useTransposed); - for (long neighborNodeId : new Neighbors(graph, useTransposed, edges, curNode)) { + nbEdgesAccessed += graph.outdegree(curNode); + LazyLongIterator it = graph.successors(curNode, edges); + for (long neighborNodeId; (neighborNodeId = it.nextLong()) != -1;) { if (!rhsVisited.contains(neighborNodeId)) { if (lhsVisited.contains(neighborNodeId)) return neighborNodeId; @@ -491,4 +501,25 @@ 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/algo/EdgeIdConsumer.java b/java/src/main/java/org/softwareheritage/graph/algo/EdgeIdConsumer.java deleted file mode 100644 --- a/java/src/main/java/org/softwareheritage/graph/algo/EdgeIdConsumer.java +++ /dev/null @@ -1,9 +0,0 @@ -package org.softwareheritage.graph.algo; - -public interface EdgeIdConsumer { - - /** Callback for incrementally receiving edge identifiers during a graph - * visit. - */ - void accept(long srcId, long dstId); -} diff --git a/java/src/main/java/org/softwareheritage/graph/algo/NodeIdConsumer.java b/java/src/main/java/org/softwareheritage/graph/algo/NodeIdConsumer.java deleted file mode 100644 --- a/java/src/main/java/org/softwareheritage/graph/algo/NodeIdConsumer.java +++ /dev/null @@ -1,11 +0,0 @@ -package org.softwareheritage.graph.algo; - -import java.util.function.LongConsumer; - -public interface NodeIdConsumer extends LongConsumer { - - /** Callback for incrementally receiving node identifiers during a graph - * visit. - */ - void accept(long nodeId); -} diff --git a/java/src/main/java/org/softwareheritage/graph/algo/NodeIdsConsumer.java b/java/src/main/java/org/softwareheritage/graph/algo/NodeIdsConsumer.java deleted file mode 100644 --- a/java/src/main/java/org/softwareheritage/graph/algo/NodeIdsConsumer.java +++ /dev/null @@ -1,14 +0,0 @@ -package org.softwareheritage.graph.algo; - -import java.util.function.BiConsumer; - -public interface NodeIdsConsumer extends BiConsumer { - - /** Callback for returning a (potentially large) list of node identifiers. - * The callback will be invoked repeatedly without reallocating the array. - * At each invocation the array might contain more than size node - * identifiers, but only identifiers located up to position size-1 are to - * be considered during that specific invocation. - */ - void accept(long nodeIds[], int size); -} diff --git a/java/src/main/java/org/softwareheritage/graph/algo/PathConsumer.java b/java/src/main/java/org/softwareheritage/graph/algo/PathConsumer.java deleted file mode 100644 --- a/java/src/main/java/org/softwareheritage/graph/algo/PathConsumer.java +++ /dev/null @@ -1,12 +0,0 @@ -package org.softwareheritage.graph.algo; - -import java.util.ArrayList; -import java.util.function.Consumer; - -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/backend/Pp.java b/java/src/main/java/org/softwareheritage/graph/backend/Pp.java deleted file mode 100644 --- a/java/src/main/java/org/softwareheritage/graph/backend/Pp.java +++ /dev/null @@ -1,42 +0,0 @@ -package org.softwareheritage.graph.backend; - -import java.io.BufferedWriter; -import java.io.FileInputStream; -import java.io.FileWriter; -import java.io.IOException; -import java.io.InputStream; -import java.io.InputStreamReader; -import java.io.Writer; -import java.util.zip.GZIPInputStream; - -import it.unimi.dsi.bits.LongArrayBitVector; -import it.unimi.dsi.fastutil.Size64; -import it.unimi.dsi.fastutil.io.BinIO; -import it.unimi.dsi.fastutil.longs.LongBigArrays; -import it.unimi.dsi.fastutil.longs.LongBigList; -import it.unimi.dsi.fastutil.objects.Object2LongFunction; -import it.unimi.dsi.fastutil.objects.ObjectBigArrays; -import it.unimi.dsi.io.FastBufferedReader; -import it.unimi.dsi.io.LineIterator; - -import org.softwareheritage.graph.Graph; -import org.softwareheritage.graph.Node; -import org.softwareheritage.graph.SwhPID; -import org.softwareheritage.graph.backend.NodeTypesMap; - -public class Pp { - - public static void main(String[] args) throws IOException { - - Object2LongFunction mphMap = null; - try { - mphMap = (Object2LongFunction) BinIO.loadObject("all.mph"); - } catch (ClassNotFoundException e) { - throw new IllegalArgumentException("The .mph file contains unknown class object: " + e); - } - - long nbIds = (mphMap instanceof Size64) ? ((Size64) mphMap).size64() : mphMap.size(); - - System.out.println("mph size: " + nbIds); - } -} 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 @@ -19,18 +19,16 @@ public class BFS { - private Graph graph; - - private void load_graph(String graphBasename) throws IOException { - System.err.println("Loading graph " + graphBasename + " ..."); - this.graph = new Graph(graphBasename); - System.err.println("Graph loaded."); - } + private final ImmutableGraph graph; private final static Logger LOGGER = LoggerFactory.getLogger(BFS.class); + public BFS(ImmutableGraph graph) { + this.graph = graph; + } + // Partly inlined from it.unimi.dsi.law.big.graph.BFS - private static void bfsperm(final ImmutableGraph graph) throws IOException { + 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); @@ -47,8 +45,6 @@ pl.itemsName = "nodes"; pl.start("Starting breadth-first visit..."); - long pos = 0; - for (long i = 0; i < n; i++) { if (visited.getBoolean(i)) continue; queue.enqueue(Longs.toByteArray(i)); @@ -101,30 +97,19 @@ return config; } - public static void main(String[] args) { + public static void main(String[] args) throws IOException { JSAPResult config = parse_args(args); String graphPath = config.getString("graphPath"); boolean useTransposed = config.getBoolean("useTransposed"); - ProgressLogger logger = new ProgressLogger(); - long startTime; - double totalTime; - + System.err.println("Loading graph " + graphPath + " ..."); + Graph graph = new Graph(graphPath); + System.err.println("Graph loaded."); - BFS bfs = new BFS(); - try { - bfs.load_graph(graphPath); - } catch (IOException e) { - System.out.println("Could not load graph: " + e); - System.exit(2); - } + if (useTransposed) + graph = graph.transpose(); - logger.start("Parallel BFS visit..."); - try { - BFS.bfsperm(bfs.graph.getBVGraph(useTransposed)); - } catch (IOException e) { - e.printStackTrace(); - } - logger.done(); + BFS bfs = new BFS(graph); + bfs.bfsperm(); } } 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 @@ -16,7 +16,7 @@ import com.martiansoftware.jsap.SimpleJSAP; import com.martiansoftware.jsap.UnflaggedOption; -import org.softwareheritage.graph.Endpoint; +import org.softwareheritage.graph.server.Endpoint; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.SwhPID; import org.softwareheritage.graph.benchmark.utils.Random; @@ -161,7 +161,7 @@ } /** - * Same as {@link timeEndpoint} but without destination or algorithm specified to endpoint call. + * Same as {@link #timeEndpoint} but without destination or algorithm specified to endpoint call. */ public void timeEndpoint(String useCaseName, Graph graph, long[] nodeIds, Function operation) throws IOException { 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 @@ -4,10 +4,9 @@ import com.martiansoftware.jsap.JSAPException; -import org.softwareheritage.graph.Endpoint; +import org.softwareheritage.graph.server.Endpoint; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.Node; -import org.softwareheritage.graph.benchmark.Benchmark; /** * Benchmark Software Heritage badlist = leo.compute(leo.graph.getBVGraph(false)); + ArrayList badlist = leo.compute(leo.graph); for (Long bad : badlist) { System.out.println(bad); } 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 @@ -4,9 +4,8 @@ import com.martiansoftware.jsap.JSAPException; -import org.softwareheritage.graph.Endpoint; +import org.softwareheritage.graph.server.Endpoint; import org.softwareheritage.graph.Graph; -import org.softwareheritage.graph.benchmark.Benchmark; /** * Benchmark Software Heritage > compute(final ImmutableGraph graph, ProgressLogger pl) throws IOException { + private ArrayList> compute(ProgressLogger pl) 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); @@ -171,7 +170,7 @@ private void parseWhitelist(String path) { System.err.println("Loading whitelist " + path + " ..."); - this.whitelist = LongArrayBitVector.ofLength(this.graph.getNbNodes()); + this.whitelist = LongArrayBitVector.ofLength(this.graph.numNodes()); Scanner scanner = null; try { scanner = new Scanner(new File(path)); @@ -205,14 +204,9 @@ forkCc.parseWhitelist(whitelistPath); } - ImmutableGraph symmetric = Transform.union( - forkCc.graph.getBVGraph(false), - forkCc.graph.getBVGraph(true) - ); - ProgressLogger logger = new ProgressLogger(); try { - ArrayList> components = forkCc.compute(symmetric, logger); + ArrayList> components = forkCc.compute(logger); printDistribution(components); // printLargestComponent(components); } catch (IOException e) { diff --git a/java/src/main/java/org/softwareheritage/graph/backend/MapBuilder.java b/java/src/main/java/org/softwareheritage/graph/maps/MapBuilder.java rename from java/src/main/java/org/softwareheritage/graph/backend/MapBuilder.java rename to java/src/main/java/org/softwareheritage/graph/maps/MapBuilder.java --- a/java/src/main/java/org/softwareheritage/graph/backend/MapBuilder.java +++ b/java/src/main/java/org/softwareheritage/graph/maps/MapBuilder.java @@ -1,4 +1,4 @@ -package org.softwareheritage.graph.backend; +package org.softwareheritage.graph.maps; import java.io.*; import java.nio.charset.StandardCharsets; @@ -6,12 +6,12 @@ import java.util.concurrent.*; import it.unimi.dsi.bits.LongArrayBitVector; +import it.unimi.dsi.fastutil.BigArrays; import it.unimi.dsi.fastutil.Size64; import it.unimi.dsi.fastutil.io.BinIO; import it.unimi.dsi.fastutil.longs.LongBigArrays; import it.unimi.dsi.fastutil.longs.LongBigList; import it.unimi.dsi.fastutil.objects.Object2LongFunction; -import it.unimi.dsi.fastutil.objects.ObjectBigArrays; import it.unimi.dsi.io.FastBufferedReader; import it.unimi.dsi.io.LineIterator; import it.unimi.dsi.logging.ProgressLogger; @@ -22,7 +22,6 @@ import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.Node; import org.softwareheritage.graph.SwhPID; -import org.softwareheritage.graph.backend.NodeTypesMap; /** * Create maps needed at runtime by the graph service, in particular: @@ -146,7 +145,7 @@ byte[] swhPIDBin = swhPID.toBytes(); long mphId = mphMap.getLong(strSwhPID); - long nodeId = LongBigArrays.get(bfsMap, mphId); + long nodeId = BigArrays.get(bfsMap, mphId); pidToNodeMap.write(swhPIDBin, 0, swhPIDBin.length); pidToNodeMap.writeLong(nodeId); diff --git a/java/src/main/java/org/softwareheritage/graph/backend/MapFile.java b/java/src/main/java/org/softwareheritage/graph/maps/MapFile.java rename from java/src/main/java/org/softwareheritage/graph/backend/MapFile.java rename to java/src/main/java/org/softwareheritage/graph/maps/MapFile.java --- a/java/src/main/java/org/softwareheritage/graph/backend/MapFile.java +++ b/java/src/main/java/org/softwareheritage/graph/maps/MapFile.java @@ -1,4 +1,4 @@ -package org.softwareheritage.graph.backend; +package org.softwareheritage.graph.maps; import java.io.File; import java.io.IOException; diff --git a/java/src/main/java/org/softwareheritage/graph/backend/NodeIdMap.java b/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java rename from java/src/main/java/org/softwareheritage/graph/backend/NodeIdMap.java rename to java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java --- a/java/src/main/java/org/softwareheritage/graph/backend/NodeIdMap.java +++ b/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java @@ -1,10 +1,9 @@ -package org.softwareheritage.graph.backend; +package org.softwareheritage.graph.maps; import java.io.IOException; import org.softwareheritage.graph.Graph; import org.softwareheritage.graph.SwhPID; -import org.softwareheritage.graph.backend.MapFile; /** * Mapping between internal long node id and external SWH PID. @@ -13,7 +12,7 @@ * {@link MapBuilder} class, then they are loaded here using mmap(). * * @author The Software Heritage developers - * @see org.softwareheritage.graph.backend.MapBuilder + * @see org.softwareheritage.graph.maps.MapBuilder */ public class NodeIdMap { diff --git a/java/src/main/java/org/softwareheritage/graph/backend/NodeTypesMap.java b/java/src/main/java/org/softwareheritage/graph/maps/NodeTypesMap.java rename from java/src/main/java/org/softwareheritage/graph/backend/NodeTypesMap.java rename to java/src/main/java/org/softwareheritage/graph/maps/NodeTypesMap.java --- a/java/src/main/java/org/softwareheritage/graph/backend/NodeTypesMap.java +++ b/java/src/main/java/org/softwareheritage/graph/maps/NodeTypesMap.java @@ -1,4 +1,4 @@ -package org.softwareheritage.graph.backend; +package org.softwareheritage.graph.maps; import java.io.IOException; diff --git a/java/src/main/java/org/softwareheritage/graph/App.java b/java/src/main/java/org/softwareheritage/graph/server/App.java rename from java/src/main/java/org/softwareheritage/graph/App.java rename to java/src/main/java/org/softwareheritage/graph/server/App.java --- a/java/src/main/java/org/softwareheritage/graph/App.java +++ b/java/src/main/java/org/softwareheritage/graph/server/App.java @@ -1,4 +1,4 @@ -package org.softwareheritage.graph; +package org.softwareheritage.graph.server; import java.io.IOException; import java.util.List; @@ -17,11 +17,9 @@ import io.javalin.Javalin; import io.javalin.http.Context; import io.javalin.plugin.json.JavalinJackson; - -import org.softwareheritage.graph.Endpoint; import org.softwareheritage.graph.Graph; +import org.softwareheritage.graph.Stats; import org.softwareheritage.graph.SwhPID; -import org.softwareheritage.graph.algo.Stats; /** * Web framework of the swh-graph server REST API. diff --git a/java/src/main/java/org/softwareheritage/graph/Endpoint.java b/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java rename from java/src/main/java/org/softwareheritage/graph/Endpoint.java rename to java/src/main/java/org/softwareheritage/graph/server/Endpoint.java --- a/java/src/main/java/org/softwareheritage/graph/Endpoint.java +++ b/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java @@ -1,11 +1,8 @@ -package org.softwareheritage.graph; +package org.softwareheritage.graph.server; import java.util.ArrayList; -import org.softwareheritage.graph.Graph; -import org.softwareheritage.graph.SwhPID; -import org.softwareheritage.graph.SwhPath; -import org.softwareheritage.graph.algo.Traversal; +import org.softwareheritage.graph.*; import org.softwareheritage.graph.benchmark.utils.Timing; /** @@ -16,7 +13,7 @@ * all the input/output node ids conversions and logging timings. * * @author The Software Heritage developers - * @see org.softwareheritage.graph.algo.Traversal + * @see Traversal */ public class Endpoint { @@ -155,7 +152,7 @@ * @param input input parameters for the underlying endpoint call * @return the resulting list of {@link SwhPID} from endpoint call and operation metadata * @see org.softwareheritage.graph.SwhPID - * @see org.softwareheritage.graph.algo.Traversal#leaves(long) + * @see Traversal#leaves(long) */ public Output leaves(Input input) { Output> output = new Output<>(); @@ -183,7 +180,7 @@ * @param input input parameters for the underlying endpoint call * @return the resulting list of {@link SwhPID} from endpoint call and operation metadata * @see org.softwareheritage.graph.SwhPID - * @see org.softwareheritage.graph.algo.Traversal#neighbors(long) + * @see Traversal#neighbors(long) */ public Output neighbors(Input input) { Output> output = new Output<>(); @@ -212,7 +209,7 @@ * @return the resulting {@link SwhPath} from endpoint call and operation metadata * @see org.softwareheritage.graph.SwhPID * @see org.softwareheritage.graph.SwhPath - * @see org.softwareheritage.graph.algo.Traversal#walk + * @see Traversal#walk */ public Output walk(Input input) { Output output = new Output<>(); @@ -258,7 +255,7 @@ * @param input input parameters for the underlying endpoint call * @return the resulting list of {@link SwhPID} from endpoint call and operation metadata * @see org.softwareheritage.graph.SwhPID - * @see org.softwareheritage.graph.algo.Traversal#visitNodes(long) + * @see Traversal#visitNodes(long) */ public Output visitNodes(Input input) { Output> output = new Output<>(); @@ -287,7 +284,7 @@ * @return the resulting list of {@link SwhPath} from endpoint call and operation metadata * @see org.softwareheritage.graph.SwhPID * @see org.softwareheritage.graph.SwhPath - * @see org.softwareheritage.graph.algo.Traversal#visitPaths(long) + * @see Traversal#visitPaths(long) */ public Output visitPaths(Input input) { Output> output = new Output<>(); 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 @@ -20,7 +20,7 @@ @BeforeClass public static void setUp() throws IOException { - Path graphPath = Paths.get("..", "..", "swh", "graph", "tests", "dataset", "output", "example"); + Path graphPath = Paths.get("..", "swh", "graph", "tests", "dataset", "output", "example"); graph = new Graph(graphPath.toString()); } 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 @@ -4,10 +4,7 @@ import org.junit.Test; -import org.softwareheritage.graph.Endpoint; -import org.softwareheritage.graph.Graph; -import org.softwareheritage.graph.GraphTest; -import org.softwareheritage.graph.SwhPID; +import org.softwareheritage.graph.server.Endpoint; // Avoid warnings concerning Endpoint.Output.result manual cast @SuppressWarnings("unchecked") 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 @@ -4,10 +4,7 @@ import org.junit.Test; -import org.softwareheritage.graph.Endpoint; -import org.softwareheritage.graph.Graph; -import org.softwareheritage.graph.GraphTest; -import org.softwareheritage.graph.SwhPID; +import org.softwareheritage.graph.server.Endpoint; // Avoid warnings concerning Endpoint.Output.result manual cast @SuppressWarnings("unchecked") 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 @@ -6,11 +6,7 @@ import org.junit.Test; -import org.softwareheritage.graph.Endpoint; -import org.softwareheritage.graph.Graph; -import org.softwareheritage.graph.GraphTest; -import org.softwareheritage.graph.SwhPID; -import org.softwareheritage.graph.SwhPath; +import org.softwareheritage.graph.server.Endpoint; // Avoid warnings concerning Endpoint.Output.result manual cast @SuppressWarnings("unchecked") 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 @@ -1,17 +1,12 @@ package org.softwareheritage.graph; -import java.util.ArrayList; import java.util.Arrays; import java.util.List; import org.junit.Assert; import org.junit.Test; -import org.softwareheritage.graph.Endpoint; -import org.softwareheritage.graph.Graph; -import org.softwareheritage.graph.GraphTest; -import org.softwareheritage.graph.SwhPID; -import org.softwareheritage.graph.SwhPath; +import org.softwareheritage.graph.server.Endpoint; public class WalkTest extends GraphTest { @Test diff --git a/swh/graph/graph.py b/swh/graph/graph.py --- a/swh/graph/graph.py +++ b/swh/graph/graph.py @@ -156,7 +156,7 @@ return self.java_graph.getPath() def __len__(self): - return self.java_graph.getNbNodes() + return self.java_graph.numNodes() def __getitem__(self, node_id): if isinstance(node_id, int): diff --git a/swh/graph/webgraph.py b/swh/graph/webgraph.py --- a/swh/graph/webgraph.py +++ b/swh/graph/webgraph.py @@ -121,7 +121,7 @@ "{in_dir}/{graph_name}.nodes.csv.zst", "|", "{java}", - "org.softwareheritage.graph.backend.MapBuilder", + "org.softwareheritage.graph.maps.MapBuilder", "{out_dir}/{graph_name}", "{tmp_dir}", ],