Module cliques 

Cliques, independent vertex sets and vertex/edge colorings (igraph_cliques.h, igraph_coloring.h).

A clique is a set of vertices that are pairwise adjacent; an independent vertex set is a set of vertices no two of which are adjacent (i.e. a clique of the complementer graph). A proper vertex coloring assigns colors to vertices so that adjacent vertices always differ. The clique and independent-set functions ignore edge directions (igraph emits a warning for directed graphs), self-loops and multi-edges. The coloring checks ignore self-loops too, but is_bipartite_coloring reports edge directions and is_edge_coloring treats parallel edges as adjacent.

Three families of sets are distinguished, both for cliques and for independent sets:

• all sets (every clique, including every subset of a clique);
• maximal sets, which cannot be extended by adding one more vertex;
• largest (maximum) sets, those of the largest possible size. The size of the largest clique is the clique number ω(G), the size of the largest independent set is the independence number α(G).

Size ranges

The enumeration functions take the admissible sizes as a Rust range of usize (RangeBounds): .. means “any size”, 3.. “at least 3”, 2..=4 “between 2 and 4”, ..5 “fewer than 5”. An empty range (e.g. 4..=2 or ..1) is rejected with an ErrorKind::InvalidValue error, since no set could ever satisfy it. A lower bound larger than the number of vertices is not an error: the result is simply empty. An optional max_results stops the search after that many sets were found (None means no limit, Some(0) returns nothing).

Nesting searches in callbacks

The functions based on the Cliquer library (cliques, cliques_callback, clique_size_hist and the weighted clique functions) share per-thread state inside igraph: in igraph 1.0.0 and 1.0.1 the Cliquer wrapper keeps the options of the running search in a single thread-local global that every search overwrites. Calling one of them from inside a cliques_callback closure is therefore refused with an ErrorKind::Failure error instead of corrupting the running search. All other functions (for instance maximal_cliques or clique_number) may be used freely there, and maximal_cliques_callback closures may call anything. The restriction is per thread: searches running on other threads are independent. A nested call that fails only returns its Err to the closure: the running search is not affected and can go on.

Example

use igraph::{cliques::ColoringGreedy, prelude::*};

// Two triangles {0, 1, 2} and {2, 3, 4} sharing vertex 2, plus the edge 4-5.
let g = Graph::from_edges(&[(0, 1), (1, 2), (0, 2), (2, 3), (3, 4), (2, 4), (4, 5)], 6, false)
    .unwrap();

assert_eq!(g.clique_number().unwrap(), 3);
let mut largest = g.largest_cliques().unwrap();
largest.iter_mut().for_each(|c| c.sort());
largest.sort();
assert_eq!(largest, vec![vec![0, 1, 2], vec![2, 3, 4]]);

// Maximal cliques by size: none of size 1, one of size 2 (4-5), two triangles.
assert_eq!(g.maximal_cliques_hist(..).unwrap(), vec![0, 1, 2]);

// Vertices 0, 3 and 5 are pairwise non-adjacent.
assert_eq!(g.independence_number().unwrap(), 3);

// A proper coloring needs at least ω(G) = 3 colors.
let colors = g.vertex_coloring_greedy(ColoringGreedy::DSatur).unwrap();
assert!(g.is_vertex_coloring(&colors).unwrap());
assert_eq!(colors.iter().max(), Some(&2));

// Zachary's karate club: its 45 triangles are its cliques of size 3, and
// its two largest cliques have 5 members.
let karate = Graph::famous("Zachary").unwrap();
assert_eq!(karate.clique_size_hist(3..=3).unwrap(), vec![0, 0, 45]);
assert_eq!(karate.count_triangles().unwrap(), 45.0);
assert_eq!(karate.clique_number().unwrap(), 5);

Provided functionality

Rust method	C function	Computes
cliques	igraph_cliques	all cliques in a size range
cliques_callback	igraph_cliques_callback	streams all cliques to a closure
clique_size_hist	igraph_clique_size_hist	number of cliques of each size
largest_cliques	igraph_largest_cliques	the maximum cliques
clique_number	igraph_clique_number	ω(G)
maximal_cliques	igraph_maximal_cliques	maximal cliques (Bron–Kerbosch)
maximal_cliques_callback	igraph_maximal_cliques_callback	streams maximal cliques to a closure
maximal_cliques_count	igraph_maximal_cliques_count	number of maximal cliques
maximal_cliques_hist	igraph_maximal_cliques_hist	maximal cliques by size
maximal_cliques_subset	igraph_maximal_cliques_subset	maximal cliques started from some vertices
write_maximal_cliques	igraph_maximal_cliques_file	writes maximal cliques to an io::Write
weighted_cliques	igraph_weighted_cliques	(maximal) cliques in a weight range
largest_weighted_cliques	igraph_largest_weighted_cliques	heaviest cliques
weighted_clique_number	igraph_weighted_clique_number	weight of the heaviest clique
independent_vertex_sets	igraph_independent_vertex_sets	all independent sets in a size range
maximal_independent_vertex_sets	igraph_maximal_independent_vertex_sets	maximal independent sets
largest_independent_vertex_sets	igraph_largest_independent_vertex_sets	maximum independent sets
independence_number	igraph_independence_number	α(G)
vertex_coloring_greedy	igraph_vertex_coloring_greedy	a proper vertex coloring
is_vertex_coloring	igraph_is_vertex_coloring	checks a vertex coloring
is_bipartite_coloring	igraph_is_bipartite_coloring	checks a 2-coloring, and edge orientation
is_edge_coloring	igraph_is_edge_coloring	checks an edge coloring

Cliques and independent sets are returned as Vec<Vec<VertexId>>; the order of the sets, and of the vertices inside each set, is unspecified (sort them if you need a canonical form).

See also

Task	Elsewhere in the crate
test whether a given vertex set is a clique / independent set	Graph::is_clique, Graph::is_independent_vertex_set (structural)
triangles (the 3-cliques) only	Graph::count_triangles, Graph::list_triangles (isomorphism), Graph::transitivity_undirected (mixing)
switch between cliques and independent sets	Graph::complementer (operators): α(G) = ω(complement of G)
degeneracy, which bounds the cost of maximal_cliques	Graph::coreness: the degeneracy is the largest coreness
2-colorings	Graph::is_bipartite, Graph::bipartite_types (bipartite)
graph classes where χ(G) = ω(G)	Graph::is_perfect, Graph::is_chordal (structural)
graphs with known ω, α and χ	Graph::full, Graph::turan, Graph::wheel, Graph::famous (constructors), Graph::mycielskian (operators: triangle-free graphs of growing chromatic number)

Structs

WeightedCliqueOptions

Options of Graph::weighted_cliques.

Enums

ColoringGreedy

Vertex ordering heuristic of Graph::vertex_coloring_greedy (igraph_coloring_greedy_t).