I'm trying to solve clique problem. I'm using Bron Kerbosch Clique algorithm,which nicely written in java a clever implementaion can be found here. However, thanks to clique hardness, it can be extremely slow,
What I want to do is to use an initial set of vertices that I know they are connected. then call the method. For the life of me I'm not sure what I'm doing wrong here that the results are not cliques.
NOTE: commented codes are from original codes(linked above).
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;
}
}
So in short my only changes are in getAllMaximalCliques method.
I don't quite sure how the recursive call method works in here.
I'll appreciate if any help or direction could be given.
So if I understand you correctly, you're trying to prime the recursion with a partial solution which you already know to be a sub-clique, in order to reduce the number of recursive steps required?
In that case, I think where you've gone astray is in priming the candidates array. At any point when entering the recursive function, the candidates array contains all graph elements which are not in the potential clique, but which are individually connected to all members of the potential clique. This last bit is the bit you've missed: you've primed the candidates with all the remaining graph elements, which sets an invalid state for the rest of the recursion.
So try this:
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;
}
For example, from the test code in your link, this code now prints the two cliques containing both V3 and 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);
}
}
Prints:
[v1, v4, v3, v2]
[v5, v4, v3]
On a separate point, the way this code is written creates a lot of temporary arrays. It seems at first glance (and I could be wrong here) that a vertex can only ever be in one of four states: potential, candidate, found, ignored, so it would be an interesting approach to just add a state to the vertex object, use a single global collection (the graph), and manipulate the state of each vertex throughout the process, rather than continually allocating more arrays.
No idea if this would be faster or not, and the only way to find out is to write it and try it, but would be something I'd look at if I needed to speed it up some more.
Anyway, hope this helps.