com.phoenixst.plexus
Interface OrientedForest

All Known Subinterfaces:

RootedTree

All Known Implementing Classes:

AbstractOrientedForest, DefaultOrientedForest, DefaultOrientedForestView, DefaultRootedTreeView, DepthFirstForestView, DepthFirstTreeView, FileSystemForest, ForestTreeAdapter, ForestTreeExtension, TrivialOrientedForestView

public interface OrientedForest

A data structure with parent/child relationships. Each node may have at most one adjacent node distinguished as being its "parent", and the data structure should be acyclic under the parent operation. The following are definitions for other terms used here (and elsewhere):

• If node X is the parent of node Y, then we also say that Y is a "child" of X. A node may have multiple children.
• A node with no parent is a "root" node. Every node in the graph is contained in a subgraph with a unique root, which can be found by following the chain of parents until it ends.
• A node with no children is a "leaf". A non-leaf node is an "internal node".
• If node X is reachable through successive applications of the parent operation from node Y, then X is an "ancestor" of Y, and Y is a "descendant" of X. Note that any node is both an ancestor and descendant of itself.
• Two nodes with the same parent are "siblings".
• The length of the path from a given node to its root is its "depth". The depth of a root node is 0.
• The length of the longest path from a given node to a leaf is its "height". The height of a leaf is 0.

The word "oriented" was chosen instead of the more commonly used "directed" because the directedness of the edges need not have any bearing on the parent-child relationships.

Since:

1.0

Version:

$Revision: 1.2 $

Author:

Ray A. Conner

Method Summary

Traverser	childTraverser(Object node) Traverses over the children of the specified node.
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.

Method Detail

getParent

Object getParent(Object node)

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

childTraverser

Traverser childTraverser(Object node)

Traverses over the children of the specified node.

getParentEdge

Graph.Edge getParentEdge(Object node)

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

isForestEdge

boolean isForestEdge(Graph.Edge edge)

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

getParentEndpoint

Object getParentEndpoint(Graph.Edge edge)

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

rootNodes

Collection rootNodes()

Returns the root nodes of this forest.

getRoot

Object getRoot(Object node)

Gets the root of the subgraph containing the specified node.

isLeaf

boolean isLeaf(Object node)

Returns true if the specified node has no children.

isAncestor

boolean isAncestor(Object ancestor,
                   Object descendant)

Returns true if ancestor is actually an ancestor of descendant.

getLeastCommonAncestor

Object getLeastCommonAncestor(Object aNode,
                              Object bNode)

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.

getDepth

int getDepth(Object node)

Gets the depth of the specified node.

getHeight

int getHeight(Object node)

Gets the height of the specified node.