Jump to content

Bron–Kerbosch algorithm

From Rosetta Code
Task
Bron–Kerbosch algorithm
You are encouraged to solve this task according to the task description, using any language you may know.
Objective

Develop a program that identifies and lists all maximal cliques within an undirected graph. A maximal clique is a subset of vertices where every two distinct vertices are adjacent (i.e., there's an edge connecting them), and the clique cannot be extended by including any adjacent vertex not already in the clique.

Background

In graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are connected by an edge. A maximal clique is a clique that cannot be extended by adding one more adjacent vertex, meaning it's not a subset of a larger clique.

The Bron-Kerbosch algorithm is a recursive backtracking algorithm used to find all maximal cliques in an undirected graph efficiently. The algorithm is particularly effective due to its use of pivot selection, which reduces the number of recursive calls and improves performance.

Program Functionality
  1. Input Representation:
  • The graph is represented as a list of edges, where each edge is a tuple of two vertices (e.g., `('a', 'b')` indicates an undirected edge between vertices `'a'` and `'b'`).
  1. Graph Construction:
  • Convert the list of edges into an adjacency list using a `HashMap<String, HashSet<String>>`. Each key in the hashmap represents a vertex, and its corresponding hash set contains all adjacent vertices (neighbors).
  1. Bron-Kerbosch Algorithm Implementation:
  • Sets Used:
    • R (Current Clique): A set representing the current clique being constructed.
    • P (Potential Candidates): A set of vertices that can be added to R to form a larger clique.
    • X (Excluded Vertices): A set of vertices that have already been processed and should not be reconsidered for the current clique.
  • Algorithm Steps:
    • If both P and X are empty, and R contains more than two vertices, R is a maximal clique and is added to the list of cliques.
    • Otherwise, select a pivot vertex from the union of P and X that has the maximum number of neighbors. This pivot helps minimize the number of recursive calls.
    • Iterate over all vertices in P that are **not** neighbors of the pivot. For each such vertex:
      • Add the vertex to R.
      • Update P and X to include only those vertices that are neighbors of the added vertex.
      • Recursively call the Bron-Kerbosch function with the updated sets.
      • After recursion, move the vertex from P to X to mark it as processed.
  1. Output:
  • After executing the algorithm, the program prints all maximal cliques with more than two vertices. Each clique is displayed as a comma-separated list of its constituent vertices.
Example

Given the following edges:

('a', 'b'), ('b', 'a'), ('a', 'c'), ('c', 'a'), ('b', 'c'), ('c', 'b'),
('d', 'e'), ('e', 'd'), ('d', 'f'), ('f', 'd'), ('e', 'f'), ('f', 'e')

Expected Output:

a, b, c
d, e, f

These outputs represent the two maximal cliques in the graph: one comprising vertices `a`, `b`, and `c`, and the other comprising vertices `d`, `e`, and `f`.

Pseudocode

Below is the pseudocode for the Bron-Kerbosch algorithm with pivoting, closely following the Rust implementation provided earlier.

FUNCTION BronKerbosch(R, P, X, G, Cliques)
    // R: Current clique (Set)
    // P: Potential candidates to expand the clique (Set)
    // X: Vertices already processed (Set)
    // G: Graph represented as an adjacency list (Dictionary)
    // Cliques: List to store all maximal cliques (List of Lists)

    IF P is empty AND X is empty THEN
        IF size of R > 2 THEN
            SORT R lexicographically
            ADD R to Cliques
        END IF
        RETURN
    END IF

    // Select a pivot vertex from P ∪ X with the maximum degree
    Pivot := vertex in (P ∪ X) with the highest number of neighbors in G

    // Candidates are vertices in P that are not neighbors of the pivot
    Candidates := P - Neighbors(Pivot)

    FOR EACH vertex v IN Candidates DO
        // New clique including vertex v
        NewR := R ∪ {v}

        // New potential candidates are neighbors of v in P
        Neighbors_v := G[v]
        NewP := P ∩ Neighbors_v

        // New excluded vertices are neighbors of v in X
        NewX := X ∩ Neighbors_v

        // Recursive call with updated sets
        BronKerbosch(NewR, NewP, NewX, G, Cliques)

        // Move vertex v from P to X
        P := P - {v}
        X := X ∪ {v}
    END FOR
END FUNCTION

FUNCTION Main()
    // Define input edges as a list of tuples
    Input := [
        ('a', 'b'), ('b', 'a'), ('a', 'c'), ('c', 'a'),
        ('b', 'c'), ('c', 'b'), ('d', 'e'), ('e', 'd'),
        ('d', 'f'), ('f', 'd'), ('e', 'f'), ('f', 'e')
    ]

    // Build the graph as an adjacency list
    Graph := empty Dictionary
    FOR EACH (src, dest) IN Input DO
        IF src NOT IN Graph THEN
            Graph[src] := empty Set
        END IF
        ADD dest TO Graph[src]
    END FOR

    // Initialize R, P, X
    R := empty Set
    P := set of all vertices in Graph
    X := empty Set

    // Initialize list to store cliques
    Cliques := empty List

    // Execute the Bron-Kerbosch algorithm
    BronKerbosch(R, P, X, Graph, Cliques)

    // Sort the cliques for consistent output
    SORT Cliques lexicographically

    // Print each clique
    FOR EACH Clique IN Cliques DO
        PRINT elements of Clique separated by commas
    END FOR
END FUNCTION


C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

std::vector<std::vector<std::string>> cliques{};

struct Edge {
	std::string start;
	std::string end;
};

template <typename T>
void print_vector(const std::vector<T>& vec) {
	std::cout << "[";
	for ( uint32_t i = 0; i < vec.size() - 1; ++i ) {
		std::cout << vec[i] << ", ";
	}
	std::cout << vec.back() << "]";
}

template <typename T>
void print_2D_vector(const std::vector<std::vector<T>>& vecs) {
	std::cout << "[";
	for ( uint32_t i = 0; i < vecs.size() - 1; ++i ) {
		print_vector(vecs[i]); std::cout << ", ";
	}
	print_vector(vecs.back()); std::cout << "]" << std::endl;
}

void bron_kerbosch(const std::set<std::string>& current_clique,
				   std::set<std::string> candidates,
			       std::set<std::string> processed_vertices,
				   std::unordered_map<std::string, std::set<std::string>> graph) {

	if ( candidates.empty() && processed_vertices.empty() ) {
		if ( current_clique.size() > 2 ) {
			std::vector<std::string> clique(current_clique.begin(), current_clique.end());
			cliques.emplace_back(clique);
		}
		return;
	}

	// Select a pivot vertex from 'candidates' union 'processedVertices' with the maximum degree
	std::set<std::string> union_set(candidates.begin(), candidates.end());
	union_set.insert(processed_vertices.begin(), processed_vertices.end());
	const std::string pivot = *std::max_element(union_set.begin(), union_set.end(),
	    [&graph](const std::string& s1, const std::string& s2) { return graph[s1].size() < graph[s2].size(); });

	// 'possibles' are vertices in 'candidates' that are not neighbours of the 'pivot'
	std::set<std::string> possibles{};
	std::set_difference(candidates.begin(), candidates.end(),
		graph[pivot].begin(), graph[pivot].end(), std::inserter(possibles, possibles.begin()));

	for ( const std::string& vertex : possibles) {

		// Create a new clique including 'vertex'
		std::set<std::string> new_cliques(current_clique.begin(), current_clique.end());
		new_cliques.insert(vertex);

		// 'newCandidates' are the members of 'candidates' that are neighbours of 'vertex'
		std::set<std::string> new_candidates{};
		std::set_intersection(candidates.begin(), candidates.end(), graph[vertex].begin(), graph[vertex].end(),
			std::inserter(new_candidates, new_candidates.begin()));

		// 'newProcessedVertices' are members of 'processedVertices' that are neighbours of 'vertex'
		std::set<std::string> new_processed_vertices{};
		std::set_intersection(processed_vertices.begin(), processed_vertices.end(),
			graph[vertex].begin(), graph[vertex].end(),
			std::inserter(new_processed_vertices, new_processed_vertices.begin()));

		// Recursive call with the updated sets
		bron_kerbosch(new_cliques, new_candidates, new_processed_vertices, graph);

		// Move 'vertex' from 'candidates' to 'processedVertices'
		candidates.erase(vertex);
		processed_vertices.insert(vertex);
	}
}

int main() {
	const std::vector<Edge> edges = { Edge("a", "b"), Edge("b", "a"), Edge("a", "c"), Edge("c", "a"),
									  Edge("b", "c"), Edge("c", "b"), Edge("d", "e"), Edge("e", "d"),
									  Edge("d", "f"), Edge("f", "d"), Edge("e", "f"), Edge("f", "e") };

	// Build the graph as an adjacency list
	std::unordered_map<std::string, std::set<std::string>> graph{};
	std::for_each(edges.begin(), edges.end(),
		[&graph](const Edge& edge) { graph[edge.start].insert(edge.end); } );

	// Initialize current clique, candidates and processed vertices
	std::set<std::string> current_clique{};
	std::set<std::string> candidates{};
	std::transform(graph.begin(), graph.end(), std::inserter(candidates, candidates.end()),
	    [](const auto& pair) { return pair.first; } );
	std::set<std::string> processed_vertices{};

	// Execute the Bron-Kerbosch algorithm to collect the cliques
	bron_kerbosch(current_clique, candidates, processed_vertices, graph);

	// Sort the cliques for consistent display
	std::sort(cliques.begin(), cliques.end(),
		[](const std::vector<std::string>& a, const std::vector<std::string>& b) {
			for ( uint32_t i = 0; i < std::min(a.size(), b.size()); ++i ) {
				if ( a[i] != b[i] ) {
					return a[i] < b[i];
				}
			}
			return a.size() < b.size(); });

	// Display the cliques
	print_2D_vector(cliques);
}
Output:
[[a, b, c], [d, e, f]]

FreeBASIC

Type StringSet
    values(99) As String
    cnt As Integer
    
    Declare Sub add_(value As String)
    Declare Sub remove(value As String)
    Declare Function isEmpty() As Boolean
    Declare Function contains(value As String) As Boolean
    Declare Function copy() As StringSet
    Declare Function intersect(other As StringSet) As StringSet
    Declare Function union_(other As StringSet) As StringSet
    Declare Function except_(other As StringSet) As StringSet
End Type

Type Graph
    adjacency(99, 99) As Byte
    vertices(99) As String
    vertexCount As Integer
    
    Declare Sub aditionEdge(v1 As String, v2 As String)
    Declare Function getNeighbors(vertex As String) As StringSet
End Type

Type CliqueList
    cliques(99) As StringSet
    cnt As Integer
    
    Declare Sub add_(clique As StringSet)
End Type

' StringSet methods implementation
Sub StringSet.add_(value As String)
    If Not this.contains(value) Then
        this.values(this.cnt) = value
        this.cnt += 1
    End If
End Sub

Sub StringSet.remove(value As String)
    Dim As Integer i, j
    For i = 0 To this.cnt - 1
        If this.values(i) = value Then
            For j = i To this.cnt - 2
                this.values(j) = this.values(j + 1)
            Next
            this.cnt -= 1
            Exit For
        End If
    Next
End Sub

Function StringSet.isEmpty() As Boolean
    Return this.cnt = 0
End Function

Function StringSet.contains(value As String) As Boolean
    For i As Integer = 0 To this.cnt - 1
        If this.values(i) = value Then Return True
    Next
    Return False
End Function

Function StringSet.copy() As StringSet
    Dim As StringSet result
    result.cnt = this.cnt
    For i As Integer = 0 To this.cnt - 1
        result.values(i) = this.values(i)
    Next
    Return result
End Function

Function StringSet.intersect(other As StringSet) As StringSet
    Dim As StringSet result
    For i As Integer = 0 To this.cnt - 1
        If other.contains(this.values(i)) Then
            result.add_(this.values(i))
        End If
    Next
    Return result
End Function

Function StringSet.union_(other As StringSet) As StringSet
    Dim As StringSet result = this.copy()
    For i As Integer = 0 To other.cnt - 1
        result.add_(other.values(i))
    Next
    Return result
End Function

Function StringSet.except_(other As StringSet) As StringSet
    Dim As StringSet result
    For i As Integer = 0 To this.cnt - 1
        If Not other.contains(this.values(i)) Then
            result.add_(this.values(i))
        End If
    Next
    Return result
End Function

' Graph methods implementation
Sub Graph.aditionEdge(v1 As String, v2 As String)
    Dim As Integer v1idx = -1, v2idx = -1
    
    For i As Integer = 0 To this.vertexCount - 1
        If this.vertices(i) = v1 Then v1idx = i
        If this.vertices(i) = v2 Then v2idx = i
    Next
    
    If v1idx = -1 Then
        v1idx = this.vertexCount
        this.vertices(this.vertexCount) = v1
        this.vertexCount += 1
    End If
    
    If v2idx = -1 Then
        v2idx = this.vertexCount
        this.vertices(this.vertexCount) = v2
        this.vertexCount += 1
    End If
    
    this.adjacency(v1idx, v2idx) = 1
End Sub

Function Graph.getNeighbors(vertex As String) As StringSet
    Dim As StringSet result
    Dim As Integer vidx = -1, i
    
    For i = 0 To this.vertexCount - 1
        If this.vertices(i) = vertex Then
            vidx = i
            Exit For
        End If
    Next
    
    If vidx <> -1 Then
        For i = 0 To this.vertexCount - 1
            If this.adjacency(vidx, i) = 1 Then
                result.add_(this.vertices(i))
            End If
        Next
    End If
    
    Return result
End Function

' CliqueList methods
Sub CliqueList.add_(clique As StringSet)
    this.cliques(this.cnt) = clique
    this.cnt += 1
End Sub

' Bron-Kerbosch algorithm
Sub BronKerbosch(r As StringSet, p As StringSet, x As StringSet, g As Graph, Byref cliques As CliqueList)
    Dim As Integer i, j
    
    If p.isEmpty() Andalso x.isEmpty() Then
        If r.cnt > 2 Then
            ' Sort the clique before aditioning (simple bubble sort)
            For i = 0 To r.cnt - 2
                For j = 0 To r.cnt - 2 - i
                    If r.values(j) > r.values(j + 1) Then
                        Swap r.values(j), r.values(j + 1)
                    End If
                Next
            Next
            cliques.add_(r)
        End If
        Return
    End If
    
    ' Find pivot
    Dim As String pivot, v
    Dim As Integer maxC = -1
    Dim As StringSet unionSet = p.union_(x)
    
    For i = 0 To unionSet.cnt - 1
        v = unionSet.values(i)
        Dim As StringSet neighbors = g.getNeighbors(v)
        If neighbors.cnt > maxC Then
            maxC = neighbors.cnt
            pivot = v
        End If
    Next
    
    Dim As StringSet pivotNeighbors = g.getNeighbors(pivot)
    Dim As StringSet candidates = p.except_(pivotNeighbors)
    
    For i = 0 To candidates.cnt - 1
        v = candidates.values(i)
        Dim As StringSet newR = r.copy()
        newR.add_(v)
        
        Dim As StringSet neighbors = g.getNeighbors(v)
        Dim As StringSet newP = p.intersect(neighbors)
        Dim As StringSet newX = x.intersect(neighbors)
        
        BronKerbosch(newR, newP, newX, g, cliques)
        
        p.remove(v)
        x.add_(v)
    Next
End Sub

' Main program
Sub main()
    Dim As Integer i, j
    Dim As Graph g
    
    ' add_ edges
    g.aditionEdge("a", "b")
    g.aditionEdge("b", "a")
    g.aditionEdge("a", "c")
    g.aditionEdge("c", "a")
    g.aditionEdge("b", "c")
    g.aditionEdge("c", "b")
    g.aditionEdge("d", "e")
    g.aditionEdge("e", "d")
    g.aditionEdge("d", "f")
    g.aditionEdge("f", "d")
    g.aditionEdge("e", "f")
    g.aditionEdge("f", "e")
    
    Dim As StringSet r, p, x
    Dim As CliqueList cliques
    
    ' Initialize p with all vertices
    For i = 0 To g.vertexCount - 1
        p.add_(g.vertices(i))
    Next
    
    ' Execute algorithm
    BronKerbosch(r, p, x, g, cliques)
    
    ' Print results
    For i = 0 To cliques.cnt - 1
        Dim As StringSet clique = cliques.cliques(i)
        For j = 0 To clique.cnt - 1
            Print clique.values(j);
            If j < clique.cnt - 1 Then Print ", ";
        Next
        Print
    Next
End Sub

main()

Sleep
Output:
a, b, c
d, e, f

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public final class BronKerboschAlgorithm {

	public static void main(String[] args) {
		List<Edge> edges = List.of( new Edge("a", "b"), new Edge("b", "a"), new Edge("a", "c"), new Edge("c", "a"),
									new Edge("b", "c"), new Edge("c", "b"), new Edge("d", "e"), new Edge("e", "d"),
									new Edge("d", "f"), new Edge("f", "d"), new Edge("e", "f"), new Edge("f", "e") );
		
		// Build the graph as an adjacency list
	    Map<String, Set<String>> graph = new HashMap<String, Set<String>>();
	    edges.forEach( edge -> graph.computeIfAbsent(edge.start, v -> new HashSet<String>()).add(edge.end) );
	    
	    // Initialize current clique, candidates and processed vertices
	    Set<String> currentClique = new TreeSet<String>();
	    Set<String> candidates = new HashSet<String>(graph.keySet());
	    Set<String> processedVertices = new HashSet<String>();

	    // Execute the Bron-Kerbosch algorithm to collect the cliques
	    bronKerbosch(currentClique, candidates, processedVertices, graph);
	    
	    // Sort the cliques for consistent display
	    Collections.sort(cliques, listComparator);
	    
	    // Display the cliques
	    System.out.println(cliques);
	}
	
	private static void bronKerbosch(Set<String> currentClique, Set<String> candidates,
			                         Set<String> processedVertices, Map<String, Set<String>> graph) {
		
	    if ( candidates.isEmpty() && processedVertices.isEmpty() ) {
	        if ( currentClique.size() > 2 ) {
	            List<String> clique = new ArrayList<String>(currentClique);
	            cliques.add(clique);
	        }
	        return;
	    }
	    
	    // Select a pivot vertex from 'candidates' union 'processedVertices' with the maximum degree
	    Set<String> union = new HashSet<String>(candidates);
	    union.addAll(processedVertices);	 
	    String pivot = 
	    	union.stream().max( (s1, s2) -> Integer.compare(graph.get(s1).size(), graph.get(s2).size()) ).get();

	    // 'possibles' are vertices in 'candidates' that are not neighbours of the 'pivot'
	    Set<String> possibles = new HashSet<String>(candidates);
	    possibles.removeAll(graph.get(pivot));
	    
	    for ( String vertex : possibles) {
	        // Create a new clique including 'vertex'
	        Set<String> newCliques = new TreeSet<String>(currentClique);
	        newCliques.add(vertex);

	        // 'newCandidates' are the members of 'candidates' that are neighbours of 'vertex'
	        Set<String> neighbours = graph.get(vertex);
	        Set<String> newCandidates = new HashSet<String>(candidates);
	        newCandidates.retainAll(neighbours);

	        // 'newProcessedVertices' are members of 'processedVertices' that are neighbours of 'vertex'
	        Set<String> newProcessedVertices = new HashSet<String>(processedVertices);
	        newProcessedVertices.retainAll(neighbours);

	        // Recursive call with the updated sets
	        bronKerbosch(newCliques, newCandidates, newProcessedVertices, graph);

	        // Move 'vertex' from 'candidates' to 'processedVertices'
	        candidates.remove(vertex);
	        processedVertices.add(vertex);
	    }	    
	}
	
	private static Comparator<List<String>> listComparator = (list1, list2) -> {
        for ( int i = 0; i < Math.min(list1.size(), list2.size()); i++ ) {
            final int comparison = list1.get(i).compareTo(list2.get(i));
            if ( comparison != 0 ) {
                return comparison;
            }
        }
        return Integer.compare(list1.size(), list2.size());
	};
	
	private static List<List<String>> cliques = new ArrayList<List<String>>();
	
	private static record Edge(String start, String end) {}

}
Output:
[[a, b, c], [d, e, f]]

Julia

"""
For rosettacode.org/wiki/Bron–Kerbosch_algorithm

The implementation below is taken from the Graphs julia package at
https://github.com/JuliaGraphs/Graphs.jl/blob/ec6ab1b0e267e2b1722837aa113e8da9a405785b/src/community/cliques.jl

Because the Graphs.jl package uses integers for vertex labels, the letters in the Rust example are converted
to and from integers for program testing.
"""

mutable struct SimpleGraph{T <: Integer}
    ne::T
    vertices::Vector{T}
    edges::Set{Tuple{T, T}}
    adjacencies::Vector{Set{T}}
end

function SimpleGraph(ne::T, edge_list) where T <: Integer
    vertices = collect(1:ne)
    edges = Set{Tuple{T, T}}()
    sets = [Set{T}() for _ in vertices]
    for e in edge_list
        push!(edges, e, reverse(e))
        push!(sets[e[1]], e[2])
        push!(sets[e[2]], e[1])
    end
    return SimpleGraph{T}(ne, vertices, edges, sets)
end
vertices(g::SimpleGraph) = g.vertices
edges(g::SimpleGraph) = g.edges
neighbors(g, v) = g.adjacencies[v]

function Bron_Kerbosch_maximal_cliques(g::SimpleGraph{T}) where T
    max_connections = -1
    n_numbers = [Set{T}() for n in vertices(g)]
    pivot_numbers = Set{T}() # handle empty graph
    pivot_done_numbers = Set{T}()  # initialize

    for n in vertices(g)
        nbrs = Set{T}()
        union!(nbrs, neighbors(g, n))
        delete!(nbrs, n) # ignore edges between n and itself
        conn = length(nbrs)
        if conn > max_connections
            pivot_numbers = nbrs
            n_numbers[n] = pivot_numbers
            max_connections = conn
        else
            n_numbers[n] = nbrs
        end
    end

    # Initial setup
    cand = Set{T}(vertices(g))
    smallcand = setdiff(cand, pivot_numbers)
    done = Set{T}()
    stack = Vector{Tuple{Set{T}, Set{T}, Set{T}}}()
    clique_so_far = Vector{T}()
    cliques = Vector{Vector{T}}()

    # Start main loop
    while !isempty(smallcand) || !isempty(stack)
        if !isempty(smallcand) # Any vertices left to check?
            n = pop!(smallcand)
        else
            # back out clique_so_far
            cand, done, smallcand = pop!(stack)
            pop!(clique_so_far)
            continue
        end
        # Add next node to clique
        push!(clique_so_far, n)
        delete!(cand, n)
        push!(done, n)
        nn = n_numbers[n]
        new_cand = intersect(cand, nn)
        new_done = intersect(done, nn)
        # check if we have more to search
        if isempty(new_cand)
            if isempty(new_done)
                # Found a clique!
                push!(cliques, collect(clique_so_far))
            end
            pop!(clique_so_far)
            continue
        end
        # Shortcut--only one node left!
        if isempty(new_done) && length(new_cand) == 1
            push!(cliques, vcat(clique_so_far, collect(new_cand)))
            pop!(clique_so_far)
            continue
        end
        # find pivot node (max connected in cand)
        # look in done vertices first
        numb_cand = length(new_cand)
        max_connections_done = -1
        for n in new_done
            cn = intersect(new_cand, n_numbers[n])
            conn = length(cn)
            if conn > max_connections_done
                pivot_done_numbers = cn
                max_connections_done = conn
                if max_connections_done == numb_cand
                    break
                end
            end
        end
        # Shortcut--this part of tree already searched
        if max_connections_done == numb_cand
            pop!(clique_so_far)
            continue
        end
        # still finding pivot node
        # look in cand vertices second
        max_connections = -1
        for n in new_cand
            cn = intersect(new_cand, n_numbers[n])
            conn = length(cn)
            if conn > max_connections
                pivot_numbers = cn
                max_connections = conn
                if max_connections == numb_cand - 1
                    break
                end
            end
        end
        # pivot node is max connected in cand from done or cand
        if max_connections_done > max_connections
            pivot_numbers = pivot_done_numbers
        end
        # save search status for later backout
        push!(stack, (cand, done, smallcand))
        cand = new_cand
        done = new_done
        smallcand = setdiff(cand, pivot_numbers)
    end
    return cliques
end

char(i) = Char(Int32('a') + i - 1)
int(t) = Tuple(Int32(x) .- Int32('a') .+ 1 for x in t)

TEST_EDGES = [('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b'),
    ('d', 'e'), ('d', 'f'), ('e', 'd'), ('e', 'f'), ('f', 'd'), ('f', 'e')]
g_test = SimpleGraph(6, map(int, TEST_EDGES))

println("\nBron-Kerbosch maximal cliques: ")
println([sort!(map(char, clique)) for clique in Bron_Kerbosch_maximal_cliques(g_test)])
Output:
Bron-Kerbosch maximal cliques:
[['d', 'e', 'f'], ['a', 'b', 'c']]


Phix

Translation of: Wren

Note this uses an updated sets2.e, the experimental version of sets.e - download from the github repo and remove the requires statement to run (if/since 1.0.6 not yet shipped). Code to clean up no longer needed sets omitted for clarity and out of sheer laziness.

with javascript_semantics
requires("1.0.6")
include sets2.e

// Cliques: List to store all maximal cliques (List of Lists of strings)
sequence cliques = {}

procedure BronKerbosch(integer r, p, x, g)
    // r: Current clique (Set of strings)
    // p: Potential candidates to expand the clique (Set of strings)
    // x: Vertices already processed (Set of strings)
    // g: Graph represented as an adjacency list (Dict of strings to List of Strings)

    if is_empty(p) and is_empty(x) then
        if set_size(r)>2 then
            cliques = append(cliques,get_members(r))
        end if
        return
    end if
    
    // Select a pivot vertex from union(p,x) with the maximum degree.
    object pivot
    integer maxC = -1
    for v in union(p,x) do
        integer l = length(getd(v,g))
        if l>maxC then
            {maxC,pivot} = {l,v}
        end if
    end for

    // Candidates are vertices in P that are not neighbours of the pivot.
    sequence candidates = difference(p, getd(pivot,g), symmetric:=false)

    for v in candidates do
        // New clique including vertex v.
        integer newR = new_set(r)
        add_member(newR,v)

        // New potential candidates are neighbours of v in p.
        // New excluded vertices are neighbours of v in x.
        sequence neighbours = getd(v,g)
        integer newP = intersection(p,neighbours,-1),
                newX = intersection(x,neighbours,-1)

        // Recursive call with updated sets.
        BronKerbosch(newR, newP, newX, g)

        // Move vertex v from p to x.
        remove_member(p,v)
        add_member(x,v)
    end for
end procedure

// Define the input edges as a list of tuples.
constant input = {
    {"a", "b"}, {"b", "a"}, {"a", "c"}, {"c", "a"},
    {"b", "c"}, {"c", "b"}, {"d", "e"}, {"e", "d"},
    {"d", "f"}, {"f", "d"}, {"e", "f"}, {"f", "e"}
}

// Build the graph as an adjacency list.
integer graph = new_dict()
for t in input do
    setd(t[1],unique(deep_copy(getdd(t[1],{},graph))&{t[2]}),graph)
end for

// Initialize r, p, x.
integer r = new_set(),
        p = new_set(getd_all_keys(graph)),
        x = new_set()

// Execute the Bron-Kerbosch algorithm.
BronKerbosch(r, p, x, graph)

// Sort cliques for consistent output.
cliques = sort(deep_copy(cliques))
?cliques
Output:
{{"a","b","c"},{"d","e","f"}}

Raku

# Returns all maximal Cliques as sorted List of Lists.
sub BronKerbosch ( @undirected_edges ) {

    #| Adjacency list of the whole Graph, as immutable hash (Map) of immutable Sets.
    my Map $G = @undirected_edges
                .map({ |( .[0,1], .[1,0] ) })
                .classify( {.[0]}, :as{.[1]} )
                .duckmap( *.Set )
                .Map;

    #| Number of neighbors in G
    my Map $degree = $G.map({ .key => .value.elems }).Map;

    return gather BK();

    sub BK (
        Set     :$R         = Set.new,              #= Current clique
        SetHash :$P is copy = SetHash.new($G.keys), #= Potential candidates to expand the clique
        SetHash :$X is copy = SetHash.new,          #= Vertices already processed
    ) {
        if !$P and !$X {
            take $R.keys.sort.cache if $R.elems > 2;
            return;
        }

        my $Pivot = ($P$X).max({ $degree{$_} }).key;

        my @Candidates = ( $P (-) $G{$Pivot} ).keys;

        for $G{@Candidates}:kv -> $v, $Neighbors_of_v {

            &?ROUTINE.(     # Recursive call with updated sets
                R => ($R$v),
                P => ($P$Neighbors_of_v),
                X => ($X$Neighbors_of_v),
            );

            # Move vertex v from P to X
            $P{$v} = False;
            $X{$v} = True;
        }
    }
}

say .join(",") for sort BronKerbosch <a-b a-c b-c d-e d-f e-f>».split("-");
Output:
a,b,c
d,e,f

Ruby

require 'set'

def bron_kerbosch_v2(r, p, x, g, cliques)
  if p.empty? && x.empty?
    if r.size > 2
      cliques << r.to_a.sort
    end
    return
  end

  pivot = (p | x).max_by { |v| g[v]&.size.to_i }

  if pivot
    neighbors = g[pivot] || Set.new
    candidates = p - neighbors

    candidates.each do |v|
      new_r = r.dup.add(v)
      neighbors_v = g[v] || Set.new
      new_p = p & neighbors_v
      new_x = x & neighbors_v

      bron_kerbosch_v2(new_r, new_p, new_x, g, cliques)

      p.delete(v)
      x.add(v)
    end
  end
end

def main
  input = [
    ['a', 'b'], ['b', 'a'], ['a', 'c'], ['c', 'a'],
    ['b', 'c'], ['c', 'b'], ['d', 'e'], ['e', 'd'],
    ['d', 'f'], ['f', 'd'], ['e', 'f'], ['f', 'e']
  ]

  graph = Hash.new { |hash, key| hash[key] = Set.new }
  input.each do |src, dest|
    graph[src].add(dest)
  end

  r = Set.new
  p = graph.keys.to_set
  x = Set.new
  cliques = []

  bron_kerbosch_v2(r, p, x, graph, cliques)

  sorted_cliques = cliques.sort

  sorted_cliques.each do |clique|
    puts clique.join(', ')
  end
end

main

Rust

use std::collections::{HashMap, HashSet};

fn bron_kerbosch_v2(
    r: &HashSet<String>,
    p: &mut HashSet<String>,
    x: &mut HashSet<String>,
    g: &HashMap<String, HashSet<String>>,
    cliques: &mut Vec<Vec<String>>,
) {
    if p.is_empty() && x.is_empty() {
        if r.len() > 2 {
            let mut clique: Vec<String> = r.iter().cloned().collect();
            clique.sort();
            cliques.push(clique);
        }
        return;
    }

    // Choose a pivot with the maximum degree in P ∪ X
    let pivot = p
        .union(x)
        .max_by_key(|v| g.get(*v).map_or(0, |neighbors| neighbors.len()))
        .cloned();

    if let Some(pivot_vertex) = pivot {
        let neighbors = g.get(&pivot_vertex).cloned().unwrap_or_default();
        let candidates: Vec<String> = p.difference(&neighbors).cloned().collect();

        for v in candidates {
            // New R is R ∪ {v}
            let mut new_r = r.clone();
            new_r.insert(v.clone());

            // New P is P ∩ N(v)
            let neighbors_v = g.get(&v).cloned().unwrap_or_default();
            let mut new_p = p.intersection(&neighbors_v).cloned().collect::<HashSet<String>>();

            // New X is X ∩ N(v)
            let mut new_x = x.intersection(&neighbors_v).cloned().collect::<HashSet<String>>();

            // Recursive call
            bron_kerbosch_v2(&new_r, &mut new_p, &mut new_x, g, cliques);

            // Move v from P to X
            p.remove(&v);
            x.insert(v);
        }
    }
}

fn main() {
    // Define the input edges
    let input = vec![
        ("a", "b"),
        ("b", "a"),
        ("a", "c"),
        ("c", "a"),
        ("b", "c"),
        ("c", "b"),
        ("d", "e"),
        ("e", "d"),
        ("d", "f"),
        ("f", "d"),
        ("e", "f"),
        ("f", "e"),
    ];

    // Build the graph as an adjacency list
    let mut graph: HashMap<String, HashSet<String>> = HashMap::new();
    for (src, dest) in input.iter() {
        graph
            .entry(src.to_string())
            .or_insert_with(HashSet::new)
            .insert(dest.to_string());
    }

    // Initialize R, P, X
    let r: HashSet<String> = HashSet::new();
    let mut p: HashSet<String> = graph.keys().cloned().collect();
    let mut x: HashSet<String> = HashSet::new();

    // Collect cliques
    let mut cliques: Vec<Vec<String>> = Vec::new();
    bron_kerbosch_v2(&r, &mut p, &mut x, &graph, &mut cliques);

    // Sort the cliques for consistent output
    let mut sorted_cliques = cliques.clone();
    sorted_cliques.sort();

    // Print each clique
    for clique in sorted_cliques {
        println!("{}", clique.join(", "));
    }
}

Wren

Library: Wren-set
Library: Wren-sort
import "./set" for Set
import "./sort" for Sort

// r: Current clique (Set of strings)
// p: Potential candidates to expand the clique (Set of strings)
// x: Vertices already processed (Set of strings)
// g: Graph represented as an adjacency list (Map of strings to Sets)
// Cliques: List to store all maximal cliques (List of Lists of strings)
var BronKerbosch = Fn.new { |r, p, x, g, cliques|
    if (p.isEmpty && x.isEmpty) {
        if (r.count > 2) {
            var clique = r.toList
            Sort.quick(clique)
            cliques.add(clique)
        }
        return
    }

    // Select a pivot vertex from P ∪ X with the maximum degree.
    var pivot = p.union(x).max { |v| g[v] ? g[v].count : 0 }

    // Candidates are vertices in P that are not neighbors of the pivot.
    var candidates = p.except(g[pivot])

    for (v in candidates) {
        // New clique including vertex v.
        var newR = r.copy()
        newR.add(v)

        // New potential candidates are neighbors of v in p.
        var neighbors = g[v]
        var newP = p.intersect(neighbors)

        // New excluded vertices are neighbors of v in x.
        var newX = x.intersect(neighbors)

        // Recursive call with updated sets.
        BronKerbosch.call(newR, newP, newX, g, cliques)

        // Move vertex v from p to x.
        p.remove(v)
        x.add(v)
    }
}

// Define the input edges as a list of tuples.
var input = [
    ["a", "b"], ["b", "a"], ["a", "c"], ["c", "a"],
    ["b", "c"], ["c", "b"], ["d", "e"], ["e", "d"],
    ["d", "f"], ["f", "d"], ["e", "f"], ["f", "e"]
]

// Build the graph as an adjacency list.
var graph = {}
for (t in input) {
    if (!graph.containsKey(t[0])) graph[t[0]] = Set.new()
    graph[t[0]].add(t[1])
}

// Initialize r, p, x.
var r = Set.new()
var p = Set.new(graph.keys)
var x = Set.new()

// Initialize list to store cliques.
var cliques = []

// Execute the Bron-Kerbosch algorithm.
BronKerbosch.call(r, p, x, graph, cliques)

// Sort the cliqes for consistent output.
Sort.quick(cliques)

// Print each clique.
for (clique in cliques) {
    System.print(clique.join(", "))
}
Output:
a, b, c
d, e, f
Cookies help us deliver our services. By using our services, you agree to our use of cookies.