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]]