net.walend.digraph
Class AbstractHashGEDigraph

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

All Implemented Interfaces:

Digraph, GEDigraph, HasState, java.io.Serializable

Direct Known Subclasses:

HashGEDigraph, MutableHashGEDigraph

public abstract class AbstractHashGEDigraph

extends java.lang.Object

implements GEDigraph, java.io.Serializable

This abstract class implements the GEDigraph interface using two HashSets. It's great for sparse graphs. Subclass it as is for an immutable GEDigraph. Mix in the MutableGEDigraph interface for one you can change.

Since:

20010812

Author:

David Walend dfw1@cornell.edu

See Also:

Serialized Form

Nested Class Summary

protected class	AbstractHashGEDigraph.HashEdgeIterator
class	AbstractHashGEDigraph.NodeIterator
protected class	AbstractHashGEDigraph.NodePair

Field Summary

private java.util.Set	edges
private java.util.Set	nodes

Fields inherited from interface net.walend.digraph.GEDigraph

EMPTY

Constructor Summary

protected	AbstractHashGEDigraph(CEDigraph digraph)
protected	AbstractHashGEDigraph(GEDigraph digraph)
protected	AbstractHashGEDigraph(int nodeCapacity, int edgeCapacity)
protected	AbstractHashGEDigraph(UEDigraph digraph)

Method Summary

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 nodesToAdd) Return true if adding the nodes changes the digraph.
protected void	clear()
protected void	clearEdges()
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(java.lang.Object node)
boolean	containsNodes(java.util.Set nodes)
int	countInboundEdges(java.lang.Object node) Inefficient.
int	countOutboundEdges(java.lang.Object node) Inefficient.
int	edgeCount()
EdgeNodeIterator	edgeNodeIterator() Returns an iterator that iterates across pairs of nodes that make edges.
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	getNodes()
java.lang.Class	getPrincipleInterface() Returns the class's principle interface for state comparisons.
java.util.Set	getToNodes(java.lang.Object node) Returns the set of nodes that can be reached from this node by crossing one edge.
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	nodeCount()
java.util.Iterator	nodeIterator() Implementations should explicitly state how they interpret nodeIterator()'s remove method.
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.
private boolean	removeEdges(GEDigraph digraph)
protected int	removeGEDigraph(GEDigraph digraph) Return the number of edges orphaned when digraph is removed
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 nodesToRemove) 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, and all their contents have the same state.
boolean	sameStateAs(HasState victim) If two HasStates have the same internal state, return true.
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

nodes

private java.util.Set nodes

edges

private java.util.Set edges

Constructor Detail

AbstractHashGEDigraph

protected AbstractHashGEDigraph(int nodeCapacity,
                                int edgeCapacity)

AbstractHashGEDigraph

protected AbstractHashGEDigraph(GEDigraph digraph)

AbstractHashGEDigraph

protected AbstractHashGEDigraph(CEDigraph digraph)

AbstractHashGEDigraph

protected AbstractHashGEDigraph(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

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

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.

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.

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

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, and all their contents have the same state.

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

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

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

Return true if adding the nodes changes the digraph.

removeNodes

protected int removeNodes(java.util.Set nodesToRemove)

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

removeEdges

private boolean removeEdges(GEDigraph digraph)

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

clearEdges

protected void clearEdges()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object