algorithm - 在图或树中查找冗余边的算法

Question

是否存在用于在图中查找冗余边的既定算法？

比如我想发现 a->d 和 a->e 是多余的，然后去掉它们，像这样：

=>

编辑：Strilanc 很好地为我读懂了我的想法。“冗余”这个词太强了，因为在上面的例子中，a->b 或 a->c 都不被认为是冗余的，但 a->d 是。

score 36 · Accepted Answer

您想要计算保持顶点可达性的最小图。

这称为图的传递约简。维基百科文章应该让你开始走上正确的道路。

score 2 · Accepted Answer

由于@Craig 提到的 Wikipedia 文章只对实现产生了影响，因此我使用 Java 8 流发布了我的实现：

Map<String, Set<String>> reduction = usages.entrySet().stream()
                .collect(toMap(
                        Entry::getKey,
                        (Entry<String, Set<String>> entry) -> {
                            String start = entry.getKey();
                            Set<String> neighbours = entry.getValue();
                            Set<String> visited = new HashSet<>();
                            Queue<String> queue = new LinkedList<>(neighbours);

                            while (!queue.isEmpty()) {
                                String node = queue.remove();
                                usages.getOrDefault(node, emptySet()).forEach(next -> {
                                    if (next.equals(start)) {
                                        throw new RuntimeException("Cycle detected!");
                                    }
                                    if (visited.add(next)) {
                                        queue.add(next);
                                    }
                                });
                            }

                            return neighbours.stream()
                                    .filter(s -> !visited.contains(s))
                                    .collect(toSet());
                        }
                ));

score 0 · Accepted Answer

有几种方法可以解决这个问题，但首先你需要更精确地定义问题。首先，你这里的图是非循环的和有向的：这总是正确的吗？

接下来，您需要定义“冗余边缘”的含义。在这种情况下，您从一个具有两条路径 a->c 的图开始：一条通过 b，一条直接通过。由此我推断，“冗余”是指这样的东西。令G=< V, E >是一个图，其中V是顶点集，E ⊆ V×V是边集。看起来您将所有从vi到v _{j的边都定义}_为比最长边短的“冗余”。所以最简单的方法是使用深度优先搜索，枚举路径，当你找到一个更长的新路径时，将其保存为最佳候选。

不过，我无法想象你想要它做什么。你能告诉？

score 0 · Accepted Answer

我认为最简单的方法是，想象一下它在实际工作中的样子，想象一下如果你有关节，比如

(A->B)(B->C)(A->C)，想象如果近图之间的距离等于1，那么

(A->B) = 1，(B->C) = 1，(A->C) = 2。

所以你可以移除关节（A->C）。

换句话说，最小化。

这只是我一开始的想法。网上有各种各样的文章和资源，你可以看看它们并深入了解。

资源，这将帮助您：

去除非二进制 CSP 对偶图中冗余边的算法

图数据结构和基本图算法

谷歌图书，关于找到最小的两个连接子图

图形缩减

用于在任意顶点冗余或边冗余图中进行预先计划恢复的冗余树

score 0 · Accepted Answer

我有一个类似的问题，并最终以这种方式解决它：

我的数据结构由dependends字典组成，从节点 id 到依赖它的节点列表（即 DAG 中的追随者）。请注意，它仅适用于 DAG - 即有向无环图。

我还没有计算出它的确切复杂性，但它在一瞬间吞噬了我的数千张图表。

_transitive_closure_cache = {}
def transitive_closure(self, node_id):
    """returns a set of all the nodes (ids) reachable from given node(_id)"""
    global _transitive_closure_cache
    if node_id in _transitive_closure_cache:
        return _transitive_closure_cache[node_id]
    c = set(d.id for d in dependents[node_id])
    for d in dependents[node_id]:
        c.update(transitive_closure(d.id))  # for the non-pythonists - update is update self to Union result
    _transitive_closure_cache[node_id] = c
    return c

def can_reduce(self, source_id, dest_id):
    """returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
    for d in dependents[source_id]:
        if d.id == dest_id:
            continue
        if dest_id in transitive_closure(d.id):
            return True # the dest node can be reached in a less direct path, then this link is redundant
    return False

# Reduce redundant edges:
for node in nodes:      
    dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]

algorithm - 在图或树中查找冗余边的算法

5 回答 5

Related

Reference