程式扎記: [ Alg info ] Using DFS to find Articulation point

標籤

2013年6月17日 星期一

[ Alg info ] Using DFS to find Articulation point

Preface: 
考慮有下面網路拓譜圖, 當你是一個網管, 可能會希望找出當那些點 break 後則可能會造成部分的子網路無法連線而加以改善: (下面例子即是實驗室與 215 機房 的 switch
 

而你可以把網路拓譜圖視為一個 Connected graph, 而我們的目標便是找出 Argiculation point
如果在connected graph G 中的的一個 vertex v 被移除以後(包含 v 和所有incident在它上面的edge), 新的graph G’ 會變成有兩塊以上的connected components

以下面左邊的圖形為範例, Vertex 1, 3, 5 與 7 即為 Argiculation point: 
 

Use DFS to find Articulation point: 
底下說明使用 DFS (Deep First Search) 來找出 Articulation point. 首先第一步便是決定 Graph 的某一點開始跑 DFS 並標示出每點的 discover time. 假設我們取 Vertex 3 為 root 跑 DFS, 則一種可能的走法如下: (3-4-2-1-0-5-6-7-9-8
 

接著我們將 Vertex 3 視為 root 並調整長相如下 (虛線為 back edge): 
 

然後我們使用下面公式計算每一點的 low 值: 
low(u)=min{u.d, min{low(w)|w is a child of u}, min{w.d| (u,w) is a back edge}}

計算結果如下: 
 

接著只要滿足下面任一個條件即為 Articulation point: 
* Root 有超過一個 child 即為articulation point
* 當某 vertex v 有任何一個 child u 的 low(u)≥v.d 時, 則 v 為articulation point

以上面的例子來說, 因為 Root vertex 3 有兩個 child (Vertex 4,5), 故 Vertex 3 為 Articulation point; Vertex 1 的 d=3, 而其 child Vertex 0 的 low 值為 4, 故 Vertex 1 為 Articulation point... 眼尖的你應該可以發現只要 Vertex u 的 child(s) 都有 back edge 回到 Vertex u 的祖先, 則 Vertex u 就不會是 Articulation point! 

Implementation: 
底下類別實作了上面利用 DFS 找 Articulation point 的過程: (完整代碼
  1. package map.alg;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.List;  
  5. import java.util.Set;  
  6. import java.util.TreeSet;  
  7.   
  8. import map.Edge;  
  9. import map.Graph;  
  10. import map.Vertex;  
  11. import map.enums.EEdgeType;  
  12.   
  13. public class FindArtiCulationPt {  
  14.   
  15.     /** 
  16.      * BD: low(v)=min{v.d, min{low(w)|w is a child of v}, min{w.d| (v,w) is a back edge}} 
  17.      * @param v 
  18.      */  
  19.     protected static void _CalcLow(Vertex v)  
  20.     {  
  21.         int low = Integer.MAX_VALUE;  
  22.         for(Edge e:v.edgeSet)  
  23.         {  
  24.             if(e.to.d > v.d) // children  
  25.             {  
  26.                 _CalcLow(e.to);               
  27.                 low = Math.min(low, e.to.low);  
  28.             }  
  29.             else if(e.type.equals(EEdgeType.Back)) low = Math.min(low, e.to.d); // back edge  
  30.         }  
  31.         v.low = Math.min(low, v.d);  
  32.     }  
  33.       
  34.     public static Set Go(Graph g, Vertex s)  
  35.     {  
  36.         Set vset = new TreeSet();  
  37.           
  38.         // 1) Run DFS  
  39.         DFS.Run(g, s);  
  40.           
  41.         // 2.1) 如果是root的話(開始做dfs的地方), 且有超過一個的 children 是articulation point  
  42.         s.low = 1;  
  43.         List childList = new ArrayList();  
  44.         for(Edge e:s.edgeSet)  
  45.         {  
  46.             if(e.type.equals(EEdgeType.Tree)) {  
  47.                 System.out.printf("\t[Test] Child=%s\n", e.to);  
  48.                 childList.add(e.to);  
  49.             }  
  50.         }  
  51.         if(childList.size()>1) vset.add(s);  
  52.           
  53.         // 2.2) 當有一個以上的小孩,   
  54.         //      無法沿著它自己的後代及一條nontree edge (back edge)到達它的祖先的時候, 則為articulation point  
  55.         for(Vertex v:childList) _CalcLow(v);          
  56.         for(Vertex v:g.vtxMap.values())  
  57.         {  
  58.             for(Edge e:v.edgeSet)  
  59.             {  
  60.                 if(e.to.d>v.d && e.to.low>=v.d)  
  61.                 {  
  62.                     vset.add(v);  
  63.                     break;  
  64.                 }  
  65.             }  
  66.         }  
  67.                   
  68.         return vset;  
  69.     }  
  70. }  
Example: 
底下為該類別使用的一個範例: 
  1. public static void main(String[] args) {  
  2.     Graph g = new Graph(false);  
  3.     g.addVertice(09);  
  4.     g.addEdge(01);  
  5.     g.addEdge(12); g.addEdge(13);  
  6.     g.addEdge(24);  
  7.     g.addEdge(43);  
  8.     g.addEdge(35);  
  9.     g.addEdge(56); g.addEdge(57);  
  10.     g.addEdge(67);  
  11.     g.addEdge(78); g.addEdge(79);  
  12.       
  13.     Set vset = FindArtiCulationPt.Go(g, g.getVertex(3));  
  14.     System.out.printf("\t[Info] Articulation Point:\n");  
  15.     for(Vertex v:vset) System.out.printf("\t\t%s\n", v);  
  16. }  
執行結果: 
[Info] Articulation Point:
1(Black)
3(Black)
5(Black)
7(Black)

Supplement: 
[CSIE 1212] Data Structure and Algorithm - 4/9 Graph2 
Articulation Vertex / Bridge 
[ Intro Alg ] Elementary Graph Algorithms - Depth-first search

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!