drasys.or.graph
Class SparseGraph

java.lang.Object
  |
  +--drasys.or.graph.Graph
        |
        +--drasys.or.graph.BaseGraph
              |
              +--drasys.or.graph.SparseGraph

public class SparseGraph

extends BaseGraph

implements EditI

A versatile implementation of a graph that is optimized to store edge sparse graphs. This graph supports parallel edges and both directed and undirected edges in the same graph.
The vertex and edge method 'doubleValue()' returns a double value based on the element's value object. If the value object is not null and either implements 'DoubleI' or is a subclass of 'Number' then the returned value is 'value.doubleValue()'. Otherwise; the value is zero.

References:

Graphs : Theory and Algorithms
    K. Thulasiraman, M.N.S. Swamy / Paperback / Published 1992

See Also:

Serialized Form

Fields inherited from class drasys.or.graph.Graph

_symmetric

 

Constructor Summary

SparseGraph()

SparseGraph(int vertexCapacity)

SparseGraph(MatrixI matrix)           Initializes the graph from the values in 'matrix'.

 

Method Summary
protected  void	_removeVertex(VertexI vertex, boolean removeZeroVertex)
EdgeI	addEdge(EdgeI edge)           Adds a new edge to the graph.
EdgeI	addEdge(java.lang.Object fromKey, java.lang.Object toKey)           Adds a new edge to the graph where: value=null, isDirected=false, key=null.
EdgeI	addEdge(java.lang.Object fromKey, java.lang.Object toKey, java.lang.Object value)           Adds a new edge to the graph where: isDirected=false, key=null.
EdgeI	addEdge(java.lang.Object fromKey, java.lang.Object toKey, java.lang.Object value, boolean isDirected)           Adds a new edge to the graph where: key=null.
EdgeI	addEdge(java.lang.Object fromKey, java.lang.Object toKey, java.lang.Object value, boolean isDirected, java.lang.Object key)           Adds a new edge to the graph.
void	ensureEdgeCapacity(int edgeCapacity)           Increases the capacity of the graph if needed to ensure it can efficiently hold this many edges.
EdgeI	getEdge(VertexI from, VertexI to, java.lang.Object edgeKey)           Get the edge between the from and to vertices whose key matches 'edgeKey'.
EdgeI	getMutableEdge(VertexI from, VertexI to, java.lang.Object edgeKey)           Get the edge between the from and to vertices whose key matches 'edgeKey'.
boolean	isSymmetric()           Returns false by default.
protected  VertexI	newVertex(java.lang.Object key, java.lang.Object value)
void	removeAllEdges()           Removes all edges from the graph.
EdgeI	removeEdge(EdgeI edge, boolean removeZeroVertices)           Removes the edge from the graph whose keys match the keys in the argument.
EdgeI	removeEdge(java.lang.Object fromKey, java.lang.Object toKey, java.lang.Object key, boolean removeZeroVertices)           Removes the edge from the graph whose keys match the arguments.
VertexI	removeVertex(java.lang.Object key, boolean removeZeroVertices)           Removes a vertex whose key matches the argument and all its adjacent edges.
VertexI	removeVertex(VertexI vertex, boolean removeZeroVertices)           Removes a vertex whose key matches the key in the argument and all its adjacent edges.
java.lang.String	toString()

 

Methods inherited from class drasys.or.graph.BaseGraph

addVertex, addVertex, addVertex, ensureVertexCapacity, getChangeCount, getVertex, removeAllVertices, sizeOfDirectedEdges, sizeOfEdges, sizeOfVertices, vertices

 

Methods inherited from class drasys.or.graph.Graph

edges, equals, getEdge, getEdge, isSubsetOf, mutableEdges, setSymmetric, toString

 

Methods inherited from class java.lang.Object

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

 

Constructor Detail

SparseGraph

public SparseGraph()

SparseGraph

public SparseGraph(int vertexCapacity)

SparseGraph

public SparseGraph(MatrixI matrix)

Initializes the graph from the values in 'matrix'. The vertex key will be an 'Integer' object equal to the row/column index and the vertex value will be null. The edge value will be a 'Double' object equal to the matrix entry and the edge key will be null. The edges will be directed and the matrix row corresponds to the from vertex of the edge.

isSymmetric

public boolean isSymmetric()

Returns false by default. If 'setSymmetric' has been called, then the override value is returned.

ensureEdgeCapacity

public void ensureEdgeCapacity(int edgeCapacity)

Increases the capacity of the graph if needed to ensure it can efficiently hold this many edges.

addEdge

public EdgeI addEdge(java.lang.Object fromKey,
                     java.lang.Object toKey)
              throws DuplicateEdgeException,
                     VertexNotFoundException

Adds a new edge to the graph where: value=null, isDirected=false, key=null. Throws 'VertexNotFoundException' if either vertex is not in the graph. Throws 'DuplicateEdgeException' if the edge already exists.

addEdge

public EdgeI addEdge(java.lang.Object fromKey,
                     java.lang.Object toKey,
                     java.lang.Object value)
              throws DuplicateEdgeException,
                     VertexNotFoundException

Adds a new edge to the graph where: isDirected=false, key=null. Throws 'VertexNotFoundException' if either vertex is not in the graph. Throws 'DuplicateEdgeException' if the edge already exists.

addEdge

public EdgeI addEdge(java.lang.Object fromKey,
                     java.lang.Object toKey,
                     java.lang.Object value,
                     boolean isDirected)
              throws DuplicateEdgeException,
                     VertexNotFoundException

Adds a new edge to the graph where: key=null. Throws 'VertexNotFoundException' if either vertex is not in the graph. Throws 'DuplicateEdgeException' if the edge already exists.

addEdge

public EdgeI addEdge(EdgeI edge)
              throws DuplicateEdgeException,
                     VertexNotFoundException

Adds a new edge to the graph. Throws 'VertexNotFoundException' if either vertex is not in the graph. Throws 'DuplicateEdgeException' if the edge already exists.

addEdge

public final EdgeI addEdge(java.lang.Object fromKey,
                           java.lang.Object toKey,
                           java.lang.Object value,
                           boolean isDirected,
                           java.lang.Object key)
                    throws DuplicateEdgeException,
                           VertexNotFoundException

Adds a new edge to the graph. Throws 'VertexNotFoundException' if either vertex is not in the graph. Throws 'DuplicateEdgeException' if the edge already exists.

newVertex

protected VertexI newVertex(java.lang.Object key,
                            java.lang.Object value)

Overrides:

newVertex in class BaseGraph

getMutableEdge

public EdgeI getMutableEdge(VertexI from,
                            VertexI to,
                            java.lang.Object edgeKey)

Get the edge between the from and to vertices whose key matches 'edgeKey'. The graph is allowed to return a mutable edge if that is more efficient, but the edge contents must be used before 'getMutableEdge()' is called again. The arguments 'from' and 'to' must be vertices from this graph. The argument 'edgeKey' is not used.

Returns:

Null if the edge is not in the graph.

getEdge

public EdgeI getEdge(VertexI from,
                     VertexI to,
                     java.lang.Object edgeKey)

Get the edge between the from and to vertices whose key matches 'edgeKey'. The arguments 'from' and 'to' must be vertices from this graph.

Returns:

Null if the edge is not in the graph.

removeVertex

public VertexI removeVertex(VertexI vertex,
                            boolean removeZeroVertices)
                     throws VertexNotFoundException

Removes a vertex whose key matches the key in the argument and all its adjacent edges. If 'removeZeroVertices' is true then any vertex whose degree becomes zero as a result of edge removal will be removed from the graph.

Returns:

The removed vertex.

removeVertex

public VertexI removeVertex(java.lang.Object key,
                            boolean removeZeroVertices)
                     throws VertexNotFoundException

Removes a vertex whose key matches the argument and all its adjacent edges. If 'removeZeroVertices' is true then any vertex whose degree becomes zero as a result of edge removal will be removed from the graph.

Returns:

The removed vertex.

_removeVertex

protected void _removeVertex(VertexI vertex,
                             boolean removeZeroVertex)

removeEdge

public EdgeI removeEdge(EdgeI edge,
                        boolean removeZeroVertices)
                 throws VertexNotFoundException,
                        EdgeNotFoundException

Removes the edge from the graph whose keys match the keys in the argument. If 'removeZeroVertices' is true then any vertex whose degree becomes zero as a result of removing the edge will be removed.

Returns:

The removed edge.

removeEdge

public EdgeI removeEdge(java.lang.Object fromKey,
                        java.lang.Object toKey,
                        java.lang.Object key,
                        boolean removeZeroVertices)
                 throws VertexNotFoundException,
                        EdgeNotFoundException

Removes the edge from the graph whose keys match the arguments. If 'removeZeroVertices' is true then any vertex whose degree becomes zero as a result of removing the edge will be removed.

Returns:

The removed edge.

removeAllEdges

public void removeAllEdges()

Removes all edges from the graph.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object