алгоритмы графа: достижимость по карте смежности

В Питоне:

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

вот что я в итоге использовал, основываясь на ответе @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]}
}

Возможно, вам следует построить матрицу достижимости из списка смежности для быстрого поиска. Я только что нашел документ Примечания к курсу для CS336: График Теория — Джаядев Мишра , описывающая, как построить матрицу достижимости из матрицы смежности.

Если A — ваша матрица смежности, матрица достижимости будет R = A + A² + ... + A^n, где n — количество узлов в графе. A², A³, ... можно рассчитать:

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

Для матричного умножения используется логическое или вместо + и логическое и вместо x. Сложность O(n^4).

Обычный поиск в глубину или поиск в ширину добьются цели: выполните его один раз для каждого плохого узла.

Вот рабочее решение 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);

Как и в случае с Кристианом Аммером, вы берете в качестве 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-битный параллелизм, но методы шейдеров могут быть даже лучше.

РЕДАКТИРОВАТЬ: можно выполнять 128 бит параллельно с инструкциями SSE, с AVX даже больше.