com.phoenixst.plexus

Class DefaultGraph

public class DefaultGraph extends Object implements ObservableGraph, Serializable

A default implementation of the ObservableGraph interface.

Design Criteria

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 $

Author: Ray A. Conner

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.EdgeaddEdge(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.EdgeaddEdge(Object object, Object tail, Object head, boolean isDirected)
voidaddGraphListener(GraphListener listener)
booleanaddNode(Object node)
CollectionadjacentNodes(Object node, Predicate traverserPredicate)
booleancontainsEdge(Graph.Edge edge)
booleancontainsNode(Object node)
protected Graph.EdgecreateEdge(Object object, Object tail, Object head, boolean isDirected, Object edgeState)
Creates a new Graph.Edge.
intdegree(Object node)
intdegree(Object node, Predicate traverserPredicate)
protected voidedgeAdded(Graph.Edge edge)
Invoked after an edge has been added to this Graph and any GraphListeners have been notified.
protected voidedgeAdding(Graph.Edge edge)
Invoked before an edge has been added to this Graph and any GraphListeners have been notified.
protected voidedgeRemoved(Graph.Edge edge)
Invoked after an edge has been removed from this Graph and any GraphListeners have been notified.
protected voidedgeRemoving(Graph.Edge edge)
Invoked before an edge has been removed from this Graph and any GraphListeners have been notified.
Collectionedges(Predicate edgePredicate)
booleanequals(Object object)
ObjectgetAdjacentNode(Object node, Predicate traverserPredicate)
Graph.EdgegetEdge(Predicate edgePredicate)
Graph.EdgegetIncidentEdge(Object node, Predicate traverserPredicate)
ObjectgetNode(Predicate nodePredicate)
inthashCode()
CollectionincidentEdges(Object node, Predicate traverserPredicate)
protected voidnodeAdded(Object node)
Invoked after a node has been added to this Graph and any GraphListeners have been notified.
protected voidnodeAdding(Object node)
Invoked before a node has been added to this Graph and any GraphListeners have been notified.
protected voidnodeRemoved(Object node)
Invoked after a node has been removed from this Graph and any GraphListeners have been notified.
protected voidnodeRemoving(Object node)
Invoked before a node has been removed from this Graph and any GraphListeners have been notified.
Collectionnodes(Predicate nodePredicate)
booleanremoveEdge(Graph.Edge edge)
voidremoveGraphListener(GraphListener listener)
booleanremoveNode(Object node)
StringtoString()
Traversertraverser(Object node, Predicate traverserPredicate)
Returns a Traverser from node to all adjacent nodes for which the specified filter is satisfied.

Constructor Detail

DefaultGraph

public DefaultGraph()
Creates a new DefaultGraph.

DefaultGraph

public DefaultGraph(Graph graph)
Creates a new DefaultGraph which is a copy of the specified Graph.

DefaultGraph

protected DefaultGraph(int nodeSize)
Creates a new DefaultGraph with a capacity for the specified number of nodes (avoiding unnecessary rehashing).

Method Detail

addEdge

protected final 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. 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.

addEdge

public Graph.Edge addEdge(Object object, Object tail, Object head, boolean isDirected)

addGraphListener

public void addGraphListener(GraphListener listener)

addNode

public boolean addNode(Object node)

adjacentNodes

public Collection adjacentNodes(Object node, Predicate traverserPredicate)

containsEdge

public boolean containsEdge(Graph.Edge edge)

containsNode

public boolean containsNode(Object node)

createEdge

protected Graph.Edge createEdge(Object object, Object tail, Object head, boolean isDirected, Object edgeState)
Creates a new 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.

degree

public int degree(Object node)

degree

public int degree(Object node, Predicate traverserPredicate)

edgeAdded

protected void edgeAdded(Graph.Edge edge)
Invoked after an edge has been added to this Graph and any GraphListeners have been notified.

edgeAdding

protected void edgeAdding(Graph.Edge edge)
Invoked before an edge has been added to this Graph and any GraphListeners have been notified.

edgeRemoved

protected void edgeRemoved(Graph.Edge edge)
Invoked after an edge has been removed from this Graph and any GraphListeners have been notified.

edgeRemoving

protected void edgeRemoving(Graph.Edge edge)
Invoked before an edge has been removed from this Graph and any GraphListeners have been notified.

edges

public Collection edges(Predicate edgePredicate)

equals

public boolean equals(Object object)

getAdjacentNode

public Object getAdjacentNode(Object node, Predicate traverserPredicate)

getEdge

public Graph.Edge getEdge(Predicate edgePredicate)

getIncidentEdge

public Graph.Edge getIncidentEdge(Object node, Predicate traverserPredicate)

getNode

public Object getNode(Predicate nodePredicate)

hashCode

public int hashCode()

incidentEdges

public Collection incidentEdges(Object node, Predicate traverserPredicate)

nodeAdded

protected void nodeAdded(Object node)
Invoked after a node has been added to this Graph and any GraphListeners have been notified.

nodeAdding

protected void nodeAdding(Object node)
Invoked before a node has been added to this Graph and any GraphListeners have been notified.

nodeRemoved

protected void nodeRemoved(Object node)
Invoked after a node has been removed from this Graph and any GraphListeners have been notified.

nodeRemoving

protected void nodeRemoving(Object node)
Invoked before a node has been removed from this Graph and any GraphListeners have been notified.

nodes

public Collection nodes(Predicate nodePredicate)

removeEdge

public boolean removeEdge(Graph.Edge edge)

removeGraphListener

public void removeGraphListener(GraphListener listener)

removeNode

public boolean removeNode(Object node)

toString

public String toString()

traverser

public Traverser traverser(Object node, Predicate traverserPredicate)
Returns a 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 }

See the Plexus project home, hosted by SourceForge.
Copyright B) 1994-2006, by Phoenix Software Technologists, Inc. and others. All Rights Reserved. Use is subject to license terms.