A DirectedAcyclicGraph is a DirectedGraph with no circuits, often abbreviated DAG.
A *circuit* is an ordered sequence of *N* arcs (*N* > 0), where
*path* is an ordered sequence of *N* arcs (*N* >= 0), where,
*({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:

Contributors: ChracotheneGrailly, DanielBrockman See also LatticeStructure CategoryDataStructure

- 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*n*th arc is the second vertex of the previous one.

- if
*N*> 1, for all*n*such that 2 <=*n*<= N, the first vertex of the*n*th 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.

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.

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

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 See also LatticeStructure CategoryDataStructure

EditText of this page (last edited August 11, 2009) or FindPage with title or text search