我发现了等待图(wait-for graphs)，我想知道，是否有有效的算法可以检测在有向图中添加一条边是否会导致出现环路?
所讨论的图是可变的(可以添加或删除节点和边)。我们只需要知道是否存在环路即可(以防止添加一个冒犯边)。
当然，可以使用计算强连通分量(例如Tarjan算法)的算法来检查新图是否为无环图，但每次添加边时都要重新运行它似乎相当低效。
如何检测向有向图中添加边是否会导致出现环？
40
- Petr
7
你有记忆或时间限制吗？ - Mark Elliot
@MarkElliot 这些图表用于协调许多并发运行的线程的锁定。我预计该图表将具有数十到数百个节点，边的数量可能是节点数量的平方。该图表将经常更新，并且所有更新都需要检查是否会导致循环。 - Petr
如果这个图是“等待图(wait-for graph)”，那么节点只有在某些操作完成时才能被删除。因此，删除只发生在叶子节点上。我的理解正确吗？ - Jacob
2@PetrPudlák，你能补充一下Thomas的回答中你所缺少的内容吗？我认为这个问题已经得到了回答。你是想在插入时检测循环吗？ - user
@Jacob 这并不一定是正确的。一个节点可以等待另一个节点，如果超时了，该节点将被移除。 - Petr
显示剩余2条评论
5个回答
43
如果我理解正确，那么只有当以前从v到u没有路径时才插入新的边(u，v)(即如果(u，v)不创建一个循环)。因此，您的图始终是一个DAG（有向无环图）。在这种情况下，使用Tarjan算法检测强连通分量可能会过度复杂化(http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)。在插入(u，v)之前，你所要检查的就是是否存在从v到u的有向路径，这可以通过简单的BFS/DFS来完成。
因此，最简单的方法是以下（n = |V|，m = |E|）：
- 插入(u，v)：检查是否存在从v到u的路径(BFS/DFS)。 时间复杂度：O(m) - 删除边：直接从图中删除它们。时间复杂度：O(1)
虽然在最坏情况下插入(u，v)需要O(m)的时间，但在您的情况下可能非常快速。在从v开始进行BFS/DFS检查可达性时，您只会访问从v可达的顶点。我猜在您的设置中，图形相当稀疏，并且由另一个顶点可达的顶点数量并不高。
因此，最简单的方法是以下（n = |V|，m = |E|）：
- 插入(u，v)：检查是否存在从v到u的路径(BFS/DFS)。 时间复杂度：O(m) - 删除边：直接从图中删除它们。时间复杂度：O(1)
虽然在最坏情况下插入(u，v)需要O(m)的时间，但在您的情况下可能非常快速。在从v开始进行BFS/DFS检查可达性时，您只会访问从v可达的顶点。我猜在您的设置中，图形相当稀疏，并且由另一个顶点可达的顶点数量并不高。
然而，如果你想提高理论运行时间，以下是一些提示（主要表明这并不容易）。假设我们的目标是以O（1）的时间测试是否存在从v到u的有向路径。在这种情况下，关键词是DAG的传递闭包（即，如果DAG中存在从u到v的有向路径，则其中包含边缘（u，v））。不幸的是，在动态设置中维护传递闭包似乎并不简单。有几篇论文考虑了这个问题，我找到的所有论文都是STOC或FOCS论文，这表明它们非常复杂。我找到的最新（也是最快）的结果是Sankowski的论文“Dynamic Transitive Closure via Dynamic Matrix Inverse”（http://dl.acm.org/citation.cfm?id=1033207）。
即使你愿意理解其中一种动态传递闭包算法（甚至想要实现它），它们也不会给你任何加速，因为这些算法是针对具有大量连接查询（然后可以在O（1）时间内执行）和图中仅有少量更改的情况设计的。然而，目标仍然是使这些更改比重新计算传递闭包更便宜。但是，这种更新仍然比单个连接性检查慢。因此，如果您需要在每次连接查询上进行更新，则最好使用上述简单方法。
那么，为什么我要提到维护传递闭包的方法，如果它不符合您的需求呢？这表明，仅消耗O（1）查询时间的算法搜索可能不会比使用BFS / DFS的简单算法更快地解决问题。您可以尝试获取查询时间，该时间比O（m）更快但比O（1）更差，同时更新速度也比O（m）更快。这是一个非常有趣的问题，但对我来说似乎是一个非常雄心勃勃的目标（所以可能不要花太多时间去尝试实现它...）。
- Thomas
5
正如Mark所建议的，可以使用存储连接节点的数据结构。最好使用布尔矩阵|V|x|V。值可以用Floyd-Warshall算法初始化。这是在O(|V|^3)中完成的。
设T(i)为具有到顶点i的路径的顶点集合，F(j)为存在从顶点j到达的顶点集合。第一个是i行中的true，第二个是j列中的true。
添加边(i,j)是一个简单的操作。如果以前没有连接i和j，则对于来自T(i)中的每个a和来自F(j)中的每个b，将矩阵元素(a,b)设置为true。但是该操作不便宜。在最坏的情况下，它是O(|V|^2)。在有向线的情况下，从终点到起点顶点添加边会使所有顶点都连接到所有其他顶点。
删除边(i,j)并不是那么简单，但在最坏情况下不是更昂贵的操作:-)如果在删除边之后从i到j存在路径，则什么也不会改变。这通过Dijkstra检查，少于O(|V|^2)。不再连接的顶点是(a,b)：
- a在T(i)-i-T(j) - b在F(j)+j
仅T(j)随着删除边(i,j)而改变，因此必须重新计算。这是通过任何类型的图遍历（BFS，DFS），通过从顶点j反向遍历边缘方向完成的。这是在小于O(|V|^2)的时间内完成的。由于矩阵元素的设置在最坏情况下仍为O(|V|^2)，因此该操作具有与添加边相同的最坏情况复杂度。
设T(i)为具有到顶点i的路径的顶点集合，F(j)为存在从顶点j到达的顶点集合。第一个是i行中的true，第二个是j列中的true。
添加边(i,j)是一个简单的操作。如果以前没有连接i和j，则对于来自T(i)中的每个a和来自F(j)中的每个b，将矩阵元素(a,b)设置为true。但是该操作不便宜。在最坏的情况下，它是O(|V|^2)。在有向线的情况下，从终点到起点顶点添加边会使所有顶点都连接到所有其他顶点。
删除边(i,j)并不是那么简单，但在最坏情况下不是更昂贵的操作:-)如果在删除边之后从i到j存在路径，则什么也不会改变。这通过Dijkstra检查，少于O(|V|^2)。不再连接的顶点是(a,b)：
- a在T(i)-i-T(j) - b在F(j)+j
仅T(j)随着删除边(i,j)而改变，因此必须重新计算。这是通过任何类型的图遍历（BFS，DFS），通过从顶点j反向遍历边缘方向完成的。这是在小于O(|V|^2)的时间内完成的。由于矩阵元素的设置在最坏情况下仍为O(|V|^2)，因此该操作具有与添加边相同的最坏情况复杂度。
- Ante
1
这是我最近在稍微不同的情况下遇到的问题（互相依赖编译器指令的最佳排序）。
虽然我无法改进O(n*n)的理论界限，但经过一定量的实验和对我的情况做出的启发式假设（例如，假设初始排序没有恶意地创建），以下是性能方面最好的折衷算法。
（在我的情况下，我有一个可以接受的“右侧失败”：在添加初始节点和弧之后（这是有保证的），优化器偶尔拒绝添加更多弧，其中实际上可以添加一个。当完全执行此算法时，此近似不是必需的，但如果您希望这样做，则可以使用此算法，并因此进一步限制其运行时间。）
当图形按拓扑排序时，保证它是无环的。在第一阶段中，当我有一个静态的节点和弧块要添加时，我添加了节点，然后按拓扑排序进行排序。
在第二阶段中，添加其他弧时，在考虑从A到B的弧时有两种情况。如果A已经位于B的左侧进行了排序，则可以简单地添加一条弧，并且不会生成循环，因为列表仍然按拓扑排序。
如果B在A的左侧，则考虑从B到A之间的子序列，并将其分成两个不相交的序列X，Y，其中X是可以到达A的节点（Y为其他节点）。如果A从B中不可达，即没有直接弧从B进入X或到达A，则可以在添加A到B弧之前重新排序XABY，显示它仍然是无环的并保持拓扑排序。这里与朴素算法相比的效率是我们只需要考虑B和A之间的子序列，因为我们的列表已按拓扑排序：A不能从A右侧的任何节点到达。对于我的情况，局部重排序最频繁且最重要，这是一个重要的收益。
由于我们不在序列X、A、B、Y内重新排序，因此任何在同一序列内开始或结束的弧仍然正确排序，而且在每个侧面上都相同，在飞越左侧到右侧侧面的任何弧也是如此。任何在侧面和X、A、B、Y之间的弧也仍然正确排序，因为我们的重新排序仅限于此本地区域。因此，我们只需要考虑四个序列之间的弧。依次考虑我们最终排序XABY的每个可能的“有问题”的弧：YB YA YX BA BX AX。我们的初始顺序是B[XY]A，因此不能出现AX和YB。X可以到达A，但Y不能，因此YX和YA不会发生，否则可以从Y弧的源头（可能通过X）到达A，这是矛盾的。我们接受性的标准是没有链接BX或BA。因此，没有问题的弧，而且我们仍然按拓扑排序。
我们唯一可接受的标准（即A无法从B到达）足以在添加弧A->B时创建一个循环： B -（X）-> A-> B，因此反之亦然。如果我们可以向每个节点添加标志，则可以相对有效地实现此操作。从紧靠A左侧的节点开始，沿着从右到左的方向考虑节点[BXY]。如果该节点直接连接A，则设置标志。在任意一个这样的节点，我们只需要考虑直接外向弧：其右侧的节点要么在A之后（因此不相关），要么如果从A可达则已经被标记，因此当遇到任何带有标记节点的直接连通时，该节点上的标记就会被设置。如果在过程结束时未在B上标记，则重新排序是可以接受的，并且被标记的节点包括X。
虽然如果完全完成，此方法始终会产生正确的排序（据我所知），但正如我在前言中提到的，如果您的初始构建大致正确（即能够适应可能的其他弧而无需重新排序），则此方法尤其高效。
还存在一种有效的近似方法，如果您的上下文允许拒绝“过分”的弧（那些会大幅重新排序的弧），则可以通过限制您愿意扫描的A到B距离来进行。如果您有要添加的附加弧的初始列表，则可以按距离递增的顺序对它们进行排序，直到用尽一些扫描“信用”，然后在那一点结束您的优化。
- Dannie
0
如果所有之前的工作都是按照拓扑排序的顺序进行的。那么，如果您添加一个似乎会打破排序且无法修复的边缘，则会形成一个循环。
假设我们想要从x到z添加一条边。这似乎会破坏排序。因此，我们可以将节点x移动到位置z+1，这将修复排序，前提是(x，z]中的任何节点都没有与节点x相连的边。
https://dev59.com/D3VC5IYBdhLWcg3wixs0#261621
如果我们有一个已排序的节点列表：
1, 2, 3, ..., x, ..., z, ...
Such that each node is waiting for nodes to its left.
假设我们想要从x到z添加一条边。这似乎会破坏排序。因此，我们可以将节点x移动到位置z+1，这将修复排序，前提是(x，z]中的任何节点都没有与节点x相连的边。
- Jacob
0
如果图是有向的，您只需要检查节点的父节点（向上导航直到达到根节点），以确定新边应该从哪个节点开始。如果其中一个父节点等于边的末端，则添加边将创建一个循环。
- user3072850
1
3图不一定是一棵树。根节点可以通过不同的祖先到达，你需要检查所有的祖先。虽然这并不特别耗费时间，但它是一个潜在的O（|E|）解决方案——这正是@Thomas所提出的。 - tucuxi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接