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.
Read more about this topic: Directed Acyclic Graph
Famous quotes containing the words causal, temporal and/or structures:
“There is the illusion of time, which is very deep; who has disposed of it? Mor come to the conviction that what seems the succession of thought is only the distribution of wholes into causal series.”
—Ralph Waldo Emerson (1803–1882)
“When once a certain class of people has been placed by the temporal and spiritual authorities outside the ranks of those whose life has value, then nothing comes more naturally to men than murder.”
—Simone Weil (1909–1943)
“The philosopher believes that the value of his philosophy lies in its totality, in its structure: posterity discovers it in the stones with which he built and with which other structures are subsequently built that are frequently better—and so, in the fact that that structure can be demolished and yet still possess value as material.”
—Friedrich Nietzsche (1844–1900)