directed acyclic graph (DAG) - help

Blayz

Well-Known Member
Aug 1, 2007
3,367
231
59
Singapore
✟4,827.00
Faith
Atheist
Marital Status
Married
What do you need to know? a graph consists of a set of nodes (usually represented by circles) connected by edges (represented by lines). Directed means that you can only travel in 1 direction along an edge. Acyclic means that there are no loops in the graph.

An evolutionary tree is a DAG, as is the Btree structure that computer hard drives use for storage.

DAGs are good because it is easy to build search and traversal routines, usually using recursion, and they grow in height logarithmically with data increase.
 
Upvote 0

Pesto

Senior Member
Sep 19, 2006
957
27
✟16,297.00
Faith
Atheist
Marital Status
Single
To go back to the very basics, a graph is made up of "nodes" and "edges".

If you want to draw a graph on a piece of paper, a node would be a dot or a circle. An edge would be a line connecting two nodes.

These pictures are all graphs. Notice, they're all just dots connected by lines.

Directed graphs are just graphs where instead of dots connected by lines, you have dots connected by arrows. You're correct in saying that a flow chart is like a graph. In fact, a flow chart is a graph, and a directed graph, to boot.

In a flow chart, actions and decisions are represented by the various shapes. These are the nodes of the graph. You then have arrows that lead you from one action to the next, to the next, to the next. These arrows are the edges.

Now, to explain directed acyclic graphs. Acyclic just means there are no cycles or loops in the graph. That means that no matter where you start on the directed graph, so long as you only follow the arrows, you will never pass over the same node twice.

Let me give you an example of an everyday process that is not acyclic

1. Wash
2. Rinse
3. Repeat

Notice the word, "repeat." That means "go back to step 1". This means do these steps in this order 1 -> 2 -> 3 -> 1 -> 2. That means there is a cycle in this graph. There is a way to leave node 1 and eventually return by following the edges of the graph.

An example of a process that could be modeled using a DAG might be a tax form, like a 1040. These are formatted to follow in a very logical way. You simply do all the steps in order. Sometimes you will skip a step here or there, but you never go back and repeat a step.
 
Upvote 0

GrowingSmaller

Muslm Humanist
Apr 18, 2010
7,421
345
✟49,085.00
Country
United Kingdom
Faith
Humanist
Marital Status
Private
Awesome explanation Pesto. Thanks for your simplification. I imagine that they DAG might be used in philosophy, one mapping theism and the other naturalism. The point might be to show how the "nodes" of the present world could be arrived at in a simpler manner using naturalistic "edges" than using both natural and non-natural edges as theism in the form of God directing natural laws, instead of there simply being independent natural laws, implies. So, Occam's razor could be restated in this context as an appeal for the simplest causal graph which models the phenomena in question. What do you think?
 
Upvote 0