Использование рекурсивного метода для клики
Я пытаюсь решить проблему клики. Я использую алгоритм 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 метод. Я не совсем уверен, как здесь работает метод рекурсивного вызова.
Я буду признателен, если будет оказана помощь или направление.
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]
С другой стороны, способ написания этого кода создает много временных массивов. На первый взгляд кажется (и я могу ошибаться), что вершина может быть только в одном из четырех состояний: потенциальный, кандидат, найден, проигнорирован, так что было бы интересным просто добавить состояние в объект вершины. используйте одну глобальную коллекцию (график) и управляйте состоянием каждой вершины на протяжении всего процесса, а не постоянно выделяйте больше массивов.
Не знаю, будет ли это быстрее или нет, и единственный способ выяснить это - написать и попробовать, но я бы посмотрел на это, если бы мне нужно было еще немного ускорить его.
В любом случае, надеюсь, это поможет.