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] 

在一个单独的点上，写这段代码的方式创建了很多临时数组。这乍看起来（我可以在这里是错误的），一个顶点永远只能是在四种状态之一：潜在，候选人，发现，忽略，所以这将是一个有趣的方法只需向顶点对象添加一个状态，使用单个全局集合（图），并操纵整个过程中每个顶点的状态，而不是不断分配更多的数组。

不知道这是否会更快与否，并找出的唯一方法就是把它写和尝试，但会是什么我想看看，如果我需要加快速度多一些。

无论如何，希望这有助于。