petgraph::algo::maximal_cliques

Function maximal_cliques

Source 
pub fn maximal_cliques<G>(g: G) -> Vec<HashSet<G::NodeId>>
where
    G: GetAdjacencyMatrix + IntoNodeIdentifiers + IntoNeighbors,
    G::NodeId: Eq + Hash,
Expand description

Find all maximal cliques in an undirected graph using Bron–Kerbosch algorithm with pivoting. Also works on symmetric directed graphs, see the note below.

A clique is a set of nodes such that every node connects to every other. A maximal clique is a clique that cannot be extended by including one more adjacent vertex. A graph may have multiple maximal cliques.

This method may also be called on directed graphs, but one needs to ensure that if an edge (u, v) exists, then (v, u) also exists.

§Arguments

  • g: The graph to find maximal cliques in.

§Returns

  • Vec<HashSet>: A vector of [struct@hashbrown::HashSet] making up the maximal cliques in the graph.

§Complexity

  • Time complexity: O(3^(|V|/3))
  • Auxiliary space: O(|V|²).

where |V| is the number of nodes.

§Example

use petgraph::algo::maximal_cliques;
use petgraph::graph::UnGraph;

let mut g = UnGraph::<i32, ()>::from_edges([(0, 1), (0, 2), (1, 2), (2, 3)]);
g.add_node(4);
// The example graph:
//
// 0 --- 2 -- 3
//  \   /
//   \ /
//    1       4
//
// maximal cliques: {4}, {2, 3}, {0, 1, 2}
// Output the result
let cliques = maximal_cliques(&g);
println!("{:?}", cliques);
// [
//   {NodeIndex(4)},
//   {NodeIndex(0), NodeIndex(1), NodeIndex(2)},
//   {NodeIndex(2), NodeIndex(3)}
// ]