2014年12月27日 星期六

最大團Maximum Clique

好久沒有po文了,來講一下最大團的一派作法,
更改自Bron-Kerbosch演算法。

主要想法是,首先先照度數從大排到小,並將他狀態壓縮成int128,
也就是128bit的一個整數,要#include <limits.h>才會有的東西。

最naive的算法就是從第一個可以取的人開始枚舉放進clique裡頭,
但放過的人之後就不要再放了,所以將他從candi裡頭移除,可以看Without Pivot那部分。

第一個cut是算一下最多可以再放多少人+已經放多少人(potential),連ans都不到就cut掉。
第二個cut來自Bron-Kerbosch演算法,選出一個pivot來加速,詳細可以看pivot前面的那段註解。
第三個cut則在枚舉的裡頭,如果有個點他連出去的點被pivot連出去的點覆蓋了,我們就不需要去枚舉那個點。

基本上就是這樣子。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
int128 one = 1;
int128 linkto[MXN];

int popcount(int128 val){
 return __builtin_popcountll(val >> 50)
   + __builtin_popcountll(val & ((one << 50) - 1));
}

int lowbit(int128 val){
 if((val & ((one << 50) - 1)) == 0)
    return __builtin_ctzll(val >> 50) + 50;
 return __builtin_ctzll(val & ((one << 50) - 1));
}

/* candi should be sorted from big deg. to small deg. */

int ans;

void maxclique(int elem_num, int128 candi){
 if(elem_num > ans) ans = elem_num;

 int potential = elem_num + popcount(candi);
 if(potential <= ans) return;
 
 /*  Since Maximum Clique must contain >= 1 node not in Neighbor(pivot),
  *  Otherwise pivot can be added into the Clique.
  */

 int pivot = lowbit(candi);
 int128 smaller_candi = candi & (~linkto[pivot]);

 /* Without pivot:
  *
  *  while(candi && potential > ans){
  *  int next = lowbit(candi);
  *   
  *   candi ^= one << next;
  *   potential --;
  * 
  *   maxclique(elem_num + 1, candi & linkto[next]);
  *  }
  */

 while(smaller_candi && potential > ans){
  int next = lowbit(smaller_candi);
  
  candi ^= one << next;
  smaller_candi ^= one << next;
  potential --;

  /* The "later if" is 0,
   * iff "next" is connected to a subset of Neighbor(pivot).
   * Then it is suffice to pick pivot only.
   */

  if(next == pivot || (smaller_candi & linkto[next]))
   maxclique(elem_num + 1, candi & linkto[next]);
 }
}