mathspp
  • Blog
    • Pydon'ts
    • Problems
    • TIL
    • Twitter threads
  • Books
  • Talks
  • Trainings
    • Advanced iteration
    • Python for scripting and automation
    • Rust for Python developers
  • Courses
  • About
Link blog

Bron-Kerbosch algorithm

on 24-12-2024 17:39 (via)

This year I've been solving Advent of Code consistently and for day 23 I had to implement a small algorithm that finds clicks in a graph. My recursive function isn't particularly clever but stands at 5 lines of code:

def find_clicks(click, nodes, edges):
    for idx, node in enumerate(nodes):
        if click <= edges[node]:
            yield from find_clicks(click | {node}, nodes[idx + 1 :], edges)

    yield click

nodes is a list of all the vertices in the graph and edges is a mapping from vertex to set of neighoubrs. Initially, call it with find_clicks(set(), nodes, edges). The generator yields sub-maximal clicks but this was good enough for my purposes. I was pleasantly surprised (but not too surprised) to find later that there is an algorithm that finds maximal clicks in a graph.

Previous link Next link

I know a proof that there's irrational numbers that one to the power of the other give a rational number and this footer is almost the right size for it.

mathspp
  • Blog
    • Pydon'ts
    • Problems
    • TIL
    • Twitter threads
  • Books
  • Talks
  • Trainings
    • Advanced iteration
    • Python for scripting and automation
    • Rust for Python developers
  • Courses
  • About