Directed Acyclic Graph - Causal and Temporal Structures

Causal and Temporal Structures

Graphs that have vertices representing events, and edges representing causal relations between events, are often acyclic. For instance, a Bayesian network represents a system of probabilistic events as nodes in a directed acyclic graph, in which the likelihood of an event may be calculated from the likelihoods of its predecessors in the DAG. In this context, the moral graph of a DAG is the undirected graph created by adding an (undirected) edge between all parents of the same node (sometimes called marrying), and then replacing all directed edges by undirected edges.

Another type of graph with a similar causal structure is an influence diagram, the nodes of which represent either decisions to be made or unknown information, and the edges of which represent causal influences from one node to another. In epidemiology, for instance, these diagrams are often used to estimate the expected value of different choices for intervention.

Family trees may also be seen as directed acyclic graphs, with a vertex for each family member and an edge for each parent-child relationship. Despite the name, these graphs are not necessarily trees, because of the possibility of marriages between distant relatives, but the time ordering of births (a parent's birthday is always prior to their child's birthday) causes these graphs to be acyclic. For the same reason, the version history of a distributed revision control system generally has the structure of a directed acyclic graph, in which there is a vertex for each revision and an edge connecting pairs of revisions that were directly derived from each other.