Contents Menu Expand Light mode Dark mode Auto light/dark, in light mode Auto light/dark, in dark mode Skip to content
Graph Theory
Light Logo Dark Logo
Version 10.6 Reference Manual
  • Home - Graph Theory
  • Generic graphs (common to directed/undirected)
  • Undirected graphs
  • Directed graphs
  • Bipartite graphs
  • Matching covered graphs
  • View classes
  • Common graphs
  • Common digraphs
  • Common graphs and digraphs generators (Cython)
  • Graph database
  • Database of strongly regular graphs
  • Database of distance regular graphs
  • Families of graphs derived from classical geometries over finite fields
  • Various families of graphs
  • Basic graphs
  • Chessboard graphs
  • Intersection graphs
  • 1-skeletons of Platonic solids
  • Random graphs
  • Various small graphs
  • Graphs from the World Map
  • ISGCI: Information System on Graph Classes and their Inclusions
  • Overview of (di)graph data structures
  • Fast compiled graphs
  • Fast sparse graphs
  • Fast dense graphs
  • Static dense graphs
  • Static sparse graphs
  • Static sparse graph backend
  • Backends for Sage (di)graphs
  • Interface to run Boost algorithms
  • Hypergraph generators
  • Incidence structures (i.e. hypergraphs, i.e. set systems)
  • Graph coloring
  • Interface with Cliquer (clique-related problems)
  • Centrality
  • Asteroidal triples
  • Independent sets
  • Cographs
  • Comparability and permutation graphs
  • Line graphs
  • Spanning trees
  • PQ-Trees
  • Generation of trees
  • Matching
  • Matching polynomial
  • Genus
  • Lovász theta-function of graphs
  • Schnyder’s algorithm for straight-line planar embeddings
  • Wrapper for Boyer’s (C) planarity algorithm
  • Graph traversals
  • Graph plotting
  • Graph plotting in Javascript with d3.js
  • Tree decompositions
  • Vertex separation
  • Rank Decompositions of graphs
  • Bandwidth of undirected graphs
  • Cutwidth
  • Products of graphs
  • Slice decomposition
  • Modular Decomposition
  • Decomposition by clique minimal separators
  • Convexity properties of graphs
  • Weakly chordal graphs
  • Distances/shortest paths between all pairs of vertices
  • LaTeX options for graphs
  • Graph editor widget
  • Lists of graphs
  • Functions for reading/building graphs/digraphs
  • Hyperbolicity
  • Tutte polynomial
  • Partial cubes
  • Path enumeration
  • GenericGraph Cython functions
  • Orientations
  • Connectivity related functions
  • Edge connectivity
  • Domination
Back to top
View this page
Edit this page

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:

[NO2003]

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_size and max_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, parameter max_size must 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. When min_size is 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]]

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]]
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
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]
Next
Centrality
Previous
Graph coloring
Copyright © 2005--2025, The Sage Development Team
Made with Sphinx and @pradyunsg's Furo
On this page
  • Interface with Cliquer (clique-related problems)
    • Methods
    • all_cliques()
    • all_max_clique()
    • clique_number()
    • max_clique()