圖算法：從鄰接地圖

我有，我已表示爲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

圖算法：從鄰接地圖

回答

相關問題