Directed acyclic graphs
[Shortest path methods]


Modules

 DAG composition

Enumerations

enum  abstractMixedGraph::TOptDAGSearch {
  abstractMixedGraph::DAG_TOPSORT = 0,
  abstractMixedGraph::DAG_CRITICAL = 1,
  abstractMixedGraph::DAG_SPTREE = 2
}

Functions

TNode abstractDiGraph::TopSort () throw ()
TNode abstractDiGraph::CriticalPath () throw ()
TNode abstractMixedGraph::DAGSearch (TOptDAGSearch opt, const indexSet< TArc > &EligibleArcs, TNode s=NoNode, TNode t=NoNode) throw (ERRange)

Enumeration Type Documentation

enum TOptDAGSearch [inherited]
 

Alternative options for the DAG search procedure.

Enumerator:
DAG_TOPSORT  Determine a topological numbering.
DAG_CRITICAL  Determine a forest of critical paths.
DAG_SPTREE  Determine a shortest path tree or forest.

Function Documentation

TNode CriticalPath (   )  throw () [inherited]
 

Determine a critical path.

Returns:
The end node of the critical path, or NoNode if the graph is not a DAG

TNode DAGSearch (  TOptDAGSearch  opt,
const indexSet< TArc > &  EligibleArcs,
TNode  s = NoNode,
TNode  t = NoNode
)  throw (ERRange) [inherited]
 

Perform a DAG search.

Parameters:
opt The goal of this graph search
EligibleArcs The set of eligible arcs
s For DAG_SPTREE: The source node (optional)
t For DAG_SPTREE: The target node (optional)
Returns:
A node index ranged [0,1,..,n-1]
If the graph is a DAG and opt==DAG_TOPSORT or opt==DAG_SPTREE, the ordinal numbers of a topological numbering are provided by the node colour register. For opt==DAG_SPTREE and opt==DAG_CRITICAL, the distance and the predecessor label registers are assigned.

TNode TopSort (   )  throw () [inherited]
 

Determine a topological numbering.

Returns:
A node on a directed cycle, or NoNode if the graph is a DAG
The ordinal numbers are provided by the node colour register