ptolemy.graph
Class DirectedAcyclicGraph

java.lang.Object
  |
  +--ptolemy.graph.Graph
        |
        +--ptolemy.graph.DirectedGraph
              |
              +--ptolemy.graph.DirectedAcyclicGraph

All Implemented Interfaces:

CPO

public class DirectedAcyclicGraph

extends DirectedGraph

implements CPO

A directed acyclic graph (DAG). The graphs constructed by this class cannot have cycles. For performance reasons, this requirement is not checked (except for self-loops) during the construction of the graph (calls to add and addEdge), but is checked when any of the other methods is called for the first time after the addition of nodes or edges. If the graph is cyclic, an InvalidStateException is thrown. The check for cycles is done by computing the transitive closure, so the first operation after a graph change is slower. This class implements the CPO interface since the Hasse diagram of a CPO can be viewed as a DAG. Therefore, this class can be viewed as both a DAG and a finite CPO. In the case of CPO, the node weights are the CPO elements. The CPO does not require the bottom element to exist. The call to bottom returns null if the bottom element does not exist.

NOTE: This class is a starting point for implementing graph algorithms, more methods will be added.

Since:

Ptolemy II 0.2

Version:

$Id: DirectedAcyclicGraph.java,v 1.45.2.1 2002/03/11 17:11:36 cxh Exp $

Author:

Yuhong Xiong, Shuvra S. Bhattacharyya

Fields inherited from class ptolemy.graph.DirectedGraph

_transitiveClosure

Fields inherited from interface ptolemy.graph.CPO

HIGHER, INCOMPARABLE, LOWER, SAME

Constructor Summary

DirectedAcyclicGraph()
Construct an empty DAG.

DirectedAcyclicGraph(int nodeCount)
Construct an empty DAG with enough storage allocated for the specified number of elements.

Method Summary

protected Edge	_addEdge(Node node1, Node node2, boolean weighted, java.lang.Object weight) Create and add an edge with a specified source node, sink node, and optional weight.
protected Graph	_emptyGraph() Return an empty DAG.
protected void	_initializeListeners() Create and register all of the change listeners for this graph, and initialize the change counter of the graph.
java.lang.Object	bottom() Return the bottom element of this CPO.
int	compare(java.lang.Object e1, java.lang.Object e2) Compare two elements in this CPO.
java.lang.Object[]	downSet(java.lang.Object e) Compute the down-set of an element in this CPO.
java.lang.Object	greatestElement(java.lang.Object[] subset) Compute the greatest element of a subset.
java.lang.Object	greatestLowerBound(java.lang.Object[] subset) Compute the greatest lower bound (GLB) of a subset.
java.lang.Object	greatestLowerBound(java.lang.Object e1, java.lang.Object e2) Compute the greatest lower bound (GLB) of two elements.
boolean	isLattice() Test if this CPO is a lattice.
java.lang.Object	leastElement(java.lang.Object[] subset) Compute the least element of a subset.
java.lang.Object	leastUpperBound(java.lang.Object[] subset) Compute the least upper bound (LUB) of a subset.
java.lang.Object	leastUpperBound(java.lang.Object e1, java.lang.Object e2) Compute the least upper bound (LUB) of two elements.
java.lang.Object	top() Return the top element of this CPO.
java.lang.Object[]	topologicalSort() Topological sort the whole graph.
java.lang.Object[]	topologicalSort(java.lang.Object[] objects) Sort the given graph objects in their topological order.
java.lang.Object[]	upSet(java.lang.Object e) Compute the up-set of an element in this CPO.

Methods inherited from class ptolemy.graph.DirectedGraph

_computeTransitiveClosure, _connect, _disconnect, _registerEdge, _registerNode, attemptTopologicalSort, attemptTopologicalSort, backwardReachableNodes, backwardReachableNodes, backwardReachableNodes, backwardReachableNodes, cycleNodeCollection, cycleNodes, edgeExists, edgeExists, inputEdgeCount, inputEdges, isAcyclic, outputEdgeCount, outputEdges, predecessorEdges, predecessors, reachableNodes, reachableNodes, reachableNodes, reachableNodes, sccDecomposition, selfLoopEdgeCount, sinkNodeCount, sinkNodes, sourceNodeCount, sourceNodes, successorEdges, successors

Methods inherited from class ptolemy.graph.Graph

_registerChange, add, addAll, addEdge, addEdge, addEdge, addEdge, addEdge, addListener, addNode, addNode, addNodeWeight, addNodeWeights, changeCount, connectedComponents, contains, containsEdge, containsEdgeWeight, containsNode, containsNodeWeight, description, edge, edge, edgeCount, edgeLabel, edgeLabel, edges, edges, edges, edgeWeight, incidentEdgeCount, incidentEdges, neighborEdges, neighbors, node, node, nodeCount, nodeLabel, nodeLabel, nodes, nodes, nodes, nodeWeight, removeEdge, removeNode, selfLoopEdgeCount, selfLoopEdges, selfLoopEdges, subgraph, subgraph, subgraph, toString, weightArray

Methods inherited from class java.lang.Object

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

Constructor Detail

DirectedAcyclicGraph

public DirectedAcyclicGraph()

Construct an empty DAG.

DirectedAcyclicGraph

public DirectedAcyclicGraph(int nodeCount)

Construct an empty DAG with enough storage allocated for the specified number of elements. Memory management is more efficient with this constructor if the number of elements is known.

Parameters:

nodeCount - The number of elements.

Method Detail

bottom

public java.lang.Object bottom()

Return the bottom element of this CPO.

Specified by:

bottom in interface CPO

Returns:

An Object representing the bottom element, or null if the bottom does not exist.

compare

public int compare(java.lang.Object e1,
                   java.lang.Object e2)

Compare two elements in this CPO.

Specified by:

compare in interface CPO

Parameters:

e1 - An Object representing a CPO element.

e2 - An Object representing a CPO element.

Returns:

One of CPO.LOWER, CPO.SAME, CPO.HIGHER, CPO.INCOMPARABLE.

Throws:

java.lang.IllegalArgumentException - If at least one of the specified Objects is not an element of this CPO.

downSet

public java.lang.Object[] downSet(java.lang.Object e)

Compute the down-set of an element in this CPO.

Specified by:

downSet in interface CPO

Parameters:

e - An Object representing an element in this CPO.

Returns:

An array of of Objects representing the elements in the down-set of the specified element.

Throws:

java.lang.IllegalArgumentException - If the specified Object is not an element in this CPO.

greatestLowerBound

public java.lang.Object greatestLowerBound(java.lang.Object e1,
                                           java.lang.Object e2)

Compute the greatest lower bound (GLB) of two elements.

Specified by:

greatestLowerBound in interface CPO

Parameters:

e1 - An Object representing an element in this CPO.

e2 - An Object representing an element in this CPO.

Returns:

An Object representing the GLB of the two specified elements, or null if the GLB does not exist.

Throws:

java.lang.IllegalArgumentException - If at least one of the specified Objects is not an element of this CPO.

greatestLowerBound

public java.lang.Object greatestLowerBound(java.lang.Object[] subset)

Compute the greatest lower bound (GLB) of a subset. If the specified array representing the subset has size 0, the subset is considered empty, in which case the top element of this CPO is returned, if it exists. If the subset is empty and the top does not exist, null is returned.

Specified by:

greatestLowerBound in interface CPO

Parameters:

subset - An array of Objects representing the subset.

Returns:

An Object representing the GLB of the subset, or null if the GLB does not exist.

Throws:

java.lang.IllegalArgumentException - If at least one Object in the specified array is not an element of this CPO.

greatestElement

public java.lang.Object greatestElement(java.lang.Object[] subset)

Compute the greatest element of a subset.

Specified by:

greatestElement in interface CPO

Parameters:

subset - An array of Objects representing the subset.

Returns:

An Object representing the greatest element of the subset, or null if the greatest element does not exist.

Throws:

java.lang.IllegalArgumentException - If at least one Object in the specified array is not an element of this CPO.

isLattice

public boolean isLattice()

Test if this CPO is a lattice. By a theorem in Davey and Priestley, only the LUB or the GLB need to be checked, but not both. The implementation tests the existence of the LUB of any pair of elements, as well as the existence of the bottom and top elements. The complexity is O(|N|*|N|) where N for elements, and an individual computation is the LUB of two elements.

Specified by:

isLattice in interface CPO

Returns:

True if this CPO is a lattice; false otherwise.

leastElement

public java.lang.Object leastElement(java.lang.Object[] subset)

Compute the least element of a subset.

Specified by:

leastElement in interface CPO

Parameters:

subset - An array of Objects representing the subset.

Returns:

An Object representing the least element of the subset, or null if the least element does not exist.

Throws:

java.lang.IllegalArgumentException - If at least one Object in the specified array is not an element of this CPO.

leastUpperBound

public java.lang.Object leastUpperBound(java.lang.Object e1,
                                        java.lang.Object e2)

Compute the least upper bound (LUB) of two elements.

Specified by:

leastUpperBound in interface CPO

Parameters:

e1 - An Object representing an element in this CPO.

e2 - An Object representing element in this CPO.

Returns:

An Object representing the LUB of the two specified elements, or null if the LUB does not exist.

Throws:

java.lang.IllegalArgumentException - If at least one of the specified Objects is not an element of this CPO.

leastUpperBound

public java.lang.Object leastUpperBound(java.lang.Object[] subset)

Compute the least upper bound (LUB) of a subset. If the specified array representing the subset has size 0, the subset is considered empty, in which case the bottom element of this CPO is returned, if it exists. If the subset is empty and the bottom does not exist, null is returned.

Specified by:

leastUpperBound in interface CPO

Parameters:

subset - An array of Objects representing the subset.

Returns:

An Object representing the LUB of the subset, or null if the LUB does not exist.

Throws:

java.lang.IllegalArgumentException - If at least one Object in the specified array is not an element of this CPO.

top

public java.lang.Object top()

Return the top element of this CPO.

Specified by:

top in interface CPO

Returns:

An Object representing the top element, or null if the top does not exist.

topologicalSort

public java.lang.Object[] topologicalSort()

Topological sort the whole graph. The implementation uses the method of A. B. Kahn: "Topological Sorting of Large Networks," Communications of the ACM, Vol. 5, 558-562, 1962. It has complexity O(|N|+|E|), where N for nodes and E for edges,

Returns:

An array of Objects representing the nodes sorted according to the topology.

Throws:

InvalidStateException - If the graph is cyclic.

topologicalSort

public java.lang.Object[] topologicalSort(java.lang.Object[] objects)

Sort the given graph objects in their topological order. This method use the transitive closure matrix. Since generally the graph is checked for cyclicity before this method is called, the use of the transitive closure matrix should not add any overhead. A bubble sort is used for the internal implementation, so the complexity is O(n^2).

Returns:

The objects in their sorted order.

upSet

public java.lang.Object[] upSet(java.lang.Object e)

Compute the up-set of an element in this CPO.

Specified by:

upSet in interface CPO

Parameters:

e - An Object representing an element in this CPO.

Returns:

An array of Objects representing the elements in the up-set of the specified element.

Throws:

java.lang.IllegalArgumentException - If the specified Object is not an element of this CPO.

_addEdge

protected Edge _addEdge(Node node1,
                        Node node2,
                        boolean weighted,
                        java.lang.Object weight)

Create and add an edge with a specified source node, sink node, and optional weight. The third parameter specifies whether the edge is to be weighted, and the fourth parameter is the weight that is to be applied if the edge is weighted. Returns the edge that is added.

Overrides:

_addEdge in class Graph

Parameters:

node1 - The source node of the edge.

node2 - The sink node of the edge.

weighted - True if the edge is to be weighted.

weight - The weight that is to be applied if the edge is to be weighted.

Returns:

The edge.

Throws:

java.lang.IllegalArgumentException - If either of the specified nodes is not in the graph, or if the specified nodes are identical.

java.lang.NullPointerException - If the edge is to be weighted, but the specified weight is null.

_emptyGraph

protected Graph _emptyGraph()

Return an empty DAG.

Overrides:

_emptyGraph in class DirectedGraph

Returns:

An empty DAG.

_initializeListeners

protected void _initializeListeners()

Create and register all of the change listeners for this graph, and initialize the change counter of the graph.

Overrides:

_initializeListeners in class DirectedGraph