net.walend.digraph
Class AbstractMatrixCEDigraph

java.lang.Object
  |
  +--net.walend.digraph.AbstractMatrixCEDigraph

All Implemented Interfaces:

CEDigraph, Digraph, HasState, IndexedCEDigraph, IndexedDigraph, java.io.Serializable

Direct Known Subclasses:

AbstractLMCEDigraph, MatrixCEDigraph, MutableMatrixCEDigraph

public abstract class AbstractMatrixCEDigraph

extends java.lang.Object

implements IndexedCEDigraph, java.io.Serializable

This abstract class implements the CEDigraph interface using a Map and a Set. It's great for sparse graphs. Subclass it as is for an immutable CEDigraph. Mix in the MutableCEDigraph interface for one you can change.

Since:

20011116

Author:

David Walend dfw1@cornell.edu

See Also:

Serialized Form

Nested Class Summary

protected class	AbstractMatrixCEDigraph.MatrixEdgeIterator
protected class	AbstractMatrixCEDigraph.NodeIterator

Field Summary

private int	edgeCount
private MutableGrid2D	edgeGrid
private int	nodeCount
private java.util.ArrayList	nodeList

Fields inherited from interface net.walend.digraph.CEDigraph

EMPTY

Constructor Summary

protected	AbstractMatrixCEDigraph(CEDigraph digraph)
protected	AbstractMatrixCEDigraph(GEDigraph digraph, java.lang.Object edge)
protected	AbstractMatrixCEDigraph(int nodeCapacity)
protected	AbstractMatrixCEDigraph(UEDigraph digraph)

Method Summary

protected java.lang.Object	addEdge(int fromIndex, int toIndex, java.lang.Object edge)
protected java.lang.Object	addEdge(java.lang.Object fromNode, java.lang.Object toNode, java.lang.Object edge) Return null if no existing edge is displaced by edge.
protected boolean	addNode(java.lang.Object node)
protected boolean	addNodes(java.util.Set nodesToAdd)
private void	checkEdge(java.lang.Object edge)
private void	checkNode(java.lang.Object node)
protected void	clear()
protected void	clearEdges()
boolean	containsCEDigraph(CEDigraph digraph) Returns true if digraph is a subgraph of this CEDigraph.
boolean	containsEdge(int fromIndex, int toIndex)
boolean	containsEdge(int fromIndex, int toIndex, java.lang.Object edge)
boolean	containsEdge(java.lang.Object fromNode, java.lang.Object toNode) Returns true if the digraph contains any edge from fromNode to toNode
boolean	containsEdge(java.lang.Object fromNode, java.lang.Object toNode, java.lang.Object edge) Returns true if edge links fromNode to toNode
boolean	containsNode(int index)
boolean	containsNode(java.lang.Object node)
boolean	containsNodes(java.util.Set nodes)
int	countInboundEdges(int toIndex)
int	countInboundEdges(java.lang.Object node) Inefficient.
int	countOutboundEdges(int fromIndex)
int	countOutboundEdges(java.lang.Object node) Inefficient.
int	edgeCount()
EdgeIterator	edgeIterator()
EdgeNodeIterator	edgeNodeIterator() Returns an iterator that iterates across pairs of nodes that make edges.
java.lang.Object	getEdge(int fromIndex, int toIndex)
java.lang.Object	getEdge(java.lang.Object fromNode, java.lang.Object toNode) Returns null if no edge links fromNode to toNode
Bag	getEdges()
int[]	getFromIndices(int toIndex)
java.util.Set	getFromNodes(int toIndex)
java.util.Set	getFromNodes(java.lang.Object node) Returns the set of nodes that can reach this node by crossing one edge.
Bag	getInboundEdges(int toIndex)
Bag	getInboundEdges(java.lang.Object node) Returns the empty set if node has no inbound edges.
java.lang.Object	getNode(int index)
int	getNodeIndex(java.lang.Object node)
java.util.Set	getNodes()
Bag	getOutboundEdges(int fromIndex)
Bag	getOutboundEdges(java.lang.Object node) Returns the empty set if node has no outbound edges.
java.lang.Class	getPrincipleInterface() Returns the class's principle interface for state comparisons.
int[]	getToIndices(int fromIndex)
java.util.Set	getToNodes(int fromIndex)
java.util.Set	getToNodes(java.lang.Object node) Returns the set of nodes that can be reached from this node by crossing one edge.
protected void	growMatrix(int newSize) This method doubles the size of the matrix
IndexedEdgeIterator	indexedEdgeIterator()
IndexedEdgeNodeIterator	indexedEdgeNodeIterator()
IndexedIterator	indexedNodeIterator()
private int	indexOfNode(java.lang.Object node)
void	insureCapacity(int capacity)
CEDigraph	intersectWithCEDigraph(CEDigraph digraph) Returns a new digraph that is the intersection of this with digraph.
boolean	isEdgeFree() Returns true if this CEDigraph has no edges.
boolean	isEmpty()
int	nodeCapacity() Returns the maximum capacity for nodes in this IndexedDigraph.
int	nodeCount()
int[]	nodeIndices() Returns an array if ints that show which node indices are being used.
java.util.Iterator	nodeIterator() Implementations should explicitly state how they interpret nodeIterator()'s remove method.
private void	putNodeInFirstNull(java.lang.Object node)
protected Bag	removeCEDigraph(CEDigraph digraph)
protected java.lang.Object	removeEdge(int fromIndex, int toIndex)
protected java.lang.Object	removeEdge(java.lang.Object fromNode, java.lang.Object toNode) Return the edge that connected fromNode to toNode, or null if no edge existed.
private Bag	removeEdges(CEDigraph digraph)
protected Bag	removeNode(int index)
protected Bag	removeNode(java.lang.Object node) Return the Set of orphaned edges that are removed with node
protected Bag	removeNodes(java.util.Set nodesToRemove)
protected Bag	retainNodes(java.util.Set retainedNodes)
boolean	sameCEDigraphAs(CEDigraph digraph) Returns true if digraph is the same as this, and all their contents have the same state.
boolean	sameStateAs(HasState victim) If two HasStates have the same internal state, return true.
protected java.lang.Object	setNode(int index, java.lang.Object node)
java.lang.String	toString()
CEDigraph	unionCEDigraph(CEDigraph digraph) Returns a new digraph that is the union of this with digraph.

Methods inherited from class java.lang.Object

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

Field Detail

nodeList

private java.util.ArrayList nodeList

edgeGrid

private MutableGrid2D edgeGrid

nodeCount

private int nodeCount

edgeCount

private int edgeCount

Constructor Detail

AbstractMatrixCEDigraph

protected AbstractMatrixCEDigraph(int nodeCapacity)

AbstractMatrixCEDigraph

protected AbstractMatrixCEDigraph(CEDigraph digraph)

AbstractMatrixCEDigraph

protected AbstractMatrixCEDigraph(UEDigraph digraph)

AbstractMatrixCEDigraph

protected AbstractMatrixCEDigraph(GEDigraph digraph,
                                  java.lang.Object edge)

Method Detail

nodeCount

public int nodeCount()

Specified by:

nodeCount in interface Digraph

edgeCount

public int edgeCount()

Specified by:

edgeCount in interface Digraph

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Digraph

checkNode

private void checkNode(java.lang.Object node)

containsNode

public boolean containsNode(java.lang.Object node)

Specified by:

containsNode in interface Digraph

indexOfNode

private int indexOfNode(java.lang.Object node)

containsEdge

public boolean containsEdge(java.lang.Object fromNode,
                            java.lang.Object toNode)
                     throws NodeMissingException

Returns true if the digraph contains any edge from fromNode to toNode

Specified by:

containsEdge in interface Digraph

Throws:

NodeMissingException - if either node is missing from the digraph.

checkEdge

private void checkEdge(java.lang.Object edge)

containsEdge

public boolean containsEdge(java.lang.Object fromNode,
                            java.lang.Object toNode,
                            java.lang.Object edge)
                     throws NodeMissingException

Returns true if edge links fromNode to toNode

Specified by:

containsEdge in interface CEDigraph

Throws:

NodeMissingException - if either node is missing from the digraph.

countInboundEdges

public int countInboundEdges(java.lang.Object node)
                      throws NodeMissingException

Inefficient. Iterates through all the edges' toNodes. This method could iterate over just the nodes, but would involve creating lots of NodePairs as trial keys. Since the digraph should be sparse anyway, iterating through the edges should be faster.

Specified by:

countInboundEdges in interface Digraph

Throws:

NodeMissingException - if node is not in the digraph.

countOutboundEdges

public int countOutboundEdges(java.lang.Object node)
                       throws NodeMissingException

Inefficient. Iterates through all the edges' fromNodes.

Specified by:

countOutboundEdges in interface Digraph

Throws:

NodeMissingException - if node is not in the digraph.

getInboundEdges

public Bag getInboundEdges(java.lang.Object node)
                    throws NodeMissingException

Returns the empty set if node has no inbound edges.

Inefficient. Iterates through all the edges.

Specified by:

getInboundEdges in interface CEDigraph

Throws:

NodeMissingException - if node is not in the digraph.

getOutboundEdges

public Bag getOutboundEdges(java.lang.Object node)
                     throws NodeMissingException

Returns the empty set if node has no outbound edges.

Inefficient. Iterates through all the edges.

Specified by:

getOutboundEdges in interface CEDigraph

Throws:

NodeMissingException - if node is not in the digraph.

getEdge

public java.lang.Object getEdge(java.lang.Object fromNode,
                                java.lang.Object toNode)
                         throws NodeMissingException

Returns null if no edge links fromNode to toNode

Specified by:

getEdge in interface CEDigraph

Throws:

NodeMissingException - if either node is missing from the digraph.

getFromNodes

public java.util.Set getFromNodes(java.lang.Object node)
                           throws NodeMissingException

Returns the set of nodes that can reach this node by crossing one edge.

Specified by:

getFromNodes in interface Digraph

Throws:

NodeMissingException - if node is not in the digraph.

getToNodes

public java.util.Set getToNodes(java.lang.Object node)
                         throws NodeMissingException

Returns the set of nodes that can be reached from this node by crossing one edge.

Inefficient. Iterates through all the edges.

Specified by:

getToNodes in interface Digraph

Throws:

NodeMissingException - if node is not in the digraph.

nodeIterator

public java.util.Iterator nodeIterator()

Description copied from interface: Digraph

Implementations should explicitly state how they interpret nodeIterator()'s remove method. It should either throw an UnsupportedOperationException or cause a hidden side effects of removing edges.

Specified by:

nodeIterator in interface Digraph

edgeIterator

public EdgeIterator edgeIterator()

Specified by:

edgeIterator in interface CEDigraph

edgeNodeIterator

public EdgeNodeIterator edgeNodeIterator()

Returns an iterator that iterates across pairs of nodes that make edges.

Specified by:

edgeNodeIterator in interface Digraph

getNodes

public java.util.Set getNodes()

Specified by:

getNodes in interface Digraph

getEdges

public Bag getEdges()

Specified by:

getEdges in interface CEDigraph

isEdgeFree

public boolean isEdgeFree()

Returns true if this CEDigraph has no edges.

Specified by:

isEdgeFree in interface Digraph

containsNodes

public boolean containsNodes(java.util.Set nodes)

Specified by:

containsNodes in interface Digraph

containsCEDigraph

public boolean containsCEDigraph(CEDigraph digraph)

Returns true if digraph is a subgraph of this CEDigraph.

Specified by:

containsCEDigraph in interface CEDigraph

sameCEDigraphAs

public boolean sameCEDigraphAs(CEDigraph digraph)

Returns true if digraph is the same as this, and all their contents have the same state.

Specified by:

sameCEDigraphAs in interface CEDigraph

intersectWithCEDigraph

public CEDigraph intersectWithCEDigraph(CEDigraph digraph)

Returns a new digraph that is the intersection of this with digraph. Implementations should generally return the same implementation of CEDigraph as they have themselves.

Specified by:

intersectWithCEDigraph in interface CEDigraph

unionCEDigraph

public CEDigraph unionCEDigraph(CEDigraph digraph)

Returns a new digraph that is the union of this with digraph. Implementations should generally return the same implementation of CEDigraph as they are themselves. If the digraphs contain conflicting edges, then (unless you have a better rule) let digraph's edge win out.

Specified by:

unionCEDigraph in interface CEDigraph

getPrincipleInterface

public java.lang.Class getPrincipleInterface()

Description copied from interface: HasState

Returns the class's principle interface for state comparisons. If two objects have different principle interfaces, they never have the same state.

Specified by:

getPrincipleInterface in interface HasState

sameStateAs

public boolean sameStateAs(HasState victim)

Description copied from interface: HasState

If two HasStates have the same internal state, return true.

For objects with subobjects, Generally this method should only return true if the internal objects are equal. Implement a contentsHaveSameState() method to determine if the contents have the same state.

Specified by:

sameStateAs in interface HasState

nodeCapacity

public int nodeCapacity()

Returns the maximum capacity for nodes in this IndexedDigraph.

Specified by:

nodeCapacity in interface IndexedDigraph

nodeIndices

public int[] nodeIndices()

Returns an array if ints that show which node indices are being used.

Specified by:

nodeIndices in interface IndexedDigraph

containsNode

public boolean containsNode(int index)

Specified by:

containsNode in interface IndexedDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

getNode

public java.lang.Object getNode(int index)

Specified by:

getNode in interface IndexedDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

getNodeIndex

public int getNodeIndex(java.lang.Object node)
                 throws NodeMissingException

Specified by:

getNodeIndex in interface IndexedDigraph

Throws:

a - NodeMissingException if the node is not in the digraph.

NodeMissingException

containsEdge

public boolean containsEdge(int fromIndex,
                            int toIndex)

Specified by:

containsEdge in interface IndexedDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

countInboundEdges

public int countInboundEdges(int toIndex)

Specified by:

countInboundEdges in interface IndexedDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

countOutboundEdges

public int countOutboundEdges(int fromIndex)

Specified by:

countOutboundEdges in interface IndexedDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

getFromNodes

public java.util.Set getFromNodes(int toIndex)

Specified by:

getFromNodes in interface IndexedDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

getFromIndices

public int[] getFromIndices(int toIndex)

Specified by:

getFromIndices in interface IndexedDigraph

getToNodes

public java.util.Set getToNodes(int fromIndex)

Specified by:

getToNodes in interface IndexedDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

getToIndices

public int[] getToIndices(int fromIndex)

Specified by:

getToIndices in interface IndexedDigraph

indexedEdgeNodeIterator

public IndexedEdgeNodeIterator indexedEdgeNodeIterator()

Specified by:

indexedEdgeNodeIterator in interface IndexedDigraph

containsEdge

public boolean containsEdge(int fromIndex,
                            int toIndex,
                            java.lang.Object edge)

Specified by:

containsEdge in interface IndexedCEDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

getInboundEdges

public Bag getInboundEdges(int toIndex)

Specified by:

getInboundEdges in interface IndexedCEDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

getOutboundEdges

public Bag getOutboundEdges(int fromIndex)

Specified by:

getOutboundEdges in interface IndexedCEDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

indexedEdgeIterator

public IndexedEdgeIterator indexedEdgeIterator()

Specified by:

indexedEdgeIterator in interface IndexedCEDigraph

indexedNodeIterator

public IndexedIterator indexedNodeIterator()

Specified by:

indexedNodeIterator in interface IndexedDigraph

getEdge

public java.lang.Object getEdge(int fromIndex,
                                int toIndex)

Specified by:

getEdge in interface IndexedCEDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

setNode

protected java.lang.Object setNode(int index,
                                   java.lang.Object node)

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

addEdge

protected java.lang.Object addEdge(int fromIndex,
                                   int toIndex,
                                   java.lang.Object edge)

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

removeNode

protected Bag removeNode(int index)

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

removeEdge

protected java.lang.Object removeEdge(int fromIndex,
                                      int toIndex)

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndices() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

growMatrix

protected void growMatrix(int newSize)

This method doubles the size of the matrix

insureCapacity

public void insureCapacity(int capacity)

putNodeInFirstNull

private void putNodeInFirstNull(java.lang.Object node)

addNode

protected boolean addNode(java.lang.Object node)

addEdge

protected java.lang.Object addEdge(java.lang.Object fromNode,
                                   java.lang.Object toNode,
                                   java.lang.Object edge)
                            throws NodeMissingException

Return null if no existing edge is displaced by edge. Otherwise, return the edge that is displaced.

Throws:

NodeMissingException - if either node is not in the digraph.

removeNode

protected Bag removeNode(java.lang.Object node)
                  throws NodeMissingException

Return the Set of orphaned edges that are removed with node

Throws:

NodeMissingException - if the node is not in the digraph

removeEdge

protected java.lang.Object removeEdge(java.lang.Object fromNode,
                                      java.lang.Object toNode)
                               throws NodeMissingException

Return the edge that connected fromNode to toNode, or null if no edge existed.

Throws:

NodeMissingException - if either node is not in the digraph

addNodes

protected boolean addNodes(java.util.Set nodesToAdd)

removeNodes

protected Bag removeNodes(java.util.Set nodesToRemove)

removeEdges

private Bag removeEdges(CEDigraph digraph)

removeCEDigraph

protected Bag removeCEDigraph(CEDigraph digraph)

retainNodes

protected Bag retainNodes(java.util.Set retainedNodes)

clear

protected void clear()

clearEdges

protected void clearEdges()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object