com.phoenixst.plexus
public class DefaultGraph extends Object implements ObservableGraph, Serializable
There are many ways of representing graphs in software, and
this package uses just one of those for the general
implementation. Of the two most basic, adjacency list and
adjacency matrix, adjacency list is the most efficient for even
remotely sparse graphs. Also, the design constraint that nodes
and edges are user-provided objects would have made an adjacency
matrix representation much more costly in terms of space (a
HashMap
would be required to map nodes to indices).
In general, it seems preferable to implement a graph as a
HashMap
from nodes to their adjacency lists. The
alternative (using some non-O(1) access Collection) is just too
prohibitive in time for the modest gains in space. The design
constraints (allowing both directed and undirected edges and edges
having identity) really don't leave a lot of room for
implementations largely different from the one found here. An
adjacency list is pretty much just a list of Edges, with some
extra bookkeeping information. Only if a single adjacency list
could grow very large would it be worthwhile to implement it as
something other than a simple list.
Since: 1.0
Version: $Revision: 1.117 $
Constructor Summary | |
---|---|
DefaultGraph()
Creates a new DefaultGraph . | |
DefaultGraph(Graph graph)
Creates a new DefaultGraph which is a copy of the
specified Graph . | |
protected | DefaultGraph(int nodeSize)
Creates a new DefaultGraph with a capacity for
the specified number of nodes (avoiding unnecessary rehashing). |
Method Summary | |
---|---|
protected Graph.Edge | addEdge(Object object, Object tail, Object head, boolean isDirected, Object edgeState)
Adds a new Graph.Edge with additional information
provided by the edgeState argument, which is
given to the createEdge() method. |
Graph.Edge | addEdge(Object object, Object tail, Object head, boolean isDirected) |
void | addGraphListener(GraphListener listener) |
boolean | addNode(Object node) |
Collection | adjacentNodes(Object node, Predicate traverserPredicate) |
boolean | containsEdge(Graph.Edge edge) |
boolean | containsNode(Object node) |
protected Graph.Edge | createEdge(Object object, Object tail, Object head, boolean isDirected, Object edgeState)
Creates a new Graph.Edge . |
int | degree(Object node) |
int | degree(Object node, Predicate traverserPredicate) |
protected void | edgeAdded(Graph.Edge edge)
Invoked after an edge has been added to this
Graph and any
GraphListeners have been notified. |
protected void | edgeAdding(Graph.Edge edge)
Invoked before an edge has been added to this
Graph and any
GraphListeners have been notified. |
protected void | edgeRemoved(Graph.Edge edge)
Invoked after an edge has been removed from this
Graph and any
GraphListeners have been notified. |
protected void | edgeRemoving(Graph.Edge edge)
Invoked before an edge has been removed from this
Graph and any
GraphListeners have been notified. |
Collection | edges(Predicate edgePredicate) |
boolean | equals(Object object) |
Object | getAdjacentNode(Object node, Predicate traverserPredicate) |
Graph.Edge | getEdge(Predicate edgePredicate) |
Graph.Edge | getIncidentEdge(Object node, Predicate traverserPredicate) |
Object | getNode(Predicate nodePredicate) |
int | hashCode() |
Collection | incidentEdges(Object node, Predicate traverserPredicate) |
protected void | nodeAdded(Object node)
Invoked after a node has been added to this Graph
and any GraphListeners have been
notified. |
protected void | nodeAdding(Object node)
Invoked before a node has been added to this
Graph and any
GraphListeners have been notified. |
protected void | nodeRemoved(Object node)
Invoked after a node has been removed from this
Graph and any
GraphListeners have been notified. |
protected void | nodeRemoving(Object node)
Invoked before a node has been removed from this
Graph and any
GraphListeners have been notified. |
Collection | nodes(Predicate nodePredicate) |
boolean | removeEdge(Graph.Edge edge) |
void | removeGraphListener(GraphListener listener) |
boolean | removeNode(Object node) |
String | toString() |
Traverser | traverser(Object node, Predicate traverserPredicate)
Returns a Traverser from node to all
adjacent nodes for which the specified filter is satisfied.
|
DefaultGraph
.DefaultGraph
which is a copy of the
specified Graph
.DefaultGraph
with a capacity for
the specified number of nodes (avoiding unnecessary rehashing).Graph.Edge
with additional information
provided by the edgeState
argument, which is
given to the createEdge()
method. This
method is intended to be called by subclasses which require
more information than just the object, tail, head, and
direction to construct the edge. This method cannot be
overridden.
Returns the newly created Graph.Edge
if this
Graph
changed as a result of the call. Returns
null
if this Graph
does not allow
duplicate edges and already contains the specified edge.
Graph.Edge
. This method can be
overridden by subclasses to provide a different implementation
than this one, which produces a DefaultObjectEdge.
This method should simply create the requested
Graph.Edge
, without checking to see whether it
already exists. DefaultGraph
will not allow
two edges which are .equals()
in the same
adjacency list.Graph
and any
GraphListeners
have been notified.Graph
and any
GraphListeners
have been notified.Graph
and any
GraphListeners
have been notified.Graph
and any
GraphListeners
have been notified.Graph
and any GraphListeners
have been
notified.Graph
and any
GraphListeners
have been notified.Graph
and any
GraphListeners
have been notified.Graph
and any
GraphListeners
have been notified.Traverser
from node
to all
adjacent nodes for which the specified filter is satisfied.
The returned Traverser
is tolerant of changes
to the underlying Graph
. Note that this does not
mean the Traverser
is thread-safe. However, if a
node or edge is added or removed while the iteration is is
progress, the iteration will not throw a
ConcurrentModificationException
. In fact, its
state will reflect the changes. This means that, among other
things, you should always call Traverser
before Traverser if there is a chance the
structure has changed since the last call to
hasNext()
. The one exception is that if the node
upon which the returned Traverser
is based is
removed, then all operations except hasNext()
will throw a ConcurrentModificationException
.
Description copied from interface: Graph
{@inheritDoc }