Changeset View
Changeset View
Standalone View
Standalone View
java/server/src/main/java/org/softwareheritage/graph/Graph.java
package org.softwareheritage.graph; | package org.softwareheritage.graph; | ||||
import java.io.IOException; | import java.io.IOException; | ||||
import it.unimi.dsi.big.webgraph.BVGraph; | import it.unimi.dsi.big.webgraph.BVGraph; | ||||
import org.softwareheritage.graph.Node; | import org.softwareheritage.graph.Node; | ||||
import org.softwareheritage.graph.SwhId; | import org.softwareheritage.graph.SwhId; | ||||
import org.softwareheritage.graph.backend.NodeIdMap; | import org.softwareheritage.graph.backend.NodeIdMap; | ||||
import org.softwareheritage.graph.backend.NodeTypesMap; | import org.softwareheritage.graph.backend.NodeTypesMap; | ||||
/** | /** | ||||
* Main class storing the compressed graph and node id mappings. | * Main class storing the compressed graph and node id mappings. | ||||
* <p> | |||||
* The compressed graph is stored using the <a href="http://webgraph.di.unimi.it/">WebGraph</a> | |||||
* ecosystem. Additional mappings are necessary because Software Heritage uses string based <a | |||||
* href="https://docs.softwareheritage.org/devel/swh-model/persistent-identifiers.html">persistent | |||||
* identifiers</a> (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 Thibault Allançon | * @author Thibault Allançon | ||||
* @version 0.0.1 | * @version 0.0.1 | ||||
* @since 0.0.1 | * @since 0.0.1 | ||||
* @see org.softwareheritage.graph.AllowedEdges | |||||
* @see org.softwareheritage.graph.NodeIdMap; | |||||
* @see org.softwareheritage.graph.NodeTypesMap; | |||||
*/ | */ | ||||
public class Graph { | public class Graph { | ||||
/** File extension for the SWH PID to long node id map */ | /** File extension for the SWH PID to long node id map */ | ||||
public static final String PID_TO_NODE = ".pid2node.csv"; | public static final String PID_TO_NODE = ".pid2node.csv"; | ||||
/** File extension for the long node id to SWH PID map */ | /** File extension for the long node id to SWH PID map */ | ||||
public static final String NODE_TO_PID = ".node2pid.csv"; | public static final String NODE_TO_PID = ".node2pid.csv"; | ||||
/** File extension for the long node id to node typ map */ | /** File extension for the long node id to node typ map */ | ||||
▲ Show 20 Lines • Show All 89 Lines • ▼ Show 20 Lines | public class Graph { | ||||
public long getNbEdges() { | public long getNbEdges() { | ||||
return graph.numArcs(); | return graph.numArcs(); | ||||
} | } | ||||
/** | /** | ||||
* Returns list of successors of a node. | * Returns list of successors of a node. | ||||
* | * | ||||
* @param nodeId node specified as a long id | * @param nodeId node specified as a long id | ||||
* @return list of successors of the node, specified as a {@link LongBigArrays} | * @return list of successors of the node, specified as a <a | ||||
* @see it.unimi.dsi.fastutil.longs.LongBigArrays | * href="http://fastutil.di.unimi.it/">fastutil</a> LongBigArrays | ||||
*/ | */ | ||||
public long[][] successors(long nodeId) { | public long[][] successors(long nodeId) { | ||||
return graph.successorBigArray(nodeId); | return graph.successorBigArray(nodeId); | ||||
} | } | ||||
/** | /** | ||||
* Returns the outdegree of a node. | * Returns the outdegree of a node. | ||||
* | * | ||||
* @param nodeId node specified as a long id | * @param nodeId node specified as a long id | ||||
* @return outdegree of a node | * @return outdegree of a node | ||||
*/ | */ | ||||
public long outdegree(long nodeId) { | public long outdegree(long nodeId) { | ||||
return graph.outdegree(nodeId); | return graph.outdegree(nodeId); | ||||
} | } | ||||
/** | /** | ||||
* Returns list of predecessors of a node. | * Returns list of predecessors of a node. | ||||
* | * | ||||
* @param nodeId node specified as a long id | * @param nodeId node specified as a long id | ||||
* @return list of predecessors of the node, specified as a {@link LongBigArrays} | * @return list of successors of the node, specified as a <a | ||||
* @see it.unimi.dsi.fastutil.longs.LongBigArrays | * href="http://fastutil.di.unimi.it/">fastutil</a> LongBigArrays | ||||
*/ | */ | ||||
public long[][] predecessors(long nodeId) { | public long[][] predecessors(long nodeId) { | ||||
return graphTransposed.successorBigArray(nodeId); | return graphTransposed.successorBigArray(nodeId); | ||||
} | } | ||||
/** | /** | ||||
* Returns the indegree of a node. | * Returns the indegree of a node. | ||||
* | * | ||||
Show All 15 Lines | public long degree(long nodeId, boolean useTransposed) { | ||||
return (useTransposed) ? indegree(nodeId) : outdegree(nodeId); | return (useTransposed) ? indegree(nodeId) : outdegree(nodeId); | ||||
} | } | ||||
/** | /** | ||||
* Returns the neighbors of a node, depending on graph orientation. | * Returns the neighbors of a node, depending on graph orientation. | ||||
* | * | ||||
* @param nodeId node specified as a long id | * @param nodeId node specified as a long id | ||||
* @param useTransposed boolean value to use transposed graph | * @param useTransposed boolean value to use transposed graph | ||||
* @return list of neighbors of the node, specified as a {@link LongBigArrays} | * @return list of successors of the node, specified as a <a | ||||
* @see it.unimi.dsi.fastutil.longs.LongBigArrays | * href="http://fastutil.di.unimi.it/">fastutil</a> LongBigArrays | ||||
*/ | */ | ||||
public long[][] neighbors(long nodeId, boolean useTransposed) { | public long[][] neighbors(long nodeId, boolean useTransposed) { | ||||
return (useTransposed) ? predecessors(nodeId) : successors(nodeId); | return (useTransposed) ? predecessors(nodeId) : successors(nodeId); | ||||
} | } | ||||
} | } |