DirectedAcyclicGraph

Last edit August 11, 2009

A DirectedAcyclicGraph is a DirectedGraph with no circuits, often abbreviated DAG.

A circuit is an ordered sequence of N arcs (N > 0), where

the second vertex of the last arc is the first vertex of the first arc, and
for all n such that 2 <= n <= N, the first vertex of the nth arc is the second vertex of the previous one.

More generally, in a DirectedGraph, a path is an ordered sequence of N arcs (N >= 0), where,

if N > 1, for all n such that 2 <= n <= N, the first vertex of the nth arc is the second vertex of the previous one (same as above);
if N = 1, that's a length 1 path, and no particular condition is required;
if N = 0, that's the length 0 path (the null path), and no particular condition is required.

Thus, a circuit is a path that returns to its starting point.

For example, ({A, B}, {(A, B), (B, A)}) and ({A, B, C}, {(A, B), (B, C), (C, A)}) both contain circuits, whereas ({A, B, C}, {(A, B), (B, C), (A, C)}) is acyclic.

NB: Some people use the words "cycle" and "circuit" interchangeably. It's more correct to use "circuit" for a directed path and "cycle" for an undirected chain. (Also note the terminological asymmetry between "circuit" and "acyclic".)

"cyclic" is an adjective where "circuit" is a noun, and the former ultimately derives from Greek whereas the latter comes from Latin, so there are multiple barriers to saying "* acircuit" or even "* acircuitous", although one could say "noncircuitous" (adjective + Latin prefix).

A very common use of DAGs is to represent expressions in a compiler or interpreter. The representation typically begins (conceptually or temporally) as a parse tree or syntax tree, and then recognition of common subexpressions (especially the simple case of multiply-appearing variables) transforms the tree into a DAG.

I don't like the circuit definition because it distinguishes the start vertex. To me, the point of a circuit is that there is no "start point".

Perhaps this could be corrected by as simple a change as "returns to a starting point" rather than "returns to its starting point.

[It should be noted that the choice of the "start point" is arbitrary; the definition of a circuit above is equally valid no matter which point you start on.]

That's what I was hoping would be implied by saying "a" rather than "its".

How about this? (I'll use <- to mean "is an element of")

Given a set of Nodes N and a set of arcs A, where sink(a<-A)<-N, and source(a<-A)<-N, we define a function isConnectedTo(x<-A, y<-A) := sink(x) = source(y) OR (there exists z<=A: isConnectedTo(x, z) AND sink(z)=source(y)) (ie, "is connected to" is transitive); a "cycle" is a minimal set of nodes C such that for all x<-C, for all y<-C, isConnectedTo(x, y).

The WaterCycle can be represented as a Directedgraph:

  W = {V,E}
  V = {Cryosphere(c),Atmosphere(a),Biospher(b),Lithosphere(l),Hydrosphere(h)}
  E = {evaporate(h,a),drain(b,h),absorb(b,l),energize(l,b),transpire(b,a),precipitate(a,b),melt(c,b),sublimate(c,a)}

DifferentialEquations as a basis for a SimulationProgram could be included for each Edge.

Contributors: ChracotheneGrailly, DanielBrockman