
Plexus v0.13.1  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object com.phoenixst.plexus.DefaultGraph
public class DefaultGraph
A default implementation of the ObservableGraph
interface.
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 userprovided 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 nonO(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.
Nested Class Summary 

Nested classes/interfaces inherited from interface com.phoenixst.plexus.Graph 

Graph.Edge 
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  

Graph.Edge 
addEdge(Object object,
Object tail,
Object head,
boolean isDirected)
Adds the specified edge to the Graph (optional
operation). 
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. 
void 
addGraphListener(GraphListener listener)
Adds the specified GraphListener which will be
notified whenever this ObservableGraph's
structure changes. 
boolean 
addNode(Object node)
Adds node to this Graph (optional
operation). 
Collection 
adjacentNodes(Object node,
org.apache.commons.collections.Predicate traverserPredicate)
Returns the nodes adjacent to the specified node
for which the specified Predicate is satisfied. 
boolean 
containsEdge(Graph.Edge edge)
Returns true if this Graph contains
the specified Graph.Edge . 
boolean 
containsNode(Object node)
Returns true if this Graph contains
the specified node. 
protected Graph.Edge 
createEdge(Object object,
Object tail,
Object head,
boolean isDirected,
Object edgeState)
Creates a new Graph.Edge . 
int 
degree(Object node)
Returns the degree of node , defined as the number
of edges incident on node , with selfloops
counted twice. 
int 
degree(Object node,
org.apache.commons.collections.Predicate traverserPredicate)
Returns the degree of node for which the
specified Predicate is satisfied, defined as the
number of edges incident on node that pass the
predicate, with selfloops counted only once. 
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(org.apache.commons.collections.Predicate edgePredicate)
Returns the Graph.Edges from this
Graph that satisfy the specified
predicate . 
boolean 
equals(Object object)

Object 
getAdjacentNode(Object node,
org.apache.commons.collections.Predicate traverserPredicate)
Returns a node adjacent to the specified node for
which the specified Predicate is satisfied. 
Graph.Edge 
getEdge(org.apache.commons.collections.Predicate edgePredicate)
Returns a Graph.Edge from this Graph
that satisfies the specified predicate , or
null if no such Graph.Edge exists. 
Graph.Edge 
getIncidentEdge(Object node,
org.apache.commons.collections.Predicate traverserPredicate)
Returns a Graph.Edge incident on the specified
node for which the specified
Predicate is satisfied. 
Object 
getNode(org.apache.commons.collections.Predicate nodePredicate)
Returns a node from this Graph that satisfies the
specified predicate , or null if no
such node exists. 
int 
hashCode()

Collection 
incidentEdges(Object node,
org.apache.commons.collections.Predicate traverserPredicate)
Returns the Graph.Edges incident on the specified
node for which the specified
Predicate is satisfied. 
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(org.apache.commons.collections.Predicate nodePredicate)
Returns the nodes from this Graph that satisfy
the specified predicate . 
boolean 
removeEdge(Graph.Edge edge)
Removes the specified Graph.Edge from this
Graph (optional operation). 
void 
removeGraphListener(GraphListener listener)
Removes a previously added GraphListener . 
boolean 
removeNode(Object node)
Removes node from this Graph
(optional operation). 
String 
toString()

Traverser 
traverser(Object node,
org.apache.commons.collections.Predicate traverserPredicate)
Returns a Traverser from node to all
adjacent nodes for which the specified filter is satisfied. 
Methods inherited from class java.lang.Object 

clone, finalize, getClass, notify, notifyAll, wait, wait, wait 
Constructor Detail 

public DefaultGraph()
DefaultGraph
.
public DefaultGraph(Graph graph)
DefaultGraph
which is a copy of the
specified Graph
.
protected DefaultGraph(int nodeSize)
DefaultGraph
with a capacity for
the specified number of nodes (avoiding unnecessary rehashing).
Method Detail 

protected Graph.Edge createEdge(Object object, Object tail, Object head, boolean isDirected, Object edgeState)
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.
protected final Graph.Edge addEdge(Object object, Object tail, Object head, boolean isDirected, Object edgeState)
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.
protected void nodeAdding(Object node)
Graph
and any GraphListeners
have been notified.
protected void nodeAdded(Object node)
Graph
and any GraphListeners
have been
notified.
protected void nodeRemoving(Object node)
Graph
and any GraphListeners
have been notified.
protected void nodeRemoved(Object node)
Graph
and any GraphListeners
have been notified.
protected void edgeAdding(Graph.Edge edge)
Graph
and any GraphListeners
have been notified.
protected void edgeAdded(Graph.Edge edge)
Graph
and any GraphListeners
have been notified.
protected void edgeRemoving(Graph.Edge edge)
Graph
and any GraphListeners
have been notified.
protected void edgeRemoved(Graph.Edge edge)
Graph
and any GraphListeners
have been notified.
public boolean addNode(Object node)
Graph
node
to this Graph
(optional
operation). Returns true
if this
Graph
changed as a result of the call. Returns
false
if this Graph
already contains
node
.
If a Graph
refuses to add a particular node
for any reason other than that it already contains the node,
it must throw an exception (rather than returning
false
). This preserves the invariant that a
Graph
always contains the specified node after
this call returns. Graph
classes should clearly
specify in their documentation any other restrictions on what
nodes may be added.
addNode
in interface Graph
node
 the node to be added to this Graph
.
true
if this Graph
changed
as a result of the call, false
if this
Graph
already contains the specified node.public boolean removeNode(Object node)
Graph
node
from this Graph
(optional operation). This method will also remove all edges
incident on node
.
removeNode
in interface Graph
node
 the node to be removed from this
Graph
.
true
if this Graph
contained
node
.public boolean containsNode(Object node)
Graph
true
if this Graph
contains
the specified node.
containsNode
in interface Graph
node
 the node whose presence in this Graph
is to be tested.
true
if this Graph
contains
the specified node.public Graph.Edge addEdge(Object object, Object tail, Object head, boolean isDirected)
Graph
Graph
(optional
operation). 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.
If a Graph
refuses to add a particular edge
for any reason other than that it already contains the edge,
it must throw an exception (rather than returning
null
). This preserves the invariant that a
Graph
always contains the specified edge after
this call returns. Graph
classes should clearly
specify in their documentation any other restrictions on what
edges may be added.
addEdge
in interface Graph
object
 the userdefined object to be contained in the
new edge.tail
 the first endpoint of the new edge.head
 the second endpoint of the new edge.isDirected
 whether the new edge is directed.
Graph.Edge
if this
Graph
changed as a result of the call,
null
if this Graph
does not allow
duplicate edges and already contains the specified edge.public boolean removeEdge(Graph.Edge edge)
Graph
Graph.Edge
from this
Graph
(optional operation).
removeEdge
in interface Graph
edge
 the Graph.Edge
to be removed from
this Graph
.
true
if this Graph
contained
the specified Graph.Edge
.public boolean containsEdge(Graph.Edge edge)
Graph
true
if this Graph
contains
the specified Graph.Edge
.
containsEdge
in interface Graph
edge
 the Graph.Edge
whose presence in this
Graph
is to be tested.
true
if this Graph
contains
the specified Graph.Edge
.public int degree(Object node)
Graph
node
, defined as the number
of edges incident on node
, with selfloops
counted twice. If this node has more than
Integer.MAX_VALUE
incident edges, returns
Integer.MAX_VALUE
.
degree
in interface Graph
node
 return the degree of this node.
node
.public int degree(Object node, org.apache.commons.collections.Predicate traverserPredicate)
Graph
node
for which the
specified Predicate
is satisfied, defined as the
number of edges incident on node
that pass the
predicate, with selfloops counted only once. The argument to
the Predicate.evaluate()
method is expected to be
an OrderedPair
. The first
element of the OrderedPair
is the specified
node
, the second is the Graph.Edge
.
If this node has more than Integer.MAX_VALUE
such
edges, returns Integer.MAX_VALUE
.
degree
in interface Graph
node
 return the degree of this node for which the
specified predicate is satisfied.traverserPredicate
 the predicate which the counted
Graph.Edges
must satisfy.
node
for which the
specified predicate is satisfied.public Collection nodes(org.apache.commons.collections.Predicate nodePredicate)
Graph
Graph
that satisfy
the specified predicate
.
nodes
in interface Graph
nodePredicate
 the predicate which the returned nodes
must satisfy.
Graph
that satisfy
the specified predicate
.public Collection edges(org.apache.commons.collections.Predicate edgePredicate)
Graph
Graph.Edges
from this
Graph
that satisfy the specified
predicate
.
edges
in interface Graph
edgePredicate
 the predicate which the returned
Graph.Edges
must satisfy.
Graph.Edges
from this
Graph
that satisfy the specified
predicate
.public Collection adjacentNodes(Object node, org.apache.commons.collections.Predicate traverserPredicate)
Graph
node
for which the specified Predicate
is satisfied.
The argument to the Predicate.evaluate()
method
is expected to be an OrderedPair
. The first element of
the OrderedPair
is the specified
node
, the second is the Graph.Edge
.
It should be noted that removing a node from the returned
Collection
merely removes one instance of it
being adjacent to the specified node
. In other
words, a connecting Graph.Edge
is removed.
adjacentNodes
in interface Graph
node
 return the nodes adjacent to this node for which
the specified predicate is satisfied.traverserPredicate
 the predicate which the returned
nodes and the traversed Graph.Edges
must satisfy.
node
for which the specified predicate is satisfied.public Collection incidentEdges(Object node, org.apache.commons.collections.Predicate traverserPredicate)
Graph
Graph.Edges
incident on the specified
node
for which the specified
Predicate
is satisfied. The argument to the
Predicate.evaluate()
method is expected to be an
OrderedPair
. The first
element of the OrderedPair
is the specified
node
, the second is the Graph.Edge
.
incidentEdges
in interface Graph
node
 return the Graph.Edges
incident on
this node for which the specified predicate is satisfied.traverserPredicate
 the predicate which the returned
Graph.Edges
must satisfy.
Graph.Edges
incident on the specified
node
for which the specified predicate is
satisfied.public Object getNode(org.apache.commons.collections.Predicate nodePredicate)
Graph
Graph
that satisfies the
specified predicate
, or null
if no
such node exists.
getNode
in interface Graph
nodePredicate
 the predicate which the returned node
must satisfy.
Graph
that satisfies the
specified predicate
, or null
if no
such node exists.public Graph.Edge getEdge(org.apache.commons.collections.Predicate edgePredicate)
Graph
Graph.Edge
from this Graph
that satisfies the specified predicate
, or
null
if no such Graph.Edge
exists.
getEdge
in interface Graph
edgePredicate
 the predicate which the returned
Graph.Edge
must satisfy.
Graph.Edge
from this Graph
that satisfies the specified predicate
, or
null
if no such Graph.Edge
exists.public Object getAdjacentNode(Object node, org.apache.commons.collections.Predicate traverserPredicate)
Graph
node
for
which the specified Predicate
is satisfied. The
argument to the Predicate.evaluate()
method is
expected to be an OrderedPair
. The first element of
the OrderedPair
is the specified
node
, the second is the Graph.Edge
.
getAdjacentNode
in interface Graph
node
 traverse to a node adjacent to this node for which
the specified predicate is satisfied.traverserPredicate
 the predicate which the returned
node and the traversed Graph.Edge
must satisfy.
node
for
which the specified predicate is satisfied.public Graph.Edge getIncidentEdge(Object node, org.apache.commons.collections.Predicate traverserPredicate)
Graph
Graph.Edge
incident on the specified
node
for which the specified
Predicate
is satisfied. The argument to the
Predicate.evaluate()
method is expected to be an
OrderedPair
. The first
element of the OrderedPair
is the specified
node
, the second is the Graph.Edge
.
getIncidentEdge
in interface Graph
node
 traverse to a Graph.Edge
incident on
this node for which the specified predicate is satisfied.traverserPredicate
 the predicate which the returned
Graph.Edge
must satisfy.
Graph.Edge
incident on the specified
node
for which the specified predicate is
satisfied.public Traverser traverser(Object node, org.apache.commons.collections.Predicate traverserPredicate)
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 threadsafe. 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 Iterator.hasNext()
before Iterator.next()
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
Returns a Traverser
from node
to all
adjacent nodes for which the specified Predicate
is satisfied. The argument to the
Predicate.evaluate()
method is expected to be an
OrderedPair
. The first
element of the OrderedPair
is the specified
node
, the second is the Graph.Edge
.
The nodes returned by Iterator.next()
are not
necessarily distinct. Selfloops are only traversed once.
There are no guarantees concerning the order in which the
nodes are returned (unless this Graph
is an
instance of some class that provides a guarantee).
traverser
in interface Graph
node
 traverse over all nodes adjacent to this node for
which the specified predicate is satisfied.traverserPredicate
 the predicate which the returned
nodes and their traversed Graph.Edges
must
satisfy.
Traverser
from node
to all
adjacent nodes for which the specified predicate is satisfied.public void addGraphListener(GraphListener listener)
ObservableGraph
GraphListener
which will be
notified whenever this ObservableGraph's
structure changes.
addGraphListener
in interface ObservableGraph
public void removeGraphListener(GraphListener listener)
ObservableGraph
GraphListener
.
removeGraphListener
in interface ObservableGraph
public boolean equals(Object object)
equals
in class Object
public int hashCode()
hashCode
in class Object
public String toString()
toString
in class Object

Plexus v0.13.1  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 