3

I am currently trying to make an algorithm for finding cliques in a graph, and luckily I found the documentation from Networkx for a function that does just that. Unfortunately, the variable names are a little terse and I'm having trouble understanding what each part of the code does.

Here is the code for find_cliques:

def find_cliques(G):
    if len(G) == 0:
        return

    adj = {u: {v for v in G[u] if v != u} for u in G}
    Q = [None]

    subg = set(G)
    cand = set(G)
    u = max(subg, key=lambda u: len(cand & adj[u]))
    ext_u = cand - adj[u]
    stack = []

    try:
        while True:
            if ext_u:
                q = ext_u.pop()
                cand.remove(q)
                Q[-1] = q
                adj_q = adj[q]
                subg_q = subg & adj_q
                if not subg_q:
                    yield Q[:]
                else:
                    cand_q = cand & adj_q
                    if cand_q:
                        stack.append((subg, cand, ext_u))
                        Q.append(None)
                        subg = subg_q
                        cand = cand_q
                        u = max(subg, key=lambda u: len(cand & adj[u]))
                        ext_u = cand - adj[u]
            else:
                Q.pop()
                subg, cand, ext_u = stack.pop()
    except IndexError:
        pass

It works just fie, but I just want to understand what is happening here, and I can't seem to find any resources online explaining it.

NeonCop
  • 75
  • 1
  • 2
  • 12

1 Answers1

2

The documentation of the find_cliques method lists three references for this algorithm. You may want to look at them or you take a look at wikipedia.

Some variables:

adj= dictionary storing for each node the neighbours as a set

u= the node with the highest number of neighbours, which do not belong to other clique.

ext_u = all neighbours of u, which are not member of another clique

Sparky05
  • 4,692
  • 1
  • 10
  • 27