net.walend.digraph
Class AbstractLMCEDigraph

java.lang.Object
  |
  +--net.walend.digraph.AbstractMatrixCEDigraph
        |
        +--net.walend.digraph.AbstractLMCEDigraph

All Implemented Interfaces:

CEDigraph, Digraph, HasState, IndexedCEDigraph, IndexedDigraph, java.io.Serializable

Direct Known Subclasses:

LMCEDigraph, MutableLMCEDigraph

public abstract class AbstractLMCEDigraph

extends AbstractMatrixCEDigraph

implements java.io.Serializable

An extension of AbstractMatrixCEDigraph that keeps an additional int[][] that shows what nodes can be reached from what other nodes. This speeds up the getFromIndices[] method to constant time and the EdgeIterator to O(e) time. It also slows down the removeEdge to O(n) and the removeNode method to O(n^2).

Author:

David Walend dfw1@cornell.edu

See Also:

Serialized Form

Nested Class Summary

protected class

AbstractLMCEDigraph.LMEdgeIterator

Nested classes inherited from class net.walend.digraph.AbstractMatrixCEDigraph

AbstractMatrixCEDigraph.MatrixEdgeIterator, AbstractMatrixCEDigraph.NodeIterator

Field Summary

private int[][]

fromIndices

Fields inherited from class net.walend.digraph.AbstractMatrixCEDigraph

Fields inherited from interface net.walend.digraph.CEDigraph

EMPTY

Constructor Summary

protected	AbstractLMCEDigraph(CEDigraph digraph)
protected	AbstractLMCEDigraph(GEDigraph digraph, java.lang.Object edge)
protected	AbstractLMCEDigraph(int nodeCapacity)
protected	AbstractLMCEDigraph(UEDigraph digraph)

Method Summary

protected java.lang.Object	addEdge(int fromIndex, int toIndex, java.lang.Object edge)
protected void	clearEdges()
int	countInboundEdges(int toIndex)
EdgeIterator	edgeIterator()
int[]	getFromIndices(int toIndex)
Bag	getInboundEdges(int toIndex)
protected void	growMatrix(int newSize) This method doubles the size of the matrix
IndexedEdgeIterator	indexedEdgeIterator()
protected java.lang.Object	removeEdge(int fromIndex, int toIndex)
protected Bag	removeNode(int index)

Methods inherited from class net.walend.digraph.AbstractMatrixCEDigraph

addEdge, addNode, addNodes, clear, containsCEDigraph, containsEdge, containsEdge, containsEdge, containsEdge, containsNode, containsNode, containsNodes, countInboundEdges, countOutboundEdges, countOutboundEdges, edgeCount, edgeNodeIterator, getEdge, getEdge, getEdges, getFromNodes, getFromNodes, getInboundEdges, getNode, getNodeIndex, getNodes, getOutboundEdges, getOutboundEdges, getPrincipleInterface, getToIndices, getToNodes, getToNodes, indexedEdgeNodeIterator, indexedNodeIterator, insureCapacity, intersectWithCEDigraph, isEdgeFree, isEmpty, nodeCapacity, nodeCount, nodeIndices, nodeIterator, removeCEDigraph, removeEdge, removeNode, removeNodes, retainNodes, sameCEDigraphAs, sameStateAs, setNode, toString, unionCEDigraph

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

fromIndices

private int[][] fromIndices

Constructor Detail

AbstractLMCEDigraph

protected AbstractLMCEDigraph(int nodeCapacity)

AbstractLMCEDigraph

protected AbstractLMCEDigraph(CEDigraph digraph)

AbstractLMCEDigraph

protected AbstractLMCEDigraph(UEDigraph digraph)

AbstractLMCEDigraph

protected AbstractLMCEDigraph(GEDigraph digraph,
                              java.lang.Object edge)

Method Detail

edgeIterator

public EdgeIterator edgeIterator()

Specified by:

edgeIterator in interface CEDigraph

Overrides:

edgeIterator in class AbstractMatrixCEDigraph

countInboundEdges

public int countInboundEdges(int toIndex)

Specified by:

countInboundEdges in interface IndexedDigraph

Overrides:

countInboundEdges in class AbstractMatrixCEDigraph

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

Overrides:

getFromIndices in class AbstractMatrixCEDigraph

getInboundEdges

public Bag getInboundEdges(int toIndex)

Specified by:

getInboundEdges in interface IndexedCEDigraph

Overrides:

getInboundEdges in class AbstractMatrixCEDigraph

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.

indexedEdgeIterator

public IndexedEdgeIterator indexedEdgeIterator()

Specified by:

indexedEdgeIterator in interface IndexedCEDigraph

Overrides:

indexedEdgeIterator in class AbstractMatrixCEDigraph

addEdge

protected java.lang.Object addEdge(int fromIndex,
                                   int toIndex,
                                   java.lang.Object edge)

Overrides:

addEdge in class AbstractMatrixCEDigraph

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.

removeNode

protected Bag removeNode(int index)

Overrides:

removeNode in class AbstractMatrixCEDigraph

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.

removeEdge

protected java.lang.Object removeEdge(int fromIndex,
                                      int toIndex)

Overrides:

removeEdge in class AbstractMatrixCEDigraph

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.

growMatrix

protected void growMatrix(int newSize)

This method doubles the size of the matrix

Overrides:

growMatrix in class AbstractMatrixCEDigraph

clearEdges

protected void clearEdges()

Overrides:

clearEdges in class AbstractMatrixCEDigraph