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
- 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'`).
- 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).
- 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.
- 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
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
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