Interface with Cliquer (clique-related problems)¶
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
Jeroen Demeyer (2011-05-06): Make cliquer interruptible (Issue #11252)
Nico Van Cleemput (2013-05-27): Handle the empty graph (Issue #14525)
REFERENCE:
Methods¶
- sage.graphs.cliquer.all_cliques(graph, min_size=0, max_size=0)[source]¶
Iterator over the cliques in
graph.A clique is an induced complete subgraph. This method is an iterator over all the cliques with size in between
min_sizeandmax_size. By default, this method returns only maximum cliques. Each yielded clique is represented by a list of vertices.Note
Currently only implemented for undirected graphs. Use
to_undirected()to convert a digraph to an undirected graph.INPUT:
min_size– integer (default: 0); minimum size of reported cliques. When set to 0 (default), this method searches for maximum cliques. In such case, parametermax_sizemust also be set to 0.max_size– integer (default: 0); maximum size of reported cliques. When set to 0 (default), the maximum size of the cliques is unbounded. Whenmin_sizeis set to 0, this parameter must be set to 0.
ALGORITHM:
This function is based on Cliquer [NO2003].
EXAMPLES:
sage: G = graphs.CompleteGraph(5) sage: list(sage.graphs.cliquer.all_cliques(G)) [[0, 1, 2, 3, 4]] sage: list(sage.graphs.cliquer.all_cliques(G, 2, 3)) [[3, 4], [2, 3], [2, 3, 4], [2, 4], [1, 2], [1, 2, 3], [1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [0, 1], [0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2], [0, 2, 3], [0, 2, 4], [0, 3], [0, 3, 4], [0, 4]] sage: G.delete_edge([1,3]) sage: list(sage.graphs.cliquer.all_cliques(G)) [[0, 2, 3, 4], [0, 1, 2, 4]]
>>> from sage.all import * >>> G = graphs.CompleteGraph(Integer(5)) >>> list(sage.graphs.cliquer.all_cliques(G)) [[0, 1, 2, 3, 4]] >>> list(sage.graphs.cliquer.all_cliques(G, Integer(2), Integer(3))) [[3, 4], [2, 3], [2, 3, 4], [2, 4], [1, 2], [1, 2, 3], [1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [0, 1], [0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2], [0, 2, 3], [0, 2, 4], [0, 3], [0, 3, 4], [0, 4]] >>> G.delete_edge([Integer(1),Integer(3)]) >>> list(sage.graphs.cliquer.all_cliques(G)) [[0, 2, 3, 4], [0, 1, 2, 4]]
G = graphs.CompleteGraph(5) list(sage.graphs.cliquer.all_cliques(G)) list(sage.graphs.cliquer.all_cliques(G, 2, 3)) G.delete_edge([1,3]) list(sage.graphs.cliquer.all_cliques(G))
Todo
Use the re-entrant functionality of Cliquer [NO2003] to avoid storing all cliques.
- sage.graphs.cliquer.all_max_clique(graph)[source]¶
Return the vertex sets of ALL the maximum complete subgraphs.
Returns the list of all maximum cliques, with each clique represented by a list of vertices. A clique is an induced complete subgraph, and a maximum clique is one of maximal order.
Note
Currently only implemented for undirected graphs. Use
to_undirected()to convert a digraph to an undirected graph.ALGORITHM:
This function is based on Cliquer [NO2003].
EXAMPLES:
sage: graphs.ChvatalGraph().cliques_maximum() # indirect doctest [[0, 1], [0, 4], [0, 6], [0, 9], [1, 2], [1, 5], [1, 7], [2, 3], [2, 6], [2, 8], [3, 4], [3, 7], [3, 9], [4, 5], [4, 8], [5, 10], [5, 11], [6, 10], [6, 11], [7, 8], [7, 11], [8, 10], [9, 10], [9, 11]] sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: G.show(figsize=[2,2]) # needs sage.plot sage: G.cliques_maximum() [[0, 1, 2], [0, 1, 3]] sage: C = graphs.PetersenGraph() sage: C.cliques_maximum() [[0, 1], [0, 4], [0, 5], [1, 2], [1, 6], [2, 3], [2, 7], [3, 4], [3, 8], [4, 9], [5, 7], [5, 8], [6, 8], [6, 9], [7, 9]] sage: C = Graph('DJ{') sage: C.cliques_maximum() [[1, 2, 3, 4]]
>>> from sage.all import * >>> graphs.ChvatalGraph().cliques_maximum() # indirect doctest [[0, 1], [0, 4], [0, 6], [0, 9], [1, 2], [1, 5], [1, 7], [2, 3], [2, 6], [2, 8], [3, 4], [3, 7], [3, 9], [4, 5], [4, 8], [5, 10], [5, 11], [6, 10], [6, 11], [7, 8], [7, 11], [8, 10], [9, 10], [9, 11]] >>> G = Graph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(2)], Integer(3):[Integer(0),Integer(1)]}) >>> G.show(figsize=[Integer(2),Integer(2)]) # needs sage.plot >>> G.cliques_maximum() [[0, 1, 2], [0, 1, 3]] >>> C = graphs.PetersenGraph() >>> C.cliques_maximum() [[0, 1], [0, 4], [0, 5], [1, 2], [1, 6], [2, 3], [2, 7], [3, 4], [3, 8], [4, 9], [5, 7], [5, 8], [6, 8], [6, 9], [7, 9]] >>> C = Graph('DJ{') >>> C.cliques_maximum() [[1, 2, 3, 4]]
graphs.ChvatalGraph().cliques_maximum() # indirect doctest G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) G.show(figsize=[2,2]) # needs sage.plot G.cliques_maximum() C = graphs.PetersenGraph() C.cliques_maximum() C = Graph('DJ{') C.cliques_maximum()
- sage.graphs.cliquer.clique_number(graph)[source]¶
Return the size of the largest clique of the graph (clique number).
Note
Currently only implemented for undirected graphs. Use
to_undirected()to convert a digraph to an undirected graph.EXAMPLES:
sage: C = Graph('DJ{') sage: C.clique_number() 4 sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: G.show(figsize=[2,2]) # needs sage.plot sage: G.clique_number() 3
>>> from sage.all import * >>> C = Graph('DJ{') >>> C.clique_number() 4 >>> G = Graph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(2)], Integer(3):[Integer(0),Integer(1)]}) >>> G.show(figsize=[Integer(2),Integer(2)]) # needs sage.plot >>> G.clique_number() 3
C = Graph('DJ{') C.clique_number() G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) G.show(figsize=[2,2]) # needs sage.plot G.clique_number()
- sage.graphs.cliquer.max_clique(graph)[source]¶
Return the vertex set of a maximum complete subgraph.
Note
Currently only implemented for undirected graphs. Use
to_undirected()to convert a digraph to an undirected graph.EXAMPLES:
sage: C = graphs.PetersenGraph() sage: from sage.graphs.cliquer import max_clique sage: max_clique(C) [7, 9]
>>> from sage.all import * >>> C = graphs.PetersenGraph() >>> from sage.graphs.cliquer import max_clique >>> max_clique(C) [7, 9]
C = graphs.PetersenGraph() from sage.graphs.cliquer import max_clique max_clique(C)