Clique使用遞歸方法

Question

我試圖解決clique problem。 我使用的是Bron Kerbosch Clique algorithm，很好用java編寫了一個巧妙的實現，可以找到here。但是，由於團聚硬度，它可能會非常緩慢，我想要做的是使用我知道他們連接的一組初始頂點組合。然後調用該方法。對於我的生活，我不確定我在做什麼錯誤，結果不是派系。

注意：評論代碼來自原始代碼（上面鏈接）。

public class BronKerboschCliqueFinder<V, E> { 

    //~ Instance fields -------------------------------------------------------- 

private final UndirectedGraph<V, E> graph; 
private Collection<Set<V>> cliques; 

// public Collection<Set<V>> getAllMaximalCliques() 
public Collection<Set<V>> getAllMaximalCliqes(Set<String> initials){ 
{ 
    // TODO: assert that graph is simple 

    cliques = new ArrayList<Set<V>>(); 
    List<V> potential_clique = new ArrayList<V>(); 
    List<V> candidates = new ArrayList<V>(); 
    List<V> already_found = new ArrayList<V>(); 
    // candidates.addAll(graph.getVertices()); instead I do this: 
    for(V v : graph.getVertices()){ 
     if(initial.contains(v)){ 
      potential_clique.add(v); 
     }else{ 
      candidates.add(v); 
     } 
    } 
    findCliques(potential_clique, candidates, already_found); 
    return cliques; 
} 


private void findCliques(
    List<V> potential_clique, 
    List<V> candidates, 
    List<V> already_found) 
{ 

    List<V> candidates_array = new ArrayList<V>(candidates); 
    if (!end(candidates, already_found)) { 
     // for each candidate_node in candidates do 
     for (V candidate : candidates_array) { 
      List<V> new_candidates = new ArrayList<V>(); 
      List<V> new_already_found = new ArrayList<V>(); 

      // move candidate node to potential_clique 
      potential_clique.add(candidate); 
      candidates.remove(candidate); 

      // create new_candidates by removing nodes in candidates not 
      // connected to candidate node 
      for (V new_candidate : candidates) { 
       if (graph.isNeighbor(candidate, new_candidate)) 
       { 
        new_candidates.add(new_candidate); 
       } // of if 
      } // of for 

      // create new_already_found by removing nodes in already_found 
      // not connected to candidate node 
      for (V new_found : already_found) { 
       if (graph.isNeighbor(candidate, new_found)) { 
        new_already_found.add(new_found); 
       } // of if 
      } // of for 

      // if new_candidates and new_already_found are empty 
      if (new_candidates.isEmpty() && new_already_found.isEmpty()) { 
       // potential_clique is maximal_clique 
       cliques.add(new HashSet<V>(potential_clique)); 
       return; 
      } // of if 
      else { 
       // recursive call 
       findCliques(
        potential_clique, 
        new_candidates, 
        new_already_found); 
      } // of else 

      // move candidate_node from potential_clique to already_found; 
      already_found.add(candidate); 
      potential_clique.remove(candidate); 
     } // of for 
    } // of if 
} 

private boolean end(List<V> candidates, List<V> already_found) 
{ 
    // if a node in already_found is connected to all nodes in candidates 
    boolean end = false; 
    int edgecounter; 
    for (V found : already_found) { 
     edgecounter = 0; 
     for (V candidate : candidates) { 
      if (graph.isNeighbor(found, candidate)) { 
       edgecounter++; 
      } // of if 
     } // of for 
     if (edgecounter == candidates.size()) { 
      end = true; 
     } 
    } // of for 
    return end; 
} 
} 

因此，在短期我唯一的變化是getAllMaximalCliques方法。 我不太確定遞歸調用方法在這裏的工作原理。

我會感激，如果任何幫助或方向可以給。

Answer 1

所以，如果我理解正確的話，你想總理遞歸與你已經知道是一個子集團，以減少遞歸步驟所需數量的部分解決方案？

在這種情況下，我認爲你誤入歧途的地方在於啓動候選人陣列。在進入遞歸函數時的任何點，候選數組包含其不是在潛在集團，但被單獨連接到電勢集團的所有成員的所有圖元。最後一位是您錯過的位：您已經爲所有剩餘的圖元設置了候選，這爲剩餘的遞歸設置了無效狀態。

那麼試試這個：

public Collection<Set<V>> getAllMaximalCliques(Collection<V> initials) { 
    // TODO: assert that graph is simple 

    cliques = new ArrayList<>(); 
    List<V> potential_clique = new ArrayList<>(); 
    List<V> candidates = new ArrayList<>(); 
    List<V> already_found = new ArrayList<>(); 

    // candidates.addAll(graph.getVertices()); 

    for (V v : graph.getVertices()) { 
     if (initials.contains(v)) { 
      // add initial values to potential clique 
      potential_clique.add(v); 
     } else { 
      // only add to candidates if they are a neighbour of all other initials 
      boolean isCandidate = true; 
      for (V i : initials) { 
       if (!graph.isNeighbor(v, i)) { 
        isCandidate = false; 
        break; 
       } 
      } 
      if (isCandidate) { 
       candidates.add(v); 
      } 
     } 
    } 

    findCliques(potential_clique, candidates, already_found); 
    return cliques; 
} 

例如，從你的鏈接測試代碼，這個代碼現在打印含有V3和V4兩個派系：

public void testFindBiggestV3V4() 
{ 
    UndirectedGraph<String, String> g = new UndirectedSparseGraph<>(); 
    createGraph(g); 

    BronKerboschCliqueFinder2<String, String> finder = new BronKerboschCliqueFinder<>(g); 

    Collection<String> initials = new ArrayList<>(); 
    initials.add(V3); 
    initials.add(V4); 

    Collection<Set<String>> cliques = finder.getAllMaximalCliques(initials); 
    for (Set<String> clique : cliques) { 
     System.out.println(clique); 
    } 
} 

打印：

[v1, v4, v3, v2] 
[v5, v4, v3] 

在一個單獨的點上，寫這段代碼的方式創建了很多臨時數組。這乍看起來（我可以在這裏是錯誤的），一個頂點永遠只能是在四種狀態之一：潛在，候選人，發現，忽略，所以這將是一個有趣的方法只需向頂點對象添加一個狀態，使用單個全局集合（圖），並操縱整個過程中每個頂點的狀態，而不是不斷分配更多的數組。

不知道這是否會更快與否，並找出的唯一方法就是把它寫和嘗試，但會是什麼我想看看，如果我需要加快速度多一些。

無論如何，希望這有助於。