Cliquer : routines for finding cliques in graphs

This module defines functions based on Cliquer, an exact branch-and-bound algorithm developed by Patric R. J. Ostergard and written by Sampo Niskanen.

AUTHORS:

• Nathann Cohen (2009-08-14): Initial version

Functions

sage.graphs.cliquer.all_max_clique(graph)

Returns the vertex sets of ALL the maximum complete subgraphs.

Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.

EXAMPLES:

sage: C=graphs.PetersenGraph()
sage: all_max_clique(C)
[[2, 7], [7, 9], [6, 8], [6, 9], [0, 4], [4, 9], [5, 7], [0, 5], [5, 8], [3, 4], [2, 3], [3, 8], [1, 6], [0, 1], [1, 2]]

sage.graphs.cliquer.clique_number(graph)

Returns the size of the largest clique of the graph (clique number).

Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.

EXAMPLES:

sage: C = Graph('DJ{')
sage: clique_number(C)
4
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])
sage: clique_number(G)
3

sage.graphs.cliquer.list_composition(a, b)

Composes a list a with a map b.

EXAMPLE:

sage: from sage.graphs.cliquer import list_composition
sage: list_composition([1,3,'a'], {'a':'b', 1:2, 2:3, 3:4})
[2, 4, 'b']

sage.graphs.cliquer.max_clique(graph)

Returns the vertex set of a maximum complete subgraph.

Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.

EXAMPLES:

sage: C=graphs.PetersenGraph()
sage: max_clique(C)
[7, 9]