DenseMemoryGraph (Cognitive Foundry)

java.lang.Object
- gov.sandia.cognition.graph.DenseMemoryGraph<NodeNameType>

Type Parameters:

NodeNameType - The type for the node names

All Implemented Interfaces:

DirectedNodeEdgeGraph<NodeNameType>, java.io.Serializable

Direct Known Subclasses:

WeightedDenseMemoryGraph
```
public class DenseMemoryGraph<NodeNameType>
extends java.lang.Object
implements DirectedNodeEdgeGraph<NodeNameType>, java.io.Serializable
```
Most basic-est of graph types. This is a directed graph that stores node names and edges between them

Author:

jdwendt

See Also:

Serialized Form

Constructor Summary

Constructors
Constructor and Description
`DenseMemoryGraph()` Initializes an empty graph.
`DenseMemoryGraph(int expectedNumNodes, int expectedNumEdges)` Initializes an empty graph, but sets aside O(m + n) memory.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`addEdge(NodeNameType left, NodeNameType right)` Adds a directed edge from left to right.
`void`	`addNode(NodeNameType node)` Adds the input node to the graph.
`void`	`clear()` Clears the graph back to the original, empty state
`boolean`	`containsNode(NodeNameType node)` Returns whether or not the graph contains the specified vertex.
`static DenseMemoryGraph<?>`	`deserialize(java.lang.String fileName)` Helper method for deserializing from a file
`Pair<java.lang.Integer,java.lang.Integer>`	`getEdgeEndpointIds(int i)` Helper that returns the endpoint values for the input edge id.
`protected int`	`getFirstEdgeFrom(int nodeVal)` Helper that returns the first edge that node nodeVal (id) participates in.
`NodeNameType`	`getNode(int nodeId)` Helper that returns the node for the internal ID.
`int`	`getNodeId(NodeNameType node)` Helper that returns the internal ID for the input node.
`java.util.Collection<NodeNameType>`	`getNodes()` Returns all of the nodes contained in the graph.
`int`	`getNumEdges()` Return the number of edges.
`int`	`getNumNodes()` Return the number of nodes
`java.util.Collection<NodeNameType>`	`getSuccessors(NodeNameType node)` Returns all the nodes this node connects to (outgoing edges only).
`protected void`	`optimizeEdges()` This private helper sorts all edges for quicker edge-lookup times.
`static void`	`serialize(java.lang.String fileName, DenseMemoryGraph<?> graph)` Helper method for serializing the input to file.
`protected void`	`swap(int i, int j)` Helper that swaps the values at i and j in the edge list (handles the fact that the edge list is 2 values in a row for each edge).

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - DenseMemoryGraph
```
public DenseMemoryGraph()
```
    Initializes an empty graph. Execution: O(1).
  - DenseMemoryGraph
```
public DenseMemoryGraph(int expectedNumNodes,
                        int expectedNumEdges)
```
    Initializes an empty graph, but sets aside O(m + n) memory. This speeds up later filling of the graph by removing the need to re-allocate more memory for the nodes and edges as the graph grows (until the input values are exceeded at least). Execution: O(1) + time to allocate O(m+n) memory.
    
    Parameters:
    
    expectedNumNodes - The expected number of nodes for the graph
    
    expectedNumEdges - The expected number of edges for the graph
- Method Detail
  - getNodes
```
public java.util.Collection<NodeNameType> getNodes()
```
    Description copied from interface: DirectedNodeEdgeGraph
    
    Returns all of the nodes contained in the graph.
    
    Specified by:
    
    getNodes in interface DirectedNodeEdgeGraph<NodeNameType>
    
    Returns:
    
    all of the nodes in the graph
    
    See Also:
    
    Execution: O(1) time
  - getNumNodes
```
public int getNumNodes()
```
    Description copied from interface: DirectedNodeEdgeGraph
    
    Return the number of nodes
    
    Specified by:
    
    getNumNodes in interface DirectedNodeEdgeGraph<NodeNameType>
    
    Returns:
    
    the number of nodes
    
    See Also:
    
    Execution: O(1) time
  - getNumEdges
```
public int getNumEdges()
```
    Description copied from interface: DirectedNodeEdgeGraph
    
    Return the number of edges.
    
    Specified by:
    
    getNumEdges in interface DirectedNodeEdgeGraph<NodeNameType>
    
    Returns:
    
    the number of edges
    
    See Also:
    
    Execution: O(1) time
  - 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>
    
    Parameters:
    
    left - The source of the edge
    
    right - The destination of the edge
    
    See Also:
    
    Execution: O(1) time
  - addNode
```
public void addNode(NodeNameType node)
```
    Description copied from interface: DirectedNodeEdgeGraph
    
    Adds the input node to the graph. Calling this method is unnecessary if the node participates in any edges. If you call DirectedNodeEdgeGraph.addEdge(Object, Object), it handles adding new nodes.
    
    Specified by:
    
    addNode in interface DirectedNodeEdgeGraph<NodeNameType>
    
    Parameters:
    
    node - The node to add to the graph
    
    See Also:
    
    Execution: O(1) time
  - containsNode
```
public boolean containsNode(NodeNameType node)
```
    Description copied from interface: DirectedNodeEdgeGraph
    
    Returns whether or not the graph contains the specified vertex.
    
    Specified by:
    
    containsNode in interface DirectedNodeEdgeGraph<NodeNameType>
    
    Parameters:
    
    node - The node to check for
    
    Returns:
    
    true if this contains node
    
    See Also:
    
    Execution: O(1) time
  - getSuccessors
```
public java.util.Collection<NodeNameType> getSuccessors(NodeNameType node)
```
    Description copied from interface: DirectedNodeEdgeGraph
    
    Returns all the nodes this node connects to (outgoing edges only).
    
    Specified by:
    
    getSuccessors in interface DirectedNodeEdgeGraph<NodeNameType>
    
    Parameters:
    
    node - The node whose successors are requested
    
    Returns:
    
    all the nodes this node connects to.
    
    See Also:
    
    Execution: O(log m + d) where d is the degree of the input node (d can be O(m) but usually is closer to O(1)) (With a O(m log m) one-time cost after edges are newly added)
  - getNodeId
```
public int getNodeId(NodeNameType node)
```
    Helper that returns the internal ID for the input node. Throws an exception if the input node isn't found. Execution: O(1)
    
    Specified by:
    
    getNodeId in interface DirectedNodeEdgeGraph<NodeNameType>
    
    Parameters:
    
    node - The node to search for
    
    Returns:
    
    the internal ID for that node
  - getNode
```
public NodeNameType getNode(int nodeId)
```
    Helper that returns the node for the internal ID. Throws an exception if the input ID is invalid. Execution: O(1)
    
    Specified by:
    
    getNode in interface DirectedNodeEdgeGraph<NodeNameType>
    
    Parameters:
    
    nodeId - The id for the sought-after node
    
    Returns:
    
    The node for the input id
  - getEdgeEndpointIds
```
public Pair<java.lang.Integer,java.lang.Integer> getEdgeEndpointIds(int i)
```
    Helper that returns the endpoint values for the input edge id. Execution: O(1) (one time O(m log m) cost after addEdges is called to get the edges in the right order)
    
    Specified by:
    
    getEdgeEndpointIds in interface DirectedNodeEdgeGraph<NodeNameType>
    
    Parameters:
    
    i - The edge id to search for
    
    Returns:
    
    the endpoint values for the input edge id
  - getFirstEdgeFrom
```
protected int getFirstEdgeFrom(int nodeVal)
```
    Helper that returns the first edge that node nodeVal (id) participates in. Execution: O(log m + d) where d is the degree of node nodeVal (With a O(m log m) one-time cost after edges are newly added)
    
    Parameters:
    
    nodeVal - The id of the node whose first edge is sought
    
    Returns:
    
    The integer id of the first edge nodeVal participates in
  - optimizeEdges
```
protected void optimizeEdges()
```
    This private helper sorts all edges for quicker edge-lookup times. Execution: If !isOptimized, O(m log m), else O(1).
  - swap
```
protected void swap(int i,
                    int j)
```
    Helper that swaps the values at i and j in the edge list (handles the fact that the edge list is 2 values in a row for each edge). Execution: O(1)
    
    Parameters:
    
    i - The edge index to swap with j
    
    j - The edge index to swap with i
  - 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>
    
    See Also:
    
    gov.sandia.graph.IDirectedNodeEdgeGraph#clear()
  - serialize
```
public static void serialize(java.lang.String fileName,
                             DenseMemoryGraph<?> 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 DenseMemoryGraph<?> 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

Class DenseMemoryGraph<NodeNameType>

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

DenseMemoryGraph

DenseMemoryGraph

Method Detail

getNodes

getNumNodes

getNumEdges

addEdge

addNode

containsNode

getSuccessors

getNodeId

getNode

getEdgeEndpointIds

getFirstEdgeFrom

optimizeEdges

swap

clear

serialize

deserialize