对 Clique 使用递归方法

Question

我正在尝试解决 clique problem。我正在使用 Bron Kerbosch Clique algorithm,which nicely written in java a clever implementaion can be found here。但是，由于 clique hardness，它可能非常慢，

我想做的是使用一组我知道它们相互连接的初始顶点。然后调用方法。对于我的一生，我不确定我在这里做错了什么，结果不是小集团。

注意：注释代码来自原始代码（上面链接）。

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;
}

例如，根据您 link 中的测试代码，此代码现在打印包含 V3 和 V4 的两个 cliques：

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]

另外一点，这段代码的编写方式会创建很多临时数组。乍一看（我在这里可能是错的）似乎顶点只能处于四种状态之一：potential、candidate、 found，ignored，所以使用单个全局集合（图）将状态添加到顶点对象将是一种有趣的方法，并在整个过程中操纵每个顶点的状态，而不是不断地分配更多的数组。

不知道这是否会更快，找出答案的唯一方法是编写并尝试，但如果我需要进一步加快速度，我会看看它。

无论如何，希望这对您有所帮助。

对 Clique 使用递归方法

Using recursive method for Clique

java

recursion

clique-problem