net.walend.digraph
Class AbstractHashGEDigraph

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

All Implemented Interfaces:

GEDigraph, HasState

Direct Known Subclasses:

HashGEDigraph, MutableHashGEDigraph

public abstract class AbstractHashGEDigraph

extends java.lang.Object

implements GEDigraph

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

Nested Class Summary

protected class	AbstractHashGEDigraph.HashEdgeIterator
protected class	AbstractHashGEDigraph.IteratorWrapper
protected class	AbstractHashGEDigraph.NodePair

Field Summary

private MutableSet	edges
private MutableSet	nodes

Fields inherited from interface net.walend.digraph.GEDigraph

EMPTY

Constructor Summary

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

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(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(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.
Set	getFromNodes(java.lang.Object node) Returns the set of nodes that can reach this node by crossing one edge.
Set	getNodes() Since HashGEDigraph is immutable, edgeIterator()'s remove() method throws an UnsupportedOperationException.
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.
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() Since HashGEDigraph is immutable, nodeIterator()'s remove() method throws an UnsupportedOperationException.
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(Set nodesToRemove) Return the number of edges orphaned edges when these nodes are removed.
protected int	retainNodes(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 victem) 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 MutableSet nodes

edges

private MutableSet edges

Constructor Detail

AbstractHashGEDigraph

protected AbstractHashGEDigraph(int nodeCapacity,
                                int edgeCapacity)

AbstractHashGEDigraph

protected AbstractHashGEDigraph(GEDigraph digraph)

Method Detail

nodeCount

public int nodeCount()

Specified by:

nodeCount in interface GEDigraph

edgeCount

public int edgeCount()

Specified by:

edgeCount in interface GEDigraph

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface GEDigraph

containsNode

public boolean containsNode(java.lang.Object node)

Specified by:

containsNode in interface GEDigraph

containsEdge

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

Description copied from interface: GEDigraph

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

Specified by:

containsEdge in interface GEDigraph

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 GEDigraph

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 GEDigraph

Throws:

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

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 GEDigraph

Throws:

NodeMissingException - if node is not in the digraph.

nodeIterator

public java.util.Iterator nodeIterator()

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

Specified by:

nodeIterator in interface GEDigraph

edgeNodeIterator

public EdgeNodeIterator edgeNodeIterator()

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

Specified by:

edgeNodeIterator in interface GEDigraph

getNodes

public Set getNodes()

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

Specified by:

getNodes in interface GEDigraph

isEdgeFree

public boolean isEdgeFree()

Returns true if this GEDigraph has no edges.

Specified by:

isEdgeFree in interface GEDigraph

containsNodes

public boolean containsNodes(Set nodes)

Specified by:

containsNodes in interface GEDigraph

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

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

Return true if adding the nodes changes the digraph.

removeNodes

protected int removeNodes(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(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