net.walend.digraph
Class AbstractLMGEDigraph

java.lang.Object
  |
  +--net.walend.digraph.AbstractMatrixGEDigraph
        |
        +--net.walend.digraph.AbstractLMGEDigraph

All Implemented Interfaces:

Digraph, GEDigraph, HasState, IndexedDigraph, IndexedGEDigraph, java.io.Serializable

Direct Known Subclasses:

LMGEDigraph, MutableLMGEDigraph

public abstract class AbstractLMGEDigraph

extends AbstractMatrixGEDigraph

implements java.io.Serializable

An extension of AbstractMatrixGEDigraph 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

AbstractLMGEDigraph.LMEdgeNodeIterator

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

AbstractMatrixGEDigraph.MatrixEdgeIterator, AbstractMatrixGEDigraph.NodeIterator

Field Summary

private int[][]

fromIndices

Fields inherited from class net.walend.digraph.AbstractMatrixGEDigraph

Fields inherited from interface net.walend.digraph.GEDigraph

EMPTY

Constructor Summary

protected	AbstractLMGEDigraph(CEDigraph digraph)
protected	AbstractLMGEDigraph(GEDigraph digraph)
protected	AbstractLMGEDigraph(int nodeCapacity)
protected	AbstractLMGEDigraph(UEDigraph digraph)

Method Summary

protected boolean	addEdge(int fromIndex, int toIndex)
protected void	clearEdges() Remove all the edges from the GEDigraph.
int	countInboundEdges(int toIndex)
int[]	getFromIndices(int toIndex)
protected void	growMatrix(int newSize) This method doubles the size of the matrix
protected boolean	removeEdge(int fromIndex, int toIndex)
protected int	removeNode(int index)

Methods inherited from class net.walend.digraph.AbstractMatrixGEDigraph

addEdge, addNode, addNodes, clear, containsEdge, containsEdge, containsGEDigraph, containsNode, containsNode, containsNodes, countInboundEdges, countOutboundEdges, countOutboundEdges, edgeCount, edgeNodeIterator, getFromNodes, getFromNodes, getNode, getNodeIndex, getNodes, getPrincipleInterface, getToIndices, getToNodes, getToNodes, indexedEdgeNodeIterator, indexedNodeIterator, insureCapacity, intersectWithGEDigraph, isEdgeFree, isEmpty, nodeCapacity, nodeCount, nodeIndices, nodeIterator, removeEdge, removeGEDigraph, removeNode, removeNodes, retainNodes, sameGEDigraphAs, sameStateAs, setNode, toString, unionGEDigraph

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

AbstractLMGEDigraph

protected AbstractLMGEDigraph(int nodeCapacity)

AbstractLMGEDigraph

protected AbstractLMGEDigraph(GEDigraph digraph)

AbstractLMGEDigraph

protected AbstractLMGEDigraph(CEDigraph digraph)

AbstractLMGEDigraph

protected AbstractLMGEDigraph(UEDigraph digraph)

Method Detail

countInboundEdges

public int countInboundEdges(int toIndex)

Specified by:

countInboundEdges in interface IndexedDigraph

Overrides:

countInboundEdges in class AbstractMatrixGEDigraph

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 AbstractMatrixGEDigraph

addEdge

protected boolean addEdge(int fromIndex,
                          int toIndex)

Overrides:

addEdge in class AbstractMatrixGEDigraph

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 int removeNode(int index)

Overrides:

removeNode in class AbstractMatrixGEDigraph

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 boolean removeEdge(int fromIndex,
                             int toIndex)

Overrides:

removeEdge in class AbstractMatrixGEDigraph

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 AbstractMatrixGEDigraph

clearEdges

protected void clearEdges()

Description copied from class: AbstractMatrixGEDigraph

Remove all the edges from the GEDigraph.

Overrides:

clearEdges in class AbstractMatrixGEDigraph