net.walend.digraph
Class AbstractMatrixUEDigraph

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

All Implemented Interfaces:

Digraph, HasState, java.io.Serializable, UEDigraph

Direct Known Subclasses:

MatrixUEDigraph, MutableMatrixUEDigraph

public abstract class AbstractMatrixUEDigraph

extends java.lang.Object

implements UEDigraph, java.io.Serializable

This abstract class implements the UEDigraph interface using a List and a Grid. It's great for sparse graphs. Subclass it as is for an immutable UEDigraph. Mix in the MutableUEDigraph interface for one you can change.

Author:

David Walend dfw1@cornell.edu

See Also:

Serialized Form

Nested Class Summary

protected class	AbstractMatrixUEDigraph.MatrixEdgeIterator
protected class	AbstractMatrixUEDigraph.NodeIterator

Field Summary

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

Fields inherited from interface net.walend.digraph.UEDigraph

EMPTY

Constructor Summary

protected	AbstractMatrixUEDigraph(int nodeCapacity)
protected	AbstractMatrixUEDigraph(UEDigraph digraph)

Method Summary

protected java.lang.Object	addEdge(java.lang.Object fromNode, java.lang.Object toNode, java.lang.Object 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	containsEdge(java.lang.Object edge) Returns true if edge exists in the digraph anywhere.
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	containsEdges(java.util.Set edges)
boolean	containsNode(java.lang.Object node)
boolean	containsNodes(java.util.Set nodes)
boolean	containsUEDigraph(UEDigraph digraph) Returns true if digraph is a subgraph of this UEDigraph.
int	countInboundEdges(java.lang.Object node) Efficient.
int	countOutboundEdges(java.lang.Object node) Efficient.
int	edgeCount()
EdgeIterator	edgeIterator()
EdgeNodeIterator	edgeNodeIterator() Returns an iterator that iterates across pairs of nodes that make edges.
java.lang.Object	getEdge(java.lang.Object fromNode, java.lang.Object toNode) Returns null if no edge links fromNode to toNode
java.util.Set	getEdges()
java.lang.Object	getFromNode(java.lang.Object edge)
java.util.Set	getFromNodes(java.lang.Object node) Returns the set of nodes that can reach this node by crossing one edge.
java.util.Set	getInboundEdges(java.lang.Object node) Returns the empty set if node has no inbound edges.
java.util.Set	getNodes()
java.util.Set	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.
java.lang.Object	getToNode(java.lang.Object edge)
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
private int	indexOfNode(java.lang.Object node)
UEDigraph	intersectWithUEDigraph(UEDigraph digraph) Returns a new digraph that is the intersection of this with digraph.
boolean	isEdgeFree() Returns true if this UEDigraph has no edges.
boolean	isEmpty()
int	nodeCount()
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(java.lang.Object edge)
protected java.lang.Object	removeEdge(java.lang.Object fromNode, java.lang.Object toNode)
protected boolean	removeEdges(java.util.Set edges)
private java.util.Set	removeEdges(UEDigraph digraph)
protected java.util.Set	removeNode(java.lang.Object node)
protected java.util.Set	removeNodes(java.util.Set nodesToRemove)
protected java.util.Set	removeUEDigraph(UEDigraph digraph)
protected boolean	retainEdges(java.util.Set retainedEdges)
protected java.util.Set	retainNodes(java.util.Set retainedNodes)
boolean	sameStateAs(HasState victim) If two HasStates have the same internal state, return true.
boolean	sameUEDigraphAs(UEDigraph digraph) Returns true if digraph is the same as this, and all their contents have the same state.
java.lang.String	toString()
UEDigraph	unionUEDigraph(UEDigraph 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

AbstractMatrixUEDigraph

protected AbstractMatrixUEDigraph(int nodeCapacity)

AbstractMatrixUEDigraph

protected AbstractMatrixUEDigraph(UEDigraph digraph)

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

Description copied from interface: Digraph

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.

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 UEDigraph

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 edge)

Returns true if edge exists in the digraph anywhere. Inefficient--it scans the grid.

Specified by:

containsEdge in interface UEDigraph

countInboundEdges

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

Efficient. Iterattes accross a stripe.

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

Efficient. Iterattes accross a stripe.

Specified by:

countOutboundEdges in interface Digraph

Throws:

NodeMissingException - if node is not in the digraph.

getInboundEdges

public java.util.Set 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 UEDigraph

Throws:

NodeMissingException - if node is not in the digraph.

getOutboundEdges

public java.util.Set 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 UEDigraph

Throws:

NodeMissingException - if node is not in the digraph.

getFromNode

public java.lang.Object getFromNode(java.lang.Object edge)
                             throws EdgeMissingException

Specified by:

getFromNode in interface UEDigraph

Throws:

EdgeMissingException - if the edge is not in the digraph.

getToNode

public java.lang.Object getToNode(java.lang.Object edge)
                           throws EdgeMissingException

Specified by:

getToNode in interface UEDigraph

Throws:

EdgeMissingException - if the edge 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 UEDigraph

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.

Inefficient. Iterates through all the edges.

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 UEDigraph

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 java.util.Set getEdges()

Specified by:

getEdges in interface UEDigraph

isEdgeFree

public boolean isEdgeFree()

Returns true if this UEDigraph has no edges.

Specified by:

isEdgeFree in interface Digraph

containsNodes

public boolean containsNodes(java.util.Set nodes)

Specified by:

containsNodes in interface Digraph

containsEdges

public boolean containsEdges(java.util.Set edges)

Specified by:

containsEdges in interface UEDigraph

containsUEDigraph

public boolean containsUEDigraph(UEDigraph digraph)

Returns true if digraph is a subgraph of this UEDigraph.

Specified by:

containsUEDigraph in interface UEDigraph

sameUEDigraphAs

public boolean sameUEDigraphAs(UEDigraph digraph)

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

Specified by:

sameUEDigraphAs in interface UEDigraph

intersectWithUEDigraph

public UEDigraph intersectWithUEDigraph(UEDigraph digraph)

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

Specified by:

intersectWithUEDigraph in interface UEDigraph

unionUEDigraph

public UEDigraph unionUEDigraph(UEDigraph digraph)

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

unionUEDigraph in interface UEDigraph

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

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)

addEdge

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

NodeMissingException

EdgeNotUniqueException

removeNode

protected java.util.Set removeNode(java.lang.Object node)
                            throws NodeMissingException

NodeMissingException

removeEdge

protected boolean removeEdge(java.lang.Object edge)

removeEdge

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

NodeMissingException

addNodes

protected boolean addNodes(java.util.Set nodesToAdd)

removeNodes

protected java.util.Set removeNodes(java.util.Set nodesToRemove)

removeEdges

protected boolean removeEdges(java.util.Set edges)

removeEdges

private java.util.Set removeEdges(UEDigraph digraph)

removeUEDigraph

protected java.util.Set removeUEDigraph(UEDigraph digraph)

retainNodes

protected java.util.Set retainNodes(java.util.Set retainedNodes)

retainEdges

protected boolean retainEdges(java.util.Set retainedEdges)

clear

protected void clear()

clearEdges

protected void clearEdges()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object