NodeNameType
- public class WeightedDenseMemoryGraph<NodeNameType> extends DenseMemoryGraph<NodeNameType> implements DirectedWeightedNodeEdgeGraph<NodeNameType>
Constructor and Description |
---|
WeightedDenseMemoryGraph()
Default constructor creates an empty graph
Execution: O(1)
|
WeightedDenseMemoryGraph(int expectedNumNodes,
int expectedNumEdges)
Initialize an empty graph with a default size (for speed-ups later)
Execution: O(m + n) for reserving necessary space
|
Modifier and Type | Method and Description |
---|---|
void |
addEdge(NodeNameType left,
NodeNameType right)
Adds a directed edge from left to right.
|
void |
addEdge(NodeNameType left,
NodeNameType right,
double weight)
Adds a directed edge from left to right with the input weight.
|
void |
clear()
Clears the graph back to the original, empty state
|
static WeightedDenseMemoryGraph<?> |
deserialize(java.lang.String fileName)
Helper method for deserializing from a file
|
double |
getEdgeWeight(int id)
This returns the weight of edge id (where id is [0 ...
|
java.util.Collection<Pair<NodeNameType,java.lang.Double>> |
getSuccessorsWithWeights(NodeNameType node)
Execution: O(log m + d) where d is the degree of the specified node
(which can be O(m) but is usually O(1)).
|
static void |
serialize(java.lang.String fileName,
WeightedDenseMemoryGraph<?> graph)
Helper method for serializing the input to file.
|
protected void |
swap(int i,
int j)
Overrides the parent's version to ensure the weights swap at the same
time the edges do
|
addNode, containsNode, getEdgeEndpointIds, getFirstEdgeFrom, getNode, getNodeId, getNodes, getNumEdges, getNumNodes, getSuccessors, optimizeEdges, serialize
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
addNode, containsNode, getEdgeEndpointIds, getNode, getNodeId, getNodes, getNumEdges, getNumNodes, getSuccessors
public WeightedDenseMemoryGraph()
public WeightedDenseMemoryGraph(int expectedNumNodes, int expectedNumEdges)
expectedNumNodes
- expectedNumEdges
- public void addEdge(NodeNameType left, NodeNameType right)
DirectedNodeEdgeGraph
addEdge
in interface DirectedNodeEdgeGraph<NodeNameType>
addEdge
in interface DirectedWeightedNodeEdgeGraph<NodeNameType>
addEdge
in class DenseMemoryGraph<NodeNameType>
left
- The source of the edgeright
- The destination of the edgeExecution: O(1)
public void addEdge(NodeNameType left, NodeNameType right, double weight)
DirectedWeightedNodeEdgeGraph
addEdge
in interface DirectedWeightedNodeEdgeGraph<NodeNameType>
left
- The source of the edgeright
- The destination of the edgeweight
- The weight to assign this edgeExecution: O(1)
protected void swap(int i, int j)
swap
in class DenseMemoryGraph<NodeNameType>
i
- The edge index to swap with jj
- The edge index to swap with ipublic java.util.Collection<Pair<NodeNameType,java.lang.Double>> getSuccessorsWithWeights(NodeNameType node)
getSuccessorsWithWeights
in interface DirectedWeightedNodeEdgeGraph<NodeNameType>
node
- The node whose successors are wantedpublic double getEdgeWeight(int id)
DirectedWeightedNodeEdgeGraph
getEdgeWeight
in interface DirectedWeightedNodeEdgeGraph<NodeNameType>
id
- The id of the edge whose weight is desiredExecution: O(1) with a one-time O(m log m) cost after calling addEdge.
public void clear()
DirectedNodeEdgeGraph
clear
in interface DirectedNodeEdgeGraph<NodeNameType>
clear
in class DenseMemoryGraph<NodeNameType>
gov.sandia.graph.BasicDenseMemoryGraph#clear()
public static void serialize(java.lang.String fileName, WeightedDenseMemoryGraph<?> graph)
fileName
- The filename (with optional path) to write this out tograph
- The graph to writepublic static WeightedDenseMemoryGraph<?> deserialize(java.lang.String fileName)
fileName
- The file (with path if necessary) to read a graph from