net.walend.digraph
Class AbstractHashCEDigraph

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

All Implemented Interfaces:

CEDigraph, HasState

Direct Known Subclasses:

HashCEDigraph, MutableHashCEDigraph

public abstract class AbstractHashCEDigraph

extends java.lang.Object

implements CEDigraph

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:

20010613

Author:

David Walend

Nested Class Summary

protected class	AbstractHashCEDigraph.HashEdgeIterator
protected class	AbstractHashCEDigraph.IteratorWrapper
protected class	AbstractHashCEDigraph.NodePair

Field Summary

private MutableMap	nodePairsToEdges
private MutableSet	nodes

Fields inherited from interface net.walend.digraph.CEDigraph

EMPTY

Constructor Summary

protected	AbstractHashCEDigraph(CEDigraph digraph)
protected	AbstractHashCEDigraph(int nodeCapacity, int edgeCapacity)

Method Summary

protected java.lang.Object	addEdge(java.lang.Object fromNode, java.lang.Object toNode, java.lang.Object edge) Return null if fromNode or toNode are not in this CEDigraph, or if no existing edge is displaced by edge.
protected boolean	addNode(java.lang.Object node)
protected boolean	addNodes(Set nodesToAdd)
protected void	clear()
protected void	clearEdges()
boolean	containsCEDigraph(CEDigraph digraph) Returns true if digraph is a subgraph of this CEDigraph.
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(java.lang.Object node)
boolean	containsNodes(Set nodes)
int	countInboundEdges(java.lang.Object node) Inefficient.
int	countOutboundEdges(java.lang.Object node) Inefficient.
int	edgeCount()
EdgeIterator	edgeIterator() Since HashCEDigraph is immutable, edgeIterator()'s remove() method throws an UnsupportedOperationException.
java.lang.Object	getEdge(java.lang.Object fromNode, java.lang.Object toNode) Returns null if either node is not in the digraph or if no edge links fromNode to toNode
Set	getFromNodes(java.lang.Object node) Returns the set of nodes that can reach this node by crossing one edge.
Set	getInboundEdges(java.lang.Object node) Returns the empty set if node is not in the digraph, or if node has no inbound edges.
Set	getNodes()
Set	getOutboundEdges(java.lang.Object node) Returns the empty set if node is not in the digraph, or if node has no outbound edges.
java.lang.Class	getPrincipleInterface() Returns the class's principle interface for state comparisons.
Set	getToNodes(java.lang.Object node) Returns the set of nodes that can be reached from this node by crossing one edge.
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	nodeCount()
java.util.Iterator	nodeIterator() Since HashCEDigraph is immutable, nodeIterator()'s remove() method throws an UnsupportedOperationException.
protected Set	removeCEDigraph(CEDigraph digraph)
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 Set	removeEdges(CEDigraph digraph)
protected Set	removeNode(java.lang.Object node) Return the Set of orphaned edges that are removed with node
protected Set	removeNodes(Set nodesToRemove)
protected Set	retainNodes(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 victem) If two HasStates have the same internal state, return true.
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

nodes

private MutableSet nodes

nodePairsToEdges

private MutableMap nodePairsToEdges

Constructor Detail

AbstractHashCEDigraph

protected AbstractHashCEDigraph(int nodeCapacity,
                                int edgeCapacity)

AbstractHashCEDigraph

protected AbstractHashCEDigraph(CEDigraph digraph)

Method Detail

nodeCount

public int nodeCount()

Specified by:

nodeCount in interface CEDigraph

edgeCount

public int edgeCount()

Specified by:

edgeCount in interface CEDigraph

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface CEDigraph

containsNode

public boolean containsNode(java.lang.Object node)

Specified by:

containsNode in interface CEDigraph

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 CEDigraph

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 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 CEDigraph

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 CEDigraph

Throws:

NodeMissingException - if node is not in the digraph.

getInboundEdges

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

Returns the empty set if node is not in the digraph, or 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 Set getOutboundEdges(java.lang.Object node)
                     throws NodeMissingException

Returns the empty set if node is not in the digraph, or 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 either node is not in the digraph or 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 Set getFromNodes(java.lang.Object node)
                 throws NodeMissingException

Returns the set of nodes that can reach this node by crossing one edge. Returns the empty set if node is not in the digraph.

Inefficient. Iterates through all the edges.

Specified by:

getFromNodes in interface CEDigraph

Throws:

NodeMissingException - if node is not in the digraph.

getToNodes

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

Returns the set of nodes that can be reached from this node by crossing one edge. Returns the empty set if node is not in the digraph.

Inefficient. Iterates through all the edges.

Specified by:

getToNodes in interface CEDigraph

Throws:

NodeMissingException - if node is not in the digraph.

nodeIterator

public java.util.Iterator nodeIterator()

Since HashCEDigraph is immutable, nodeIterator()'s remove() method throws an UnsupportedOperationException.

Specified by:

nodeIterator in interface CEDigraph

edgeIterator

public EdgeIterator edgeIterator()

Since HashCEDigraph is immutable, edgeIterator()'s remove() method throws an UnsupportedOperationException.

Specified by:

edgeIterator in interface CEDigraph

getNodes

public Set getNodes()

Specified by:

getNodes in interface CEDigraph

isEdgeFree

public boolean isEdgeFree()

Returns true if this CEDigraph has no edges.

Specified by:

isEdgeFree in interface CEDigraph

containsNodes

public boolean containsNodes(Set nodes)

Specified by:

containsNodes in interface CEDigraph

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

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)

addEdge

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

Return null if fromNode or toNode are not in this CEDigraph, or 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 Set 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(Set nodesToAdd)

removeNodes

protected Set removeNodes(Set nodesToRemove)

removeEdges

private Set removeEdges(CEDigraph digraph)

removeCEDigraph

protected Set removeCEDigraph(CEDigraph digraph)

retainNodes

protected Set retainNodes(Set retainedNodes)

clear

protected void clear()

clearEdges

protected void clearEdges()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object