edu.uci.ics.jung.graph.impl
Class AbstractSparseGraph

java.lang.Object
  edu.uci.ics.jung.utils.UserData
      edu.uci.ics.jung.graph.impl.AbstractArchetypeGraph
          edu.uci.ics.jung.graph.impl.AbstractSparseGraph

All Implemented Interfaces:

ArchetypeGraph, java.lang.Cloneable, Graph, UserDataContainer

Direct Known Subclasses:

SparseGraph

public abstract class AbstractSparseGraph

extends AbstractArchetypeGraph

implements Graph, java.lang.Cloneable

This class provides a skeletal implementation of the Graph interface to minimize the effort required to implement this interface. This graph implementation stores vertices and edges in Sets. It is appropriate for sparse graphs (those in which each vertex has only a few neighbors). For dense graphs (those in which each vertex is connected to most other vertices), a different implementation (for example, one which represents a graph via a matrix) may be more appropriate.

Currently, the addition and removal methods will notify their arguments that they have been added to or removed from this graph only if they are instances of AbstractSparseVertex or AbstractSparseEdge.

This class extends UserData, which provides storage and retrieval mechanisms for user-defined data for each graph instance. This allows users to attach data to graphs without having to extend this class.

Author:

Scott D. White, Danyel Fisher, Joshua O'Madadhain

Nested Class Summary

Nested classes inherited from class edu.uci.ics.jung.utils.UserDataContainer

UserDataContainer.CopyAction

Field Summary

Fields inherited from class edu.uci.ics.jung.utils.UserData

CLONE, REMOVE, SHARED

Fields inherited from interface edu.uci.ics.jung.graph.Graph

DIRECTED_EDGE, NOT_PARALLEL_EDGE, SIMPLE_EDGE, UNDIRECTED_EDGE

Fields inherited from interface edu.uci.ics.jung.graph.ArchetypeGraph

SUBSET_MANAGER

Constructor Summary

AbstractSparseGraph()
Creates an instance of a sparse graph.

Method Summary

Edge	addEdge(Edge e) Adds e to this graph, and returns a reference to the added vertex.
Vertex	addVertex(Vertex v) Adds v to this graph, and returns a reference to the added vertex.
java.util.Set	getEdges() Returns an unmodifiable set view of the edges in this graph.
java.util.Set	getVertices() Returns an unmodifiable set view of the vertices in this graph.
boolean	isDirected() Returns true if each edge of this graph is directed, and false if each edge of this graph is undirected.
void	removeAllEdges() Removes all edges from this graph.
void	removeAllVertices() Removes all vertices (and, therefore, all edges) from this graph.
void	removeEdge(Edge e) Removes the edge from the graph, and notifies that the edge and its incident vertices that it has been removed.
void	removeEdges(java.util.Set edges) Removes all edges in the specified set from this graph.
void	removeVertex(Vertex v) Removes all edges adjacent to the specified vertex, removes the vertex, and notifies the vertex that it has been removed.
void	removeVertices(java.util.Set vertices) Removes all vertices in the specified set from this graph.

Methods inherited from class edu.uci.ics.jung.graph.impl.AbstractArchetypeGraph

addListener, copy, getEdgeConstraints, getVertexConstraints, newInstance, numEdges, numVertices, removeListener, toString

Methods inherited from class edu.uci.ics.jung.utils.UserData

addUserDatum, containsUserDatumKey, getUserDatum, getUserDatumCopyAction, getUserDatumKeyIterator, importUserData, removeUserDatum, setUserDatum

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface edu.uci.ics.jung.graph.ArchetypeGraph

addListener, copy, getEdgeConstraints, getVertexConstraints, newInstance, numEdges, numVertices, removeListener

Methods inherited from interface edu.uci.ics.jung.utils.UserDataContainer

addUserDatum, containsUserDatumKey, getUserDatum, getUserDatumCopyAction, getUserDatumKeyIterator, importUserData, removeUserDatum, setUserDatum

Constructor Detail

AbstractSparseGraph

public AbstractSparseGraph()

Creates an instance of a sparse graph. Invokes initialize() to set up the local data structures.

See Also:

#initialize()

Method Detail

getVertices

public java.util.Set getVertices()

Returns an unmodifiable set view of the vertices in this graph. Will reflect changes made to the graph after the view is generated.

Specified by:

getVertices in interface ArchetypeGraph

See Also:

ArchetypeGraph.getVertices(), Collections.unmodifiableSet(java.util.Set)

getEdges

public java.util.Set getEdges()

Returns an unmodifiable set view of the edges in this graph. Will reflect changes made to the graph after the view is generated.

Specified by:

getEdges in interface ArchetypeGraph

See Also:

ArchetypeGraph.getEdges(), Collections.unmodifiableSet(java.util.Set)

addEdge

public Edge addEdge(Edge e)

Description copied from interface: Graph

Adds e to this graph, and returns a reference to the added vertex.

Specified by:

addEdge in interface Graph

Parameters:

e - the edge to be added

See Also:

Graph.addEdge(edu.uci.ics.jung.graph.Edge)

addVertex

public Vertex addVertex(Vertex v)

Description copied from interface: Graph

Adds v to this graph, and returns a reference to the added vertex.

Specified by:

addVertex in interface Graph

Parameters:

v - the vertex to be added

See Also:

Graph.addVertex(edu.uci.ics.jung.graph.Vertex)

removeVertex

public void removeVertex(Vertex v)

Removes all edges adjacent to the specified vertex, removes the vertex, and notifies the vertex that it has been removed. Note: the vertex will not be notified unless it is an instance of AbstractSparseVertex.

Specified by:

removeVertex in interface Graph

removeEdge

public void removeEdge(Edge e)

Removes the edge from the graph, and notifies that the edge and its incident vertices that it has been removed. Note: the edge will not be notified unless it is an instance of AbstractSparseEdge, and the incident vertices will not be notified unless they are instances of AbstractSparseVertex.

Specified by:

removeEdge in interface Graph

removeVertices

public void removeVertices(java.util.Set vertices)

Removes all vertices in the specified set from this graph. Syntactic sugar for a loop that calls removeVertex on all elements of the set.

Specified by:

removeVertices in interface ArchetypeGraph

Parameters:

vertices - the set of vertices to be removed

See Also:

ArchetypeGraph.removeVertices(java.util.Set)

removeEdges

public void removeEdges(java.util.Set edges)

Removes all edges in the specified set from this graph. Syntactic sugar for a loop that calls removeEdge on all elements of the set.

Specified by:

removeEdges in interface ArchetypeGraph

See Also:

ArchetypeGraph.removeEdges(java.util.Set)

removeAllVertices

public void removeAllVertices()

Removes all vertices (and, therefore, all edges) from this graph. Syntactic sugar for a loop that calls removeVertex on all vertices of this graph.

Specified by:

removeAllVertices in interface ArchetypeGraph

See Also:

ArchetypeGraph.removeAllVertices()

removeAllEdges

public void removeAllEdges()

Removes all edges from this graph. Syntactic sugar for a loop that calls removeEdge on all edges of this graph.

Specified by:

removeAllEdges in interface ArchetypeGraph

See Also:

ArchetypeGraph.removeAllEdges()

isDirected

public boolean isDirected()

Deprecated. As of version 1.4, the semantics of this method have changed; it no longer returns a boolean value that is hardwired into the class definition, but checks to see whether one of the requirements of this graph is that it only accepts directed edges.

Description copied from interface: Graph

Returns true if each edge of this graph is directed, and false if each edge of this graph is undirected. If some edges are directed and some are not, throws FatalException.

Specified by:

isDirected in interface Graph

See Also:

Graph.isDirected()