ptolemy.graph
Class DirectedAcyclicGraph

java.lang.Object
  ptolemy.graph.Graph
      ptolemy.graph.DirectedGraph
          ptolemy.graph.DirectedAcyclicGraph

All Implemented Interfaces:

java.lang.Cloneable, 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, a GraphTopologyException 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 57040 2010-01-27 20:52:32Z cxh $

Author:

Yuhong Xiong, Shuvra S. Bhattacharyya

Accepted Rating:

Green (kienhuis)

Proposed Rating:

Green (yuhong)

Field Summary

private java.lang.Object	_bottom
private boolean[][]	_closure
private java.lang.Object	_top
private boolean[][]	_tranClosureTranspose
private TransitiveClosureAnalysis	_transitiveClosureAnalysis

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.
private int	_compareNodeId(int i1, int i2)
protected void	_initializeAnalyses() Initialize the list of analyses that are associated with this graph, and initialize the change counter of the graph.
private java.lang.Object	_leastElementNodeId(int[] ids)
private java.lang.Object	_leastElementShared(java.lang.Object[] subset)
private java.lang.Object	_lubShared(java.lang.Object[] subset)
private java.lang.Object	_lubShared(java.lang.Object e1, java.lang.Object e2)
private java.lang.Object[]	_upSetShared(java.lang.Object e)
private void	_validate()
private void	_validateDual()
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[] weights) Sort the given node weights 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

_connect, _connectedSubGraph, _disconnect, _registerNode, 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, subgraphs, successorEdges, successors, toDirectedAcyclicGraph, topologicalSort, transitiveClosure

Methods inherited from class ptolemy.graph.Graph

_connectEdge, _disconnectEdge, _emptyGraph, _registerChange, _registerEdge, addAnalysis, addEdge, addEdge, addEdge, addEdge, addEdge, addEdges, addGraph, addNode, addNode, addNodes, addNodeWeight, addNodeWeights, changeCount, clone, cloneAs, connectedComponents, containsEdge, containsEdgeWeight, containsNode, containsNodeWeight, edge, edge, edgeCount, edgeLabel, edgeLabel, edges, edges, edges, edgeWeight, equals, hashCode, hidden, hiddenEdgeCount, hiddenEdges, hideEdge, incidentEdgeCount, incidentEdges, neighborEdges, neighbors, node, node, nodeCount, nodeLabel, nodeLabel, nodes, nodes, nodes, nodeWeight, removeEdge, removeNode, restoreEdge, selfLoopEdgeCount, selfLoopEdges, selfLoopEdges, subgraph, subgraph, toString, validateWeight, validateWeight, validateWeight, validateWeight, validEdgeWeight, validNodeWeight, weightArray

Methods inherited from class java.lang.Object

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

Field Detail

_closure

private boolean[][] _closure

_tranClosureTranspose

private boolean[][] _tranClosureTranspose

_transitiveClosureAnalysis

private TransitiveClosureAnalysis _transitiveClosureAnalysis

_bottom

private java.lang.Object _bottom

_top

private java.lang.Object _top

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.

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.

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.

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:

GraphStateException - If the graph is cyclic.

topologicalSort

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

Sort the given node weights in their topological order. In other words, this method returns the specified node weights according to a topological sort of the corresponding graph nodes. 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). The result is unpredictable if the multiple nodes have the same weight (i.e., if the specified weights are not uniquely associated with nodes).

Overrides:

topologicalSort in class DirectedGraph

Parameters:

weights - The given node weights.

Returns:

The weights in their sorted order.

See Also:

DirectedGraph.topologicalSort(Collection)

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:

GraphConstructionException - If the specified nodes are identical.

GraphElementException - If either of the specified nodes is not in the graph.

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

_initializeAnalyses

protected void _initializeAnalyses()

Initialize the list of analyses that are associated with this graph, and initialize the change counter of the graph.

Overrides:

_initializeAnalyses in class DirectedGraph

See Also:

Analysis

_compareNodeId

private int _compareNodeId(int i1,
                           int i2)

_leastElementNodeId

private java.lang.Object _leastElementNodeId(int[] ids)

_leastElementShared

private java.lang.Object _leastElementShared(java.lang.Object[] subset)

_lubShared

private java.lang.Object _lubShared(java.lang.Object e1,
                                    java.lang.Object e2)

_lubShared

private java.lang.Object _lubShared(java.lang.Object[] subset)

_upSetShared

private java.lang.Object[] _upSetShared(java.lang.Object e)

_validate

private void _validate()

_validateDual

private void _validateDual()