CODEWITHSUNDEEP
algorithmgraph-theory
Bean Greasy
Bean Greasy

Reputation: 1

Why isn't this implementation of Bron–Kerbosch algorithm correct?

class Node(object):

    def __init__(self, name):
        self.name = name
        self.neighbors = []

    def __repr__(self):
        return self.name


A = Node('A')
B = Node('B')
C = Node('C')
D = Node('D')
E = Node('E')
F = Node('F')
G = Node('G')
H = Node('H')




A.neighbors = [B, E, F, G, H]
B.neighbors = [A, C, E, F, H]
C.neighbors = [ B, D, G, H]
D.neighbors = [C, E, G]
E.neighbors = [A, B, D, F]
F.neighbors = [A, B, E, G]
G.neighbors = [A, C, D, F, H]
H.neighbors = [A, B, C, G]

all_nodes = [A, B, C, D, E, F, G, H]


def find_cliques(potential_clique=[], remaining_nodes=[], skip_nodes=[], depth=0):

    if len(remaining_nodes) == 0 and len(skip_nodes) == 0:
        print('This is a clique:', potential_clique)
        return 1

    found_cliques = 0
    for node in remaining_nodes:

        # Try adding the node to the current potential_clique to see if we can make it work.
        new_potential_clique = potential_clique + [node]
        new_remaining_nodes = [n for n in remaining_nodes if n in node.neighbors]
        new_skip_list = [n for n in skip_nodes if n in node.neighbors]
        found_cliques += find_cliques(new_potential_clique, new_remaining_nodes, new_skip_list, depth + 1)

        # We're done considering this node.  If there was a way to form a clique with it, we
        # already discovered its maximal clique in the recursive call above.  So, go ahead
        # and remove it from the list of remaining nodes and add it to the skip list.
        remaining_nodes.remove(node)
        skip_nodes.append(node)
    return found_cliques

total_cliques = find_cliques(remaining_nodes=all_nodes)
print('Total cliques found:', total_cliques)

When illustrated it becomes quite clear there are far more cliques than this. Why is this missing say, [A,B,F] or [A,B,E]?

I'm trying to find all the disjoint cycles of this graph, and I identified the BK algorithm as a necessary preliminary step. But I can't find any good code implementations of it, and I thought this would suffice, but it appears it does not.

Why not?

Upvotes: 0

Views: 146

Answers (1)

Adam Jamil
Adam Jamil

Reputation: 21

Because the BK algorithm is for finding maximal cliques. A maximal clique is a set of vertices S such that for any vertex v, either v is already in S, or adding v to S would not give you a clique.

Consider the clique {A, B, E, F}. {A, B, E} is a subset, and therefore also a clique. Thus, it doesn't help you to get out {A, B, E} - you could just iterate through all the subsets of the maximal cliques.

Upvotes: 1

Related Questions