Просмотр кода страницы DAG (Directed Acyclic Graph)

'''DAG (Directed Acyclic Graph)''' — ''[[бесконтурный орграф]].'' 

A '''[[directed acyclic graph]]''', also called a '''DAG''', is a ''[[directed graph]]'' without ''[[cycle|cycles]]''

The reachability relation in a DAG forms a partial order, and any finite partial order may be represented by a DAG using reachability.
DAGs may also be used to model expressions and basic blocks.


A DAG presentation for an expression identifies the common subexpression of the expression. Like a ''[[syntax tree]]'', an '''[[expression dag]]''' has a [[node]] for every subexpression of the expression; an interior node represents an operator and its children represent its operands. The difference is that a node in a dag representing a common subexpression has more than one ''parent'', in a syntax tree, the common subexpression would be represented as a duplicated subtree.

DAG is a useful data structure for implementing transformations on basic blocks. A DAG representation for a basic block gives a picture of how the value computed by each
statement in a basic block is used in subsequent statements of a block.
A '''[[dag for basic block|dag for a basic block]]''' is a directed acyclic graph with the following labels on nodes.


(1) Leaves are labeled by unique identifiers, either variable names or constants. From the operator applied to a name, we determine whether
the <math>\,l</math>-value or <math>\,r</math>-value of a name is needed; most leaves represent <math>\,r</math>-values. The leaves represent the initial values of names, and we subscript them with <math>\,0</math> to avoid confusion with labels denoting ''current'' values of names as in (3) below.

(2) Interior nodes are labeled by an operator symbol.

(3) Nodes are also optionally given a sequence of identifiers for a label. The intention is that interior nodes represent computed values,
and the identifiers labeling a node are deemed to have that value.

(4) Certain nodes are designated output nodes. These are the nodes whose variables are live on exit from the block; that is, their values may be used later, in another
block of the flow graph.

It is important not to confuse dags with ''[[flow graph|flow graphs]]''. Each node of a flow graph can be represented by a dag, since each node of the
flow graph stands for a basic block.

==Литература==
*Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.