图算法：从邻接地图

我有，我已表示为Map<Node, Collection<Node>>（在Java中发言，或f(Node n) -> Collection[Node]作为函数依赖图的可达性;这是从一个给定节点n到节点的集合依赖的映射在n）。该图可能是循环*。图算法：从邻接地图

给定一个列表中的节点的badlist，我想解决reachability problem：即产生一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++类型，并且结构可以具有指向正在讨论的结构的成员。

来源

2011-09-01 Jason S

在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

来源

2011-09-01 20:34:41 quaint

好的，这很简单。出于某种原因，我挂断了一个事实，即必须重新执行'for root in badlist'循环，而没有利用以前执行循环所获得的知识。所以也许可以优化速度......但是你拥有的很简单。 –

@Jason这对于有界的入度（即结构引用的不同结构类型的数量）的图是渐近最优的。如果瓶颈不在其他地方，我会感到惊讶。 – quaint

@Jason：如果您想优化该算法的速度，请将标记位置于顶点本身，而不是在外部'visited'集合中查找它。 –

普通深度优先搜索或广度优先搜索就可以了：每个坏节点一次执行它。

来源

2011-09-01 20:36:59 zvrba

这里有一个工作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);

来源

2011-09-01 20:50:31 ChrisJ

这里就是我最终使用的基础上，@古朴的回答是：

（需要一些番石榴类方便）

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

来源

2011-09-01 21:02:10

您可能应该从您的邻接列表中构建一个可达性矩阵以进行快速搜索。我刚刚找到描述如何从邻接矩阵构建可达性矩阵的论文Course Notes for CS336: Graph Theory - Jayadev Misra 。

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

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

对于矩阵乘法的逻辑或代替+和逻辑和用来代替x被使用。复杂度是O（n^4）。

来源

2011-09-01 21:11:20

+1表示有趣，但我的'badlist'与图中节点总数相比是非常少的节点数（badlist通常大小为4-10，而节点总数在数万），所以我不确定这是否有效或易于实现我的目的。 –

就像Christian Ammer一样，当采取邻接矩阵A并使用布尔算术时，在进行以下操作时，其中I是单位矩阵。

此外，标准的矩阵乘法（包括算术和逻辑的）是O(n^3)，不O(n^2)。但是如果n <= 64，你可以排除一个因素n，因为你可以在现今的64位机器上并行执行64位。对于更大的图形，64位并行性也很有用，但着色技术甚至可能更好。

编辑：人们可以做128位与SSE指令并行，与AVX甚至更多。

来源

2016-11-22 14:48:01 Michiel

图算法：从邻接地图

回答

相关问题