graph algorithms: reachability from adjacency map

问题:

I have a dependency graph that I have represented as a Map<Node, Collection<Node>> (in Java-speak, or f(Node n) -> Collection[Node] as a function; this is a mapping from a given node n to a collection of nodes that depend on n). The graph is potentially cyclic*.

Given a list badlist of nodes, I would like to solve a reachability problem: i.e. generate a Map<Node, Set<Node>> badmap that represents a mapping from each node N in the list badlist to a set of nodes which includes N or other node that transitively depends on it.

Example:

(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

This can be represented as the adjacency map {n1: [n2], n2: [n3], n3: [n1, n5], n4: [n2, n5], n6: [n1], n7: [n1]}.

If badlist = [n4, n5, n1] then I expect to get badmap = {n4: [n4, n2, n3, n1, n5], n5: [n5], n1: [n1, n2, n3, n5]}.

I'm floundering with finding graph algorithm references online, so if anyone could point me at an efficient algorithm description for reachability, I'd appreciate it. (An example of something that is not helpful to me is http://www.cs.fit.edu/~wds/classes/cse5081/reach/reach.html since that algorithm is to determine whether a specific node A is reachable from a specific node B.)

*cyclic: if you're curious, it's because it represents C/C++ types, and structures can have members which are pointers to the structure in question.

回答1:

In 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

回答2:

here's what I ended up using, based on @quaint's answer:

(requires a few Guava classes for convenience)

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]}
}

回答3:

You maybe should build a reachability matrix from your adjacency list for fast searches. I just found the paper Course Notes for CS336: Graph Theory - Jayadev Misra which describes how to build the reachability matrix from a adjacency matrix.

If A is your adjacency matrix, the reachability matrix would be R = A + A² + ... + A^n where n is the number of nodes in the graph. A², A³, ... can be calculated by:

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

For the matrix multiplication the logical or is used in place of + and the logical and is used in place of x. The complexity is O(n^4).

回答4:

Ordinary depth-first search or breadth-first search will do the trick: execute it once for each bad node.

回答5:

Here's a working Java solution:

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

回答6:

Just like with Christian Ammer, you take for A the adjacency matrix and use Boolean arithmetic, when doing the following, where I is the identity matrix.

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

Furthermore, standard matrix multiplication (both arithmetical and logical) is O(n^3), not O(n^2). But if n <= 64, you can sort of get rid of one factor n, because you can do 64 bits in parallel on nowadays 64 bits machines. For larger graphs, 64 bits parallelism is useful, too, but shader techniques might even be better.

EDIT: one can do 128 bits in parallel with SSE instructions, with AVX even more.