net.walend.digraph
Class AbstractMatrixGEDigraph

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

All Implemented Interfaces:

Digraph, GEDigraph, HasState, IndexedDigraph, IndexedGEDigraph, java.io.Serializable

Direct Known Subclasses:

AbstractLMGEDigraph, MatrixGEDigraph, MutableMatrixGEDigraph

public abstract class AbstractMatrixGEDigraph

extends java.lang.Object

implements IndexedGEDigraph, java.io.Serializable

A GEDigraph backed by an ArrayList of nodes and a boolean[][] matrix that stores edges.

Since:

20011022

Author:

David Walend dfw1@cornell.edu

See Also:

Serialized Form

Nested Class Summary

protected class	AbstractMatrixGEDigraph.MatrixEdgeIterator
protected class	AbstractMatrixGEDigraph.NodeIterator

Field Summary

private int	edgeCount
private boolean[][]	edges
private int	nodeCount
private java.util.ArrayList	nodes

Fields inherited from interface net.walend.digraph.GEDigraph

EMPTY

Constructor Summary

protected	AbstractMatrixGEDigraph(CEDigraph digraph)
protected	AbstractMatrixGEDigraph(GEDigraph digraph)
protected	AbstractMatrixGEDigraph(int nodeCapacity)
protected	AbstractMatrixGEDigraph(UEDigraph digraph)

Method Summary

protected boolean	addEdge(int fromIndex, int toIndex)
protected boolean	addEdge(java.lang.Object fromNode, java.lang.Object toNode) Return true if the digraph changes when this edge is added, false if the digraph is unchanged.
protected boolean	addNode(java.lang.Object node) Return true if the node is added successfully, false if the digraph does not change.
protected boolean	addNodes(java.util.Set nodes) Return true if adding the nodes changes the digraph.
private void	checkNode(java.lang.Object node)
protected void	clear() Remove all nodes and edges from the GEDigraph
protected void	clearEdges() Remove all the edges from the GEDigraph.
boolean	containsEdge(int fromIndex, int toIndex)
boolean	containsEdge(java.lang.Object fromNode, java.lang.Object toNode) Returns true if the digraph contains any edge from fromNode to toNode.
boolean	containsGEDigraph(GEDigraph digraph) Returns true if digraph is a subgraph of this GEDigraph.
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)
int	countOutboundEdges(int fromIndex)
int	countOutboundEdges(java.lang.Object node)
int	edgeCount() This method scans the edges matrix to count them.
EdgeNodeIterator	edgeNodeIterator() Returns an iterator that iterates across pairs of nodes that make edges.
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.
java.lang.Object	getNode(int index)
int	getNodeIndex(java.lang.Object node)
java.util.Set	getNodes()
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
IndexedEdgeNodeIterator	indexedEdgeNodeIterator()
IndexedIterator	indexedNodeIterator()
protected void	insureCapacity(int capacity)
GEDigraph	intersectWithGEDigraph(GEDigraph digraph) Returns a new digraph that is the intersection of this with digraph.
boolean	isEdgeFree() Returns true if this GEDigraph 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 boolean	removeEdge(int fromIndex, int toIndex)
protected boolean	removeEdge(java.lang.Object fromNode, java.lang.Object toNode) Return true if the digraph changes when the edge is removed, false if the digraph didn't have an edge between these two nodes.
protected int	removeGEDigraph(GEDigraph digraph) Return the number of edges orphaned when digraph is removed
protected int	removeNode(int index)
protected int	removeNode(java.lang.Object node) Return the number of orphaned edges that were lost when this node is removed.
protected int	removeNodes(java.util.Set nodes) Return the number of edges orphaned edges when these nodes are removed.
protected int	retainNodes(java.util.Set retainedNodes) Return the number of orphaned edges when the nodes are removed.
boolean	sameGEDigraphAs(GEDigraph digraph) Returns true if digraph is the same as this; that is, if this.containsGEDigraph(digraph) and digraph.containsGEDigraph(this).
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()
GEDigraph	unionGEDigraph(GEDigraph 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

nodeCount

private int nodeCount

nodes

private java.util.ArrayList nodes

edgeCount

private int edgeCount

edges

private boolean[][] edges

Constructor Detail

AbstractMatrixGEDigraph

protected AbstractMatrixGEDigraph(int nodeCapacity)

AbstractMatrixGEDigraph

protected AbstractMatrixGEDigraph(GEDigraph digraph)

AbstractMatrixGEDigraph

protected AbstractMatrixGEDigraph(CEDigraph digraph)

AbstractMatrixGEDigraph

protected AbstractMatrixGEDigraph(UEDigraph digraph)

Method Detail

nodeCount

public int nodeCount()

Specified by:

nodeCount in interface Digraph

edgeCount

public int edgeCount()

This method scans the edges matrix to count them.

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

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.

countInboundEdges

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

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

Specified by:

countOutboundEdges in interface Digraph

Throws:

NodeMissingException - if node is not in 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.

Specified by:

getToNodes in interface Digraph

Throws:

NodeMissingException - if node is not in the digraph.

nodeIterator

public java.util.Iterator nodeIterator()

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

Specified by:

nodeIterator in interface Digraph

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

isEdgeFree

public boolean isEdgeFree()

Returns true if this GEDigraph has no edges.

Specified by:

isEdgeFree in interface Digraph

containsNodes

public boolean containsNodes(java.util.Set nodes)

Specified by:

containsNodes in interface Digraph

containsGEDigraph

public boolean containsGEDigraph(GEDigraph digraph)

Returns true if digraph is a subgraph of this GEDigraph.

Specified by:

containsGEDigraph in interface GEDigraph

sameGEDigraphAs

public boolean sameGEDigraphAs(GEDigraph digraph)

Returns true if digraph is the same as this; that is, if this.containsGEDigraph(digraph) and digraph.containsGEDigraph(this).

Specified by:

sameGEDigraphAs in interface GEDigraph

intersectWithGEDigraph

public GEDigraph intersectWithGEDigraph(GEDigraph digraph)

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

Specified by:

intersectWithGEDigraph in interface GEDigraph

unionGEDigraph

public GEDigraph unionGEDigraph(GEDigraph digraph)

Returns a new digraph that is the union of this with digraph. Implementations should generally return the same implementation of GEDigraph 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:

unionGEDigraph in interface GEDigraph

getPrincipleInterface

public java.lang.Class getPrincipleInterface()

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)

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

indexedNodeIterator

public IndexedIterator indexedNodeIterator()

Specified by:

indexedNodeIterator in interface IndexedDigraph

growMatrix

protected void growMatrix(int newSize)

This method doubles the size of the matrix

putNodeInFirstNull

private void putNodeInFirstNull(java.lang.Object node)

addNode

protected boolean addNode(java.lang.Object node)

Return true if the node is added successfully, false if the digraph does not change.

addEdge

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

Return true if the digraph changes when this edge is added, false if the digraph is unchanged.

Throws:

NodeMissingException - if either node is not in the digraph.

removeNode

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

Return the number of orphaned edges that were lost when this node is removed.

Throws:

NodeMissingException - if the node is not in the digraph

removeEdge

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

Return true if the digraph changes when the edge is removed, false if the digraph didn't have an edge between these two nodes.

Throws:

NodeMissingException - if either node is not in the digraph

addNodes

protected boolean addNodes(java.util.Set nodes)

Return true if adding the nodes changes the digraph.

removeNodes

protected int removeNodes(java.util.Set nodes)

Return the number of edges orphaned edges when these nodes are removed.

removeGEDigraph

protected int removeGEDigraph(GEDigraph digraph)

Return the number of edges orphaned when digraph is removed

retainNodes

protected int retainNodes(java.util.Set retainedNodes)

Return the number of orphaned edges when the nodes are removed.

clear

protected void clear()

Remove all nodes and edges from the GEDigraph

clearEdges

protected void clearEdges()

Remove all the edges from the GEDigraph.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

insureCapacity

protected void insureCapacity(int capacity)

setNode

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

Throws:

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

addEdge

protected boolean addEdge(int fromIndex,
                          int toIndex)

Throws:

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

removeNode

protected int removeNode(int index)

Throws:

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

removeEdge

protected boolean removeEdge(int fromIndex,
                             int toIndex)

Throws:

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