gov.sandia.cognition.graph

Class WeightedDenseMemoryGraph<NodeNameType>

java.lang.Object

gov.sandia.cognition.graph.DenseMemoryGraph<NodeNameType>

gov.sandia.cognition.graph.WeightedDenseMemoryGraph<NodeNameType>

Type Parameters:

NodeNameType -

All Implemented Interfaces:

DirectedNodeEdgeGraph<NodeNameType>, DirectedWeightedNodeEdgeGraph<NodeNameType>, java.io.Serializable

public class WeightedDenseMemoryGraph<NodeNameType>
extends DenseMemoryGraph<NodeNameType>
implements DirectedWeightedNodeEdgeGraph<NodeNameType>

Implementation for a weighted graph type

Author:

jdwendt

See Also:

Serialized Form

Constructor Summary

Constructors

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

Method Summary

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

Methods inherited from class gov.sandia.cognition.graph.DenseMemoryGraph

addNode, containsNode, getEdgeEndpointIds, getFirstEdgeFrom, getNode, getNodeId, getNodes, getNumEdges, getNumNodes, getSuccessors, optimizeEdges, serialize

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface gov.sandia.cognition.graph.DirectedNodeEdgeGraph

addNode, containsNode, getEdgeEndpointIds, getNode, getNodeId, getNodes, getNumEdges, getNumNodes, getSuccessors

Constructor Detail

WeightedDenseMemoryGraph

public WeightedDenseMemoryGraph()

Default constructor creates an empty graph Execution: O(1)

WeightedDenseMemoryGraph

public 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

Parameters:

expectedNumNodes -

expectedNumEdges -

Method Detail

addEdge

public void addEdge(NodeNameType left,
                    NodeNameType right)

Description copied from interface: DirectedNodeEdgeGraph

Adds a directed edge from left to right. If left and right are not already in the graph, they are added before the edge is added.

Specified by:

addEdge in interface DirectedNodeEdgeGraph<NodeNameType>

Specified by:

addEdge in interface DirectedWeightedNodeEdgeGraph<NodeNameType>

Overrides:

addEdge in class DenseMemoryGraph<NodeNameType>

Parameters:

left - The source of the edge

right - The destination of the edge

See Also:

Execution: O(1)

addEdge

public void addEdge(NodeNameType left,
                    NodeNameType right,
                    double weight)

Description copied from interface: DirectedWeightedNodeEdgeGraph

Adds a directed edge from left to right with the input weight. If left and right are not already in the graph, they are added before the edge is added.

Specified by:

addEdge in interface DirectedWeightedNodeEdgeGraph<NodeNameType>

Parameters:

left - The source of the edge

right - The destination of the edge

weight - The weight to assign this edge

See Also:

Execution: O(1)

swap

protected void swap(int i,
                    int j)

Overrides the parent's version to ensure the weights swap at the same time the edges do

Overrides:

swap in class DenseMemoryGraph<NodeNameType>

Parameters:

i - The edge index to swap with j

j - The edge index to swap with i

getSuccessorsWithWeights

public 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)). NOTE: This has a one-time O(m log m) cost after adding new edges.

Specified by:

getSuccessorsWithWeights in interface DirectedWeightedNodeEdgeGraph<NodeNameType>

Parameters:

node - The node whose successors are wanted

Returns:

all the nodes this node connects to.

getEdgeWeight

public double getEdgeWeight(int id)

Description copied from interface: DirectedWeightedNodeEdgeGraph

This returns the weight of edge id (where id is [0 ... numEdges())). Note that the ids for edges are not necessarily fixed across calls to addEdge (as edge ordering can change due to insertion of new edges).

Specified by:

getEdgeWeight in interface DirectedWeightedNodeEdgeGraph<NodeNameType>

Parameters:

id - The id of the edge whose weight is desired

Returns:

The weight for edge id

See Also:

Execution: O(1) with a one-time O(m log m) cost after calling addEdge.

clear

public void clear()

Description copied from interface: DirectedNodeEdgeGraph

Clears the graph back to the original, empty state

Specified by:

clear in interface DirectedNodeEdgeGraph<NodeNameType>

Overrides:

clear in class DenseMemoryGraph<NodeNameType>

See Also:

gov.sandia.graph.BasicDenseMemoryGraph#clear()

serialize

public static void serialize(java.lang.String fileName,
                             WeightedDenseMemoryGraph<?> graph)

Helper method for serializing the input to file.

Parameters:

fileName - The filename (with optional path) to write this out to

graph - The graph to write

deserialize

public static WeightedDenseMemoryGraph<?> deserialize(java.lang.String fileName)

Helper method for deserializing from a file

Parameters:

fileName - The file (with path if necessary) to read a graph from

Returns:

The file object read from the input filename