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 ''n''th 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 ''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.

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

See also LatticeStructure

CategoryDataStructure