byucc.jhdl.synth.graph
Class DAG

java.lang.Object
  byucc.jhdl.synth.graph.NamedObject
      byucc.jhdl.synth.graph.Graph
          byucc.jhdl.synth.graph.DAG

All Implemented Interfaces:

Nameable

Direct Known Subclasses:

DataFlowGraph

public class DAG

extends Graph

A directed Acyclic Graph (DAG).

Author:

Mike Wirthlin

Field Summary

protected boolean

sorted This member indicates whether the structure of the DAG has been verified.

Fields inherited from class byucc.jhdl.synth.graph.Graph

printNum, vertexVector

Fields inherited from class byucc.jhdl.synth.graph.NamedObject

name

Constructor Summary

DAG()

DAG(java.lang.String name)

Method Summary

Edge	addEdge(Edge edge) Adds an Edge to the graph using an existing Edge object.
boolean	isSorted() Is this DAG sorted?
protected static void	localVisit(Graph g, Vertex v, VertexVector topo_sort)
void	topologicalSort() Perform a topological sort on the vertices in this DAG if necessary.
static VertexVector	topologicalSort(Graph g) The purpose of this method is to perform a sort on the vertices and validate that this is indeed a DAG.

Methods inherited from class byucc.jhdl.synth.graph.Graph

addEdge, addVertex, addVertex, getEdge, getEdges, getPrintWriter, getVertices, hasEdge, hasEdge, hasVertex, mergeVertices, newEdge, newVertex, printGraph, printGraph, printGraph, printGraph, removeEdge, removeEdge, removeVertex, resetVisited, setEdgeProperty, setVertexProperty, toDot, toDot, toString

Methods inherited from class byucc.jhdl.synth.graph.NamedObject

getName, setName

Methods inherited from class java.lang.Object

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

Field Detail

sorted

protected boolean sorted

This member indicates whether the structure of the DAG has been verified. Any time an edge is added to the graph, this flag is set to false. Whenever the DAG is succesfully sorted it is set to true.

Constructor Detail

DAG

public DAG()

DAG

public DAG(java.lang.String name)

Method Detail

isSorted

public boolean isSorted()

Is this DAG sorted?

Returns:

true if this DAG is a valid DAG and is sorted, false otherwise.

addEdge

public Edge addEdge(Edge edge)

Adds an Edge to the graph using an existing Edge object. DAG overrides Graph.addEdge so that sorted will be set to false whenever an edge is added.

Overrides:

addEdge in class Graph

Parameters:

edge - A valid edge object with tail and head Vertex objects that already exist in the graph.

Returns:

The edge created in the graph, (the same edge that was passed in).

topologicalSort

public void topologicalSort()

Perform a topological sort on the vertices in this DAG if necessary.

topologicalSort

public static VertexVector topologicalSort(Graph g)

The purpose of this method is to perform a sort on the vertices and validate that this is indeed a DAG. This method should not necessarily be called every time a vertex/edge is accessed.

localVisit

protected static void localVisit(Graph g,
                                 Vertex v,
                                 VertexVector topo_sort)