diff --git a/java/server/src/main/java/org/softwareheritage/graph/Graph.java b/java/server/src/main/java/org/softwareheritage/graph/Graph.java index b38dc6f..d77724f 100644 --- a/java/server/src/main/java/org/softwareheritage/graph/Graph.java +++ b/java/server/src/main/java/org/softwareheritage/graph/Graph.java @@ -1,212 +1,212 @@ package org.softwareheritage.graph; 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 org.softwareheritage.graph.Node; import org.softwareheritage.graph.SwhPID; import org.softwareheritage.graph.backend.NodeIdMap; import org.softwareheritage.graph.backend.NodeTypesMap; /** * Main class storing the compressed graph and node id mappings. *

* The compressed graph is stored using the WebGraph * ecosystem. Additional mappings are necessary because Software Heritage uses string based persistent * identifiers (PID) while WebGraph uses integers internally. These two mappings (long id ↔ * PID) are used for the input (users refer to the graph using PID) and the output (convert back to * PID for users results). However, since graph traversal can be restricted depending on the node * type (see {@link AllowedEdges}), a long id → node type map is stored as well to avoid a full * PID lookup. * * @author The Software Heritage developers - * @see org.softwareheritage.graph.AllowedEdges - * @see org.softwareheritage.graph.NodeIdMap; - * @see org.softwareheritage.graph.NodeTypesMap; + * @see org.softwareheritage.graph.AllowedEdges; + * @see org.softwareheritage.graph.backend.NodeIdMap; + * @see org.softwareheritage.graph.backend.NodeTypesMap; */ public class Graph implements FlyweightPrototype { /** File extension for the SWH PID to long node id map */ public static final String PID_TO_NODE = ".pid2node.csv"; /** File extension for the long node id to SWH PID map */ public static final String NODE_TO_PID = ".node2pid.csv"; /** File extension for the long node id to node typ map */ public static final String NODE_TO_TYPE = ".node2type.map"; /** Compressed graph stored as a {@link it.unimi.dsi.big.webgraph.BVGraph} */ BVGraph graph; /** Transposed compressed graph (used for backward traversals) */ BVGraph graphTransposed; /** Path and basename of the compressed graph */ String path; /** Mapping long id ↔ SWH PIDs */ NodeIdMap nodeIdMap; /** Mapping long id → node types */ NodeTypesMap nodeTypesMap; /** * Constructor. * * @param path path and basename of the compressed graph to load */ public Graph(String path) throws IOException { this.graph = BVGraph.load(path); this.graphTransposed = BVGraph.load(path + "-transposed"); this.path = path; this.nodeIdMap = new NodeIdMap(path, getNbNodes()); this.nodeTypesMap = new NodeTypesMap(path); } // Protected empty constructor to implement copy() protected Graph() { } /** * 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; } /** * Cleans up graph resources after use. */ public void cleanUp() throws IOException { nodeIdMap.close(); } /** * Returns the graph full path. * * @return graph full path */ public String getPath() { return path; } /** * 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 * @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 */ public Node.Type getNodeType(long nodeId) { return nodeTypesMap.getType(nodeId); } /** * Returns number of nodes in the graph. * * @return number of nodes in the graph */ public long getNbNodes() { return graph.numNodes(); } /** * Returns number of edges in the graph. * * @return number of edges in the graph */ public long getNbEdges() { 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 */ public LazyLongIterator successors(long nodeId) { return graph.successors(nodeId); } /** * Returns the outdegree of a node. * * @param nodeId node specified as a long id * @return outdegree of a node */ 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 graphTransposed.successors(nodeId); } /** * Returns the indegree of a node. * * @param nodeId node specified as a long id * @return indegree of a node */ public long indegree(long nodeId) { return graphTransposed.outdegree(nodeId); } /** * Returns the degree of a node, depending on graph orientation. * * @param nodeId node specified as a long id * @param useTransposed boolean value to use transposed graph * @return degree of a node */ public long degree(long nodeId, boolean useTransposed) { return (useTransposed) ? indegree(nodeId) : outdegree(nodeId); } /** * Returns the neighbors of a node (as a lazy iterator), depending on graph orientation. * * @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 */ public LazyLongIterator neighbors(long nodeId, boolean useTransposed) { return (useTransposed) ? predecessors(nodeId) : successors(nodeId); } } diff --git a/java/server/src/main/java/org/softwareheritage/graph/SwhPath.java b/java/server/src/main/java/org/softwareheritage/graph/SwhPath.java index 49925d7..83772a2 100644 --- a/java/server/src/main/java/org/softwareheritage/graph/SwhPath.java +++ b/java/server/src/main/java/org/softwareheritage/graph/SwhPath.java @@ -1,124 +1,124 @@ package org.softwareheritage.graph; import java.util.ArrayList; import com.fasterxml.jackson.annotation.JsonValue; import org.softwareheritage.graph.SwhPID; /** * Wrapper class to store a list of {@link SwhPID}. * * @author The Software Heritage developers * @see org.softwareheritage.graph.SwhPID */ public class SwhPath { /** Internal list of {@link SwhPID} */ ArrayList path; /** * Constructor. */ public SwhPath() { this.path = new ArrayList(); } /** * Constructor. * * @param swhPIDs variable number of string PIDs to initialize this path with */ public SwhPath(String... swhPIDs) { this(); for (String swhPID : swhPIDs) { add(new SwhPID(swhPID)); } } /** * Constructor. * * @param swhPIDs variable number of {@link SwhPID} to initialize this path with * @see org.softwareheritage.graph.SwhPID */ public SwhPath(SwhPID... swhPIDs) { this(); for (SwhPID swhPID : swhPIDs) { add(swhPID); } } /** * Returns this path as a list of {@link SwhPID}. * * @return list of {@link SwhPID} constituting the path * @see org.softwareheritage.graph.SwhPID */ @JsonValue public ArrayList getPath() { return path; } /** * Adds a {@link SwhPID} to this path. * - * @param {@link SwhPID} to add to this path + * @param swhPID {@link SwhPID} to add to this path * @see org.softwareheritage.graph.SwhPID */ public void add(SwhPID swhPID) { path.add(swhPID); } /** * Returns the {@link SwhPID} at the specified position in this path. * * @param index position of the {@link SwhPID} to return * @return {@link SwhPID} at the specified position * @see org.softwareheritage.graph.SwhPID */ public SwhPID get(int index) { return path.get(index); } /** * Returns the number of elements in this path. * * @return number of elements in this path */ public int size() { return path.size(); } @Override public boolean equals(Object otherObj) { if (otherObj == this) return true; if (!(otherObj instanceof SwhPath)) return false; SwhPath other = (SwhPath) otherObj; if (size() != other.size()) { return false; } for (int i = 0; i < size(); i++) { SwhPID thisSwhPID = get(i); SwhPID otherSwhPID = other.get(i); if (!thisSwhPID.equals(otherSwhPID)) { return false; } } return true; } @Override public String toString() { String str = new String(); for (SwhPID swhPID : path) { str += swhPID + "/"; } return str; } }