public abstract class AbstractSparseGraph extends AbstractArchetypeGraph implements Graph, java.lang.Cloneable
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.
Constraints imposed by this class:
NotInGraphVertexPredicate
, NotInGraphEdgePredicate
user (visible, modifiable via getEdgeConstraints
): none
AbstractArchetypeGraph.Requirements
UserDataContainer.CopyAction
Modifier and Type | Field and Description |
---|---|
protected java.util.Set |
mEdges
The set of edges registered with the graph.
|
protected java.util.Set |
mVertices
The set of vertices registered with the graph.
|
edge_requirements, mEdgeIDs, mGraphListenerHandler, mVertexIDs, vertex_requirements
factory, udc_delegate
DIRECTED_EDGE, NOT_PARALLEL_EDGE, SIMPLE_EDGE, UNDIRECTED_EDGE
SUBSET_MANAGER
Constructor and Description |
---|
AbstractSparseGraph()
Creates an instance of a sparse graph.
|
Modifier and Type | Method and Description |
---|---|
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.
|
protected void |
initialize()
Initializes all of the graph's internal data structures.
|
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.
|
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 vertices in the specified set from
g . |
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
g . |
addAllNotInitializers, addListener, checkConstraints, copy, getEdgeConstraints, getVertexConstraints, listenersExist, newInstance, numEdges, numVertices, removeAllEdges, removeAllVertices, removeListener, toString
addUserDatum, clone, containsUserDatumKey, getUserDatum, getUserDatumCopyAction, getUserDatumKeyIterator, importUserData, removeUserDatum, setUserDataFactory, setUserDatum
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
addListener, copy, getEdgeConstraints, getVertexConstraints, newInstance, numEdges, numVertices, removeAllEdges, removeAllVertices, removeListener
addUserDatum, clone, containsUserDatumKey, getUserDatum, getUserDatumCopyAction, getUserDatumKeyIterator, importUserData, removeUserDatum, setUserDatum
protected java.util.Set mVertices
protected java.util.Set mEdges
public AbstractSparseGraph()
initialize()
to set up the local data structures.initialize()
protected void initialize()
AbstractArchetypeGraph
Note: this method is not a substitute for
removeAllVertices()
, as it will not notify the vertices
and edges that they have been removed from the graph.
initialize
in class AbstractArchetypeGraph
public java.util.Set getVertices()
getVertices
in interface ArchetypeGraph
ArchetypeGraph.getVertices()
,
Collections.unmodifiableSet(java.util.Set)
public java.util.Set getEdges()
getEdges
in interface ArchetypeGraph
ArchetypeGraph.getEdges()
,
Collections.unmodifiableSet(java.util.Set)
public Edge addEdge(Edge e)
Graph
e
to this graph, and returns a reference to the
added vertex.addEdge
in interface Graph
e
- the edge to be addedGraph.addEdge(edu.uci.ics.jung.graph.Edge)
public Vertex addVertex(Vertex v)
Graph
v
to this graph, and returns a reference to the
added vertex.addVertex
in interface Graph
v
- the vertex to be addedGraph.addVertex(edu.uci.ics.jung.graph.Vertex)
public void removeVertex(Vertex v)
AbstractSparseVertex
.removeVertex
in interface Graph
public void removeEdge(Edge e)
AbstractSparseEdge
,
and the incident vertices will not be notified unless they are instances
of AbstractSparseVertex
.removeEdge
in interface Graph
public boolean isDirected()
Graph
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
.isDirected
in interface Graph
Graph.isDirected()
public void removeVertices(java.util.Set vertices)
g
. Syntactic
sugar for a loop that calls g.removeVertex
on all elements
of the set.
If any element of vertices
is not part of this graph,
then throws IllegalArgumentException
. If this
exception is thrown, any vertices that may have been removed already
are not guaranteed to be restored to the graph.removeVertices
in interface ArchetypeGraph
vertices
- the set of vertices to be removedpublic void removeEdges(java.util.Set edges)
g
. Syntactic
sugar for a loop that calls g.removeVertex
on all elements
of the set.
If any element of edges
is not part of this graph,
then throws IllegalArgumentException
. If this
exception is thrown, any edges that may have been removed already
are not guaranteed to be restored to the graph.removeEdges
in interface ArchetypeGraph