org.apache.avalon.fortress.util.dag
Class Vertex

java.lang.Object
  org.apache.avalon.fortress.util.dag.Vertex

All Implemented Interfaces:

java.lang.Comparable

public final class Vertex
extends java.lang.Object
implements java.lang.Comparable

Vertex is used to track dependencies and each node in a graph. Typical uses would be to ensure components are started up and torn down in the proper order, or bundles were loaded and unloaded in the proper order, etc.

Version:

CVS $ Revision: 1.1 $

Author:

Avalon Development Team

Field Summary

private java.util.List	m_dependencies List of all direct dependent Vertices.
private java.lang.String	m_name
private java.lang.Object	m_node
private int	m_order
private boolean	m_seen Flag used to keep track of whether or not a given vertex has been seen by the resolveOrder methods.

Constructor Summary

Vertex(java.lang.Object node)
A vertex wraps a node, which can be anything.

Vertex(java.lang.String name, java.lang.Object node)
A vertex wraps a node, which can be anything.

Method Summary

void	addDependency(Vertex v) Add a dependecy to this Vertex.
int	compareTo(java.lang.Object o) Used in the sort algorithm to sort all the Vertices so that they respect the ordinal they were given during the topological sort.
java.util.List	getDependencies() Get the list of dependencies.
java.lang.String	getName() Returns the name of the Vertex.
java.lang.Object	getNode() Get the wrapped node that this Vertex represents.
int	getOrder() Get the ordinal for this vertex.
void	reset() Reset the Vertex so that all the flags and runtime states are set back to the original values.
void	resolveOrder() Recurse through the tree from this vertex assigning an order to each and at the same time checking for any cyclic dependencies.
private int	resolveOrder(java.lang.String path) Recursively searches for cycles by travelling down the dependency lists of this vertex, looking for the start vertex.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

m_name

private final java.lang.String m_name

m_node

private final java.lang.Object m_node

m_order

private int m_order

m_seen

private boolean m_seen

Flag used to keep track of whether or not a given vertex has been seen by the resolveOrder methods.

m_dependencies

private final java.util.List m_dependencies

List of all direct dependent Vertices.

Constructor Detail

Vertex

public Vertex(java.lang.Object node)

A vertex wraps a node, which can be anything.

Parameters:

node - The wrapped node.

Vertex

public Vertex(java.lang.String name,
              java.lang.Object node)

A vertex wraps a node, which can be anything.

Parameters:

name - A name for the node which will be used to produce useful errors.

node - The wrapped node.

Method Detail

reset

public void reset()

Reset the Vertex so that all the flags and runtime states are set back to the original values.

getName

public java.lang.String getName()

Returns the name of the Vertex.

Returns:

The name of the Vertex.

getNode

public java.lang.Object getNode()

Get the wrapped node that this Vertex represents.

Returns:

the node

addDependency

public void addDependency(Vertex v)

Add a dependecy to this Vertex. The Vertex that this one depends on will be marked as referenced and then added to the list of dependencies. The list is checked before the dependency is added.

Parameters:

v - The vertex we depend on.

resolveOrder

public void resolveOrder()
                  throws CyclicDependencyException

Recurse through the tree from this vertex assigning an order to each and at the same time checking for any cyclic dependencies.

Throws:

CyclicDependencyException - If a cyclic dependency is discovered.

resolveOrder

private int resolveOrder(java.lang.String path)
                  throws CyclicDependencyException

Recursively searches for cycles by travelling down the dependency lists of this vertex, looking for the start vertex.

Parameters:

path - The path to the Vertex. It is worth the load as it makes a descriptive error message possible.

Returns:

The highest order of any of the dependent vertices.

Throws:

CyclicDependencyException - If a cyclic dependency is discovered.

getDependencies

public java.util.List getDependencies()

Get the list of dependencies.

Returns:

The list of dependencies.

compareTo

public int compareTo(java.lang.Object o)

Used in the sort algorithm to sort all the Vertices so that they respect the ordinal they were given during the topological sort.

Specified by:

compareTo in interface java.lang.Comparable

Parameters:

o - The other Vertex to compare with

Returns:

-1 if this < o, 0 if this == o, or 1 if this > o

getOrder

public int getOrder()

Get the ordinal for this vertex.

Returns:

the order.