Аноним

DAG (Directed Acyclic Graph): различия между версиями

Материал из WEGA
нет описания правки
(Новая страница: «'''DAG (Directed Acyclic Graph)''' --- бесконтурный орграф. A '''directed acyclic graph''', also called a '''DAG''', is a ''directed graph''witho…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''DAG (Directed Acyclic Graph)''' --- бесконтурный орграф.  
'''DAG (Directed Acyclic Graph)''' — ''[[бесконтурный орграф]].''


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


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




A DAG presentation for an expression identifies the common
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.
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
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
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.
statement in a basic block is used in subsequent statements of a block.
A '''dag for a basic block''' is a directed acyclic graph with the
A '''[[dag for basic block|dag for a basic block]]''' is a directed acyclic graph with the following labels on nodes.
following labels on nodes.




(1) Leaves are labeled by unique identifiers, either variable names
(1) Leaves are labeled by unique identifiers, either variable names or constants. From the operator applied to a name, we determine whether
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.
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.
(2) Interior nodes are labeled by an operator symbol.


(3) Nodes are also optionally given a sequence of identifiers for
(3) Nodes are also optionally given a sequence of identifiers for a label. The intention is that interior nodes represent computed values,
a label. The intention is that interior nodes represent computed values,
and the identifiers labeling a node are deemed to have that value.
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
(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
live on exit from the block; that is, their values may be used later, in another
block of the flow graph.
block of the flow graph.


It is important not to confuse dags with ''flow graphs''. Each node
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
of a flow graph can be represented by a dag, since each node of the
flow graph stands for a basic block.
flow graph stands for a basic block.
==Литература==
*Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.