2

我正在尝试解决集团问题。我正在使用 Bron Kerbosch Clique 算法，它很好地用 java 编写，一个聪明的实现可以在这里找到。然而，由于派系的硬度，它可能非常缓慢，

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

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

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方法上。我不太确定递归调用方法在这里是如何工作的。

如果可以提供任何帮助或指导，我将不胜感激。

4

1 回答 1

2

因此，如果我对您的理解正确，您正在尝试使用您已经知道是子集团的部分解决方案来启动递归，以减少所需的递归步骤的数量？

在这种情况下，我认为您误入歧途的地方是启动候选人阵列。在进入递归函数的任何时候，候选数组包含所有不在潜在团中但单独连接到潜在团的所有成员的图元素。最后一点是您错过的一点：您已经为候选者准备了所有剩余的图形元素，这为其余的递归设置了无效状态。

所以试试这个：

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]

另一方面，这段代码的编写方式创建了很多临时数组。乍一看（这里我可能错了）一个顶点只能处于以下四种状态之一：潜在、候选、发现、忽略，因此将状态添加到顶点对象将是一种有趣的方法，使用单个全局集合（图），并在整个过程中操纵每个顶点的状态，而不是不断地分配更多的数组。

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

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

于 2015-01-19T11:01:53.957 回答