com.phoenixst.plexus

Class DefaultOrientedForest

java.lang.Object

com.phoenixst.plexus.DefaultGraph

com.phoenixst.plexus.DefaultOrientedForest

All Implemented Interfaces:

Graph, ObservableGraph, OrientedForest, Serializable

public class DefaultOrientedForest
extends DefaultGraph
implements OrientedForest

A default implementation of the Graph and OrientedForest interfaces.

Since:

1.0

Version:

$Revision: 1.21 $

Author:

Ray A. Conner

See Also:

Serialized Form

Nested Class Summary

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

Graph.Edge

Constructor Summary

Constructors

Constructor and Description
DefaultOrientedForest() Creates a new DefaultOrientedForest.
DefaultOrientedForest(Graph graph) Creates a new DefaultOrientedForest which is a copy of the specified Graph.

Method Summary

Methods

Modifier and Type	Method and Description
Graph.Edge	addEdge(Object object, Object tail, Object head, boolean isDirected) Adds the specified edge to the Graph (optional operation).
Traverser	childTraverser(Object node) Traverses over the children of the specified node.
protected Graph.Edge	createEdge(Object object, Object tail, Object head, boolean isDirected, Object edgeState) Creates a new Graph.Edge.
int	getDepth(Object node) Gets the depth of the specified node.
int	getHeight(Object node) Gets the height of the specified node.
Object	getLeastCommonAncestor(Object aNode, Object bNode) Returns the least common ancestor of the specified nodes, or null if none exists.
Object	getParent(Object node) Gets the parent of the specified node, or null if it doesn't have one.
Graph.Edge	getParentEdge(Object node) Gets the parent Edge of the specified node, or null if it doesn't have one.
Object	getParentEndpoint(Graph.Edge edge) Returns the parent endpoint of the specified forest Edge.
Object	getRoot(Object node) Gets the root of the subgraph containing the specified node.
boolean	isAncestor(Object ancestor, Object descendant) Returns true if ancestor is actually an ancestor of descendant.
boolean	isForestEdge(Graph.Edge edge) Gets whether or not the specified Edge is a forest edge.
boolean	isLeaf(Object node) Returns true if the specified node has no children.
Collection	rootNodes() Returns the root nodes of this forest.
Graph.Edge	setParent(Object object, Object tail, Object head, boolean isDirected, Object parent) Adds a new forest Edge.

Methods inherited from class com.phoenixst.plexus.DefaultGraph

addEdge, addGraphListener, addNode, adjacentNodes, containsEdge, containsNode, degree, degree, edgeAdded, edgeAdding, edgeRemoved, edgeRemoving, edges, equals, getAdjacentNode, getEdge, getIncidentEdge, getNode, hashCode, incidentEdges, nodeAdded, nodeAdding, nodeRemoved, nodeRemoving, nodes, removeEdge, removeGraphListener, removeNode, toString, traverser

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

DefaultOrientedForest

public DefaultOrientedForest()

Creates a new DefaultOrientedForest.

DefaultOrientedForest

public DefaultOrientedForest(Graph graph)

Creates a new DefaultOrientedForest which is a copy of the specified Graph.

Method Detail

createEdge

protected Graph.Edge createEdge(Object object,
                    Object tail,
                    Object head,
                    boolean isDirected,
                    Object edgeState)

Description copied from class: DefaultGraph

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.

Overrides:

createEdge in class DefaultGraph

addEdge

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

Description copied from interface: Graph

Adds the specified edge to the 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.

Specified by:

addEdge in interface Graph

Overrides:

addEdge in class DefaultGraph

Parameters:

object - the user-defined 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.

Returns:

the newly created 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.

getParent

public Object getParent(Object node)

Description copied from interface: OrientedForest

Gets the parent of the specified node, or null if it doesn't have one. If null is a valid node, then OrientedForest.getParentEdge(java.lang.Object) must be used to distinguish the two cases.

Specified by:

getParent in interface OrientedForest

childTraverser

public Traverser childTraverser(Object node)

Description copied from interface: OrientedForest

Traverses over the children of the specified node.

Specified by:

childTraverser in interface OrientedForest

getParentEdge

public Graph.Edge getParentEdge(Object node)

Description copied from interface: OrientedForest

Gets the parent Edge of the specified node, or null if it doesn't have one.

Specified by:

getParentEdge in interface OrientedForest

isForestEdge

public boolean isForestEdge(Graph.Edge edge)

Description copied from interface: OrientedForest

Gets whether or not the specified Edge is a forest edge.

Specified by:

isForestEdge in interface OrientedForest

getParentEndpoint

public Object getParentEndpoint(Graph.Edge edge)

Description copied from interface: OrientedForest

Returns the parent endpoint of the specified forest Edge. If the specified Edge is not a forest edge, throws an IllegalArgumentException.

Specified by:

getParentEndpoint in interface OrientedForest

rootNodes

public Collection rootNodes()

Description copied from interface: OrientedForest

Returns the root nodes of this forest.

Specified by:

rootNodes in interface OrientedForest

getRoot

public Object getRoot(Object node)

Description copied from interface: OrientedForest

Gets the root of the subgraph containing the specified node.

Specified by:

getRoot in interface OrientedForest

isLeaf

public boolean isLeaf(Object node)

Description copied from interface: OrientedForest

Returns true if the specified node has no children.

Specified by:

isLeaf in interface OrientedForest

isAncestor

public boolean isAncestor(Object ancestor,
                 Object descendant)

Description copied from interface: OrientedForest

Returns true if ancestor is actually an ancestor of descendant.

Specified by:

isAncestor in interface OrientedForest

getLeastCommonAncestor

public Object getLeastCommonAncestor(Object aNode,
                            Object bNode)

Description copied from interface: OrientedForest

Returns the least common ancestor of the specified nodes, or null if none exists. If null is a valid node, then some other method must be used to distinguish the two cases.

Specified by:

getLeastCommonAncestor in interface OrientedForest

getDepth

public int getDepth(Object node)

Description copied from interface: OrientedForest

Gets the depth of the specified node.

Specified by:

getDepth in interface OrientedForest

getHeight

public int getHeight(Object node)

Description copied from interface: OrientedForest

Gets the height of the specified node.

Specified by:

getHeight in interface OrientedForest

setParent

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

Adds a new forest Edge. The specified parent must be one of the specified endpoints. If the child endpoint already has a parent edge, it will be removed.