net.walend.digraph
Class MutableLMGEDigraph

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

All Implemented Interfaces:

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

public class MutableLMGEDigraph

extends AbstractLMGEDigraph

implements IndexedMutableGEDigraph, java.io.Serializable

This class implements the GEDigraph interface using an ArrayList and a boolean matrix and 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

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

AbstractLMGEDigraph.LMEdgeNodeIterator

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

AbstractMatrixGEDigraph.MatrixEdgeIterator, AbstractMatrixGEDigraph.NodeIterator

Field Summary

private static int

DEFAULTSIZE

Fields inherited from class net.walend.digraph.AbstractLMGEDigraph

Fields inherited from class net.walend.digraph.AbstractMatrixGEDigraph

Fields inherited from interface net.walend.digraph.GEDigraph

EMPTY

Constructor Summary

MutableLMGEDigraph()

MutableLMGEDigraph(CEDigraph digraph)

MutableLMGEDigraph(GEDigraph digraph)

MutableLMGEDigraph(int nodeCapacity)

MutableLMGEDigraph(UEDigraph digraph)

Method Summary

boolean	addEdge(int fromIndex, int toIndex)
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.
boolean	addNode(java.lang.Object node) Return true if the node is added successfully, false if the digraph does not change.
boolean	addNodes(java.util.Set nodes) Return true if adding the nodes changes the digraph.
void	clear() Remove all nodes and edges from the GEDigraph
void	clearEdges() Remove all the edges from the GEDigraph.
void	insureCapacity(int capacity)
boolean	removeEdge(int fromIndex, int toIndex)
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.
int	removeGEDigraph(GEDigraph digraph) Return the number of edges orphaned when digraph is removed
int	removeNode(int index)
int	removeNode(java.lang.Object node) Return the number of orphaned edges that were lost when this node is removed.
int	removeNodes(java.util.Set nodes) Return the number of edges orphaned edges when these nodes are removed.
int	retainNodes(java.util.Set nodes) Return the number of orphaned edges when the nodes are removed.
java.lang.Object	setNode(int index, java.lang.Object node)

Methods inherited from class net.walend.digraph.AbstractLMGEDigraph

countInboundEdges, getFromIndices, growMatrix

Methods inherited from class net.walend.digraph.AbstractMatrixGEDigraph

containsEdge, containsEdge, containsGEDigraph, containsNode, containsNode, containsNodes, countInboundEdges, countOutboundEdges, countOutboundEdges, edgeCount, edgeNodeIterator, getFromNodes, getFromNodes, getNode, getNodeIndex, getNodes, getPrincipleInterface, getToIndices, getToNodes, getToNodes, indexedEdgeNodeIterator, indexedNodeIterator, intersectWithGEDigraph, isEdgeFree, isEmpty, nodeCapacity, nodeCount, nodeIndices, nodeIterator, sameGEDigraphAs, sameStateAs, toString, unionGEDigraph

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.walend.digraph.GEDigraph

containsGEDigraph, intersectWithGEDigraph, sameGEDigraphAs, unionGEDigraph

Methods inherited from interface net.walend.digraph.Digraph

containsEdge, containsNode, containsNodes, countInboundEdges, countOutboundEdges, edgeCount, edgeNodeIterator, getFromNodes, getNodes, getToNodes, isEdgeFree, isEmpty, nodeCount, nodeIterator

Methods inherited from interface net.walend.collection.HasState

getPrincipleInterface, sameStateAs

Methods inherited from interface net.walend.digraph.IndexedDigraph

containsEdge, containsNode, countInboundEdges, countOutboundEdges, getFromIndices, getFromNodes, getNode, getNodeIndex, getToIndices, getToNodes, indexedEdgeNodeIterator, indexedNodeIterator, nodeCapacity, nodeIndices

Field Detail

DEFAULTSIZE

private static final int DEFAULTSIZE

See Also:

Constant Field Values

Constructor Detail

MutableLMGEDigraph

public MutableLMGEDigraph()

MutableLMGEDigraph

public MutableLMGEDigraph(int nodeCapacity)

MutableLMGEDigraph

public MutableLMGEDigraph(GEDigraph digraph)

MutableLMGEDigraph

public MutableLMGEDigraph(CEDigraph digraph)

MutableLMGEDigraph

public MutableLMGEDigraph(UEDigraph digraph)

Method Detail

addNode

public boolean addNode(java.lang.Object node)

Description copied from interface: MutableGEDigraph

Return true if the node is added successfully, false if the digraph does not change.

Specified by:

addNode in interface MutableGEDigraph

Overrides:

addNode in class AbstractMatrixGEDigraph

addEdge

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

Description copied from interface: MutableGEDigraph

Return true if the digraph changes when this edge is added, false if the digraph is unchanged.

Specified by:

addEdge in interface MutableGEDigraph

Overrides:

addEdge in class AbstractMatrixGEDigraph

Throws:

NodeMissingException - if either node is not in the digraph.

removeNode

public int removeNode(java.lang.Object node)
               throws NodeMissingException

Description copied from interface: MutableGEDigraph

Return the number of orphaned edges that were lost when this node is removed.

Specified by:

removeNode in interface MutableGEDigraph

Overrides:

removeNode in class AbstractMatrixGEDigraph

Throws:

NodeMissingException - if the node is not in the digraph

removeEdge

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

Description copied from interface: MutableGEDigraph

Return true if the digraph changes when the edge is removed, false if the digraph didn't have an edge between these two nodes.

Specified by:

removeEdge in interface MutableGEDigraph

Overrides:

removeEdge in class AbstractMatrixGEDigraph

Throws:

NodeMissingException - if either node is not in the digraph

addNodes

public boolean addNodes(java.util.Set nodes)

Description copied from interface: MutableGEDigraph

Return true if adding the nodes changes the digraph.

Specified by:

addNodes in interface MutableGEDigraph

Overrides:

addNodes in class AbstractMatrixGEDigraph

removeNodes

public int removeNodes(java.util.Set nodes)

Description copied from interface: MutableGEDigraph

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

Specified by:

removeNodes in interface MutableGEDigraph

Overrides:

removeNodes in class AbstractMatrixGEDigraph

removeGEDigraph

public int removeGEDigraph(GEDigraph digraph)

Description copied from interface: MutableGEDigraph

Return the number of edges orphaned when digraph is removed

Specified by:

removeGEDigraph in interface MutableGEDigraph

Overrides:

removeGEDigraph in class AbstractMatrixGEDigraph

retainNodes

public int retainNodes(java.util.Set nodes)

Description copied from interface: MutableGEDigraph

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

Specified by:

retainNodes in interface MutableGEDigraph

Overrides:

retainNodes in class AbstractMatrixGEDigraph

clear

public void clear()

Description copied from interface: MutableGEDigraph

Remove all nodes and edges from the GEDigraph

Specified by:

clear in interface MutableGEDigraph

Overrides:

clear in class AbstractMatrixGEDigraph

clearEdges

public void clearEdges()

Description copied from interface: MutableGEDigraph

Remove all the edges from the GEDigraph.

Specified by:

clearEdges in interface MutableGEDigraph

Overrides:

clearEdges in class AbstractLMGEDigraph

insureCapacity

public void insureCapacity(int capacity)

Specified by:

insureCapacity in interface IndexedMutableGEDigraph

Overrides:

insureCapacity in class AbstractMatrixGEDigraph

setNode

public java.lang.Object setNode(int index,
                                java.lang.Object node)

Specified by:

setNode in interface IndexedMutableGEDigraph

Overrides:

setNode in class AbstractMatrixGEDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndicies() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

addEdge

public boolean addEdge(int fromIndex,
                       int toIndex)

Specified by:

addEdge in interface IndexedMutableGEDigraph

Overrides:

addEdge in class AbstractLMGEDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndicies() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

removeNode

public int removeNode(int index)

Specified by:

removeNode in interface IndexedMutableGEDigraph

Overrides:

removeNode in class AbstractLMGEDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndicies() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.

removeEdge

public boolean removeEdge(int fromIndex,
                          int toIndex)

Specified by:

removeEdge in interface IndexedMutableGEDigraph

Overrides:

removeEdge in class AbstractLMGEDigraph

Throws:

java.lang.ArrayIndexOutOfBoundsException - if index does not have a node. Use nodeIndicies() or getNodeIndex() to avoid these. In your code, catch ArrayIndexOutOfBoundsException and throw a ConcurrentModificationException if you think that's the problem.