图算法：邻接图的可达性

Question

我有一个依赖图，我将其表示为 Map> （用 Java 语言，或 f(Node n) -> Collection[Node] 作为一个函数；这是从给定节点 n 到依赖于 n 的节点集合的映射。该图可能是循环的*。

给定一个节点列表 badlist，我想解决可达性问题：即生成一个Map>； badmap 表示从列表 badlist 中的每个节点 N 到包含 N 或传递依赖于它的其他节点的一组节点的映射。

示例：

(x -> y means node y depends on node x)
n1 -> n2
n2 -> n3
n3 -> n1
n3 -> n5
n4 -> n2
n4 -> n5
n6 -> n1
n7 -> n1

这可以表示为邻接图 {n1: [n2], n2: [n3], n3: [n1, n5], n4: [n2, n5], n6: [n1], n7: [n1]}。

如果 badlist = [n4, n5, n1] 那么我期望得到 badmap = {n4: [n4, n2, n3, n1, n5], n5: [n5], n1: [n1，n2，n3，n5]}。

我正在努力寻找在线图算法参考，所以如果有人能给我指出一个有效的可达性算法描述，我将不胜感激。 （对我没有帮助的一个例子是 http://www.cs.fit.edu/~wds/classes/cse5081/reach/reach.html 因为该算法是确定从特定节点是否可以到达特定节点 A B.)

*循环：如果您好奇，这是因为它代表 C/C++ 类型，并且结构可以具有指向相关结构的指针的成员。

Answer 1

在Python中：

def reachable(graph, badlist):
    badmap = {}
    for root in badlist:
        stack = [root]
        visited = set()
        while stack:
            v = stack.pop()
            if v in visited: continue
            stack.extend(graph[v])
            visited.add(v)
        badmap[root] = visited
    return badmap

Answer 2

这是我最终使用的，基于 @quaint 的答案：（

为了方便起见，需要一些 Guava 类）

static public <T> Set<T> findDependencies(
        T rootNode, 
        Multimap<T, T> dependencyGraph)
{
    Set<T> dependencies = Sets.newHashSet();
    LinkedList<T> todo = Lists.newLinkedList();
    for (T node = rootNode; node != null; node = todo.poll())
    {
        if (dependencies.contains(node))
            continue;
        dependencies.add(node);
        Collection<T> directDependencies = 
                dependencyGraph.get(node);
        if (directDependencies != null)
        todo.addAll(directDependencies);
    }
    return dependencies;
}
static public <T> Multimap<T,T> findDependencies(
        Iterable<T> rootNodes, 
        Multimap<T, T> dependencyGraph)
{
    Multimap<T, T> dependencies = HashMultimap.create();
    for (T rootNode : rootNodes)
        dependencies.putAll(rootNode, 
                findDependencies(rootNode, dependencyGraph));
    return dependencies;
}
static public void testDependencyFinder()
{
    Multimap<Integer, Integer> dependencyGraph = 
            HashMultimap.create();
    dependencyGraph.put(1, 2);
    dependencyGraph.put(2, 3);
    dependencyGraph.put(3, 1);
    dependencyGraph.put(3, 5);
    dependencyGraph.put(4, 2);
    dependencyGraph.put(4, 5);
    dependencyGraph.put(6, 1);
    dependencyGraph.put(7, 1);
    Multimap<Integer, Integer> dependencies = 
            findDependencies(ImmutableList.of(4, 5, 1), dependencyGraph);
    System.out.println(dependencies);
    // prints {1=[1, 2, 3, 5], 4=[1, 2, 3, 4, 5], 5=[5]}
}

Answer 3

您也许应该从邻接列表中构建一个可达性矩阵以进行快速搜索。我刚刚找到了论文 CS336 课程笔记：图表理论 - 贾亚德夫·米斯拉
描述了如何从邻接矩阵构建可达性矩阵。

如果 A 是邻接矩阵，则可达性矩阵将为 R = A + A² + ... + A^n，其中 n 是图中的节点数。 A², A³, ... 计算公式如下：

• A² = A x A
• A³ = A x A²
• ...

对于矩阵乘法逻辑或用于代替+，逻辑与用于代替x。复杂度为O(n^4)。

Answer 4

普通的深度优先搜索或广度优先搜索就可以解决问题：对每个坏节点执行一次。

Answer 5

这是一个有效的 Java 解决方案：

// build the example graph
Map<Node, Collection<Node>> graph = new HashMap<Node, Collection<Node>>();
graph.put(n1, Arrays.asList(new Node[] {n2}));
graph.put(n2, Arrays.asList(new Node[] {n3}));
graph.put(n3, Arrays.asList(new Node[] {n1, n5}));
graph.put(n4, Arrays.asList(new Node[] {n2, n5}));
graph.put(n5, Arrays.asList(new Node[] {}));
graph.put(n6, Arrays.asList(new Node[] {n1}));
graph.put(n7, Arrays.asList(new Node[] {n1}));

// compute the badmap
Node[] badlist = {n4, n5, n1};
Map<Node, Collection<Node>> badmap = new HashMap<Node, Collection<Node>>();

for(Node bad : badlist) {
    Stack<Node> toExplore = new Stack<Node>();
    toExplore.push(bad);
    Collection<Node> reachable = new HashSet<Node>(toExplore);
    while(toExplore.size() > 0) {
        Node aNode = toExplore.pop();
        for(Node n : graph.get(aNode)) {
            if(! reachable.contains(n)) {
                reachable.add(n);
                toExplore.push(n);
            }
        }
    }

    badmap.put(bad, reachable);
}

System.out.println(badmap);

Answer 6

就像 Christian Ammer 一样，在执行以下操作时，您将邻接矩阵视为 A 并使用布尔算术，其中 I 是单位矩阵。

    B = A + I;
    C = B * B;
    while (B != C) {
        B = C;
        C = B * B;
    }
    return B;

此外，标准矩阵乘法（算术和逻辑）是 O(n^3)，而不是 O(n^2)。但是，如果n <= 64，您就可以摆脱一个因素n，因为您可以在当今的 64 位机器上并行执行 64 位操作。对于较大的图形，64 位并行性也很有用，但着色器技术可能更好。

编辑：可以与 SSE 指令并行执行 128 位，使用 AVX 指令甚至更多。