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

Question

У меня есть граф зависимостей, который я представлял как Map<Node, Collection<Node>> (на языке Java или f(Node n) -> Collection[Node] как функция; это отображение из данного узла n в набор узлов, которые зависят от n). График потенциально циклический *.

Учитывая список badlist узлов, я хотел бы решить проблему достижимости : т.е. сгенерировать Map<Node, Set<Node>> badmap, который представляет отображение из каждого узла N в списке badlist к набору узлов, который включает 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

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

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

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

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

Answer 3

вот что я в итоге использовал, основываясь на ответе @ quaint:

(для удобства требуется несколько классов гуавы)

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 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);

Answer 5

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

Answer 6

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