可以将有向图分解为列表吗？

Question

这更像是一个理论问题，但是对于 DAG 是否可以将其压缩为一个操作列表？或者这是一个数据结构，不能按照类似这样的顺序分解成一个平面列表：

STEPS = [
    filter A to country = 'US',
    (join A to B on A.id=B.id) AS c,
    filter C to...
]

是否可以构建一个不丢失信息就无法分解的DAG？

Answer 1

是的，有向无环图 (DAG) 可以压缩成有序操作列表，if ，其实DAG代表的是数据流经操作。即赋值语句和函数调用的有序列表可以表示为DAG，反之亦然。

上述示例的 DAG 可能看起来像

+-----+     +-------------+
|     |  A  |   filter I1 | A'
|  A  |-----|1  to country|---+                    
|     |     |       ='US' |   |                                           
+-----+     +-------------+   |  +--------------+   +-----------+   +----------+
                              +--|1  join I1 to | C |   filter  | C'|   Result |
                                 |   I2 on I1.id|---|1  I1 to...|---|1    = I1 |
                              +--|2      = I2.id|   |           |   |          |
                  +-------+   |  +--------------+   +------- ---+   +----------+
                  |       | B |                                  
                  |   B   |---+
                  |       |
                  +-------+

或者，"list of operations" 可以被认为是嵌套函数调用，从嵌套最深到嵌套最不深进行评估。例如，

Result = Fn3( Fn2( Fn1(A), B ) ).

DAG是一样的，这里重画了，没有显示中间变量，简化了函数名。

+-----+     +-------------+
|     |     |             |
|  A  |-----|1    Fn1     |---+                    
|     |     |             |   |                                        
+-----+     +-------------+   |  +--------------+   +-----------+   +----------+
                              +--|1             |   |           |   |          |
                                 |      Fn2     |---|1   Fn3    |---|1  Result |
                              +--|2             |   |           |   |          |
                  +-------+   |  +--------------+   +------- ---+   +----------+
                  |       |   |                                  
                  |   B   |---+
                  |       |
                  +-------+

我不知道在从 DAG 分解到 "list of operations" 时信息会丢失的任何情况。两种形式是等价的

如何构造 DAG 来表示操作列表的实际示例可以在 IEC 61131-3:2013 中找到，其中 "specifies syntax and semantics of programming languages for programmable controllers..." 该标准将 DAG 称为网络，定义为 "a maximal set of interconnected graphic elements"（在部分有序集的上下文中）并提出评估规则，包括 "No element of a network shall be evaluated until the states of all of its inputs have been evaluated." 该规则为操作顺序提供基础。

可以将有向图分解为列表吗？

Possible to decompose a directed-graph into a list?

etl

graph

directed-acyclic-graphs