<p>这是一个简单的通用算法。算法可以向前或向后运行。这个和乔尔的答案基本上是双重的,他向后跑,这个向前跑:</p>
<pre><code>def remove_redundant_edges(G):
"""
Remove redundant edges from a DAG using networkx (nx).
An edge is redundant if there is an alternate path
from its start node to its destination node.
This algorithm could work front to back, or back to front.
We choose to work front to back.
The main persistent variable (in addition to the graph
itself) is indirect_pred_dict, which is a dictionary with
one entry per graph node. Each entry is a set of indirect
predecessors of this node.
The algorithmic complexity of the code on a worst-case
fully-connected graph is O(V**3), where V is the number
of nodes.
"""
indirect_pred_dict = collections.defaultdict(set)
for node in nx.topological_sort(G):
indirect_pred = indirect_pred_dict[node]
direct_pred = G.predecessors(node)
for pred in direct_pred:
if pred in indirect_pred:
G.remove_edge(pred, node)
indirect_pred.update(direct_pred)
for succ in G.successors(node):
indirect_pred_dict[succ] |= indirect_pred
</code></pre>
<h2>复杂性分析与大O优化</h2>
<p>对于一个<strong>最小连通图</strong>,其中每个节点只连接到一条边,其复杂性为<code>O(V+E)</code>。然而,即使对于一个简单的线性图(其中每个节点都有一个传入边和一个传出边),复杂度也是<code>O(V*E)</code>,而对于一个<strong>最大连通图</strong>(这是最坏的情况,其中每个节点都连接到图上的每个下游节点),复杂性也是<code>O(V**3)</code>。对于这种情况,ops的数量遵循序列<a href="https://oeis.org/A000292" rel="nofollow">A000292</a>,这是<code>n * (n+1) * (n+2) / 6</code>,其中n是节点数(V)减去3。在</p>
<p>根据图形的形状,还可以进行其他优化。下面是一个带有几种不同优化器的版本,它们可以显著降低某些类型图形的复杂性和运行时:</p>
^{pr2}$
<p>我还没有分析是否可以构造一个稠密但非最大连通的图,该图的执行复杂度大于<code>O(V**2)</code>,并且启用了优化密集选项,但我没有理由先验地相信这是不可能的。优化对最大连通图最有效,并且不会做任何事情,例如,在每个节点与其子节点共享继承者而不是子节点的情况下,我还没有分析这种情况下的运行时。在</p>
<h2>示例试验台</h2>
<p>我已经剥离了基本算法的代码,添加了记录最坏情况路径所需操作数的工具,以及生成最大连接图的示例测试生成器。在</p>
<pre><code>import collections
import networkx as nx
def makegraph(numnodes):
"""
Make a fully-connected graph given a number of nodes
"""
edges = []
for i in range(numnodes):
for j in range(i+1, numnodes):
edges.append((i, j))
return nx.DiGraph(edges)
def remove_redundant_edges(G):
ops = 0
indirect_pred_dict = collections.defaultdict(set)
for node in nx.topological_sort(G):
indirect_pred = indirect_pred_dict[node]
direct_pred = G.predecessors(node)
for pred in direct_pred:
if pred in indirect_pred:
G.remove_edge(pred, node)
indirect_pred.update(direct_pred)
for succ in G.successors(node):
indirect_pred_dict[succ] |= indirect_pred
ops += len(indirect_pred)
return ops
def test_1(f, numnodes):
G = makegraph(numnodes)
e1 = nx.number_of_edges(G)
ops = f(G)
e2 = nx.number_of_edges(G)
return ops, e1, e2
for numnodes in range(30):
a = test_1(remove_redundant_edges, numnodes)
print numnodes, a[0]
</code></pre>