Changeset View
Changeset View
Standalone View
Standalone View
java/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 it.unimi.dsi.big.webgraph.ImmutableGraph; | |||||
import it.unimi.dsi.big.webgraph.Transform; | |||||
import it.unimi.dsi.lang.FlyweightPrototype; | import it.unimi.dsi.lang.FlyweightPrototype; | ||||
import it.unimi.dsi.big.webgraph.LazyLongIterator; | import it.unimi.dsi.big.webgraph.LazyLongIterator; | ||||
import org.softwareheritage.graph.Node; | import org.softwareheritage.graph.Node; | ||||
import org.softwareheritage.graph.SwhPID; | import org.softwareheritage.graph.SwhPID; | ||||
import org.softwareheritage.graph.backend.NodeIdMap; | import org.softwareheritage.graph.backend.NodeIdMap; | ||||
import org.softwareheritage.graph.backend.NodeTypesMap; | import org.softwareheritage.graph.backend.NodeTypesMap; | ||||
Show All 10 Lines | |||||
* PID lookup. | * PID lookup. | ||||
* | * | ||||
* @author The Software Heritage developers | * @author The Software Heritage developers | ||||
* @see org.softwareheritage.graph.AllowedEdges | * @see org.softwareheritage.graph.AllowedEdges | ||||
* @see org.softwareheritage.graph.backend.NodeIdMap | * @see org.softwareheritage.graph.backend.NodeIdMap | ||||
* @see org.softwareheritage.graph.backend.NodeTypesMap | * @see org.softwareheritage.graph.backend.NodeTypesMap | ||||
*/ | */ | ||||
public class Graph implements FlyweightPrototype<Graph> { | public class Graph extends ImmutableGraph { | ||||
/** 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.bin"; | public static final String PID_TO_NODE = ".pid2node.bin"; | ||||
/** 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.bin"; | public static final String NODE_TO_PID = ".node2pid.bin"; | ||||
/** File extension for the long node id to node type map */ | /** File extension for the long node id to node type map */ | ||||
public static final String NODE_TO_TYPE = ".node2type.map"; | public static final String NODE_TO_TYPE = ".node2type.map"; | ||||
/** Compressed graph stored as a {@link it.unimi.dsi.big.webgraph.BVGraph} */ | /** Compressed graph stored as a {@link it.unimi.dsi.big.webgraph.BVGraph} */ | ||||
BVGraph graph; | ImmutableGraph graph; | ||||
/** Transposed compressed graph (used for backward traversals) */ | /** Transposed compressed graph (used for backward traversals) */ | ||||
BVGraph graphTransposed; | ImmutableGraph graphTransposed; | ||||
/** Path and basename of the compressed graph */ | /** Path and basename of the compressed graph */ | ||||
String path; | String path; | ||||
/** Mapping long id ↔ SWH PIDs */ | /** Mapping long id ↔ SWH PIDs */ | ||||
NodeIdMap nodeIdMap; | NodeIdMap nodeIdMap; | ||||
/** Mapping long id → node types */ | /** Mapping long id → node types */ | ||||
NodeTypesMap nodeTypesMap; | NodeTypesMap nodeTypesMap; | ||||
/** | /** | ||||
* Constructor. | * Constructor. | ||||
* | * | ||||
* @param path path and basename of the compressed graph to load | * @param path path and basename of the compressed graph to load | ||||
*/ | */ | ||||
public Graph(String path) throws IOException { | public Graph(String path) throws IOException { | ||||
this.graph = BVGraph.loadMapped(path); | this.graph = BVGraph.loadMapped(path); | ||||
this.graphTransposed = BVGraph.loadMapped(path + "-transposed"); | this.graphTransposed = BVGraph.loadMapped(path + "-transposed"); | ||||
this.path = path; | this.path = path; | ||||
this.nodeTypesMap = new NodeTypesMap(path); | this.nodeTypesMap = new NodeTypesMap(path); | ||||
// TODO: we don't need to load the nodeIdMap now that all the | // TODO: we don't need to load the nodeIdMap now that all the | ||||
// translation between ints and PIDs is happening on the Python side. | // translation between ints and PIDs is happening on the Python side. | ||||
// However, some parts of the code still depend on this, so it's | // However, some parts of the code still depend on this, so it's | ||||
// commented out while we decide on what to do with it. | // commented out while we decide on what to do with it. | ||||
this.nodeIdMap = null; // new NodeIdMap(path, getNbNodes()); | this.nodeIdMap = null; // new NodeIdMap(path, numNodes()); | ||||
} | } | ||||
// Protected empty constructor to implement copy() | // Protected empty constructor to implement copy() | ||||
protected Graph() { } | 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. | * Return a flyweight copy of the graph. | ||||
*/ | */ | ||||
@Override | @Override | ||||
public Graph copy() { | public Graph copy() { | ||||
final Graph ng = new Graph(); | return new Graph(this.graph.copy(), this.graphTransposed.copy(), this.path, this.nodeIdMap, this.nodeTypesMap); | ||||
ng.graph = this.graph.copy(); | } | ||||
ng.graphTransposed = this.graphTransposed.copy(); | |||||
ng.path = path; | public Graph transpose() { | ||||
ng.nodeIdMap = this.nodeIdMap; | return new Graph(this.graphTransposed.copy(), this.graph.copy(), this.path, this.nodeIdMap, this.nodeTypesMap); | ||||
ng.nodeTypesMap = this.nodeTypesMap; | } | ||||
return ng; | |||||
public Graph symmetrize() { | |||||
ImmutableGraph symmetric = Transform.union(graph, graphTransposed); | |||||
return new Graph(symmetric, symmetric, this.path, this.nodeIdMap, this.nodeTypesMap); | |||||
} | } | ||||
/** | /** | ||||
* Cleans up graph resources after use. | * Cleans up graph resources after use. | ||||
*/ | */ | ||||
public void cleanUp() throws IOException { | public void cleanUp() throws IOException { | ||||
nodeIdMap.close(); | nodeIdMap.close(); | ||||
} | } | ||||
Show All 35 Lines | public class Graph extends ImmutableGraph { | ||||
* @param nodeId node specified as a long id | * @param nodeId node specified as a long id | ||||
* @return corresponding node type | * @return corresponding node type | ||||
* @see org.softwareheritage.graph.Node.Type | * @see org.softwareheritage.graph.Node.Type | ||||
*/ | */ | ||||
public Node.Type getNodeType(long nodeId) { | public Node.Type getNodeType(long nodeId) { | ||||
return nodeTypesMap.getType(nodeId); | return nodeTypesMap.getType(nodeId); | ||||
} | } | ||||
public boolean randomAccess() { return graph.randomAccess() && graphTransposed.randomAccess(); } | |||||
/** | /** | ||||
* Returns number of nodes in the graph. | * Returns number of nodes in the graph. | ||||
* | * | ||||
* @return number of nodes in the graph | * @return number of nodes in the graph | ||||
*/ | */ | ||||
public long getNbNodes() { | public long numNodes() { | ||||
return graph.numNodes(); | return graph.numNodes(); | ||||
} | } | ||||
/** | /** | ||||
* Returns number of edges in the graph. | * Returns number of edges in the graph. | ||||
* | * | ||||
* @return number of edges in the graph | * @return number of edges in the graph | ||||
*/ | */ | ||||
public long getNbEdges() { | public long numArcs() { | ||||
return graph.numArcs(); | return graph.numArcs(); | ||||
} | } | ||||
/** | /** | ||||
* Returns lazy iterator of successors of a node. | * Returns lazy iterator of successors of a node. | ||||
* | * | ||||
* @param nodeId node specified as a long id | * @param nodeId node specified as a long id | ||||
* @return lazy iterator of successors of the node, specified as a <a | * @return lazy iterator of successors of the node, specified as a <a | ||||
Show All 30 Lines | public class Graph extends ImmutableGraph { | ||||
* @param nodeId node specified as a long id | * @param nodeId node specified as a long id | ||||
* @return indegree of a node | * @return indegree of a node | ||||
*/ | */ | ||||
public long indegree(long nodeId) { | public long indegree(long nodeId) { | ||||
return graphTransposed.outdegree(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 <a | |||||
* href="http://webgraph.di.unimi.it/">WebGraph</a> LazyLongIterator | |||||
*/ | |||||
public LazyLongIterator neighbors(long nodeId, boolean useTransposed) { | |||||
return (useTransposed) ? predecessors(nodeId) : successors(nodeId); | |||||
} | |||||
/** | |||||
* Returns the underlying BVGraph. | * Returns the underlying BVGraph. | ||||
* | * | ||||
* @param useTransposed boolean value to use transposed graph | |||||
* @return WebGraph BVGraph | * @return WebGraph BVGraph | ||||
*/ | */ | ||||
public BVGraph getBVGraph(boolean useTransposed) { | public ImmutableGraph getGraph() { | ||||
return (useTransposed) ? this.graphTransposed : this.graph; | return this.graph; | ||||
} | } | ||||
} | } |