Package ptolemy.graph

Class DirectedAcyclicGraph

java.lang.Object

ptolemy.graph.Graph

ptolemy.graph.DirectedGraph

ptolemy.graph.DirectedAcyclicGraph

All Implemented Interfaces:

java.lang.Cloneable, CPO<java.lang.Object>

public class DirectedAcyclicGraph
extends DirectedGraph
implements CPO<java.lang.Object>

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$

Author:

Yuhong Xiong, Shuvra S. Bhattacharyya

Pt.AcceptedRating:

Green (kienhuis)

Pt.ProposedRating:

Green (yuhong)

Nested Class Summary

Nested classes/interfaces inherited from interface ptolemy.graph.CPO

CPO.BoundType

Field Summary

Fields inherited from class ptolemy.graph.DirectedGraph

_transitiveClosureAnalysis

Fields inherited from interface ptolemy.graph.CPO

HIGHER, INCOMPARABLE, LOWER, SAME

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
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 void	_initializeAnalyses()	Initialize the list of analyses that are associated with 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.util.Set<java.lang.Object> subset)	Compute the greatest element of a subset.
java.lang.Object	greatestLowerBound(java.lang.Object e1, java.lang.Object e2)	Compute the greatest lower bound (GLB) of two elements.
java.lang.Object	greatestLowerBound(java.util.Set<java.lang.Object> subset)	Compute the greatest lower bound (GLB) of a subset.
boolean	isLattice()	Test if this CPO is a lattice.
java.lang.Object	leastElement(java.util.Set<java.lang.Object> subset)	Compute the least element 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	leastUpperBound(java.util.Set<java.lang.Object> subset)	Compute the least upper bound (LUB) of a subset.
NonLatticeCounterExample	nonLatticeReason()	Return a counterexample reason as to why this graph is not a lattice.
static int	reverseCompareCode(int compareCode)	Return the opposite of the given compare return code, as if the arguments had been given to compare in the reverse order.
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

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<java.lang.Object>

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<java.lang.Object>

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<java.lang.Object>

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.util.Set<java.lang.Object> subset)

Compute the greatest element of a subset.

Specified by:

greatestElement in interface CPO<java.lang.Object>

Parameters:

subset - A set 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<java.lang.Object>

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.util.Set<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<java.lang.Object>

Parameters:

subset - A set 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.

Specified by:

isLattice in interface CPO<java.lang.Object>

Returns:

True if this CPO is a lattice; false otherwise.

leastElement

public java.lang.Object leastElement(java.util.Set<java.lang.Object> subset)

Compute the least element of a subset.

Specified by:

leastElement in interface CPO<java.lang.Object>

Parameters:

subset - A set 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<java.lang.Object>

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.util.Set<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<java.lang.Object>

Parameters:

subset - A set 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.

nonLatticeReason

public NonLatticeCounterExample nonLatticeReason()

Return a counterexample reason as to why this graph is not a lattice. If it is a lattice, return null. First check to see if the graph has a cycle. If it does not, then check to see if all pair combinations of elements in the graph have both a least upper bound and a greatest lower bound. The first time a counterexample is found, return it.

Returns:

A counterexample that demonstrates why this graph is not a lattice, or null if it is.

reverseCompareCode

public static final int reverseCompareCode(int compareCode)

Return the opposite of the given compare return code, as if the arguments had been given to compare in the reverse order.

Parameters:

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

Returns:

The compare code that represents the opposite result from the given compare code.

top

public java.lang.Object top()

Return the top element of this CPO.

Specified by:

top in interface CPO<java.lang.Object>

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<java.lang.Object>

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