Bron–Kerbosch algorithm
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.

You are encouraged to solve this task according to the task description, using any language you may know.
- Objective
- 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
using System;
using System.Collections.Generic;
using System.Linq;
public class BronKerboschAlgorithm
{
private static List<List<string>> cliques = new List<List<string>>();
public static void Main(string[] args)
{
var edges = new List<Edge>
{
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
var graph = new Dictionary<string, HashSet<string>>();
foreach (var edge in edges)
{
if (!graph.ContainsKey(edge.Start))
graph[edge.Start] = new HashSet<string>();
graph[edge.Start].Add(edge.End);
}
// Initialize current clique, candidates and processed vertices
var currentClique = new SortedSet<string>();
var candidates = new HashSet<string>(graph.Keys);
var processedVertices = new HashSet<string>();
// Execute the Bron-Kerbosch algorithm to collect the cliques
BronKerbosch(currentClique, candidates, processedVertices, graph);
// Sort the cliques for consistent display
cliques = cliques.OrderBy(c => c, new ListComparer()).ToList();
// Display the cliques
Console.WriteLine("[{0}]", string.Join(", ", cliques.Select(c => "[" + string.Join(", ", c) + "]")));
}
private static void BronKerbosch(
SortedSet<string> currentClique,
HashSet<string> candidates,
HashSet<string> processedVertices,
Dictionary<string, HashSet<string>> graph)
{
if (candidates.Count == 0 && processedVertices.Count == 0)
{
if (currentClique.Count > 2)
{
cliques.Add(new List<string>(currentClique));
}
return;
}
// Select a pivot vertex from 'candidates' union 'processedVertices' with the maximum degree
var union = new HashSet<string>(candidates);
union.UnionWith(processedVertices);
string pivot = union.OrderByDescending(v => graph.ContainsKey(v) ? graph[v].Count : 0).First();
// 'possibles' are vertices in 'candidates' that are not neighbours of the 'pivot'
var possibles = new HashSet<string>(candidates);
if (graph.ContainsKey(pivot))
possibles.ExceptWith(graph[pivot]);
foreach (var vertex in possibles)
{
// Create a new clique including 'vertex'
var newClique = new SortedSet<string>(currentClique);
newClique.Add(vertex);
// 'newCandidates' are the members of 'candidates' that are neighbours of 'vertex'
var neighbours = graph.ContainsKey(vertex) ? graph[vertex] : new HashSet<string>();
var newCandidates = new HashSet<string>(candidates);
newCandidates.IntersectWith(neighbours);
// 'newProcessedVertices' are members of 'processedVertices' that are neighbours of 'vertex'
var newProcessedVertices = new HashSet<string>(processedVertices);
newProcessedVertices.IntersectWith(neighbours);
// Recursive call with the updated sets
BronKerbosch(newClique, newCandidates, newProcessedVertices, graph);
// Move 'vertex' from 'candidates' to 'processedVertices'
candidates.Remove(vertex);
processedVertices.Add(vertex);
}
}
private class ListComparer : IComparer<List<string>>
{
public int Compare(List<string> x, List<string> y)
{
for (int i = 0; i < Math.Min(x.Count, y.Count); i++)
{
int comparison = x[i].CompareTo(y[i]);
if (comparison != 0)
return comparison;
}
return x.Count.CompareTo(y.Count);
}
}
private class Edge
{
public string Start { get; }
public string End { get; }
public Edge(string start, string end)
{
Start = start;
End = end;
}
}
}
- Output:
[[a, b, c], [d, e, f]]
#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]]
List<List<String>> cliques = [];
class Edge {
String start;
String end;
Edge(this.start, this.end);
}
void printVector<T>(List<T> vec) {
StringBuffer sb = StringBuffer();
sb.write('[');
for (int i = 0; i < vec.length - 1; i++) {
sb.write('${vec[i]}, ');
}
sb.write('${vec.last}]');
print(sb.toString());
}
void print2DVector<T>(List<List<T>> vecs) {
StringBuffer sb = StringBuffer();
sb.write('[');
for (int i = 0; i < vecs.length - 1; i++) {
printVector(vecs[i]);
sb.write(', ');
}
printVector(vecs.last);
sb.write(']');
}
void bronKerbosch(
Set<String> currentClique, Set<String> candidates, Set<String> processedVertices, Map<String, Set<String>> graph) {
if (candidates.isEmpty && processedVertices.isEmpty) {
if (currentClique.length > 2) {
cliques.add(List<String>.from(currentClique));
}
return;
}
// Select a pivot vertex from 'candidates' union 'processedVertices' with the maximum degree
Set<String> unionSet = Set<String>.from(candidates)..addAll(processedVertices);
String pivot = unionSet.reduce((s1, s2) => graph[s1]!.length > graph[s2]!.length ? s1 : s2);
// 'possibles' are vertices in 'candidates' that are not neighbors of the 'pivot'
Set<String> possibles = candidates.difference(graph[pivot]!);
for (String vertex in possibles) {
// Create a new clique including 'vertex'
Set<String> newCliques = Set<String>.from(currentClique)..add(vertex);
// 'newCandidates' are the members of 'candidates' that are neighbors of 'vertex'
Set<String> newCandidates = candidates.intersection(graph[vertex]!);
// 'newProcessedVertices' are members of 'processedVertices' that are neighbors of 'vertex'
Set<String> newProcessedVertices = processedVertices.intersection(graph[vertex]!);
// Recursive call with the updated sets
bronKerbosch(newCliques, newCandidates, newProcessedVertices, graph);
// Move 'vertex' from 'candidates' to 'processedVertices'
candidates.remove(vertex);
processedVertices.add(vertex);
}
}
void main() {
List<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
Map<String, Set<String>> graph = {};
edges.forEach((edge) {
graph.putIfAbsent(edge.start, () => <String>{}).add(edge.end);
});
// Initialize current clique, candidates, and processed vertices
Set<String> currentClique = {};
Set<String> candidates = graph.keys.toSet();
Set<String> processedVertices = {};
// Execute the Bron-Kerbosch algorithm to collect the cliques
bronKerbosch(currentClique, candidates, processedVertices, graph);
// Sort the cliques for consistent display
cliques.sort((a, b) {
for (int i = 0; i < a.length && i < b.length; i++) {
if (a[i] != b[i]) {
return a[i].compareTo(b[i]);
}
}
return a.length.compareTo(b.length);
});
// Display the cliques
print2DVector(cliques);
}
- Output:
[a, c, b] [f, e, d]
program bron_kerbosch_cliques
implicit none
! Maximum number of vertices and cliques
integer, parameter :: MAX_VERTICES = 100
integer, parameter :: MAX_CLIQUES = 1000
integer, parameter :: MAX_EDGES = 1000
integer, parameter :: MAX_NAME_LEN = 10
! Graph representation using adjacency matrix and vertex names
logical :: adjacency_matrix(MAX_VERTICES, MAX_VERTICES)
character(len=MAX_NAME_LEN) :: vertex_names(MAX_VERTICES)
integer :: num_vertices
! Cliques storage
integer :: cliques(MAX_CLIQUES, MAX_VERTICES)
integer :: clique_sizes(MAX_CLIQUES)
integer :: num_cliques
! Edge structure
type :: edge_type
character(len=MAX_NAME_LEN) :: start
character(len=MAX_NAME_LEN) :: end
end type edge_type
! Local variables
type(edge_type) :: edges(MAX_EDGES)
integer :: num_edges
logical :: current_clique(MAX_VERTICES)
logical :: candidates(MAX_VERTICES)
logical :: processed(MAX_VERTICES)
integer :: i, j
! Initialize
num_vertices = 0
num_cliques = 0
num_edges = 12
! Initialize adjacency matrix
adjacency_matrix = .false.
! Define edges
edges(1) = edge_type("a", "b")
edges(2) = edge_type("b", "a")
edges(3) = edge_type("a", "c")
edges(4) = edge_type("c", "a")
edges(5) = edge_type("b", "c")
edges(6) = edge_type("c", "b")
edges(7) = edge_type("d", "e")
edges(8) = edge_type("e", "d")
edges(9) = edge_type("d", "f")
edges(10) = edge_type("f", "d")
edges(11) = edge_type("e", "f")
edges(12) = edge_type("f", "e")
! Build graph
call build_graph(edges, num_edges)
! Initialize sets for Bron-Kerbosch
current_clique = .false.
candidates = .false.
processed = .false.
! Set all vertices as candidates
do i = 1, num_vertices
candidates(i) = .true.
end do
! Run Bron-Kerbosch algorithm
call bron_kerbosch_recursive(current_clique, candidates, processed)
! Sort and display cliques
call sort_cliques()
call print_cliques()
contains
! Function to find vertex index by name
function find_vertex_index(name) result(index)
implicit none
character(len=*), intent(in) :: name
integer :: index
integer :: i
do i = 1, num_vertices
if (trim(vertex_names(i)) == trim(name)) then
index = i
return
end if
end do
! Add new vertex if not found
num_vertices = num_vertices + 1
vertex_names(num_vertices) = trim(name)
index = num_vertices
end function find_vertex_index
! Subroutine to build graph from edges
subroutine build_graph(edges_array, n_edges)
implicit none
type(edge_type), intent(in) :: edges_array(:)
integer, intent(in) :: n_edges
integer :: i, start_idx, end_idx
do i = 1, n_edges
start_idx = find_vertex_index(edges_array(i)%start)
end_idx = find_vertex_index(edges_array(i)%end)
adjacency_matrix(start_idx, end_idx) = .true.
end do
end subroutine build_graph
! Count number of true values in logical array
function count_true(logical_array) result(count)
implicit none
logical, intent(in) :: logical_array(:)
integer :: count
integer :: i
count = 0
do i = 1, num_vertices
if (logical_array(i)) count = count + 1
end do
end function count_true
! Find pivot vertex with maximum degree
function find_pivot(candidates_set, processed_set) result(pivot)
implicit none
logical, intent(in) :: candidates_set(:), processed_set(:)
integer :: pivot
integer :: i, max_degree, current_degree
logical :: union_set(MAX_VERTICES)
! Create union of candidates and processed
do i = 1, num_vertices
union_set(i) = candidates_set(i) .or. processed_set(i)
end do
max_degree = -1
pivot = 1
do i = 1, num_vertices
if (union_set(i)) then
current_degree = count_neighbors(i)
if (current_degree > max_degree) then
max_degree = current_degree
pivot = i
end if
end if
end do
end function find_pivot
! Count neighbors of a vertex
function count_neighbors(vertex) result(count)
implicit none
integer, intent(in) :: vertex
integer :: count
integer :: i
count = 0
do i = 1, num_vertices
if (adjacency_matrix(vertex, i)) count = count + 1
end do
end function count_neighbors
! Set difference: result = set_a - set_b
subroutine set_difference(set_a, set_b, result_set)
implicit none
logical, intent(in) :: set_a(:), set_b(:)
logical, intent(out) :: result_set(:)
integer :: i
do i = 1, num_vertices
result_set(i) = set_a(i) .and. .not. set_b(i)
end do
end subroutine set_difference
! Set intersection: result = set_a ∩ set_b
subroutine set_intersection(set_a, set_b, result_set)
implicit none
logical, intent(in) :: set_a(:), set_b(:)
logical, intent(out) :: result_set(:)
integer :: i
do i = 1, num_vertices
result_set(i) = set_a(i) .and. set_b(i)
end do
end subroutine set_intersection
! Get neighbors of a vertex
subroutine get_neighbors(vertex, neighbors_set)
implicit none
integer, intent(in) :: vertex
logical, intent(out) :: neighbors_set(:)
integer :: i
do i = 1, num_vertices
neighbors_set(i) = adjacency_matrix(vertex, i)
end do
end subroutine get_neighbors
! Recursive Bron-Kerbosch algorithm
recursive subroutine bron_kerbosch_recursive(current_clique_set, candidates_set, processed_set)
implicit none
logical, intent(in) :: current_clique_set(:)
logical, intent(inout) :: candidates_set(:), processed_set(:)
logical :: new_clique(MAX_VERTICES)
logical :: new_candidates(MAX_VERTICES)
logical :: new_processed(MAX_VERTICES)
logical :: possibles(MAX_VERTICES)
logical :: neighbors(MAX_VERTICES)
logical :: pivot_neighbors(MAX_VERTICES)
integer :: pivot, vertex
integer :: clique_size, i
! If both candidates and processed are empty, we found a maximal clique
if (count_true(candidates_set) == 0 .and. count_true(processed_set) == 0) then
clique_size = count_true(current_clique_set)
if (clique_size > 2) then
call store_clique(current_clique_set)
end if
return
end if
! Find pivot vertex
pivot = find_pivot(candidates_set, processed_set)
call get_neighbors(pivot, pivot_neighbors)
! Get vertices in candidates that are not neighbors of pivot
call set_difference(candidates_set, pivot_neighbors, possibles)
! For each vertex in possibles
do vertex = 1, num_vertices
if (.not. possibles(vertex)) cycle
! Create new clique including vertex
new_clique = current_clique_set
new_clique(vertex) = .true.
! Get neighbors of vertex
call get_neighbors(vertex, neighbors)
! New candidates = candidates ∩ neighbors(vertex)
call set_intersection(candidates_set, neighbors, new_candidates)
! New processed = processed ∩ neighbors(vertex)
call set_intersection(processed_set, neighbors, new_processed)
! Recursive call
call bron_kerbosch_recursive(new_clique, new_candidates, new_processed)
! Move vertex from candidates to processed
candidates_set(vertex) = .false.
processed_set(vertex) = .true.
end do
end subroutine bron_kerbosch_recursive
! Store a clique
subroutine store_clique(clique_set)
implicit none
logical, intent(in) :: clique_set(:)
integer :: i, size
if (num_cliques >= MAX_CLIQUES) return
num_cliques = num_cliques + 1
size = 0
do i = 1, num_vertices
if (clique_set(i)) then
size = size + 1
cliques(num_cliques, size) = i
end if
end do
clique_sizes(num_cliques) = size
end subroutine store_clique
! Sort cliques for consistent output
subroutine sort_cliques()
implicit none
integer :: i, j, k
integer :: temp_clique(MAX_VERTICES)
integer :: temp_size
logical :: swap_needed
! Simple bubble sort
do i = 1, num_cliques - 1
do j = i + 1, num_cliques
swap_needed = .false.
! Compare cliques lexicographically
do k = 1, min(clique_sizes(i), clique_sizes(j))
if (vertex_names(cliques(i, k)) < vertex_names(cliques(j, k))) then
exit
else if (vertex_names(cliques(i, k)) > vertex_names(cliques(j, k))) then
swap_needed = .true.
exit
end if
end do
if (.not. swap_needed .and. clique_sizes(i) > clique_sizes(j)) then
swap_needed = .true.
end if
if (swap_needed) then
! Swap cliques
temp_clique(1:clique_sizes(i)) = cliques(i, 1:clique_sizes(i))
temp_size = clique_sizes(i)
cliques(i, 1:clique_sizes(j)) = cliques(j, 1:clique_sizes(j))
clique_sizes(i) = clique_sizes(j)
cliques(j, 1:temp_size) = temp_clique(1:temp_size)
clique_sizes(j) = temp_size
end if
end do
end do
end subroutine sort_cliques
! Print all cliques
subroutine print_cliques()
implicit none
integer :: i, j
write(*, '(A)', advance='no') '['
do i = 1, num_cliques
write(*, '(A)', advance='no') '['
do j = 1, clique_sizes(i)
write(*, '(A)', advance='no') trim(vertex_names(cliques(i, j)))
if (j < clique_sizes(i)) write(*, '(A)', advance='no') ', '
end do
write(*, '(A)', advance='no') ']'
if (i < num_cliques) write(*, '(A)', advance='no') ', '
end do
write(*, '(A)') ']'
end subroutine print_cliques
end program bron_kerbosch_cliques
- Output:
[[a, b, c], [d, e, f]]
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
package main
import (
"fmt"
"sort"
"strings"
)
// Using map[string]bool to simulate a set of strings
type StringSet map[string]bool
// Edge struct represents a graph edge
type Edge struct {
Start string
End string
}
// Global variable to store cliques (slices of sorted strings)
var cliques [][]string
// --- Set Operations Helper Functions ---
// setUnion returns the union of two sets (a U b)
func setUnion(a, b StringSet) StringSet {
union := make(StringSet)
for k := range a {
union[k] = true
}
for k := range b {
union[k] = true
}
return union
}
// setIntersection returns the intersection of two sets (a ∩ b)
func setIntersection(a, b StringSet) StringSet {
intersection := make(StringSet)
// Iterate over the smaller set for efficiency
if len(a) < len(b) {
for k := range a {
if b[k] {
intersection[k] = true
}
}
} else {
for k := range b {
if a[k] {
intersection[k] = true
}
}
}
return intersection
}
// setDifference returns the difference of two sets (a \ b)
func setDifference(a, b StringSet) StringSet {
difference := make(StringSet)
for k := range a {
if !b[k] { // If element from a is NOT in b
difference[k] = true
}
}
return difference
}
// setCopy creates a shallow copy of the set
func setCopy(s StringSet) StringSet {
newSet := make(StringSet)
for k := range s {
newSet[k] = true
}
return newSet
}
// setToSortedSlice converts a set to a sorted slice of strings
func setToSortedSlice(s StringSet) []string {
slice := make([]string, 0, len(s))
for k := range s {
slice = append(slice, k)
}
sort.Strings(slice)
return slice
}
// --- Printing Helper Functions ---
// printSlice prints a sorted string slice like [a, b, c]
func printSlice(slice []string) {
fmt.Printf("[%s]", strings.Join(slice, ", "))
}
// print2DSlice prints a slice of slices like [[a, b, c], [d, e, f]]
func print2DSlice(slices [][]string) {
fmt.Print("[")
for i, slice := range slices {
printSlice(slice)
if i < len(slices)-1 {
fmt.Print(", ")
}
}
fmt.Println("]")
}
// --- Bron-Kerbosch Algorithm ---
// bronKerbosch implements the algorithm with pivoting.
// R: current clique being built
// P: candidate vertices
// X: processed vertices
// graph: adjacency list representation (map[vertex] -> set of neighbors)
func bronKerbosch(currentClique, candidates, processedVertices StringSet, graph map[string]StringSet) {
if len(candidates) == 0 && len(processedVertices) == 0 {
// Base case: Found a maximal clique
if len(currentClique) > 2 {
// Convert set to sorted slice before storing
cliqueSlice := setToSortedSlice(currentClique)
cliques = append(cliques, cliqueSlice)
}
return
}
// --- Pivot Selection ---
// Choose a pivot u from P union X with the maximum number of neighbors in P.
// Python version simplifies to max degree in the *whole graph* from P union X. We'll mimic that.
unionSet := setUnion(candidates, processedVertices)
pivot := ""
maxDegree := -1
// Find pivot (vertex in P U X with highest degree in the whole graph)
if len(unionSet) > 0 {
// Find *any* element first to initialize pivot
for v := range unionSet {
pivot = v
if neighbors, ok := graph[pivot]; ok {
maxDegree = len(neighbors)
} else {
maxDegree = 0 // Handle nodes with no outgoing edges if they exist
}
break // Found the first element, stop
}
// Now find the actual max degree pivot
for v := range unionSet {
degree := 0
if neighbors, ok := graph[v]; ok {
degree = len(neighbors)
}
if degree > maxDegree {
maxDegree = degree
pivot = v
}
}
} else {
// If unionSet is empty, we should have hit the base case already,
// but handle defensively.
return
}
// --- Iteration ---
// Iterate through vertices v in P \ N(u) (candidates not neighbors of pivot)
pivotNeighbors := graph[pivot] // Might be nil if pivot has no neighbors listed
if pivotNeighbors == nil {
pivotNeighbors = make(StringSet) // Treat as empty set if nil
}
// Create a copy of candidates to iterate over, as candidates set is modified inside the loop
candidatesWithoutPivotNeighbors := setDifference(candidates, pivotNeighbors)
// Need to iterate over a stable copy because 'candidates' is modified
verticesToProcess := setToSortedSlice(candidatesWithoutPivotNeighbors) // Get keys to iterate safely
for _, vertex := range verticesToProcess {
// Ensure vertex is still in the *current* candidates set before processing
// (It might have been removed if processing another vertex moved it to X implicitly,
// although the standard BK algorithm structure should prevent this here).
// This check is mostly for robustness if the sets were modified unexpectedly.
// In this specific BK implementation, removing happens *after* recursion, so it's safe.
// if !candidates[vertex] {
// continue
// }
vertexNeighbors := graph[vertex]
if vertexNeighbors == nil {
vertexNeighbors = make(StringSet)
}
// Create new clique R U {v}
newClique := setCopy(currentClique)
newClique[vertex] = true
// New candidates P ∩ N(v)
newCandidates := setIntersection(candidates, vertexNeighbors)
// New processed vertices X ∩ N(v)
newProcessed := setIntersection(processedVertices, vertexNeighbors)
// Recursive call
bronKerbosch(newClique, newCandidates, newProcessed, graph)
// Move vertex from P to X: P = P \ {v}, X = X U {v}
delete(candidates, vertex)
processedVertices[vertex] = true
}
}
func main() {
// Define edges
edges := []Edge{
{"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 (map[string]StringSet)
graph := make(map[string]StringSet)
allVertices := make(StringSet) // Keep track of all unique vertices
for _, edge := range edges {
// Ensure the map for the start node exists
if _, ok := graph[edge.Start]; !ok {
graph[edge.Start] = make(StringSet)
}
graph[edge.Start][edge.End] = true // Add neighbor
// Add vertices to our set of all vertices
allVertices[edge.Start] = true
allVertices[edge.End] = true
}
// Initialize sets for the algorithm
currentClique := make(StringSet)
// Candidates initially contain all vertices in the graph
candidates := setCopy(allVertices) // Start with all unique vertices found
processedVertices := make(StringSet)
// Execute the Bron-Kerbosch algorithm
bronKerbosch(currentClique, candidates, processedVertices, graph)
// Sort the final list of cliques for consistent display
// Sort first by length, then lexicographically by the elements
sort.Slice(cliques, func(i, j int) bool {
if len(cliques[i]) != len(cliques[j]) {
return len(cliques[i]) < len(cliques[j])
}
// If lengths are equal, compare element by element
for k := 0; k < len(cliques[i]); k++ {
if cliques[i][k] != cliques[j][k] {
return cliques[i][k] < cliques[j][k]
}
}
return false // Should not happen for distinct cliques
})
// Display the cliques
print2DSlice(cliques)
}
- Output:
[[a, b, c], [d, e, f]]
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]]
// Global variable to store the found cliques
let cliques = [];
// Equivalent to the Edge struct
// (We'll just use plain objects inline)
// Helper function to print the final result (similar to print_2D_vector)
function printCliques(cliquesArray) {
// Sort cliques before printing for consistent output
// Sort primarily by first element, then second, etc., then by length
cliquesArray.sort((a, b) => {
const len = Math.min(a.length, b.length);
for (let i = 0; i < len; i++) {
if (a[i] < b[i]) return -1;
if (a[i] > b[i]) return 1;
}
// If one is a prefix of the other, shorter comes first
return a.length - b.length;
});
// Pretty print using JSON.stringify
console.log(JSON.stringify(cliquesArray, null, 2));
}
// --- Set Operations Helpers ---
// Set Intersection: Returns a new Set containing elements present in both setA and setB
function setIntersection(setA, setB) {
const intersection = new Set();
for (const elem of setB) { // Iterate smaller set for potential efficiency
if (setA.has(elem)) {
intersection.add(elem);
}
}
return intersection;
}
// Set Difference: Returns a new Set containing elements present in setA but NOT in setB (A \ B)
function setDifference(setA, setB) {
const difference = new Set(setA); // Start with a copy of setA
for (const elem of setB) {
difference.delete(elem); // Remove elements found in setB
}
return difference;
}
/**
* Bron-Kerbosch algorithm with pivoting to find maximal cliques.
* @param {Set<string>} currentClique - The clique being built (R in common notation).
* @param {Set<string>} candidates - Potential vertices to add (P).
* @param {Set<string>} processedVertices - Vertices already processed/excluded (X).
* @param {Map<string, Set<string>>} graph - Adjacency list representation of the graph.
*/
function bronKerbosch(currentClique, candidates, processedVertices, graph) {
if (candidates.size === 0 && processedVertices.size === 0) {
// Base case: Found a maximal clique
if (currentClique.size > 2) {
// Convert Set to Array, sort it for consistent ordering, and add to results
const cliqueArray = Array.from(currentClique).sort();
cliques.push(cliqueArray);
}
return;
}
// --- Pivoting ---
// Combine candidates and processed vertices for pivot selection
const unionSet = new Set([...candidates, ...processedVertices]);
let pivot = '';
let maxDegree = -1;
// Select pivot: vertex in unionSet with the most neighbors *in candidates*
// (Optimization: C++ version used total degree, JS version uses neighbors in candidates for better pruning)
// Let's stick closer to the provided C++ heuristic (max degree in the *entire graph* among unionSet members) for direct translation.
for (const u of unionSet) {
const neighbors = graph.get(u) || new Set(); // Neighbors in the whole graph
if (neighbors.size > maxDegree) {
maxDegree = neighbors.size;
pivot = u;
}
}
// If unionSet was empty (should be caught by base case, but safety check)
if (!pivot && unionSet.size > 0) {
pivot = unionSet.values().next().value; // Fallback: pick any element if degree calc failed
} else if (!pivot) {
return; // Union set is truly empty
}
// 'possibles': Candidates that are NOT neighbors of the pivot (candidates \ N(pivot))
const pivotNeighbors = graph.get(pivot) || new Set();
const possibles = setDifference(candidates, pivotNeighbors); // P \ N(u)
// --- Recursion ---
// Iterate over a *copy* of possibles because we modify 'candidates' and 'processedVertices' below
const possiblesCopy = Array.from(possibles);
for (const vertex of possiblesCopy) {
// Ensure vertex hasn't been moved from candidates in another branch's backtracking
// (This check is usually implicitly handled by iterating the right set,
// but explicit check can prevent errors if logic is complex)
if (!candidates.has(vertex)) {
continue;
}
const neighborsOfVertex = graph.get(vertex) || new Set();
// Create NEW clique for recursive call: currentClique U {vertex}
const newClique = new Set(currentClique);
newClique.add(vertex);
// Create NEW candidates for recursive call: candidates ∩ N(vertex)
const newCandidates = setIntersection(candidates, neighborsOfVertex);
// Create NEW processed vertices for recursive call: processedVertices ∩ N(vertex)
const newProcessedVertices = setIntersection(processedVertices, neighborsOfVertex);
// Recursive call
bronKerbosch(newClique, newCandidates, newProcessedVertices, graph);
// Backtracking: Move 'vertex' from candidates to processedVertices
// Modify the sets belonging to *this* function call's scope
candidates.delete(vertex);
processedVertices.add(vertex);
}
}
// --- Main Execution ---
function main() {
const edges = [
{ start: "a", end: "b" }, { start: "b", end: "a" },
{ start: "a", end: "c" }, { start: "c", end: "a" },
{ start: "b", end: "c" }, { start: "c", end: "b" },
{ start: "d", end: "e" }, { start: "e", end: "d" },
{ start: "d", end: "f" }, { start: "f", end: "d" },
{ start: "e", end: "f" }, { start: "f", end: "e" }
];
// Build the graph as an adjacency list (Map<string, Set<string>>)
const graph = new Map();
const allVertices = new Set(); // Keep track of all unique vertices
for (const edge of edges) {
// Ensure nodes exist in the map
if (!graph.has(edge.start)) {
graph.set(edge.start, new Set());
}
// Add edge
graph.get(edge.start).add(edge.end);
// Keep track of all vertices encountered
allVertices.add(edge.start);
allVertices.add(edge.end); // Ensure end node is also tracked if it never starts an edge
}
// Ensure all nodes mentioned (even if only as end nodes) exist as keys in the graph map
for(const vertex of allVertices) {
if (!graph.has(vertex)) {
graph.set(vertex, new Set());
}
}
// Initialize sets for the algorithm
const initialCurrentClique = new Set();
// Candidates are initially all vertices in the graph
const initialCandidates = new Set(allVertices);
const initialProcessedVertices = new Set();
// Reset global cliques array before running
cliques = [];
// Execute the Bron-Kerbosch algorithm
bronKerbosch(
initialCurrentClique,
initialCandidates,
initialProcessedVertices,
graph
);
// Display the cliques (sorted)
printCliques(cliques);
}
// Run the main function
main();
- Output:
[ [ "a", "b", "c" ], [ "d", "e", "f" ] ]
"""
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']]
import java.util.*
object MainKt {
private val cliques: MutableList<List<String>> = mutableListOf()
@JvmStatic
fun main(args: Array<String>) {
val edges = listOf(
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
val graph: MutableMap<String, MutableSet<String>> = mutableMapOf()
edges.forEach { edge ->
graph.computeIfAbsent(edge.start) { mutableSetOf() }.add(edge.end)
}
// Initialize current clique, candidates, and processed vertices
val currentClique: MutableSet<String> = mutableSetOf()
val candidates: MutableSet<String> = mutableSetOf<String>().apply { addAll(graph.keys) }
val processedVertices: MutableSet<String> = mutableSetOf()
// Execute the Bron-Kerbosch algorithm to collect the cliques
bronKerbosch(currentClique, candidates, processedVertices, graph)
// Sort the cliques for consistent display
cliques.sortWith(listComparator)
// Display the cliques
println(cliques)
}
private fun bronKerbosch(
currentClique: MutableSet<String>,
candidates: MutableSet<String>,
processedVertices: MutableSet<String>,
graph: Map<String, Set<String>>
) {
if (candidates.isEmpty() && processedVertices.isEmpty()) {
if (currentClique.size > 2) {
val clique = ArrayList(currentClique)
cliques.add(clique)
}
return
}
// Select a pivot vertex from 'candidates' union 'processedVertices' with the maximum degree
val union = candidates.toMutableSet().apply { addAll(processedVertices) }
val pivot = union.maxBy { s -> graph[s]?.size ?: 0 }
if (pivot == null) {
return
}
// 'possibles' are vertices in 'candidates' that are not neighbors of the 'pivot'
val possibles = candidates.toMutableSet().apply { removeAll(graph[pivot] ?: emptySet()) }
for (vertex in possibles) {
// Create a new clique including 'vertex'
val newCliques = currentClique.toMutableSet().apply { add(vertex) }
// 'newCandidates' are the members of 'candidates' that are neighbors of 'vertex'
val neighbors = graph[vertex] ?: emptySet()
val newCandidates = candidates.toMutableSet().apply { retainAll(neighbors) }
// 'newProcessedVertices' are members of 'processedVertices' that are neighbors of 'vertex'
val newProcessedVertices = processedVertices.toMutableSet().apply { retainAll(neighbors) }
// Recursive call with the updated sets
bronKerbosch(newCliques, newCandidates, newProcessedVertices, graph)
// Move 'vertex' from 'candidates' to 'processedVertices'
candidates.remove(vertex)
processedVertices.add(vertex)
}
}
private val listComparator = Comparator<Any> { list1, list2 ->
val typedList1 = list1 as List<String>
val typedList2 = list2 as List<String>
for (i in 0 until minOf(typedList1.size, typedList2.size)) {
val comparison = typedList1[i].compareTo(typedList2[i])
if (comparison != 0) {
return@Comparator comparison
}
}
typedList1.size.compareTo(typedList2.size)
}
private data class Edge(val start: String, val end: String)
}
- Output:
[[a, b, c], [d, e, f]]
local edges = {
{ start = "a", end_ = "b" },
{ start = "b", end_ = "a" },
{ start = "a", end_ = "c" },
{ start = "c", end_ = "a" },
{ start = "b", end_ = "c" },
{ start = "c", end_ = "b" },
{ start = "d", end_ = "e" },
{ start = "e", end_ = "d" },
{ start = "d", end_ = "f" },
{ start = "f", end_ = "d" },
{ start = "e", end_ = "f" },
{ start = "f", end_ = "e" },
}
-- Simple serialization function for table display
function serialize(obj)
local lua = ""
local t = type(obj)
if t == "number" then
lua = lua .. obj
elseif t == "boolean" then
lua = lua .. tostring(obj)
elseif t == "string" then
lua = lua .. string.format("%q", obj)
elseif t == "table" then
lua = lua .. "{\n"
for k, v in pairs(obj) do
lua = lua .. "[" .. serialize(k) .. "]=" .. serialize(v) .. ",\n"
end
lua = lua .. "}"
elseif t == "nil" then
return nil
else
error("can not serialize a " .. t .. " type.")
end
return lua
end
function bron_kerbosch(current_clique, candidates, processed_vertices, graph, cliques)
if next(candidates) == nil and next(processed_vertices) == nil then
if #current_clique > 2 then
local new_clique = {}
for _, v in ipairs(current_clique) do
table.insert(new_clique, v)
end
table.insert(cliques, new_clique)
end
return
end
-- Select a pivot vertex from 'candidates' union 'processedVertices' with the maximum degree
local union = {}
for k, v in pairs(candidates) do union[k] = v end
for k, v in pairs(processed_vertices) do union[k] = v end
local pivot = max_degree_vertex(union, graph)
-- 'possibles' are vertices in 'candidates' that are not neighbors of the 'pivot'
local possibles = {}
for k, v in pairs(candidates) do possibles[k] = v end
if graph[pivot] then
for _, neighbor in ipairs(graph[pivot]) do
possibles[neighbor] = nil
end
end
for vertex, _ in pairs(possibles) do
-- Create a new clique including 'vertex'
local new_clique = {}
for _, v in ipairs(current_clique) do
table.insert(new_clique, v)
end
table.insert(new_clique, vertex)
-- 'newCandidates' are the members of 'candidates' that are neighbors of 'vertex'
local neighbors = {}
if graph[vertex] then
for _, neighbor in ipairs(graph[vertex]) do
neighbors[neighbor] = true
end
end
local new_candidates = {}
for candidate, _ in pairs(candidates) do
if neighbors[candidate] then
new_candidates[candidate] = true
end
end
-- 'newProcessedVertices' are members of 'processedVertices' that are neighbors of 'vertex'
local new_processed_vertices = {}
for processed, _ in pairs(processed_vertices) do
if neighbors[processed] then
new_processed_vertices[processed] = true
end
end
-- Recursive call with the updated sets
bron_kerbosch(new_clique, new_candidates, new_processed_vertices, graph, cliques)
-- Move 'vertex' from 'candidates' to 'processedVertices'
candidates[vertex] = nil
processed_vertices[vertex] = true
end
end
function max_degree_vertex(vertices, graph)
local max_vertex, max_degree = nil, -1
for vertex, _ in pairs(vertices) do
local degree = 0
if graph[vertex] then
degree = #graph[vertex]
end
if degree > max_degree then
max_degree = degree
max_vertex = vertex
end
end
return max_vertex
end
function list_comparator(list1, list2)
local min_length = math.min(#list1, #list2)
for i = 1, min_length do
if list1[i] < list2[i] then
return -1
elseif list1[i] > list2[i] then
return 1
end
end
if #list1 < #list2 then
return -1
elseif #list1 > #list2 then
return 1
else
return 0
end
end
-- Build the graph as an adjacency list
local graph = {}
for _, edge in ipairs(edges) do
if not graph[edge.start] then
graph[edge.start] = {}
end
table.insert(graph[edge.start], edge.end_)
end
-- Initialize current clique, candidates, and processed vertices
local current_clique = {}
local candidates = {}
for vertex, _ in pairs(graph) do
candidates[vertex] = true
end
local processed_vertices = {}
-- Execute the Bron-Kerbosch algorithm to collect the cliques
local cliques = {}
bron_kerbosch(current_clique, candidates, processed_vertices, graph, cliques)
-- Sort the cliques for consistent display
table.sort(cliques, function(a, b) return list_comparator(a, b) < 0 end)
-- Display the cliques
print(serialize(cliques))
- Output:
{ [1]={ [1]="a", [2]="c", [3]="b", }, [2]={ [1]="f", [2]="e", [3]="d", }, }
(* Global variable to store cliques *)
cliques = {};
(* Function to print a sorted list *)
printVector[vec_] := Print["[", StringRiffle[Sort[ToString /@ vec], ", "], "]"]
(* Function to print a list of lists *)
print2DVector[vecs_] := (
Print["[" <> StringRiffle[
(Function[v, "[" <> StringRiffle[Sort[ToString /@ v], ", "] <> "]"] /@ vecs),
", "
] <> "]"]
)
(* Bron-Kerbosch recursive function *)
bronKerbosch[currentClique_, candidates_, processed_, adj_] := Module[
{unionSet, pivot, possibles, neighbors, newCandidates, newProcessed},
(* Base case *)
If[Length[candidates] == 0 && Length[processed] == 0,
If[Length[currentClique] > 2,
AppendTo[cliques, Sort[currentClique]]
];
Return[]
];
(* Union of candidates and processed *)
unionSet = Union[candidates, processed];
(* Choose pivot with maximum degree *)
pivot = First[MaximalBy[unionSet, Length[adj[#]] &]];
(* Possibles: candidates not adjacent to pivot *)
possibles = Complement[candidates, adj[pivot]];
(* Iterate over each possible vertex *)
Do[
neighbors = adj[vertex];
newCandidates = Intersection[candidates, neighbors];
newProcessed = Intersection[processed, neighbors];
bronKerbosch[Append[currentClique, vertex], newCandidates, newProcessed, adj],
{vertex, possibles}
]
]
(* Main function *)
main[] := Module[
{edges, nodes, adj, currentClique, candidates, processed},
(* Clear global cliques *)
cliques = {};
(* Define edges *)
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"}
};
(* Build adjacency list as an association *)
nodes = Union[Flatten[edges]];
adj = Association[# -> {} & /@ nodes];
Do[
{u, v} = edge;
If[! MemberQ[adj[u], v], AppendTo[adj[u], v]],
{edge, edges}
];
(* Initialize Bron-Kerbosch parameters *)
currentClique = {};
candidates = nodes;
processed = {};
(* Run Bron-Kerbosch *)
bronKerbosch[currentClique, candidates, processed, adj];
(* Remove duplicates and sort cliques by size and content *)
cliques = DeleteDuplicates[cliques];
cliques = SortBy[cliques, {Length, Identity}];
(* Print result *)
print2DVector[cliques]
]
(* Run main *)
main[]
- Output:
[[a, b, c], [d, e, f]]
import std/[algorithm, sequtils, sets, strutils, tables]
type StringSet = HashSet[string]
const Empty = initHashSet[string]()
proc bronKerbosch(r: var StringSet; # Current clique.
p: var StringSet; # Potential candidates to expand the clique.
x: var StringSet; # Vertices already processed.
g: Table[string, StringSet]; # Graph represented as an adjacency list.
cliques: var seq[seq[string]] # List to store all maximal cliques.
) =
if card(p) == 0 and card(x) == 0:
if card(r) > 2:
let clique = sorted(toSeq(r.items))
cliques.add clique
return
# Select a pivot vertex from P ∪ X with the maximum degree.
var pivot = ""
for v in p + x:
let n = g.getOrDefault(v, Empty).len
if n > pivot.len: pivot = v
# Candidates are vertices in "p" that are not neighbors of the pivot.
let candidates = p - g[pivot]
for v in candidates:
# New clique including vertex "v".
var newR = r
newR.incl v
# New potential candidates are neighbors of "v" in "p".
let neighbors = g[v]
var newP = p * neighbors
# New excluded vertices are neighbors of "v" in "x".
var newX = x * neighbors
# Recursive call with updated sets.
bronKerbosch(newR, newP, newX, g, cliques)
# Move vertex "v" from "p" to "x".
p.excl v
x.incl v
when isMainModule:
proc cmp(a, b: seq[string]): int =
## Comparison procedure to use for sorting.
result = cmp(a.len, b.len)
if result == 0:
for i in 0..a.len:
result = cmp(a[i], b[i])
if result != 0: return
# Define the input edges as a list of tuples.
let 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: Table[string, StringSet]
for (t1, t2) in input:
graph.mgetOrPut(t1, initHashSet[string]()).incl t2
# Initialize "r", "p", "x".
var r, x: StringSet
var p = toSeq(graph.keys).toHashSet()
# Initialize list to store cliques.
var cliques: seq[seq[string]]
# Execute the Bron-Kerbosch algorithm.
bronKerbosch(r, p, x, graph, cliques)
# Sort the cliques for consistent output.
cliques.sort(cmp)
# Print each clique.
for clique in cliques:
echo clique.join(", ")
- Output:
a, b, c d, e, f
use strict;
use warnings;
use Data::Dumper;
my @edges = (
{ start => "a", end => "b" },
{ start => "b", end => "a" },
{ start => "a", end => "c" },
{ start => "c", end => "a" },
{ start => "b", end => "c" },
{ start => "c", end => "b" },
{ start => "d", end => "e" },
{ start => "e", end => "d" },
{ start => "d", end => "f" },
{ start => "f", end => "d" },
{ start => "e", end => "f" },
{ start => "f", end => "e" },
);
# Build the graph as an adjacency list
my %graph;
foreach my $edge (@edges) {
push @{ $graph{ $edge->{start} } }, $edge->{end};
}
# Initialize current clique, candidates, and processed vertices
my @current_clique;
my %candidates = map { $_ => 1 } keys %graph;
my %processed_vertices;
# Execute the Bron-Kerbosch algorithm to collect the cliques
my @cliques;
bron_kerbosch(\@current_clique, \%candidates, \%processed_vertices, \%graph, \@cliques);
# Sort the cliques for consistent display
@cliques = sort { list_comparator($a, $b) } @cliques;
# Display the cliques
print Dumper(\@cliques);
sub bron_kerbosch {
my ($current_clique, $candidates, $processed_vertices, $graph, $cliques) = @_;
if (!%$candidates && !%$processed_vertices) {
if (@$current_clique > 2) {
push @$cliques, [@$current_clique];
}
return;
}
# Select a pivot vertex from 'candidates' union 'processedVertices' with the maximum degree
my %union = (%$candidates, %$processed_vertices);
my $pivot = max_degree_vertex(\%union, $graph);
# 'possibles' are vertices in 'candidates' that are not neighbors of the 'pivot'
my %possibles = %$candidates;
delete $possibles{$_} for @{ $graph->{$pivot} };
foreach my $vertex (keys %possibles) {
# Create a new clique including 'vertex'
my @new_cliques = @$current_clique;
push @new_cliques, $vertex;
# 'newCandidates' are the members of 'candidates' that are neighbors of 'vertex'
my %neighbors = map { $_ => 1 } @{ $graph->{$vertex} };
my %new_candidates = map { $_ => 1 } grep { $neighbors{$_} } keys %$candidates;
# 'newProcessedVertices' are members of 'processedVertices' that are neighbors of 'vertex'
my %new_processed_vertices = map { $_ => 1 } grep { $neighbors{$_} } keys %$processed_vertices;
# Recursive call with the updated sets
bron_kerbosch(\@new_cliques, \%new_candidates, \%new_processed_vertices, $graph, $cliques);
# Move 'vertex' from 'candidates' to 'processedVertices'
delete $candidates->{$vertex};
$processed_vertices->{$vertex} = 1;
}
}
sub max_degree_vertex {
my ($vertices, $graph) = @_;
my ($max_vertex, $max_degree) = (undef, -1);
foreach my $vertex (keys %$vertices) {
my $degree = scalar @{ $graph->{$vertex} };
if ($degree > $max_degree) {
$max_degree = $degree;
$max_vertex = $vertex;
}
}
return $max_vertex;
}
sub list_comparator {
my ($list1, $list2) = @_;
my $min_length = $#$list1 < $#$list2 ? $#$list1 : $#$list2;
for my $i (0..$min_length) {
my $comparison = $list1->[$i] cmp $list2->[$i];
if ($comparison != 0) {
return $comparison;
}
}
return $#$list1 <=> $#$list2;
}
- Output:
$VAR1 = [ [ 'a', 'c', 'b' ], [ 'f', 'e', 'd' ] ];
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"}}
# Global variable to store cliques
$global:cliques = @()
# Edge class equivalent
class Edge {
[string]$Start
[string]$End
Edge([string]$start, [string]$end) {
$this.Start = $start
$this.End = $end
}
}
function Print-Vector {
param([array]$vec)
$sortedVec = $vec | Sort-Object
Write-Host -NoNewline "[$($sortedVec -join ', ')]"
}
function Print-2DVector {
param([array]$vecs)
Write-Host -NoNewline "["
for ($i = 0; $i -lt ($vecs.Count - 1); $i++) {
Print-Vector $vecs[$i]
Write-Host -NoNewline ", "
}
if ($vecs.Count -gt 0) {
Print-Vector $vecs[-1]
}
Write-Host "]"
}
function Invoke-BronKerbosch {
param(
[System.Collections.Generic.HashSet[string]]$CurrentClique,
[System.Collections.Generic.HashSet[string]]$Candidates,
[System.Collections.Generic.HashSet[string]]$ProcessedVertices,
[hashtable]$Graph
)
if ($Candidates.Count -eq 0 -and $ProcessedVertices.Count -eq 0) {
if ($CurrentClique.Count -gt 2) {
$cliqueArray = @()
foreach ($item in $CurrentClique) {
$cliqueArray += $item
}
$global:cliques += ,$cliqueArray
}
return
}
# Select a pivot vertex from 'Candidates' union 'ProcessedVertices' with the maximum degree
$unionSet = [System.Collections.Generic.HashSet[string]]::new()
$unionSet.UnionWith($Candidates)
$unionSet.UnionWith($ProcessedVertices)
$pivot = $null
$maxDegree = -1
foreach ($vertex in $unionSet) {
$degree = $Graph[$vertex].Count
if ($degree -gt $maxDegree) {
$maxDegree = $degree
$pivot = $vertex
}
}
# 'Possibles' are vertices in 'Candidates' that are not neighbors of the 'pivot'
$possibles = [System.Collections.Generic.HashSet[string]]::new()
$possibles.UnionWith($Candidates)
$possibles.ExceptWith($Graph[$pivot])
# Create a copy of candidates to iterate over (to avoid modification during iteration)
$candidatesCopy = [System.Collections.Generic.HashSet[string]]::new()
$candidatesCopy.UnionWith($Candidates)
foreach ($vertex in $possibles) {
# Create a new clique including 'vertex'
$newClique = [System.Collections.Generic.HashSet[string]]::new()
$newClique.UnionWith($CurrentClique)
$newClique.Add($vertex) | Out-Null
# 'NewCandidates' are the members of 'Candidates' that are neighbors of 'vertex'
$newCandidates = [System.Collections.Generic.HashSet[string]]::new()
$newCandidates.UnionWith($Candidates)
$newCandidates.IntersectWith($Graph[$vertex])
# 'NewProcessedVertices' are members of 'ProcessedVertices' that are neighbors of 'vertex'
$newProcessedVertices = [System.Collections.Generic.HashSet[string]]::new()
$newProcessedVertices.UnionWith($ProcessedVertices)
$newProcessedVertices.IntersectWith($Graph[$vertex])
# Recursive call with the updated sets
Invoke-BronKerbosch $newClique $newCandidates $newProcessedVertices $Graph
# Move 'vertex' from 'Candidates' to 'ProcessedVertices'
$Candidates.Remove($vertex) | Out-Null
$ProcessedVertices.Add($vertex) | Out-Null
}
}
function Main {
$global:cliques = @()
# Define edges
$edges = @(
[Edge]::new("a", "b"), [Edge]::new("b", "a"), [Edge]::new("a", "c"), [Edge]::new("c", "a"),
[Edge]::new("b", "c"), [Edge]::new("c", "b"), [Edge]::new("d", "e"), [Edge]::new("e", "d"),
[Edge]::new("d", "f"), [Edge]::new("f", "d"), [Edge]::new("e", "f"), [Edge]::new("f", "e")
)
# Build the graph as an adjacency list using hashtable
$graph = @{}
foreach ($edge in $edges) {
if (-not $graph.ContainsKey($edge.Start)) {
$graph[$edge.Start] = [System.Collections.Generic.HashSet[string]]::new()
}
$graph[$edge.Start].Add($edge.End) | Out-Null
}
# Initialize current clique, candidates, and processed vertices
$currentClique = [System.Collections.Generic.HashSet[string]]::new()
$candidates = [System.Collections.Generic.HashSet[string]]::new()
foreach ($key in $graph.Keys) {
$candidates.Add($key) | Out-Null
}
$processedVertices = [System.Collections.Generic.HashSet[string]]::new()
# Execute the Bron-Kerbosch algorithm to collect the cliques
Invoke-BronKerbosch $currentClique $candidates $processedVertices $graph
# Sort the cliques for consistent display
$global:cliques = $global:cliques | Sort-Object { $_.Count }, { $_ -join ',' }
# Display the cliques
Print-2DVector $global:cliques
}
# Run the main function
Main
- Output:
[[a, b, c], [d, e, f]]
from collections import defaultdict
# Global variable to store cliques
cliques = []
class Edge:
def __init__(self, start, end):
self.start = start
self.end = end
def print_vector(vec):
print("[" + ", ".join(sorted(map(str, vec))) + "]", end="")
def print_2D_vector(vecs):
print("[", end="")
for i in range(len(vecs) - 1):
print_vector(vecs[i])
print(", ", end="")
print_vector(vecs[-1])
print("]")
def bron_kerbosch(current_clique, candidates, processed_vertices, graph):
global cliques
if not candidates and not processed_vertices:
if len(current_clique) > 2:
cliques.append(list(current_clique))
return
# Select a pivot vertex from 'candidates' union 'processed_vertices' with the maximum degree
union_set = candidates.union(processed_vertices)
pivot = max(union_set, key=lambda v: len(graph[v]))
# 'possibles' are vertices in 'candidates' that are not neighbors of the 'pivot'
possibles = candidates.difference(graph[pivot])
for vertex in possibles:
# Create a new clique including 'vertex'
new_clique = current_clique.union({vertex})
# 'new_candidates' are the members of 'candidates' that are neighbors of 'vertex'
new_candidates = candidates.intersection(graph[vertex])
# 'new_processed_vertices' are members of 'processed_vertices' that are neighbors of 'vertex'
new_processed_vertices = processed_vertices.intersection(graph[vertex])
# Recursive call with the updated sets
bron_kerbosch(new_clique, new_candidates, new_processed_vertices, graph)
# Move 'vertex' from 'candidates' to 'processed_vertices'
candidates.remove(vertex)
processed_vertices.add(vertex)
def main():
global cliques
# Define edges
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
graph = defaultdict(set)
for edge in edges:
graph[edge.start].add(edge.end)
# Initialize current clique, candidates, and processed vertices
current_clique = set()
candidates = set(graph.keys())
processed_vertices = set()
# Execute the Bron-Kerbosch algorithm to collect the cliques
bron_kerbosch(current_clique, candidates, processed_vertices, graph)
# Sort the cliques for consistent display
cliques.sort(key=lambda x: (len(x), x))
# Display the cliques
print_2D_vector(cliques)
if __name__ == "__main__":
main()
[[a, b, c], [d, e, f]]
# Global variable to store cliques
cliques <- list()
# Function to print a vector (sorted)
print_vector <- function(vec) {
cat("[", paste(sort(as.character(vec)), collapse = ", "), "]", sep = "")
}
# Function to print a list of vectors
print_2D_vector <- function(vecs) {
cat("[")
n <- length(vecs)
for (i in seq_len(n)) {
print_vector(vecs[[i]])
if (i < n) cat(", ")
}
cat("]\n")
}
# Bron-Kerbosch algorithm implementation
bron_kerbosch <- function(current_clique, candidates, processed_vertices, graph) {
# Access the global 'cliques' variable
cliques <<- cliques
# Base case: if both candidates and processed are empty, we have a maximal clique
if (length(candidates) == 0 && length(processed_vertices) == 0) {
if (length(current_clique) > 2) {
cliques <<- append(cliques, list(sort(current_clique)))
}
return()
}
# Union of candidates and processed vertices
union_set <- unique(c(candidates, processed_vertices))
# Choose pivot with maximum degree
pivot <- union_set[which.max(sapply(union_set, function(v) length(graph[[v]])))]
# Possibles: candidates not adjacent to pivot
possibles <- setdiff(candidates, graph[[pivot]])
# Iterate over each possible vertex
for (vertex in possibles) {
# Neighbors of vertex
neighbors <- graph[[vertex]]
# Intersect candidates and processed with neighbors
new_candidates <- intersect(candidates, neighbors)
new_processed_vertices <- intersect(processed_vertices, neighbors)
# Recursive call with updated sets (don't modify original sets)
bron_kerbosch(c(current_clique, vertex), new_candidates, new_processed_vertices, graph)
}
}
# Main function
main <- function() {
# Clear global cliques
cliques <<- list()
# Define edges (as character pairs)
edges <- list(
c("a", "b"), c("b", "a"), c("a", "c"), c("c", "a"),
c("b", "c"), c("c", "b"), c("d", "e"), c("e", "d"),
c("d", "f"), c("f", "d"), c("e", "f"), c("f", "e")
)
# Build graph as adjacency list
graph <- list()
nodes <- unique(unlist(edges))
for (node in nodes) {
graph[[node]] <- c()
}
for (edge in edges) {
start <- edge[1]
end <- edge[2]
if (!(end %in% graph[[start]])) {
graph[[start]] <- c(graph[[start]], end)
}
}
# Initialize Bron-Kerbosch parameters
current_clique <- c()
candidates <- names(graph)
processed_vertices <- c()
# Run Bron-Kerbosch
bron_kerbosch(current_clique, candidates, processed_vertices, graph)
# Remove duplicates and sort cliques by size and content
unique_cliques <- unique(lapply(cliques, sort))
cliques <<- unique_cliques[order(sapply(unique_cliques, length), sapply(unique_cliques, function(x) paste(sort(x), collapse = ",")))]
# Print result
print_2D_vector(cliques)
}
# Run main
main()
- Output:
[[a, b, c], [d, e, f]]
# 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
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
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(", "));
}
}
import scala.collection.mutable
import scala.collection.immutable.TreeSet
object BronKerboschAlgorithm {
case class Edge(start: String, end: String)
private var cliques: mutable.ListBuffer[List[String]] = mutable.ListBuffer.empty[List[String]]
def main(args: Array[String]): Unit = {
val edges = List(
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
val graph: mutable.Map[String, mutable.Set[String]] = mutable.Map.empty
edges.foreach { edge =>
graph.getOrElseUpdate(edge.start, mutable.Set.empty[String]).add(edge.end)
}
// Initialize current clique, candidates and processed vertices
val currentClique: TreeSet[String] = TreeSet.empty[String]
val candidates: mutable.Set[String] = mutable.Set(graph.keySet.toSeq: _*)
val processedVertices: mutable.Set[String] = mutable.Set.empty[String]
// Execute the Bron-Kerbosch algorithm to collect the cliques
val immutableGraph = graph.map { case (k, v) => k -> v.toSet }.toMap
bronKerbosch(currentClique, candidates, processedVertices, immutableGraph)
// Sort the cliques for consistent display
cliques = cliques.sortWith(listComparator)
// Display the cliques
println(cliques.toList)
}
private def bronKerbosch(
currentClique: TreeSet[String],
candidates: mutable.Set[String],
processedVertices: mutable.Set[String],
graph: Map[String, Set[String]]
): Unit = {
if (candidates.isEmpty && processedVertices.isEmpty) {
if (currentClique.size > 2) {
val clique = currentClique.toList
cliques += clique
}
return
}
// Select a pivot vertex from 'candidates' union 'processedVertices' with the maximum degree
val union = candidates ++ processedVertices
val pivot = union.maxBy(vertex => graph(vertex).size)
// 'possibles' are vertices in 'candidates' that are not neighbours of the 'pivot'
val possibles = candidates -- graph(pivot)
for (vertex <- possibles.toList) { // Convert to List to avoid concurrent modification
// Create a new clique including 'vertex'
val newCliques = currentClique + vertex
// 'newCandidates' are the members of 'candidates' that are neighbours of 'vertex'
val neighbours = graph(vertex)
val newCandidates = candidates.intersect(neighbours)
// 'newProcessedVertices' are members of 'processedVertices' that are neighbours of 'vertex'
val newProcessedVertices = processedVertices.intersect(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 def listComparator(list1: List[String], list2: List[String]): Boolean = {
val minSize = math.min(list1.size, list2.size)
for (i <- 0 until minSize) {
val comparison = list1(i).compare(list2(i))
if (comparison != 0) {
return comparison < 0
}
}
list1.size < list2.size
}
}
- Output:
List(List(a, b, c), List(d, e, f))
var cliques: [[String]] = []
struct Edge {
let start: String
let end: String
}
func bronKerbosch(currentClique: Set<String>, candidates: Set<String>, processedVertices: Set<String>, graph: [String: Set<String>]) {
if candidates.isEmpty && processedVertices.isEmpty {
if currentClique.count > 2 {
let clique = Array(currentClique).sorted()
cliques.append(clique)
}
return
}
let union = candidates.union(processedVertices)
let pivot = union.max(by: { graph[$0]!.count < graph[$1]!.count })!
let possibles = candidates.subtracting(graph[pivot]!)
for vertex in possibles {
var newClique = currentClique
newClique.insert(vertex)
let neighbors = graph[vertex]!
let newCandidates = candidates.intersection(neighbors)
let newProcessedVertices = processedVertices.intersection(neighbors)
bronKerbosch(currentClique: newClique, candidates: newCandidates, processedVertices: newProcessedVertices, graph: graph)
var newCandidatesSet = candidates
newCandidatesSet.remove(vertex)
var newProcessedVerticesSet = processedVertices
newProcessedVerticesSet.insert(vertex)
bronKerbosch(currentClique: currentClique, candidates: newCandidatesSet, processedVertices: newProcessedVerticesSet, graph: graph)
}
}
func main() {
let edges = [
Edge(start: "a", end: "b"), Edge(start: "b", end: "a"),
Edge(start: "a", end: "c"), Edge(start: "c", end: "a"),
Edge(start: "b", end: "c"), Edge(start: "c", end: "b"),
Edge(start: "d", end: "e"), Edge(start: "e", end: "d"),
Edge(start: "d", end: "f"), Edge(start: "f", end: "d"),
Edge(start: "e", end: "f"), Edge(start: "f", end: "e")
]
var graph: [String: Set<String>] = [:]
for edge in edges {
if graph[edge.start] == nil {
graph[edge.start] = Set<String>()
}
graph[edge.start]?.insert(edge.end)
}
let currentClique = Set<String>()
let candidates = Set<String>(graph.keys)
let processedVertices = Set<String>()
bronKerbosch(currentClique: currentClique, candidates: candidates, processedVertices: processedVertices, graph: graph)
cliques.sort { (list1, list2) -> Bool in
for i in 0..<min(list1.count, list2.count) {
if list1[i] != list2[i] {
return list1[i] < list2[i]
}
}
return list1.count < list2.count
}
// Remove duplicates
var uniqueCliques = [[String]]()
var seen = Set<Set<String>>()
for clique in cliques {
let cliqueSet = Set(clique)
if !seen.contains(cliqueSet) {
seen.insert(cliqueSet)
uniqueCliques.append(clique)
}
}
print(uniqueCliques)
}
main()
- Output:
[["a", "b", "c"], ["d", "e", "f"]]
# Global variable to store cliques
set cliques {}
# Procedure to print a list (equivalent to print_vector)
proc print_list {lst} {
puts -nonewline "\["
set len [llength $lst]
for {set i 0} {$i < $len} {incr i} {
if {$i > 0} {
puts -nonewline ", "
}
puts -nonewline [lindex $lst $i]
}
puts -nonewline "\]"
}
# Procedure to print 2D list (equivalent to print_2D_vector)
proc print_2D_list {lists} {
puts -nonewline "\["
set len [llength $lists]
for {set i 0} {$i < $len} {incr i} {
if {$i > 0} {
puts -nonewline ", "
}
print_list [lindex $lists $i]
}
puts "\]"
}
# Helper procedure to find set difference
proc set_difference {set1 set2} {
set result {}
foreach item $set1 {
if {$item ni $set2} {
lappend result $item
}
}
return $result
}
# Helper procedure to find set intersection
proc set_intersection {set1 set2} {
set result {}
foreach item $set1 {
if {$item in $set2} {
lappend result $item
}
}
return $result
}
# Helper procedure to find union of two sets
proc set_union {set1 set2} {
set result {}
foreach item $set1 {
lappend result $item
}
foreach item $set2 {
if {$item ni $result} {
lappend result $item
}
}
return $result
}
# Bron-Kerbosch algorithm implementation
proc bron_kerbosch {current_clique candidates processed_vertices graph} {
global cliques
# Check if both candidates and processed_vertices are empty
if {[llength $candidates] == 0 && [llength $processed_vertices] == 0} {
if {[llength $current_clique] > 2} {
lappend cliques $current_clique
set cliques $cliques
}
return
}
# Select pivot vertex with maximum degree
set union_set [set_union $candidates $processed_vertices]
set pivot ""
set max_degree -1
foreach vertex $union_set {
set degree [llength [dict get $graph $vertex]]
if {$degree > $max_degree} {
set max_degree $degree
set pivot $vertex
}
}
# Find possibles: vertices in candidates that are not neighbors of pivot
set pivot_neighbors [dict get $graph $pivot]
set possibles [set_difference $candidates $pivot_neighbors]
foreach vertex $possibles {
# Create new clique including vertex
set new_clique $current_clique
lappend new_clique $vertex
# Find new candidates: members of candidates that are neighbors of vertex
set vertex_neighbors [dict get $graph $vertex]
set new_candidates [set_intersection $candidates $vertex_neighbors]
# Find new processed vertices: members of processed_vertices that are neighbors of vertex
set new_processed_vertices [set_intersection $processed_vertices $vertex_neighbors]
# Recursive call
bron_kerbosch $new_clique $new_candidates $new_processed_vertices $graph
# Move vertex from candidates to processed_vertices
set candidates [set_difference $candidates [list $vertex]]
lappend processed_vertices $vertex
}
}
# Main procedure
proc main {} {
global cliques
# Define edges
set 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}
}
# Build graph as adjacency list (using dictionary)
set graph [dict create]
foreach edge $edges {
set start [lindex $edge 0]
set end [lindex $edge 1]
if {[dict exists $graph $start]} {
set neighbors [dict get $graph $start]
if {$end ni $neighbors} {
lappend neighbors $end
dict set graph $start $neighbors
}
} else {
dict set graph $start [list $end]
}
}
# Initialize current clique, candidates and processed vertices
set current_clique {}
set candidates {}
dict for {vertex neighbors} $graph {
lappend candidates $vertex
}
set processed_vertices {}
# Execute Bron-Kerbosch algorithm
bron_kerbosch $current_clique $candidates $processed_vertices $graph
# Sort cliques for consistent display
# First sort each clique internally
set sorted_cliques {}
foreach clique $cliques {
set sorted_clique [lsort $clique]
lappend sorted_cliques $sorted_clique
}
# Then sort cliques by lexicographic order
proc compare_cliques {a b} {
set len_a [llength $a]
set len_b [llength $b]
set min_len [expr {$len_a < $len_b ? $len_a : $len_b}]
for {set i 0} {$i < $min_len} {incr i} {
set elem_a [lindex $a $i]
set elem_b [lindex $b $i]
if {$elem_a ne $elem_b} {
return [string compare $elem_a $elem_b]
}
}
return [expr {$len_a - $len_b}]
}
set cliques [lsort -command compare_cliques $sorted_cliques]
# Display the cliques
print_2D_list $cliques
}
# Run the main procedure
main
- Output:
[[a, b, c], [d, e, f]]
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
const std = @import("std");
const Edge = struct {
start: []const u8,
end: []const u8,
};
fn printVector(vec: []const []const u8) !void {
const stdout = std.io.getStdOut().writer();
try stdout.print("[", .{});
for (vec, 0..) |element, i| {
if (i < vec.len - 1) {
try stdout.print("{s}, ", .{element});
} else {
try stdout.print("{s}", .{element});
}
}
try stdout.print("]", .{});
}
fn print2DVector(vecs: []const []const []const u8) !void {
const stdout = std.io.getStdOut().writer();
try stdout.print("[", .{});
for (vecs, 0..) |vec, i| {
try printVector(vec);
if (i < vecs.len - 1) {
try stdout.print(", ", .{});
}
}
try stdout.print("]\n", .{});
}
fn bronKerbosch(
allocator: std.mem.Allocator,
currentClique: *std.StringArrayHashMap([]const u8),
candidates: *std.StringArrayHashMap([]const u8),
processedVertices: *std.StringArrayHashMap([]const u8),
graph: *std.StringArrayHashMap(std.StringHashMap(void)),
cliques: *std.ArrayList([]const []const u8),
) !void {
if (candidates.count() == 0 and processedVertices.count() == 0) {
if (currentClique.count() > 2) {
var cliqueList = std.ArrayList([]const u8).init(allocator);
var it = currentClique.iterator();
while (it.next()) |entry| {
try cliqueList.append(entry.key_ptr.*);
}
const cliqueSlice = try cliqueList.toOwnedSlice();
try cliques.append(cliqueSlice);
}
return;
}
// Find pivot with maximum degree
var pivot: []const u8 = "";
var maxDegree: usize = 0;
var it = graph.iterator();
while (it.next()) |entry| {
const vertex = entry.key_ptr.*;
const degree = entry.value_ptr.count();
if (degree > maxDegree or (maxDegree == 0 and pivot.len == 0)) {
maxDegree = degree;
pivot = vertex;
}
}
// Candidates not connected to pivot
var possibles = std.StringArrayHashMap([]const u8).init(allocator);
defer possibles.deinit();
var cand_it = candidates.iterator();
while (cand_it.next()) |entry| {
const vertex = entry.key_ptr.*;
const is_connected = if (graph.get(vertex)) |neighbors|
neighbors.contains(pivot)
else
false;
if (!is_connected) {
try possibles.put(vertex, vertex);
}
}
// Iterate over possible vertices
var poss_it = possibles.iterator();
while (poss_it.next()) |entry| {
const vertex = entry.key_ptr.*;
// New clique
var newClique = std.StringArrayHashMap([]const u8).init(allocator);
defer newClique.deinit();
var clique_it = currentClique.iterator();
while (clique_it.next()) |clique_entry| {
try newClique.put(clique_entry.key_ptr.*, clique_entry.key_ptr.*);
}
try newClique.put(vertex, vertex);
// New candidates (neighbors of vertex)
var newCandidates = std.StringArrayHashMap([]const u8).init(allocator);
defer newCandidates.deinit();
if (graph.get(vertex)) |vertexNeighbors| {
var cand_iter = candidates.iterator();
while (cand_iter.next()) |cand| {
if (vertexNeighbors.contains(cand.key_ptr.*)) {
try newCandidates.put(cand.key_ptr.*, cand.key_ptr.*);
}
}
}
// New processed vertices (neighbors of vertex)
var newProcessed = std.StringArrayHashMap([]const u8).init(allocator);
defer newProcessed.deinit();
if (graph.get(vertex)) |vertexNeighbors| {
var proc_it = processedVertices.iterator();
while (proc_it.next()) |proc| {
if (vertexNeighbors.contains(proc.key_ptr.*)) {
try newProcessed.put(proc.key_ptr.*, proc.key_ptr.*);
}
}
}
// Recursive call
try bronKerbosch(allocator, &newClique, &newCandidates, &newProcessed, graph, cliques);
// Move vertex from candidates to processed
_ = candidates.*.swapRemove(vertex); // swapRemove - O(1)
// _ = candidates.*.orderedRemove(vertex); // orderedRemove - O(N)
try processedVertices.put(vertex, vertex);
}
}
pub fn main() !void {
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
const allocator = arena.allocator();
const edges: []const Edge = &.{
.{ .start = "a", .end = "b" },
.{ .start = "b", .end = "a" },
.{ .start = "a", .end = "c" },
.{ .start = "c", .end = "a" },
.{ .start = "b", .end = "c" },
.{ .start = "c", .end = "b" },
.{ .start = "d", .end = "e" },
.{ .start = "e", .end = "d" },
.{ .start = "d", .end = "f" },
.{ .start = "f", .end = "d" },
.{ .start = "e", .end = "f" },
.{ .start = "f", .end = "e" },
};
// Initialize graph
var graph = std.StringArrayHashMap(std.StringHashMap(void)).init(allocator);
defer graph.deinit();
for (edges) |edge| {
if (!graph.contains(edge.start)) {
try graph.put(edge.start, std.StringHashMap(void).init(allocator));
}
if (!graph.contains(edge.end)) {
try graph.put(edge.end, std.StringHashMap(void).init(allocator));
}
if (graph.getPtr(edge.start)) |neighbors| {
try neighbors.put(edge.end, {});
}
if (graph.getPtr(edge.end)) |neighbors| {
try neighbors.put(edge.start, {});
}
}
var currentClique = std.StringArrayHashMap([]const u8).init(allocator);
defer currentClique.deinit();
var candidates = std.StringArrayHashMap([]const u8).init(allocator);
defer candidates.deinit();
var graph_it = graph.iterator();
while (graph_it.next()) |entry| {
try candidates.put(entry.key_ptr.*, entry.key_ptr.*);
}
var processedVertices = std.StringArrayHashMap([]const u8).init(allocator);
defer processedVertices.deinit();
var cliques = std.ArrayList([]const []const u8).init(allocator);
defer cliques.deinit();
try bronKerbosch(allocator, ¤tClique, &candidates, &processedVertices, &graph, &cliques);
// Sort cliques
std.sort.heap([]const []const u8, cliques.items, {}, struct {
fn lessThan(_: void, a: []const []const u8, b: []const []const u8) bool {
const minLen = @min(a.len, b.len);
for (0..minLen) |i| {
if (!std.mem.eql(u8, a[i], b[i])) {
return std.mem.lessThan(u8, a[i], b[i]);
}
}
return a.len < b.len;
}
}.lessThan);
try print2DVector(cliques.items);
}
- Output:
[[d, f, e]]