为什么依赖图不表示为双向无环图？
Why are dependency graphs not represented as bi-directional acyclic graphs?
我知道依赖图（比如在安装过程中找出哪个包依赖于哪个包）可以表示为有向无环图。
a
|--> b
| |--> d
| `--> e
| |
| |
`--> c <--'
例如上图表示如下。
- a 取决于 b、c、d、e
- b 取决于 d、e、c
- c 不依赖任何东西
- d 不依赖于任何东西
- e 取决于 c
这张图可以帮助我们回答某个包在线性时间内依赖什么，即 O(n)，其中 n 是图中包和边的总数。示例：a 依赖于哪些包？结果是：b,c,d,e.
它可以帮助我们回答简单的问题，比如某个包在常数时间内立即依赖什么。示例：a 直接依赖于哪些包？结果为：b,c.
但它不能回答一个简单的问题，比如什么在常数时间内立即依赖于某个包。示例：哪些包直接依赖于 c？结果是：a 和 e。要回答这个简单的问题似乎需要对图进行完整搜索，因此需要线性时间。如果每个子顶点都保留到其父顶点的反向链接，同时仍保持子顶点与父顶点之间的区别，则可以改进这一点。
如果我们引入从每个子顶点到其父顶点的反向链接，它就变成了一个双向无环图，它似乎简化了许多图搜索算法。
我有以下问题。
- 这种依赖关系图有正式名称吗？
- 为什么我们在计算理论的研究中很少见到双向无环图？
- 依赖图的实际实现中是否使用了这种双向图？例子？
如果您添加没有语义意义且仅加速 "who refers to me" 搜索的反向链接，那仍然是 DAG。同样，搜索树中的父链接不会将树变成搜索 "graphs"。它是一个没有语义或数学意义的实现细节。因此不单独研究（顶多在讨论复杂性的时候顺便提一下）。
此外，人们对边缘的走向很灵活（依赖 -> 用户或用户 -> 依赖），两者都根据需要使用。我想不出有多少用例在同一张图中需要两者。即便如此，在需要时仅反转整个图的边（单个 O(n) 操作）可能更有利可图。
由于这些原因，这种优化通常不会被赋予单独的名称。它只是 "a DAG"，一个“（带后边）”如果需要澄清的话。
您在这里谈论的第一件事（当 a->b 和 b->c 时生成所有边，如 a->c）称为 a transitive closure。它本身是有用的、有趣的和研究过的。然而，显式存储所有这些边将导致图所需的存储 space 的（可能是二次的）爆炸，因为在具有 |V| 个节点的完整图中，您有 O(|V|2) 边。所以这是 space 和时间复杂度之间的 trade-off：如果你存储所有（前向）边，你可以更快地（向前）遍历图形，在你观察到的恒定时间内，但你付出存储价格。
虽然您没有问这个问题，但我要指出的是，显式存储传递闭包对于依赖图可能是不可取的。以包管理器为例：您希望它快速找出直接依赖项，以便检查它们是否已安装，如果未安装，可能会将缺失的依赖项添加到安装多个包的事务中。但是，启用对包的所有（直接和间接）依赖项的恒定时间访问在这种情况下似乎并不是特别有用，因为大多数间接依赖项无论如何都可能得到满足。您只会得到一个更大的列表来检查，并且可能会得出结论，大多数都已安装。
您正在谈论的另一件事，即每条边都反转的图形，称为 transpose graph. Note that you need to [bi]color the edges (use differently named member pointer/references) if you store both the "direct" and the transpose graph in the same data structure. Storing them together this way is rather trivial so I guess that's why you don't see much mention of it. Some graph algorithm works/books do assume such a representation for directed graphs, i.e. that both the incoming and outgoing edges are stored in separate (doubly linked) lists for each vertex. Although many (introductory) textbooks indeed don't talk about it (presumably in order to keep their presentation simple), this representation (i.e. with both incoming and outgoing lists) is used in practice, for example in LEDA. Here's a slide from a LEDA presentation，详细说明了它们的静态（即假设固定的）图形数据结构；动态的将有 doubly-linked 列表而不是数组。我包括单向 ("directed") 和它们的 "bidirectional" 表示以便于比较：
Boost 具有类似的功能，尽管它只是对其 adjacency list implementation:
的一个调整（称为 bidirectionalS）
The bidirectionalS selector specifies that the graph will provide the in_edges() function as well as the out_edges() function. This imposes twice as much space overhead per edge, which is why in_edges() is optional.
请记住，因为您可以区分两组边缘（在 LEDA 的情况下通过 "first in" 和 "first out" 或 in_edges() 和 out_edges 在提升的情况下）你真正拥有的是数学上的 disjoint union of a directed graph with its transpose. If you lose the distinction/color between the two sets of edges (pointers), what you get is sometimes called a bidirected graph, although the term (like alas many in graph theory) is unfortunately overloaded. And if you had hopes that LEDA's term bidirectional graph is somehow standardized with their meaning, it's actually more likely to mean the same thing as bidirected graph to theorists.
总结一下我到目前为止的回答：
我不认为像这样存储的依赖图有一个名称，但对于一般双向表示的图来说是一个合理的名称，不幸的是，它不会在几个软件包。双向（或双向）图是一个更广泛的术语，但大多数理论家可能会认为你的意思是你不能再分辨出两组边之间的区别（即他们会假设你的意思是并集而不是与转置的不相交并集图。）
它似乎主要是在实际实现环境（如 LEDA 或 boost）中讨论的一个方面，所以理论和介绍书籍似乎不太关心它。
至于包存储库 (3) 的实际表示，您似乎忽略了大多数（据我所知）将存储 AND、OR 和 NOT 约束以额外处理备选方案和冲突。您只能像我们上面讨论的那样使用依赖图处理 AND 。一旦你添加了这些额外的 OR & NOT 特征，你就会更难解决 (NP-complete) SAT problems just to install something; see the Opium paper (2007) for a discussion; for a more recent one (2010) see the Apt-pbo paper。所以 constant-time 反向依赖 look-ups 相比之下开始显得微不足道了。但要真正回答你的问题：
- 我查看了 apt 源代码，它确实将反向依赖项单独存储在它的缓存中（你 query with
apt-cache). For each package (pkgCache::Package defined in pkgcache.h) there's a RevDepends linked list and apt updates it every time you install or remove something: in depcache.cc:pkgDepCache::Update 它有 for 循环（除其他外）Update(P.ParentPkg().RevDependsList());。
我知道依赖图（比如在安装过程中找出哪个包依赖于哪个包）可以表示为有向无环图。
a
|--> b
| |--> d
| `--> e
| |
| |
`--> c <--'
例如上图表示如下。
- a 取决于 b、c、d、e
- b 取决于 d、e、c
- c 不依赖任何东西
- d 不依赖于任何东西
- e 取决于 c
这张图可以帮助我们回答某个包在线性时间内依赖什么，即 O(n)，其中 n 是图中包和边的总数。示例：a 依赖于哪些包？结果是：b,c,d,e.
它可以帮助我们回答简单的问题，比如某个包在常数时间内立即依赖什么。示例：a 直接依赖于哪些包？结果为：b,c.
但它不能回答一个简单的问题，比如什么在常数时间内立即依赖于某个包。示例：哪些包直接依赖于 c？结果是：a 和 e。要回答这个简单的问题似乎需要对图进行完整搜索，因此需要线性时间。如果每个子顶点都保留到其父顶点的反向链接，同时仍保持子顶点与父顶点之间的区别，则可以改进这一点。
如果我们引入从每个子顶点到其父顶点的反向链接，它就变成了一个双向无环图，它似乎简化了许多图搜索算法。
我有以下问题。
- 这种依赖关系图有正式名称吗？
- 为什么我们在计算理论的研究中很少见到双向无环图？
- 依赖图的实际实现中是否使用了这种双向图？例子？
如果您添加没有语义意义且仅加速 "who refers to me" 搜索的反向链接，那仍然是 DAG。同样，搜索树中的父链接不会将树变成搜索 "graphs"。它是一个没有语义或数学意义的实现细节。因此不单独研究（顶多在讨论复杂性的时候顺便提一下）。
此外，人们对边缘的走向很灵活（依赖 -> 用户或用户 -> 依赖），两者都根据需要使用。我想不出有多少用例在同一张图中需要两者。即便如此，在需要时仅反转整个图的边（单个 O(n) 操作）可能更有利可图。
由于这些原因，这种优化通常不会被赋予单独的名称。它只是 "a DAG"，一个“（带后边）”如果需要澄清的话。
您在这里谈论的第一件事（当 a->b 和 b->c 时生成所有边，如 a->c）称为 a transitive closure。它本身是有用的、有趣的和研究过的。然而，显式存储所有这些边将导致图所需的存储 space 的（可能是二次的）爆炸，因为在具有 |V| 个节点的完整图中，您有 O(|V|2) 边。所以这是 space 和时间复杂度之间的 trade-off：如果你存储所有（前向）边，你可以更快地（向前）遍历图形，在你观察到的恒定时间内，但你付出存储价格。
虽然您没有问这个问题，但我要指出的是，显式存储传递闭包对于依赖图可能是不可取的。以包管理器为例：您希望它快速找出直接依赖项，以便检查它们是否已安装，如果未安装，可能会将缺失的依赖项添加到安装多个包的事务中。但是，启用对包的所有（直接和间接）依赖项的恒定时间访问在这种情况下似乎并不是特别有用，因为大多数间接依赖项无论如何都可能得到满足。您只会得到一个更大的列表来检查，并且可能会得出结论，大多数都已安装。
您正在谈论的另一件事，即每条边都反转的图形，称为 transpose graph. Note that you need to [bi]color the edges (use differently named member pointer/references) if you store both the "direct" and the transpose graph in the same data structure. Storing them together this way is rather trivial so I guess that's why you don't see much mention of it. Some graph algorithm works/books do assume such a representation for directed graphs, i.e. that both the incoming and outgoing edges are stored in separate (doubly linked) lists for each vertex. Although many (introductory) textbooks indeed don't talk about it (presumably in order to keep their presentation simple), this representation (i.e. with both incoming and outgoing lists) is used in practice, for example in LEDA. Here's a slide from a LEDA presentation，详细说明了它们的静态（即假设固定的）图形数据结构；动态的将有 doubly-linked 列表而不是数组。我包括单向 ("directed") 和它们的 "bidirectional" 表示以便于比较：
Boost 具有类似的功能，尽管它只是对其 adjacency list implementation:
的一个调整（称为bidirectionalS）
The bidirectionalS selector specifies that the graph will provide the in_edges() function as well as the out_edges() function. This imposes twice as much space overhead per edge, which is why in_edges() is optional.
请记住，因为您可以区分两组边缘（在 LEDA 的情况下通过 "first in" 和 "first out" 或 in_edges() 和 out_edges 在提升的情况下）你真正拥有的是数学上的 disjoint union of a directed graph with its transpose. If you lose the distinction/color between the two sets of edges (pointers), what you get is sometimes called a bidirected graph, although the term (like alas many in graph theory) is unfortunately overloaded. And if you had hopes that LEDA's term bidirectional graph is somehow standardized with their meaning, it's actually more likely to mean the same thing as bidirected graph to theorists.
总结一下我到目前为止的回答：
我不认为像这样存储的依赖图有一个名称，但对于一般双向表示的图来说是一个合理的名称，不幸的是，它不会在几个软件包。双向（或双向）图是一个更广泛的术语，但大多数理论家可能会认为你的意思是你不能再分辨出两组边之间的区别（即他们会假设你的意思是并集而不是与转置的不相交并集图。）
它似乎主要是在实际实现环境（如 LEDA 或 boost）中讨论的一个方面，所以理论和介绍书籍似乎不太关心它。
至于包存储库 (3) 的实际表示，您似乎忽略了大多数（据我所知）将存储 AND、OR 和 NOT 约束以额外处理备选方案和冲突。您只能像我们上面讨论的那样使用依赖图处理 AND 。一旦你添加了这些额外的 OR & NOT 特征，你就会更难解决 (NP-complete) SAT problems just to install something; see the Opium paper (2007) for a discussion; for a more recent one (2010) see the Apt-pbo paper。所以 constant-time 反向依赖 look-ups 相比之下开始显得微不足道了。但要真正回答你的问题：
- 我查看了 apt 源代码，它确实将反向依赖项单独存储在它的缓存中（你 query with
apt-cache). For each package (pkgCache::Packagedefined inpkgcache.h) there's aRevDependslinked list and apt updates it every time you install or remove something: indepcache.cc:pkgDepCache::Update它有 for 循环（除其他外）Update(P.ParentPkg().RevDependsList());。