Undirected graphs¶

This module implements functions and operations involving undirected graphs.

Algorithmically hard stuff

`convexity_properties()`	Return a `ConvexityProperties` object corresponding to `self`.
`has_homomorphism_to()`	Check whether there is a homomorphism between two graphs.
`independent_set()`	Return a maximum independent set.
`independent_set_of_representatives()`	Return an independent set of representatives.
`is_perfect()`	Test whether the graph is perfect.
`matching_polynomial()`	Compute the matching polynomial of the graph \(G\).
`minor()`	Return the vertices of a minor isomorphic to \(H\) in the current graph.
`pathwidth()`	Compute the pathwidth of `self` (and provides a decomposition).
`rank_decomposition()`	Compute an optimal rank-decomposition of the given graph.
`topological_minor()`	Return a topological \(H\)-minor from `self` if one exists.
`treelength()`	Compute the treelength of \(G\) (and provide a decomposition).
`treewidth()`	Compute the treewidth of \(g\) (and provide a decomposition).
`tutte_polynomial()`	Return the Tutte polynomial of the graph \(G\).
`vertex_cover()`	Return a minimum vertex cover of `self` represented by a set of vertices.

Basic methods

`bipartite_color()`	Return a dictionary with vertices as the keys and the color class as the values.
`bipartite_double()`	Return the (extended) bipartite double of this graph.
`bipartite_sets()`	Return \((X,Y)\) where \(X\) and \(Y\) are the nodes in each bipartite set of graph \(G\).
`graph6_string()`	Return the graph6 representation of the graph as an ASCII string.
`is_directed()`	Since graph is undirected, returns False.
`join()`	Return the join of `self` and `other`.
`sparse6_string()`	Return the sparse6 representation of the graph as an ASCII string.
`to_directed()`	Return a directed version of the graph.
`to_undirected()`	Since the graph is already undirected, simply returns a copy of itself.
`write_to_eps()`	Write a plot of the graph to `filename` in `eps` format.

Clique-related methods

`all_cliques()`	Iterator over the cliques in `graph`.
`atoms_and_clique_separators()`	Return the atoms of the decomposition of \(G\) by clique minimal separators.
`clique_complex()`	Return the clique complex of `self`.
`clique_maximum()`	Return the vertex set of a maximal order complete subgraph.
`clique_number()`	Return the order of the largest clique of the graph.
`clique_polynomial()`	Return the clique polynomial of `self`.
`cliques_containing_vertex()`	Return the cliques containing each vertex, represented as a dictionary of lists of lists, keyed by vertex.
`cliques_get_clique_bipartite()`	Return the vertex-clique bipartite graph of `self`.
`cliques_get_max_clique_graph()`	Return the clique graph.
`cliques_maximal()`	Return the list of all maximal cliques.
`cliques_maximum()`	Return the vertex sets of ALL the maximum complete subgraphs.
`cliques_number_of()`	Return a dictionary of the number of maximal cliques containing each vertex, keyed by vertex.
`cliques_vertex_clique_number()`	Return a dictionary of sizes of the largest maximal cliques containing each vertex, keyed by vertex.
`fractional_clique_number()`	Return the fractional clique number of the graph.

Coloring

`chromatic_index()`	Return the chromatic index of the graph.
`chromatic_number()`	Return the minimal number of colors needed to color the vertices of the graph.
`chromatic_polynomial()`	Compute the chromatic polynomial of the graph G.
`chromatic_quasisymmetric_function()`	Return the chromatic quasisymmetric function of `self`.
`chromatic_symmetric_function()`	Return the chromatic symmetric function of `self`.
`coloring()`	Return the first (optimal) proper vertex-coloring found.
`fractional_chromatic_index()`	Return the fractional chromatic index of the graph.
`fractional_chromatic_number()`	Return the fractional chromatic number of the graph.
`tutte_symmetric_function()`	Return the Tutte symmetric function of `self`.

Connectivity, orientations, trees

`acyclic_orientations()`	Return an iterator over all acyclic orientations of an undirected graph \(G\).
`bounded_outdegree_orientation()`	Return an orientation of \(G\) such that every vertex \(v\) has out-degree less than \(b(v)\).
`bridges()`	Return an iterator over the bridges (or cut edges).
`cleave()`	Return the connected subgraphs separated by the input vertex cut.
`degree_constrained_subgraph()`	Return a degree-constrained subgraph.
`ear_decomposition()`	Return an Ear decomposition of the graph.
`eulerian_orientation()`	Return a DiGraph which is an Eulerian orientation of the graph \(G\).
`gomory_hu_tree()`	Return a Gomory-Hu tree of `self`.
`is_triconnected()`	Check whether the graph is triconnected.
`minimum_outdegree_orientation()`	Return an orientation of \(G\) with the smallest possible maximum outdegree.
`orient()`	Return an oriented version of \(G\) according the input function \(f\).
`orientations()`	Return an iterator over orientations of \(G\).
`random_orientation()`	Return a random orientation of a graph \(G\).
`random_spanning_tree()`	Return a random spanning tree of the graph.
`spanning_trees()`	Return an iterator over all spanning trees of the graph \(g\).
`spqr_tree()`	Return an SPQR-tree representing the triconnected components of the graph.
`strong_orientation()`	Return a strongly connected orientation of the graph \(G\).
`strong_orientations_iterator()`	Return an iterator over all strong orientations of a graph \(G\).

Distances

`center()`	Return the set of vertices in the center of the graph.
`centrality_degree()`	Return the degree centrality of a vertex.
`diameter()`	Return the diameter of the graph.
`distance_graph()`	Return the graph on the same vertex set as the original graph but vertices are adjacent in the returned graph if and only if they are at specified distances in the original graph.
`eccentricity()`	Return the eccentricity of vertex (or vertices) `v`.
`hyperbolicity()`	Return the hyperbolicity of the graph or an approximation of this value.
`periphery()`	Return the set of vertices in the periphery of the graph.
`radius()`	Return the radius of the graph.

Domination

`is_dominating()`	Check whether `dom` is a dominating set of `G`.
`is_redundant()`	Check whether `dom` has redundant vertices.
`minimal_dominating_sets()`	Return an iterator over the minimal dominating sets of a graph.
`private_neighbors()`	Return the private neighbors of a vertex with respect to other vertices.

Expansion properties

`cheeger_constant()`	Return the cheeger constant of the graph.
`edge_isoperimetric_number()`	Return the edge-isoperimetric number of the graph.
`vertex_isoperimetric_number()`	Return the vertex-isoperimetric number of the graph.

Graph properties

`apex_vertices()`	Return the list of apex vertices.
`is_antipodal()`	Check whether this graph is antipodal.
`is_apex()`	Test if the graph is apex.
`is_arc_transitive()`	Check if `self` is an arc-transitive graph.
`is_asteroidal_triple_free()`	Test if the input graph is asteroidal triple-free.
`is_biconnected()`	Test if the graph is biconnected.
`is_block_graph()`	Return whether this graph is a block graph.
`is_cactus()`	Check whether the graph is cactus graph.
`is_cartesian_product()`	Test whether the graph is a Cartesian product.
`is_circumscribable()`	Test whether the graph is the graph of a circumscribed polyhedron.
`is_cograph()`	Check whether the graph is cograph.
`is_comparability()`	Test whether the graph is a comparability graph.
`is_distance_regular()`	Test if the graph is distance-regular.
`is_edge_transitive()`	Check if `self` is an edge transitive graph.
`is_even_hole_free()`	Test whether `self` contains an induced even hole.
`is_forest()`	Test if the graph is a forest, i.e. a disjoint union of trees.
`is_half_transitive()`	Check if `self` is a half-transitive graph.
`is_inscribable()`	Test whether the graph is the graph of an inscribed polyhedron.
`is_line_graph()`	Check whether the graph \(g\) is a line graph.
`is_long_antihole_free()`	Test whether the given graph contains an induced subgraph that is isomorphic to the complement of a cycle of length at least 5.
`is_long_hole_free()`	Test whether `g` contains an induced cycle of length at least 5.
`is_odd_hole_free()`	Test whether `self` contains an induced odd hole.
`is_overfull()`	Test whether the current graph is overfull.
`is_partial_cube()`	Test whether the given graph is a partial cube.
`is_path()`	Check whether `self` is a path.
`is_permutation()`	Test whether the graph is a permutation graph.
`is_polyhedral()`	Check whether the graph is the graph of the polyhedron.
`is_prime()`	Test whether the current graph is prime.
`is_semi_symmetric()`	Check if `self` is semi-symmetric.
`is_split()`	Return `True` if the graph is a Split graph, `False` otherwise.
`is_strongly_regular()`	Check whether the graph is strongly regular.
`is_tree()`	Test if the graph is a tree.
`is_triangle_free()`	Check whether `self` is triangle-free.
`is_weakly_chordal()`	Test whether the given graph is weakly chordal, i.e., the graph and its complement have no induced cycle of length at least 5.

Leftovers

`antipodal_graph()`	Return the antipodal graph of `self`.
`arboricity()`	Return the arboricity of the graph and an optional certificate.
`common_neighbors_matrix()`	Return a matrix of numbers of common neighbors between each pairs.
`cores()`	Return the core number for each vertex in an ordered list.
`effective_resistance()`	Return the effective resistance between nodes \(i\) and \(j\).
`effective_resistance_matrix()`	Return a matrix whose (\(i\) , \(j\)) entry gives the effective resistance between vertices \(i\) and \(j\).
`folded_graph()`	Return the antipodal fold of this graph.
`geodetic_closure()`	Return the geodetic closure of the set of vertices \(S\) in \(G\).
`ihara_zeta_function_inverse()`	Compute the inverse of the Ihara zeta function of the graph.
`kirchhoff_symanzik_polynomial()`	Return the Kirchhoff-Symanzik polynomial of a graph.
`least_effective_resistance()`	Return a list of pairs of nodes with the least effective resistance.
`lovasz_theta()`	Return the value of Lovász theta-function of graph.
`magnitude_function()`	Return the magnitude function of the graph as a rational function.
`maximum_average_degree()`	Return the Maximum Average Degree (MAD) of the current graph.
`modular_decomposition()`	Return the modular decomposition of the current graph.
`most_common_neighbors()`	Return vertex pairs with maximal number of common neighbors.
`seidel_adjacency_matrix()`	Return the Seidel adjacency matrix of `self`.
`seidel_switching()`	Return the Seidel switching of `self` w.r.t. subset of vertices `s`.
`two_factor_petersen()`	Return a decomposition of the graph into 2-factors.
`twograph()`	Return the two-graph of `self`.

Matching

`has_perfect_matching()`	Return whether the graph has a perfect matching.
`is_bicritical()`	Check if the graph is bicritical.
`is_factor_critical()`	Check whether the graph is factor-critical.
`is_matching_covered()`	Check if the graph is matching covered.
`matching()`	Return a maximum weighted matching of the graph represented by the list of its edges.
`perfect_matchings()`	Return an iterator over all perfect matchings of the graph.

Traversals

`lex_M()`	Return an ordering of the vertices according the LexM graph traversal.
`maximum_cardinality_search()`	Return an ordering of the vertices according a maximum cardinality search.
`maximum_cardinality_search_M()`	Return the ordering and the edges of the triangulation produced by MCS-M.

Unsorted

`bandwidth()`	Compute the bandwidth of an undirected graph.
`cutwidth()`	Return the cutwidth of the graph and the corresponding vertex ordering.
`slice_decomposition()`	Compute a slice decomposition of the simple undirected graph

AUTHORS:

Robert L. Miller (2006-10-22): initial version
William Stein (2006-12-05): Editing
Robert L. Miller (2007-01-13): refactoring, adjusting for NetworkX-0.33, fixed
plotting bugs (2007-01-23): basic tutorial, edge labels, loops, multiple edges and arcs (2007-02-07): graph6 and sparse6 formats, matrix input
Emily Kirkmann (2007-02-11): added graph_border option to plot and show
Robert L. Miller (2007-02-12): vertex color-maps, graph boundaries, graph6
helper functions in Cython
Robert L. Miller Sage Days 3 (2007-02-17-21): 3d plotting in Tachyon
Robert L. Miller (2007-02-25): display a partition
Robert L. Miller (2007-02-28): associate arbitrary objects to vertices, edge
and arc label display (in 2d), edge coloring
Robert L. Miller (2007-03-21): Automorphism group, isomorphism check,
canonical label
Robert L. Miller (2007-06-07-09): NetworkX function wrapping
Michael W. Hansen (2007-06-09): Topological sort generation
Emily Kirkman, Robert L. Miller Sage Days 4: Finished wrapping NetworkX
Emily Kirkman (2007-07-21): Genus (including circular planar, all embeddings
and all planar embeddings), all paths, interior paths
Bobby Moretti (2007-08-12): fixed up plotting of graphs with edge colors
differentiated by label
Jason Grout (2007-09-25): Added functions, bug fixes, and general enhancements
Robert L. Miller (Sage Days 7): Edge labeled graph isomorphism
Tom Boothby (Sage Days 7): Miscellaneous awesomeness
Tom Boothby (2008-01-09): Added graphviz output
David Joyner (2009-2): Fixed docstring bug related to GAP.
Stephen Hartke (2009-07-26): Fixed bug in blocks_and_cut_vertices() that
caused an incorrect result when the vertex 0 was a cut vertex.
Stephen Hartke (2009-08-22): Fixed bug in blocks_and_cut_vertices() where the
list of cut_vertices is not treated as a set.
Anders Jonsson (2009-10-10): Counting of spanning trees and out-trees added.
Nathann Cohen (2009-09)Cliquer, Connectivity, Flows and everything that
uses Linear Programming and class numerical.MIP
Nicolas M. Thiery (2010-02): graph layout code refactoring, dot2tex/graphviz interface
David Coudert (2012-04) : Reduction rules in vertex_cover.
Birk Eisermann (2012-06): added recognition of weakly chordal graphs and
long-hole-free / long-antihole-free graphs
Alexandre P. Zuge (2013-07): added join operation.
Amritanshu Prasad (2014-08): added clique polynomial
Julian Rüth (2018-06-21): upgrade to NetworkX 2
David Coudert (2018-10-07): cleaning
Amanda Francis, Caitlin Lienkaemper, Kate Collins, Rajat Mittal (2019-03-10): methods for computing effective resistance
Amanda Francis, Caitlin Lienkaemper, Kate Collins, Rajat Mittal (2019-03-19): most_common_neighbors and common_neighbors_matrix added.
Jean-Florent Raymond (2019-04): is_redundant, is_dominating,
private_neighbors

Labels¶

Each vertex can have any hashable object as a label. These are things like strings, numbers, and tuples. Each edge is given a default label of None, but if specified, edges can have any label at all. Edges between vertices \(u\) and \(v\) are represented typically as (u, v, l), where l is the label for the edge.

Note that vertex labels themselves cannot be mutable items:

Sage

sage: M = Matrix([[0,0], [0,0]])                                                    # needs sage.modules
sage: G = Graph({ 0 : { M : None } })                                               # needs sage.modules
Traceback (most recent call last):
...
TypeError: mutable matrices are unhashable

Python

>>> from sage.all import *
>>> M = Matrix([[Integer(0),Integer(0)], [Integer(0),Integer(0)]])                                                    # needs sage.modules
>>> G = Graph({ Integer(0) : { M : None } })                                               # needs sage.modules
Traceback (most recent call last):
...
TypeError: mutable matrices are unhashable

However, if one wants to define a dictionary, with the same keys and arbitrary objects for entries, one can make that association:

Sage

sage: d = {0 : graphs.DodecahedralGraph(), 1 : graphs.FlowerSnark(), \
      2 : graphs.MoebiusKantorGraph(), 3 : graphs.PetersenGraph() }
sage: d[2]
Moebius-Kantor Graph: Graph on 16 vertices
sage: T = graphs.TetrahedralGraph()
sage: T.vertices(sort=True)
[0, 1, 2, 3]
sage: T.set_vertices(d)
sage: T.get_vertex(1)
Flower Snark: Graph on 20 vertices

Python

>>> from sage.all import *
>>> d = {Integer(0) : graphs.DodecahedralGraph(), Integer(1) : graphs.FlowerSnark(), \
      2 : graphs.MoebiusKantorGraph(), 3 : graphs.PetersenGraph() }
>>> d[Integer(2)]
Moebius-Kantor Graph: Graph on 16 vertices
>>> T = graphs.TetrahedralGraph()
>>> T.vertices(sort=True)
[0, 1, 2, 3]
>>> T.set_vertices(d)
>>> T.get_vertex(Integer(1))
Flower Snark: Graph on 20 vertices

Database¶

There is a database available for searching for graphs that satisfy a certain set of parameters, including number of vertices and edges, density, maximum and minimum degree, diameter, radius, and connectivity. To see a list of all search parameter keywords broken down by their designated table names, type

Sage

sage: graph_db_info()
{...}

Python

>>> from sage.all import *
>>> graph_db_info()
{...}

For more details on data types or keyword input, enter

Sage

sage: GraphQuery?    # not tested

Python

>>> from sage.all import *
>>> GraphQuery?    # not tested

The results of a query can be viewed with the show method, or can be viewed individually by iterating through the results

Sage

sage: Q = GraphQuery(display_cols=['graph6'],num_vertices=7, diameter=5)
sage: Q.show()
Graph6
--------------------
F?`po
F?gqg
F@?]O
F@OKg
F@R@o
FA_pW
FEOhW
FGC{o
FIAHo

Python

>>> from sage.all import *
>>> Q = GraphQuery(display_cols=['graph6'],num_vertices=Integer(7), diameter=Integer(5))
>>> Q.show()
Graph6
--------------------
F?`po
F?gqg
F@?]O
F@OKg
F@R@o
FA_pW
FEOhW
FGC{o
FIAHo

Show each graph as you iterate through the results:

Sage

sage: for g in Q:                                                                   # needs sage.plot
....:     show(g)

Python

>>> from sage.all import *
>>> for g in Q:                                                                   # needs sage.plot
...     show(g)

Visualization¶

To see a graph \(G\) you are working with, there are three main options. You can view the graph in two dimensions via matplotlib with show().

Sage

sage: G = graphs.RandomGNP(15,.3)
sage: G.show()                                                                      # needs sage.plot

Python

>>> from sage.all import *
>>> G = graphs.RandomGNP(Integer(15),RealNumber('.3'))
>>> G.show()                                                                      # needs sage.plot

And you can view it in three dimensions with show3d().

Sage

sage: G.show3d()                                                                    # needs sage.plot

Python

>>> from sage.all import *
>>> G.show3d()                                                                    # needs sage.plot

Or it can be rendered with \(\LaTeX\). This requires the right additions to a standard \(\mbox{\rm\TeX}\) installation. Then standard Sage commands, such as view(G) will display the graph, or latex(G) will produce a string suitable for inclusion in a \(\LaTeX\) document. More details on this are at the sage.graphs.graph_latex module.

Sage

sage: from sage.graphs.graph_latex import check_tkz_graph
sage: check_tkz_graph()  # random - depends on TeX installation
sage: latex(G)
\begin{tikzpicture}
...
\end{tikzpicture}

Python

>>> from sage.all import *
>>> from sage.graphs.graph_latex import check_tkz_graph
>>> check_tkz_graph()  # random - depends on TeX installation
>>> latex(G)
\begin{tikzpicture}
...
\end{tikzpicture}

Mutability¶

Graphs are mutable, and thus unusable as dictionary keys, unless data_structure="static_sparse" is used:

Sage

sage: G = graphs.PetersenGraph()
sage: {G:1}[G]
Traceback (most recent call last):
...
TypeError: This graph is mutable, and thus not hashable.
Create an immutable copy by `g.copy(immutable=True)`
sage: G_immutable = Graph(G, immutable=True)
sage: G_immutable == G
True
sage: {G_immutable:1}[G_immutable]
1

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> {G:Integer(1)}[G]
Traceback (most recent call last):
...
TypeError: This graph is mutable, and thus not hashable.
Create an immutable copy by `g.copy(immutable=True)`
>>> G_immutable = Graph(G, immutable=True)
>>> G_immutable == G
True
>>> {G_immutable:Integer(1)}[G_immutable]
1

Methods¶

class sage.graphs.graph.Graph(data=None, pos=None, loops=None, format=None, weighted=None, data_structure='sparse', vertex_labels=True, name=None, multiedges=None, convert_empty_dict_labels_to_None=None, sparse=True, immutable=False, hash_labels=None)[source]¶

Bases: GenericGraph

Undirected graph.

A graph is a set of vertices connected by edges. See the Wikipedia article Graph_(mathematics) for more information. For a collection of pre-defined graphs, see the graph_generators module.

A Graph object has many methods whose list can be obtained by typing g.<tab> (i.e. hit the Tab key) or by reading the documentation of graph, generic_graph, and digraph.

INPUT:

By default, a Graph object is simple (i.e. no loops nor multiple edges) and unweighted. This can be easily tuned with the appropriate flags (see below).

data – can be any of the following (see the format argument):
1. Graph() – build a graph on 0 vertices.
2. Graph(5) – return an edgeless graph on the 5 vertices 0,…,4.
3. Graph([list_of_vertices, list_of_edges]) – returns a graph with given vertices/edges.
  
  To bypass auto-detection, prefer the more explicit Graph([V, E], format='vertices_and_edges').
4. Graph(list_of_edges) – return a graph with a given list of edges (see documentation of add_edges()).
  
  To bypass auto-detection, prefer the more explicit Graph(L, format='list_of_edges').
5. Graph({1: [2, 3, 4], 3: [4]}) – return a graph by associating to each vertex the list of its neighbors.
  
  To bypass auto-detection, prefer the more explicit Graph(D, format='dict_of_lists').
6. Graph({1: {2: 'a', 3:'b'} ,3:{2:'c'}}) – return a graph by associating a list of neighbors to each vertex and providing its edge label.
  
  To bypass auto-detection, prefer the more explicit Graph(D, format='dict_of_dicts').
  
  For graphs with multiple edges, you can provide a list of labels instead, e.g.: Graph({1: {2: ['a1', 'a2'], 3:['b']} ,3:{2:['c']}}).
7. Graph(a_symmetric_matrix) – return a graph with given (weighted) adjacency matrix (see documentation of adjacency_matrix()).
  
  To bypass auto-detection, prefer the more explicit Graph(M, format='adjacency_matrix'). To take weights into account, use format='weighted_adjacency_matrix' instead.
8. Graph(a_nonsymmetric_matrix) – return a graph with given incidence matrix (see documentation of incidence_matrix()).
  
  To bypass auto-detection, prefer the more explicit Graph(M, format='incidence_matrix').
9. Graph([V, f]) – return a graph from a vertex set V and a symmetric function f. The graph contains an edge \(u,v\) whenever f(u,v) is True.. Example: Graph([ [1..10], lambda x,y: abs(x-y).is_square()])
10. Graph(':I`ES@obGkqegW~') – return a graph from a graph6 or sparse6 string (see documentation of graph6_string() or sparse6_string()).
11. Graph(a_seidel_matrix, format='seidel_adjacency_matrix') – return a graph with a given Seidel adjacency matrix (see documentation of seidel_adjacency_matrix()).
12. Graph(another_graph) – return a graph from a Sage (di)graph, pygraphviz graph, NetworkX graph, or igraph graph.
pos – a positioning dictionary (cf. documentation of layout()). For example, to draw 4 vertices on a square:
```
{0: [-1,-1],
 1: [ 1,-1],
 2: [ 1, 1],
 3: [-1, 1]}
```
name – (must be an explicitly named parameter, i.e.,
name='complete') gives the graph a name
loops – boolean (default: None); whether to allow loops (ignored if data is an instance of the Graph class)
multiedges – boolean (default: None); whether to allow multiple edges (ignored if data is an instance of the Graph class)
weighted – boolean (default: None); whether graph thinks of itself as weighted or not. See weighted().
format – if set to None (default), Graph tries to guess input’s format. To avoid this possibly time-consuming step, one of the following values can be specified (see description above): 'int', 'graph6', 'sparse6', 'rule', 'list_of_edges', 'dict_of_lists', 'dict_of_dicts', 'adjacency_matrix', 'weighted_adjacency_matrix', 'seidel_adjacency_matrix', 'incidence_matrix', "NX", 'igraph'.
sparse – boolean (default: True); sparse=True is an alias for data_structure="sparse", and sparse=False is an alias for data_structure="dense".
data_structure – one of the following (for more information, see overview)
- 'dense' – selects the dense_graph backend.
- 'sparse' – selects the sparse_graph backend.
- 'static_sparse' – selects the static_sparse_backend (this backend is faster than the sparse backend and smaller in memory, and it is immutable, so that the resulting graphs can be used as dictionary keys).
immutable – boolean (default: False); whether to create a immutable graph. Note that immutable=True is actually a shortcut for data_structure='static_sparse'. Set to False by default.
hash_labels – boolean (default: None); whether to include edge labels during hashing. This parameter defaults to True if the graph is weighted. This parameter is ignored if the graph is mutable. Beware that trying to hash unhashable labels will raise an error.
vertex_labels – boolean (default: True); whether to allow any object as a vertex (slower), or only the integers \(0,...,n-1\), where \(n\) is the number of vertices.
convert_empty_dict_labels_to_None – this arguments sets the default edge labels used by NetworkX (empty dictionaries) to be replaced by None, the default Sage edge label. It is set to True iff a NetworkX graph is on the input.

EXAMPLES:

We illustrate the first seven input formats (the other two involve packages that are currently not standard in Sage):

When defining an undirected graph from a function f, it is very important that f be symmetric. If it is not, anything can happen:

Sage

sage: f_sym = lambda x,y: abs(x-y) == 1
sage: f_nonsym = lambda x,y: (x-y) == 1
sage: G_sym = Graph([[4,6,1,5,3,7,2,0], f_sym])
sage: G_sym.is_isomorphic(graphs.PathGraph(8))
True
sage: G_nonsym = Graph([[4,6,1,5,3,7,2,0], f_nonsym])
sage: G_nonsym.size()
4
sage: G_nonsym.is_isomorphic(G_sym)
False

Python

>>> from sage.all import *
>>> f_sym = lambda x,y: abs(x-y) == Integer(1)
>>> f_nonsym = lambda x,y: (x-y) == Integer(1)
>>> G_sym = Graph([[Integer(4),Integer(6),Integer(1),Integer(5),Integer(3),Integer(7),Integer(2),Integer(0)], f_sym])
>>> G_sym.is_isomorphic(graphs.PathGraph(Integer(8)))
True
>>> G_nonsym = Graph([[Integer(4),Integer(6),Integer(1),Integer(5),Integer(3),Integer(7),Integer(2),Integer(0)], f_nonsym])
>>> G_nonsym.size()
4
>>> G_nonsym.is_isomorphic(G_sym)
False

By default, graphs are mutable and can thus not be used as a dictionary key:

Sage

sage: G = graphs.PetersenGraph()
sage: {G:1}[G]
Traceback (most recent call last):
...
TypeError: This graph is mutable, and thus not hashable.
Create an immutable copy by `g.copy(immutable=True)`

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> {G:Integer(1)}[G]
Traceback (most recent call last):
...
TypeError: This graph is mutable, and thus not hashable.
Create an immutable copy by `g.copy(immutable=True)`

When providing the optional arguments data_structure="static_sparse" or immutable=True (both mean the same), then an immutable graph results:

Sage

sage: G_imm = Graph(G, immutable=True)
sage: H_imm = Graph(G, data_structure='static_sparse')
sage: G_imm == H_imm == G
True
sage: {G_imm:1}[H_imm]
1

Python

>>> from sage.all import *
>>> G_imm = Graph(G, immutable=True)
>>> H_imm = Graph(G, data_structure='static_sparse')
>>> G_imm == H_imm == G
True
>>> {G_imm:Integer(1)}[H_imm]
1

acyclic_orientations(G)[source]¶

Return an iterator over all acyclic orientations of an undirected graph \(G\).

ALGORITHM:

The algorithm is based on [Sq1998]. It presents an efficient algorithm for listing the acyclic orientations of a graph. The algorithm is shown to require O(n) time per acyclic orientation generated, making it the most efficient known algorithm for generating acyclic orientations.

The function uses a recursive approach to generate acyclic orientations of the graph. It reorders the vertices and edges of the graph, creating a new graph with updated labels. Then, it iteratively generates acyclic orientations by considering subsets of edges and checking whether they form upsets in a corresponding poset.

INPUT:

G – an undirected graph

OUTPUT: an iterator over all acyclic orientations of the input graph

Note

The function assumes that the input graph is undirected and the edges are unlabelled.

EXAMPLES:

To count the number of acyclic orientations for a graph:

Sage

sage: g = Graph([(0, 3), (0, 4), (3, 4), (1, 3), (1, 2), (2, 3), (2, 4)])
sage: it = g.acyclic_orientations()
sage: len(list(it))
54

Python

>>> from sage.all import *
>>> g = Graph([(Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(3), Integer(4)), (Integer(1), Integer(3)), (Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(2), Integer(4))])
>>> it = g.acyclic_orientations()
>>> len(list(it))
54

Test for arbitrary vertex labels:

Sage

sage: g_str = Graph([('abc', 'def'), ('ghi', 'def'), ('xyz', 'abc'),
....:                ('xyz', 'uvw'), ('uvw', 'abc'), ('uvw', 'ghi')])
sage: it = g_str.acyclic_orientations()
sage: len(list(it))
42

Python

>>> from sage.all import *
>>> g_str = Graph([('abc', 'def'), ('ghi', 'def'), ('xyz', 'abc'),
...                ('xyz', 'uvw'), ('uvw', 'abc'), ('uvw', 'ghi')])
>>> it = g_str.acyclic_orientations()
>>> len(list(it))
42

Check that the method returns properly relabeled acyclic digraphs:

Sage

sage: g = Graph([(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)])
sage: orientations = set([frozenset(d.edges(labels=false)) for d in g.acyclic_orientations()])
sage: len(orientations)
18
sage: all(d.is_directed_acyclic() for d in g.acyclic_orientations())
True

Python

>>> from sage.all import *
>>> g = Graph([(Integer(0), Integer(1)), (Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(3), Integer(0)), (Integer(0), Integer(2))])
>>> orientations = set([frozenset(d.edges(labels=false)) for d in g.acyclic_orientations()])
>>> len(orientations)
18
>>> all(d.is_directed_acyclic() for d in g.acyclic_orientations())
True

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

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]]

Python

>>> 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.

antipodal_graph()[source]¶

Return the antipodal graph of self.

The antipodal graph of a graph \(G\) has the same vertex set of \(G\) and two vertices are adjacent if their distance in \(G\) is equal to the diameter of \(G\).

OUTPUT: a new graph. self is not touched

EXAMPLES:

Sage

sage: G = graphs.JohnsonGraph(10, 5)
sage: G.antipodal_graph()
Antipodal graph of Johnson graph with parameters 10,5: Graph on 252 vertices
sage: G = graphs.HammingGraph(8, 2)
sage: G.antipodal_graph()
Antipodal graph of Hamming Graph with parameters 8,2: Graph on 256 vertices

Python

>>> from sage.all import *
>>> G = graphs.JohnsonGraph(Integer(10), Integer(5))
>>> G.antipodal_graph()
Antipodal graph of Johnson graph with parameters 10,5: Graph on 252 vertices
>>> G = graphs.HammingGraph(Integer(8), Integer(2))
>>> G.antipodal_graph()
Antipodal graph of Hamming Graph with parameters 8,2: Graph on 256 vertices

The antipodal graph of a disconnected graph is its complement:

Sage

sage: G = Graph(5)
sage: H = G.antipodal_graph()
sage: H.is_isomorphic(G.complement())
True

Python

>>> from sage.all import *
>>> G = Graph(Integer(5))
>>> H = G.antipodal_graph()
>>> H.is_isomorphic(G.complement())
True

apex_vertices(k=None)[source]¶

Return the list of apex vertices.

A graph is apex if it can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph, and a graph may have more than one apex. For instance, in the minimal nonplanar graphs \(K_5\) or \(K_{3,3}\), every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove. If the graph is not connected, we say that it is apex if it has at most one non planar connected component and that this component is apex. See the Wikipedia article Apex_graph for more information.

See also

INPUT:

k – integer (default: None); when set to None, the method returns the list of all apex of the graph, possibly empty if the graph is not apex. When set to a positive integer, the method ends as soon as \(k\) apex vertices are found.

OUTPUT:

By default, the method returns the list of all apex of the graph. When parameter k is set to a positive integer, the returned list is bounded to \(k\) apex vertices.

EXAMPLES:

\(K_5\) and \(K_{3,3}\) are apex graphs, and each of their vertices is an apex:

Sage

sage: G = graphs.CompleteGraph(5)
sage: G.apex_vertices()
[0, 1, 2, 3, 4]
sage: G = graphs.CompleteBipartiteGraph(3,3)
sage: G.is_apex()
True
sage: G.apex_vertices()
[0, 1, 2, 3, 4, 5]
sage: G.apex_vertices(k=3)
[0, 1, 2]

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(5))
>>> G.apex_vertices()
[0, 1, 2, 3, 4]
>>> G = graphs.CompleteBipartiteGraph(Integer(3),Integer(3))
>>> G.is_apex()
True
>>> G.apex_vertices()
[0, 1, 2, 3, 4, 5]
>>> G.apex_vertices(k=Integer(3))
[0, 1, 2]

A \(4\\times 4\)-grid is apex and each of its vertices is an apex. When adding a universal vertex, the resulting graph is apex and the universal vertex is the unique apex vertex

Sage

sage: G = graphs.Grid2dGraph(4,4)
sage: set(G.apex_vertices()) == set(G.vertices(sort=False))
True
sage: G.add_edges([('universal',v) for v in G])
sage: G.apex_vertices()
['universal']

Python

>>> from sage.all import *
>>> G = graphs.Grid2dGraph(Integer(4),Integer(4))
>>> set(G.apex_vertices()) == set(G.vertices(sort=False))
True
>>> G.add_edges([('universal',v) for v in G])
>>> G.apex_vertices()
['universal']

The Petersen graph is not apex:

Sage

sage: G = graphs.PetersenGraph()
sage: G.apex_vertices()
[]

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> G.apex_vertices()
[]

A graph is apex if all its connected components are apex, but at most one is not planar:

Sage

sage: M = graphs.Grid2dGraph(3,3)
sage: K5 = graphs.CompleteGraph(5)
sage: (M+K5).apex_vertices()
[9, 10, 11, 12, 13]
sage: (M+K5+K5).apex_vertices()
[]

Python

>>> from sage.all import *
>>> M = graphs.Grid2dGraph(Integer(3),Integer(3))
>>> K5 = graphs.CompleteGraph(Integer(5))
>>> (M+K5).apex_vertices()
[9, 10, 11, 12, 13]
>>> (M+K5+K5).apex_vertices()
[]

Neighbors of an apex of degree 2 are apex:

Sage

sage: G = graphs.Grid2dGraph(5,5)
sage: v = (666, 666)
sage: G.add_path([(1, 1), v, (3, 3)])
sage: G.is_planar()
False
sage: G.degree(v)
2
sage: sorted(G.apex_vertices())
[(1, 1), (2, 2), (3, 3), (666, 666)]

Python

>>> from sage.all import *
>>> G = graphs.Grid2dGraph(Integer(5),Integer(5))
>>> v = (Integer(666), Integer(666))
>>> G.add_path([(Integer(1), Integer(1)), v, (Integer(3), Integer(3))])
>>> G.is_planar()
False
>>> G.degree(v)
2
>>> sorted(G.apex_vertices())
[(1, 1), (2, 2), (3, 3), (666, 666)]

arboricity(certificate=False)[source]¶

Return the arboricity of the graph and an optional certificate.

The arboricity is the minimum number of forests that covers the graph.

See Wikipedia article Arboricity

INPUT:

certificate – boolean (default: False); whether to return a certificate

OUTPUT:

When certificate = True, then the function returns \((a, F)\) where \(a\) is the arboricity and \(F\) is a list of \(a\) disjoint forests that partitions the edge set of \(g\). The forests are represented as subgraphs of the original graph.

If certificate = False, the function returns just a integer indicating the arboricity.

ALGORITHM:

Represent the graph as a graphical matroid, then apply matroid sage.matroid.partition() algorithm from the matroids module.

EXAMPLES:

Sage

sage: G = graphs.PetersenGraph()
sage: a, F = G.arboricity(True)                                             # needs sage.modules
sage: a                                                                     # needs sage.modules
2
sage: all([f.is_forest() for f in F])                                       # needs sage.modules
True
sage: len(set.union(*[set(f.edges(sort=False)) for f in F])) == G.size()    # needs sage.modules
True

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> a, F = G.arboricity(True)                                             # needs sage.modules
>>> a                                                                     # needs sage.modules
2
>>> all([f.is_forest() for f in F])                                       # needs sage.modules
True
>>> len(set.union(*[set(f.edges(sort=False)) for f in F])) == G.size()    # needs sage.modules
True

atoms_and_clique_separators(G, tree=False, rooted_tree=False, separators=False)[source]¶

Return the atoms of the decomposition of \(G\) by clique minimal separators.

Let \(G = (V, E)\) be a graph. A set \(S \subset V\) is a clique separator if \(G[S]\) is a clique and the graph \(G \setminus S\) has at least 2 connected components. Let \(C \subset V\) be the vertices of a connected component of \(G \setminus S\). The graph \(G[C + S]\) is an atom if it has no clique separator.

This method implements the algorithm proposed in [BPS2010], that improves upon the algorithm proposed in [TY1984], for computing the atoms and the clique minimal separators of a graph. This algorithm is based on the maximum_cardinality_search_M() graph traversal and has time complexity in \(O(|V|\cdot|E|)\).

If the graph is not connected, we insert empty separators between the lists of separators of each connected components. See the examples below for more details.

INPUT:

G – a Sage graph
tree – boolean (default: False); whether to return the result as a directed tree in which internal nodes are clique separators and leaves are the atoms of the decomposition. Since a clique separator is repeated when its removal partition the graph into 3 or more connected components, vertices are labels by tuples \((i, S)\), where \(S\) is the set of vertices of the atom or the clique separator, and \(0 \leq i \leq |T|\).
rooted_tree – boolean (default: False); whether to return the result as a LabelledRootedTree. When tree is True, this parameter is ignored.
separators – boolean (default: False); whether to also return the complete list of separators considered during the execution of the algorithm. When tree or rooted_tree is True, this parameter is ignored.

OUTPUT:

By default, return a tuple \((A, S_c)\), where \(A\) is the list of atoms of the graph in the order of discovery, and \(S_c\) is the list of clique separators, with possible repetitions, in the order the separator has been considered. If furthermore separators is True, return a tuple \((A, S_h, S_c)\), where \(S_c\) is the list of considered separators of the graph in the order they have been considered.
When tree is True, format the result as a directed tree
When rooted_tree is True and tree is False, format the output as a LabelledRootedTree

EXAMPLES:

Example of [BPS2010]:

Sage

sage: G = Graph({'a': ['b', 'k'], 'b': ['c'], 'c': ['d', 'j', 'k'],
....:            'd': ['e', 'f', 'j', 'k'], 'e': ['g'],
....:            'f': ['g', 'j', 'k'], 'g': ['j', 'k'], 'h': ['i', 'j'],
....:            'i': ['k'], 'j': ['k']})
sage: atoms, cliques = G.atoms_and_clique_separators()
sage: sorted(sorted(a) for a in atoms)
[['a', 'b', 'c', 'k'],
 ['c', 'd', 'j', 'k'],
 ['d', 'e', 'f', 'g', 'j', 'k'],
 ['h', 'i', 'j', 'k']]
sage: sorted(sorted(c) for c in cliques)
[['c', 'k'], ['d', 'j', 'k'], ['j', 'k']]
sage: T = G.atoms_and_clique_separators(tree=True)
sage: T.is_tree()
True
sage: T.diameter() == len(atoms)
True
sage: all(u[1] in atoms for u in T if T.degree(u) == 1)
True
sage: all(u[1] in cliques for u in T if T.degree(u) != 1)
True

Python

>>> from sage.all import *
>>> G = Graph({'a': ['b', 'k'], 'b': ['c'], 'c': ['d', 'j', 'k'],
...            'd': ['e', 'f', 'j', 'k'], 'e': ['g'],
...            'f': ['g', 'j', 'k'], 'g': ['j', 'k'], 'h': ['i', 'j'],
...            'i': ['k'], 'j': ['k']})
>>> atoms, cliques = G.atoms_and_clique_separators()
>>> sorted(sorted(a) for a in atoms)
[['a', 'b', 'c', 'k'],
 ['c', 'd', 'j', 'k'],
 ['d', 'e', 'f', 'g', 'j', 'k'],
 ['h', 'i', 'j', 'k']]
>>> sorted(sorted(c) for c in cliques)
[['c', 'k'], ['d', 'j', 'k'], ['j', 'k']]
>>> T = G.atoms_and_clique_separators(tree=True)
>>> T.is_tree()
True
>>> T.diameter() == len(atoms)
True
>>> all(u[Integer(1)] in atoms for u in T if T.degree(u) == Integer(1))
True
>>> all(u[Integer(1)] in cliques for u in T if T.degree(u) != Integer(1))
True

A graph without clique separator:

Sage

sage: G = graphs.CompleteGraph(5)
sage: G.atoms_and_clique_separators()
([{0, 1, 2, 3, 4}], [])
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
{0, 1, 2, 3, 4}

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(5))
>>> G.atoms_and_clique_separators()
([{0, 1, 2, 3, 4}], [])
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
{0, 1, 2, 3, 4}

Graphs with several biconnected components:

Sage

sage: G = graphs.PathGraph(4)
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ____{2}____
 /          /
{2, 3}   __{1}__
        /      /
       {1, 2} {0, 1}

sage: G = graphs.WindmillGraph(3, 4)
sage: G.atoms_and_clique_separators()
([{0, 1, 2}, {0, 3, 4}, {0, 5, 6}, {0, 8, 7}], [{0}, {0}, {0}])
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ________{0}________
 /                  /
{0, 1, 2}   _______{0}______
           /               /
          {0, 3, 4}   ____{0}___
                     /         /
                    {0, 8, 7} {0, 5, 6}

Python

>>> from sage.all import *
>>> G = graphs.PathGraph(Integer(4))
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ____{2}____
 /          /
{2, 3}   __{1}__
        /      /
       {1, 2} {0, 1}

>>> G = graphs.WindmillGraph(Integer(3), Integer(4))
>>> G.atoms_and_clique_separators()
([{0, 1, 2}, {0, 3, 4}, {0, 5, 6}, {0, 8, 7}], [{0}, {0}, {0}])
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ________{0}________
 /                  /
{0, 1, 2}   _______{0}______
           /               /
          {0, 3, 4}   ____{0}___
                     /         /
                    {0, 8, 7} {0, 5, 6}

When the removal of a clique separator results in \(k > 2\) connected components, this separator is repeated \(k - 1\) times, but the repetitions are not necessarily contiguous:

Sage

sage: G = Graph(2)
sage: for i in range(5):
....:     G.add_cycle([0, 1, G.add_vertex()])
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  _________{0, 1}_____
 /                   /
{0, 1, 4}   ________{0, 1}_____
           /                  /
          {0, 1, 2}   _______{0, 1}___
                     /               /
                    {0, 1, 3}   ____{0, 1}
                               /         /
                              {0, 1, 5} {0, 1, 6}

sage: G = graphs.StarGraph(3)
sage: G.subdivide_edges(G.edges(sort=False), 2)
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ______{5}______
 /              /
{1, 5}   ______{7}______
        /              /
       {2, 7}   ______{9}______
               /              /
              {9, 3}   ______{6}______
                      /              /
                     {6, 7}   ______{4}_____
                             /             /
                            {4, 5}   _____{0}_____
                                    /            /
                                   {0, 6}   ____{8}____
                                           /          /
                                          {8, 9}   __{0}__
                                                  /      /
                                                 {0, 8} {0, 4}

Python

>>> from sage.all import *
>>> G = Graph(Integer(2))
>>> for i in range(Integer(5)):
...     G.add_cycle([Integer(0), Integer(1), G.add_vertex()])
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  _________{0, 1}_____
 /                   /
{0, 1, 4}   ________{0, 1}_____
           /                  /
          {0, 1, 2}   _______{0, 1}___
                     /               /
                    {0, 1, 3}   ____{0, 1}
                               /         /
                              {0, 1, 5} {0, 1, 6}

>>> G = graphs.StarGraph(Integer(3))
>>> G.subdivide_edges(G.edges(sort=False), Integer(2))
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ______{5}______
 /              /
{1, 5}   ______{7}______
        /              /
       {2, 7}   ______{9}______
               /              /
              {9, 3}   ______{6}______
                      /              /
                     {6, 7}   ______{4}_____
                             /             /
                            {4, 5}   _____{0}_____
                                    /            /
                                   {0, 6}   ____{8}____
                                           /          /
                                          {8, 9}   __{0}__
                                                  /      /
                                                 {0, 8} {0, 4}

If the graph is not connected, we insert empty separators between the lists of separators of each connected components. For instance, let \(G\) be a graph with 3 connected components. The method returns the list \(S_c = [S_0,\cdots,S_{i},\ldots, S_{j},\ldots,S_{k-1}]\) of \(k\) clique separators, where \(i\) and \(j\) are the indexes of the inserted empty separators and \(0 \leq i < j < k - 1\). The method also returns the list \(A = [A_0,\ldots,S_{k}]\) of the \(k + 1\) atoms, with \(k + 1 \geq 3\). The lists of atoms and clique separators of each of the connected components are respectively \([A_0,\ldots,A_{i}]\) and \([S_0,\ldots,S_{i-1}]\), \([A_{i+1},\ldots,A_{j}]\) and \([S_{i+1},\ldots,S_{j-1}]\), and \([A_{j+1},\ldots,A_{k}]\) and \([S_{j+1},\ldots,S_{k-1}]\). One can check that for each connected component, we get one atom more than clique separators:

Sage

sage: G = graphs.PathGraph(3) * 3
sage: A, Sc = G.atoms_and_clique_separators()
sage: A
[{1, 2}, {0, 1}, {4, 5}, {3, 4}, {8, 7}, {6, 7}]
sage: Sc
[{1}, {}, {4}, {}, {7}]
sage: i , j = [i for i, s in enumerate(Sc) if not s]
sage: i, j
(1, 3)
sage: A[:i+1], Sc[:i]
([{1, 2}, {0, 1}], [{1}])
sage: A[i+1:j+1], Sc[i+1:j]
([{4, 5}, {3, 4}], [{4}])
sage: A[j+1:], Sc[j+1:]
([{8, 7}, {6, 7}], [{7}])
sage: I = [-1, i, j, len(Sc)]
sage: for i, j in zip(I[:-1], I[1:]):
....:     print(A[i+1:j+1], Sc[i+1:j])
[{1, 2}, {0, 1}] [{1}]
[{4, 5}, {3, 4}] [{4}]
[{8, 7}, {6, 7}] [{7}]
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ______{1}______
 /              /
{1, 2}   ______{}______
        /             /
       {0, 1}   _____{4}_____
               /            /
              {4, 5}   ____{}_____
                      /          /
                     {3, 4}   __{7}__
                             /      /
                            {6, 7} {8, 7}

Python

>>> from sage.all import *
>>> G = graphs.PathGraph(Integer(3)) * Integer(3)
>>> A, Sc = G.atoms_and_clique_separators()
>>> A
[{1, 2}, {0, 1}, {4, 5}, {3, 4}, {8, 7}, {6, 7}]
>>> Sc
[{1}, {}, {4}, {}, {7}]
>>> i , j = [i for i, s in enumerate(Sc) if not s]
>>> i, j
(1, 3)
>>> A[:i+Integer(1)], Sc[:i]
([{1, 2}, {0, 1}], [{1}])
>>> A[i+Integer(1):j+Integer(1)], Sc[i+Integer(1):j]
([{4, 5}, {3, 4}], [{4}])
>>> A[j+Integer(1):], Sc[j+Integer(1):]
([{8, 7}, {6, 7}], [{7}])
>>> I = [-Integer(1), i, j, len(Sc)]
>>> for i, j in zip(I[:-Integer(1)], I[Integer(1):]):
...     print(A[i+Integer(1):j+Integer(1)], Sc[i+Integer(1):j])
[{1, 2}, {0, 1}] [{1}]
[{4, 5}, {3, 4}] [{4}]
[{8, 7}, {6, 7}] [{7}]
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ______{1}______
 /              /
{1, 2}   ______{}______
        /             /
       {0, 1}   _____{4}_____
               /            /
              {4, 5}   ____{}_____
                      /          /
                     {3, 4}   __{7}__
                             /      /
                            {6, 7} {8, 7}

Loops and multiple edges are ignored:

Sage

sage: G.allow_loops(True)
sage: G.add_edges([(u, u) for u in G])
sage: G.allow_multiple_edges(True)
sage: G.add_edges(G.edges(sort=False))
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ______{1}______
 /              /
{1, 2}   ______{}______
        /             /
       {0, 1}   _____{4}_____
               /            /
              {4, 5}   ____{}_____
                      /          /
                     {3, 4}   __{7}__
                             /      /
                            {6, 7} {8, 7}

Python

>>> from sage.all import *
>>> G.allow_loops(True)
>>> G.add_edges([(u, u) for u in G])
>>> G.allow_multiple_edges(True)
>>> G.add_edges(G.edges(sort=False))
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
  ______{1}______
 /              /
{1, 2}   ______{}______
        /             /
       {0, 1}   _____{4}_____
               /            /
              {4, 5}   ____{}_____
                      /          /
                     {3, 4}   __{7}__
                             /      /
                            {6, 7} {8, 7}

We can check that the returned list of separators is valid:

Sage

sage: G = graphs.RandomGNP(50, .1)
sage: while not G.is_connected():
....:     G = graphs.RandomGNP(50, .1)
sage: _, separators, _ = G.atoms_and_clique_separators(separators=True)
sage: for S in separators:
....:     H = G.copy()
....:     H.delete_vertices(S)
....:     if H.is_connected():
....:         raise ValueError("something goes wrong")

Python

>>> from sage.all import *
>>> G = graphs.RandomGNP(Integer(50), RealNumber('.1'))
>>> while not G.is_connected():
...     G = graphs.RandomGNP(Integer(50), RealNumber('.1'))
>>> _, separators, _ = G.atoms_and_clique_separators(separators=True)
>>> for S in separators:
...     H = G.copy()
...     H.delete_vertices(S)
...     if H.is_connected():
...         raise ValueError("something goes wrong")

bandwidth(G, k=None)[source]¶

Compute the bandwidth of an undirected graph.

For a definition of the bandwidth of a graph, see the documentation of the bandwidth module.

INPUT:

G – a graph
k – integer (default: None); set to an integer value to test whether \(bw(G)\leq k\), or to None (default) to compute \(bw(G)\)

OUTPUT:

When \(k\) is an integer value, the function returns either False or an ordering of cost \(\leq k\).

When \(k\) is equal to None, the function returns a pair (bw, ordering).

See also

sage.graphs.generic_graph.GenericGraph.adjacency_matrix() – return the adjacency matrix from an ordering of the vertices.

EXAMPLES:

Sage

sage: from sage.graphs.graph_decompositions.bandwidth import bandwidth
sage: G = graphs.PetersenGraph()
sage: bandwidth(G,3)
False
sage: bandwidth(G)
(5, [0, 4, 5, 8, 1, 9, 3, 7, 6, 2])
sage: G.adjacency_matrix(vertices=[0, 4, 5, 8, 1, 9, 3, 7, 6, 2])               # needs sage.modules
[0 1 1 0 1 0 0 0 0 0]
[1 0 0 0 0 1 1 0 0 0]
[1 0 0 1 0 0 0 1 0 0]
[0 0 1 0 0 0 1 0 1 0]
[1 0 0 0 0 0 0 0 1 1]
[0 1 0 0 0 0 0 1 1 0]
[0 1 0 1 0 0 0 0 0 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 1 1 0 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
sage: G = graphs.ChvatalGraph()
sage: bandwidth(G)
(6, [0, 5, 9, 4, 10, 1, 6, 11, 3, 8, 7, 2])
sage: G.adjacency_matrix(vertices=[0, 5, 9, 4, 10, 1, 6, 11, 3, 8, 7, 2])       # needs sage.modules
[0 0 1 1 0 1 1 0 0 0 0 0]
[0 0 0 1 1 1 0 1 0 0 0 0]
[1 0 0 0 1 0 0 1 1 0 0 0]
[1 1 0 0 0 0 0 0 1 1 0 0]
[0 1 1 0 0 0 1 0 0 1 0 0]
[1 1 0 0 0 0 0 0 0 0 1 1]
[1 0 0 0 1 0 0 1 0 0 0 1]
[0 1 1 0 0 0 1 0 0 0 1 0]
[0 0 1 1 0 0 0 0 0 0 1 1]
[0 0 0 1 1 0 0 0 0 0 1 1]
[0 0 0 0 0 1 0 1 1 1 0 0]
[0 0 0 0 0 1 1 0 1 1 0 0]

Python

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.bandwidth import bandwidth
>>> G = graphs.PetersenGraph()
>>> bandwidth(G,Integer(3))
False
>>> bandwidth(G)
(5, [0, 4, 5, 8, 1, 9, 3, 7, 6, 2])
>>> G.adjacency_matrix(vertices=[Integer(0), Integer(4), Integer(5), Integer(8), Integer(1), Integer(9), Integer(3), Integer(7), Integer(6), Integer(2)])               # needs sage.modules
[0 1 1 0 1 0 0 0 0 0]
[1 0 0 0 0 1 1 0 0 0]
[1 0 0 1 0 0 0 1 0 0]
[0 0 1 0 0 0 1 0 1 0]
[1 0 0 0 0 0 0 0 1 1]
[0 1 0 0 0 0 0 1 1 0]
[0 1 0 1 0 0 0 0 0 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 1 1 0 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
>>> G = graphs.ChvatalGraph()
>>> bandwidth(G)
(6, [0, 5, 9, 4, 10, 1, 6, 11, 3, 8, 7, 2])
>>> G.adjacency_matrix(vertices=[Integer(0), Integer(5), Integer(9), Integer(4), Integer(10), Integer(1), Integer(6), Integer(11), Integer(3), Integer(8), Integer(7), Integer(2)])       # needs sage.modules
[0 0 1 1 0 1 1 0 0 0 0 0]
[0 0 0 1 1 1 0 1 0 0 0 0]
[1 0 0 0 1 0 0 1 1 0 0 0]
[1 1 0 0 0 0 0 0 1 1 0 0]
[0 1 1 0 0 0 1 0 0 1 0 0]
[1 1 0 0 0 0 0 0 0 0 1 1]
[1 0 0 0 1 0 0 1 0 0 0 1]
[0 1 1 0 0 0 1 0 0 0 1 0]
[0 0 1 1 0 0 0 0 0 0 1 1]
[0 0 0 1 1 0 0 0 0 0 1 1]
[0 0 0 0 0 1 0 1 1 1 0 0]
[0 0 0 0 0 1 1 0 1 1 0 0]

bipartite_color()[source]¶

Return a dictionary with vertices as the keys and the color class as the values.

Fails with an error if the graph is not bipartite.

EXAMPLES:

Sage

sage: graphs.CycleGraph(4).bipartite_color()
{0: 1, 1: 0, 2: 1, 3: 0}
sage: graphs.CycleGraph(5).bipartite_color()
Traceback (most recent call last):
...
RuntimeError: Graph is not bipartite.

Python

>>> from sage.all import *
>>> graphs.CycleGraph(Integer(4)).bipartite_color()
{0: 1, 1: 0, 2: 1, 3: 0}
>>> graphs.CycleGraph(Integer(5)).bipartite_color()
Traceback (most recent call last):
...
RuntimeError: Graph is not bipartite.

bipartite_double(extended=False)[source]¶

Return the (extended) bipartite double of this graph.

The bipartite double of a graph \(G\) has vertex set \(\{ (v,0), (v,1) : v \in G\}\) and for any edge \((u, v)\) in \(G\) it has edges \(((u,0),(v,1))\) and \(((u,1),(v,0))\). Note that this is the tensor product of \(G\) with \(K_2\).

The extended bipartite double of \(G\) is the bipartite double of \(G\) after added all edges \(((v,0),(v,1))\) for all vertices \(v\).

INPUT:

extended – boolean (default: False); whether to return the extended bipartite double, or only the bipartite double (default)

OUTPUT: a graph; self is left untouched

EXAMPLES:

Sage

sage: G = graphs.PetersenGraph()
sage: H = G.bipartite_double()
sage: G == graphs.PetersenGraph()  # G is left invariant
True
sage: H.order() == 2 * G.order()
True
sage: H.size() == 2 * G.size()
True
sage: H.is_bipartite()
True
sage: H.bipartite_sets() == (set([(v, 0) for v in G]),
....: set([(v, 1) for v in G]))
True
sage: H.is_isomorphic(G.tensor_product(graphs.CompleteGraph(2)))
True

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> H = G.bipartite_double()
>>> G == graphs.PetersenGraph()  # G is left invariant
True
>>> H.order() == Integer(2) * G.order()
True
>>> H.size() == Integer(2) * G.size()
True
>>> H.is_bipartite()
True
>>> H.bipartite_sets() == (set([(v, Integer(0)) for v in G]),
... set([(v, Integer(1)) for v in G]))
True
>>> H.is_isomorphic(G.tensor_product(graphs.CompleteGraph(Integer(2))))
True

Behaviour with disconnected graphs:

Sage

sage: G1 = graphs.PetersenGraph()
sage: G2 = graphs.HoffmanGraph()
sage: G = G1.disjoint_union(G2)
sage: H = G.bipartite_double()
sage: H1 = G1.bipartite_double()
sage: H2 = G2.bipartite_double()
sage: H.is_isomorphic(H1.disjoint_union(H2))
True

Python

>>> from sage.all import *
>>> G1 = graphs.PetersenGraph()
>>> G2 = graphs.HoffmanGraph()
>>> G = G1.disjoint_union(G2)
>>> H = G.bipartite_double()
>>> H1 = G1.bipartite_double()
>>> H2 = G2.bipartite_double()
>>> H.is_isomorphic(H1.disjoint_union(H2))
True

See also

Wikipedia article Bipartite_double_cover, WolframAlpha Bipartite Double, [VDKT2016] p. 20 for the extended bipartite double.

bipartite_sets()[source]¶

Return \((X,Y)\) where \(X\) and \(Y\) are the nodes in each bipartite set of graph \(G\).

Fails with an error if graph is not bipartite.

EXAMPLES:

Sage

sage: graphs.CycleGraph(4).bipartite_sets()
({0, 2}, {1, 3})
sage: graphs.CycleGraph(5).bipartite_sets()
Traceback (most recent call last):
...
RuntimeError: Graph is not bipartite.

Python

>>> from sage.all import *
>>> graphs.CycleGraph(Integer(4)).bipartite_sets()
({0, 2}, {1, 3})
>>> graphs.CycleGraph(Integer(5)).bipartite_sets()
Traceback (most recent call last):
...
RuntimeError: Graph is not bipartite.

bounded_outdegree_orientation(G, bound, solver, verbose=None, integrality_tolerance=False)[source]¶

Return an orientation of \(G\) such that every vertex \(v\) has out-degree less than \(b(v)\).

INPUT:

G – an undirected graph
bound – maximum bound on the out-degree. Can be of three different types :
- An integer \(k\). In this case, computes an orientation whose maximum out-degree is less than \(k\).
- A dictionary associating to each vertex its associated maximum out-degree.
- A function associating to each vertex its associated maximum out-degree.
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

A DiGraph representing the orientation if it exists. A ValueError exception is raised otherwise.

ALGORITHM:

The problem is solved through a maximum flow :

Given a graph \(G\), we create a DiGraph \(D\) defined on \(E(G)\cup V(G)\cup \{s,t\}\). We then link \(s\) to all of \(V(G)\) (these edges having a capacity equal to the bound associated to each element of \(V(G)\)), and all the elements of \(E(G)\) to \(t\) . We then link each \(v \in V(G)\) to each of its incident edges in \(G\). A maximum integer flow of value \(|E(G)|\) corresponds to an admissible orientation of \(G\). Otherwise, none exists.

EXAMPLES:

There is always an orientation of a graph \(G\) such that a vertex \(v\) has out-degree at most \(\lceil \frac {d(v)} 2 \rceil\):

Sage

sage: g = graphs.RandomGNP(40, .4)
sage: b = lambda v: integer_ceil(g.degree(v)/2)
sage: D = g.bounded_outdegree_orientation(b)
sage: all(D.out_degree(v) <= b(v) for v in g)
True

Python

>>> from sage.all import *
>>> g = graphs.RandomGNP(Integer(40), RealNumber('.4'))
>>> b = lambda v: integer_ceil(g.degree(v)/Integer(2))
>>> D = g.bounded_outdegree_orientation(b)
>>> all(D.out_degree(v) <= b(v) for v in g)
True

Chvatal’s graph, being 4-regular, can be oriented in such a way that its maximum out-degree is 2:

Sage

sage: g = graphs.ChvatalGraph()
sage: D = g.bounded_outdegree_orientation(2)
sage: max(D.out_degree())
2

Python

>>> from sage.all import *
>>> g = graphs.ChvatalGraph()
>>> D = g.bounded_outdegree_orientation(Integer(2))
>>> max(D.out_degree())
2

For any graph \(G\), it is possible to compute an orientation such that the maximum out-degree is at most the maximum average degree of \(G\) divided by 2. Anything less, though, is impossible.

sage: g = graphs.RandomGNP(40, .4) sage: mad = g.maximum_average_degree() # needs sage.numerical.mip

Hence this is possible

Sage

sage: d = g.bounded_outdegree_orientation(integer_ceil(mad/2))              # needs sage.numerical.mip

Python

>>> from sage.all import *
>>> d = g.bounded_outdegree_orientation(integer_ceil(mad/Integer(2)))              # needs sage.numerical.mip

While this is not:

Sage

sage: try:                                                                  # needs sage.numerical.mip
....:     g.bounded_outdegree_orientation(integer_ceil(mad/2-1))
....:     print("Error")
....: except ValueError:
....:     pass

Python

>>> from sage.all import *
>>> try:                                                                  # needs sage.numerical.mip
...     g.bounded_outdegree_orientation(integer_ceil(mad/Integer(2)-Integer(1)))
...     print("Error")
... except ValueError:
...     pass

The bounds can be specified in different ways:

Sage

sage: g = graphs.PetersenGraph()
sage: b = lambda v: integer_ceil(g.degree(v)/2)
sage: D = g.bounded_outdegree_orientation(b)
sage: b_dict = {u: b(u) for u in g}
sage: D = g.bounded_outdegree_orientation(b_dict)
sage: unique_bound = 2
sage: D = g.bounded_outdegree_orientation(unique_bound)

Python

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> b = lambda v: integer_ceil(g.degree(v)/Integer(2))
>>> D = g.bounded_outdegree_orientation(b)
>>> b_dict = {u: b(u) for u in g}
>>> D = g.bounded_outdegree_orientation(b_dict)
>>> unique_bound = Integer(2)
>>> D = g.bounded_outdegree_orientation(unique_bound)

bridges(G, labels=True)[source]¶

Return an iterator over the bridges (or cut edges).

A bridge is an edge whose deletion disconnects the undirected graph. A disconnected graph has no bridge.

INPUT:

labels – boolean (default: True); if False, each bridge is a tuple \((u, v)\) of vertices

EXAMPLES:

Sage

sage: from sage.graphs.connectivity import bridges
sage: from sage.graphs.connectivity import is_connected
sage: g = 2 * graphs.PetersenGraph()
sage: g.add_edge(1, 10)
sage: is_connected(g)
True
sage: list(bridges(g))
[(1, 10, None)]
sage: list(g.bridges())
[(1, 10, None)]

Python

>>> from sage.all import *
>>> from sage.graphs.connectivity import bridges
>>> from sage.graphs.connectivity import is_connected
>>> g = Integer(2) * graphs.PetersenGraph()
>>> g.add_edge(Integer(1), Integer(10))
>>> is_connected(g)
True
>>> list(bridges(g))
[(1, 10, None)]
>>> list(g.bridges())
[(1, 10, None)]

Every edge of a tree is a bridge:

Sage

sage: g = graphs.RandomTree(100)
sage: sum(1 for _ in g.bridges()) == 99
True

Python

>>> from sage.all import *
>>> g = graphs.RandomTree(Integer(100))
>>> sum(Integer(1) for _ in g.bridges()) == Integer(99)
True

center(by_weight=False, algorithm=None, weight_function=None, check_weight=True)[source]¶

Return the set of vertices in the center of the graph.

The center is the set of vertices whose eccentricity is equal to the radius of the graph, i.e., achieving the minimum eccentricity.

For more information and examples on how to use input variables, see shortest_paths() and eccentricity()

INPUT:

by_weight – boolean (default: False); if True, edge weights are taken into account; if False, all edges have weight 1
algorithm – string (default: None); see method eccentricity() for the list of available algorithms
weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight, if l is not None, else 1 as a weight.
check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge

EXAMPLES:

Is Central African Republic in the center of Africa in graph theoretic sense? Yes:

Sage

sage: A = graphs.AfricaMap(continental=True)
sage: sorted(A.center())
['Cameroon', 'Central Africa']

Python

>>> from sage.all import *
>>> A = graphs.AfricaMap(continental=True)
>>> sorted(A.center())
['Cameroon', 'Central Africa']

Some other graphs. Center can be the whole graph:

Sage

sage: G = graphs.DiamondGraph()
sage: G.center()
[1, 2]
sage: P = graphs.PetersenGraph()
sage: P.subgraph(P.center()) == P
True
sage: S = graphs.StarGraph(19)
sage: S.center()
[0]

Python

>>> from sage.all import *
>>> G = graphs.DiamondGraph()
>>> G.center()
[1, 2]
>>> P = graphs.PetersenGraph()
>>> P.subgraph(P.center()) == P
True
>>> S = graphs.StarGraph(Integer(19))
>>> S.center()
[0]

centrality_degree(v=None)[source]¶

Return the degree centrality of a vertex.

The degree centrality of a vertex \(v\) is its degree, divided by \(|V(G)|-1\). For more information, see the Wikipedia article Centrality.

INPUT:

v – a vertex (default: None); set to None (default) to get a dictionary associating each vertex with its centrality degree

See also

EXAMPLES:

Sage

sage: (graphs.ChvatalGraph()).centrality_degree()
{0: 4/11, 1: 4/11, 2: 4/11, 3: 4/11,  4: 4/11,  5: 4/11,
 6: 4/11, 7: 4/11, 8: 4/11, 9: 4/11, 10: 4/11, 11: 4/11}
sage: D = graphs.DiamondGraph()
sage: D.centrality_degree()
{0: 2/3, 1: 1, 2: 1, 3: 2/3}
sage: D.centrality_degree(v=1)
1

Python

>>> from sage.all import *
>>> (graphs.ChvatalGraph()).centrality_degree()
{0: 4/11, 1: 4/11, 2: 4/11, 3: 4/11,  4: 4/11,  5: 4/11,
 6: 4/11, 7: 4/11, 8: 4/11, 9: 4/11, 10: 4/11, 11: 4/11}
>>> D = graphs.DiamondGraph()
>>> D.centrality_degree()
{0: 2/3, 1: 1, 2: 1, 3: 2/3}
>>> D.centrality_degree(v=Integer(1))
1

cheeger_constant(g)[source]¶

Return the cheeger constant of the graph.

The Cheeger constant of a graph \(G = (V,E)\) is the minimum of \(|\partial S| / |Vol(S)|\) where \(Vol(S)\) is the sum of degrees of element in \(S\), \(\partial S\) is the edge boundary of \(S\) (number of edges with one end in \(S\) and one end in \(V \setminus S\)) and the minimum is taken over all non-empty subsets \(S\) of vertices so that \(|Vol(S)| \leq |E|\).

See also

Alternative but similar quantities can be obtained via the methods edge_isoperimetric_number() and vertex_isoperimetric_number().

EXAMPLES:

Sage

sage: graphs.PetersenGraph().cheeger_constant()
1/3

Python

>>> from sage.all import *
>>> graphs.PetersenGraph().cheeger_constant()
1/3

The Cheeger constant of a cycle on \(n\) vertices is \(1/\lfloor n/2 \rfloor\):

Sage

sage: [graphs.CycleGraph(k).cheeger_constant() for k in range(2,10)]
[1, 1, 1/2, 1/2, 1/3, 1/3, 1/4, 1/4]

Python

>>> from sage.all import *
>>> [graphs.CycleGraph(k).cheeger_constant() for k in range(Integer(2),Integer(10))]
[1, 1, 1/2, 1/2, 1/3, 1/3, 1/4, 1/4]

The Cheeger constant of a complete graph on \(n\) vertices is \(\lceil n/2 \rceil / (n-1)\):

Sage

sage: [graphs.CompleteGraph(k).cheeger_constant() for k in range(2,10)]
[1, 1, 2/3, 3/4, 3/5, 2/3, 4/7, 5/8]

Python

>>> from sage.all import *
>>> [graphs.CompleteGraph(k).cheeger_constant() for k in range(Integer(2),Integer(10))]
[1, 1, 2/3, 3/4, 3/5, 2/3, 4/7, 5/8]

For complete bipartite:

Sage

sage: [graphs.CompleteBipartiteGraph(i,j).cheeger_constant() for i in range(2,7) for j in range(2, i)]
[3/5, 1/2, 3/5, 5/9, 4/7, 5/9, 1/2, 5/9, 1/2, 5/9]

Python

>>> from sage.all import *
>>> [graphs.CompleteBipartiteGraph(i,j).cheeger_constant() for i in range(Integer(2),Integer(7)) for j in range(Integer(2), i)]
[3/5, 1/2, 3/5, 5/9, 4/7, 5/9, 1/2, 5/9, 1/2, 5/9]

More examples:

Sage

sage: G = Graph([(0, 1), (0, 3), (0, 8), (1, 4), (1, 6), (2, 4), (2, 7), (2, 9),
....:            (3, 6), (3, 8), (4, 9), (5, 6), (5, 7), (5, 8), (7, 9)])
sage: G.cheeger_constant()
1/6

sage: G = Graph([(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (3, 4), (3, 5)])
sage: G.cheeger_constant()
1/2

sage: Graph([[1,2,3,4],[(1,2),(3,4)]]).cheeger_constant()
0

Python

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(3)), (Integer(0), Integer(8)), (Integer(1), Integer(4)), (Integer(1), Integer(6)), (Integer(2), Integer(4)), (Integer(2), Integer(7)), (Integer(2), Integer(9)),
...            (Integer(3), Integer(6)), (Integer(3), Integer(8)), (Integer(4), Integer(9)), (Integer(5), Integer(6)), (Integer(5), Integer(7)), (Integer(5), Integer(8)), (Integer(7), Integer(9))])
>>> G.cheeger_constant()
1/6

>>> G = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(1), Integer(4)), (Integer(1), Integer(5)), (Integer(2), Integer(3)), (Integer(3), Integer(4)), (Integer(3), Integer(5))])
>>> G.cheeger_constant()
1/2

>>> Graph([[Integer(1),Integer(2),Integer(3),Integer(4)],[(Integer(1),Integer(2)),(Integer(3),Integer(4))]]).cheeger_constant()
0

chromatic_index(solver, verbose=None, integrality_tolerance=0)[source]¶

Return the chromatic index of the graph.

The chromatic index is the minimal number of colors needed to properly color the edges of the graph.

INPUT:

solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

This method is a frontend for method sage.graphs.graph_coloring.edge_coloring() that uses a mixed integer-linear programming formulation to compute the chromatic index.

See also

Wikipedia article Edge_coloring for further details on edge coloring
sage.graphs.graph_coloring.edge_coloring()
fractional_chromatic_index()
chromatic_number()

EXAMPLES:

The clique \(K_n\) has chromatic index \(n\) when \(n\) is odd and \(n-1\) when \(n\) is even:

Sage

sage: graphs.CompleteGraph(4).chromatic_index()
3
sage: graphs.CompleteGraph(5).chromatic_index()
5
sage: graphs.CompleteGraph(6).chromatic_index()
5

Python

>>> from sage.all import *
>>> graphs.CompleteGraph(Integer(4)).chromatic_index()
3
>>> graphs.CompleteGraph(Integer(5)).chromatic_index()
5
>>> graphs.CompleteGraph(Integer(6)).chromatic_index()
5

The path \(P_n\) with \(n \geq 2\) has chromatic index 2:

Sage

sage: graphs.PathGraph(5).chromatic_index()                                 # needs sage.numerical.mip
2

Python

>>> from sage.all import *
>>> graphs.PathGraph(Integer(5)).chromatic_index()                                 # needs sage.numerical.mip
2

The windmill graph with parameters \(k,n\) has chromatic index \((k-1)n\):

Sage

sage: k,n = 3,4
sage: G = graphs.WindmillGraph(k,n)
sage: G.chromatic_index() == (k-1)*n                                        # needs sage.numerical.mip
True

Python

>>> from sage.all import *
>>> k,n = Integer(3),Integer(4)
>>> G = graphs.WindmillGraph(k,n)
>>> G.chromatic_index() == (k-Integer(1))*n                                        # needs sage.numerical.mip
True

chromatic_number(algorithm, solver='DLX', verbose=None, integrality_tolerance=0)[source]¶

Return the minimal number of colors needed to color the vertices of the graph.

INPUT:

algorithm – string (default: 'DLX'); one of the following algorithms:
- 'DLX' (default): the chromatic number is computed using the dancing link algorithm. It is inefficient speedwise to compute the chromatic number through the dancing link algorithm because this algorithm computes all the possible colorings to check that one exists.
- 'CP': the chromatic number is computed using the coefficients of the chromatic polynomial. Again, this method is inefficient in terms of speed and it only useful for small graphs.
- 'MILP': the chromatic number is computed using a mixed integer linear program. The performance of this implementation is affected by whether optional MILP solvers have been installed (see the MILP module, or Sage’s tutorial on Linear Programming).
- 'parallel': all the above algorithms are executed in parallel and the result is returned as soon as one algorithm ends. Observe that the speed of the above algorithms depends on the size and structure of the graph.
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

See also

For more functions related to graph coloring, see the module sage.graphs.graph_coloring.

EXAMPLES:

Sage

sage: G = Graph({0: [1, 2, 3], 1: [2]})
sage: G.chromatic_number(algorithm='DLX')
3
sage: G.chromatic_number(algorithm='MILP')
3
sage: G.chromatic_number(algorithm='CP')                                    # needs sage.libs.flint
3
sage: G.chromatic_number(algorithm='parallel')
3

Python

>>> from sage.all import *
>>> G = Graph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(2)]})
>>> G.chromatic_number(algorithm='DLX')
3
>>> G.chromatic_number(algorithm='MILP')
3
>>> G.chromatic_number(algorithm='CP')                                    # needs sage.libs.flint
3
>>> G.chromatic_number(algorithm='parallel')
3

A bipartite graph has (by definition) chromatic number 2:

Sage

sage: graphs.RandomBipartite(50,50,0.7).chromatic_number()                  # needs numpy
2

Python

>>> from sage.all import *
>>> graphs.RandomBipartite(Integer(50),Integer(50),RealNumber('0.7')).chromatic_number()                  # needs numpy
2

A complete multipartite graph with \(k\) parts has chromatic number \(k\):

Sage

sage: all(graphs.CompleteMultipartiteGraph([5]*i).chromatic_number() == i
....:     for i in range(2, 5))
True

Python

>>> from sage.all import *
>>> all(graphs.CompleteMultipartiteGraph([Integer(5)]*i).chromatic_number() == i
...     for i in range(Integer(2), Integer(5)))
True

The complete graph has the largest chromatic number from all the graphs of order \(n\). Namely its chromatic number is \(n\):

Sage

sage: all(graphs.CompleteGraph(i).chromatic_number() == i for i in range(10))
True

Python

>>> from sage.all import *
>>> all(graphs.CompleteGraph(i).chromatic_number() == i for i in range(Integer(10)))
True

The Kneser graph with parameters \((n, 2)\) for \(n > 3\) has chromatic number \(n-2\):

Sage

sage: all(graphs.KneserGraph(i,2).chromatic_number() == i-2 for i in range(4,6))
True

Python

>>> from sage.all import *
>>> all(graphs.KneserGraph(i,Integer(2)).chromatic_number() == i-Integer(2) for i in range(Integer(4),Integer(6)))
True

The Flower Snark graph has chromatic index 4 hence its line graph has chromatic number 4:

Sage

sage: graphs.FlowerSnark().line_graph().chromatic_number()
4

Python

>>> from sage.all import *
>>> graphs.FlowerSnark().line_graph().chromatic_number()
4

chromatic_polynomial(G, return_tree_basis=False, algorithm='C', cache=None)[source]¶

Compute the chromatic polynomial of the graph G.

The algorithm used is a recursive one, based on the following observations of Read:

The chromatic polynomial of a tree on n vertices is x(x-1)^(n-1).

If e is an edge of G, G’ is the result of deleting the edge e, and G’’ is the result of contracting e, then the chromatic polynomial of G is equal to that of G’ minus that of G’’.

INPUT:

G – a Sage graph
return_tree_basis – boolean (default: False); not used yet
algorithm – string (default: 'C'); the algorithm to use among
- 'C', an implementation in C by Robert Miller and Gordon Royle.
- 'Python', an implementation in Python using caching to avoid recomputing the chromatic polynomial of a graph that has already been seen. This seems faster on some dense graphs.
cache – dictionary (default: None); this parameter is used only for algorithm 'Python'. It is a dictionary keyed by canonical labelings of graphs and used to cache the chromatic polynomials of the graphs generated by the algorithm. In other words, it avoids computing twice the chromatic polynomial of isometric graphs. One will be created automatically if not provided.

EXAMPLES:

Sage

sage: graphs.CycleGraph(4).chromatic_polynomial()
x^4 - 4*x^3 + 6*x^2 - 3*x
sage: graphs.CycleGraph(3).chromatic_polynomial()
x^3 - 3*x^2 + 2*x
sage: graphs.CubeGraph(3).chromatic_polynomial()
x^8 - 12*x^7 + 66*x^6 - 214*x^5 + 441*x^4 - 572*x^3 + 423*x^2 - 133*x
sage: graphs.PetersenGraph().chromatic_polynomial()
x^10 - 15*x^9 + 105*x^8 - 455*x^7 + 1353*x^6 - 2861*x^5 + 4275*x^4 - 4305*x^3 + 2606*x^2 - 704*x
sage: graphs.CompleteBipartiteGraph(3,3).chromatic_polynomial()
x^6 - 9*x^5 + 36*x^4 - 75*x^3 + 78*x^2 - 31*x
sage: for i in range(2,7):
....:     graphs.CompleteGraph(i).chromatic_polynomial().factor()
(x - 1) * x
(x - 2) * (x - 1) * x
(x - 3) * (x - 2) * (x - 1) * x
(x - 4) * (x - 3) * (x - 2) * (x - 1) * x
(x - 5) * (x - 4) * (x - 3) * (x - 2) * (x - 1) * x
sage: graphs.CycleGraph(5).chromatic_polynomial().factor()
(x - 2) * (x - 1) * x * (x^2 - 2*x + 2)
sage: graphs.OctahedralGraph().chromatic_polynomial().factor()
(x - 2) * (x - 1) * x * (x^3 - 9*x^2 + 29*x - 32)
sage: graphs.WheelGraph(5).chromatic_polynomial().factor()
(x - 2) * (x - 1) * x * (x^2 - 5*x + 7)
sage: graphs.WheelGraph(6).chromatic_polynomial().factor()
(x - 3) * (x - 2) * (x - 1) * x * (x^2 - 4*x + 5)
sage: C(x)=graphs.LCFGraph(24, [12,7,-7], 8).chromatic_polynomial()  # long time (6s on sage.math, 2011)
sage: C(2)  # long time
0

Python

>>> from sage.all import *
>>> graphs.CycleGraph(Integer(4)).chromatic_polynomial()
x^4 - 4*x^3 + 6*x^2 - 3*x
>>> graphs.CycleGraph(Integer(3)).chromatic_polynomial()
x^3 - 3*x^2 + 2*x
>>> graphs.CubeGraph(Integer(3)).chromatic_polynomial()
x^8 - 12*x^7 + 66*x^6 - 214*x^5 + 441*x^4 - 572*x^3 + 423*x^2 - 133*x
>>> graphs.PetersenGraph().chromatic_polynomial()
x^10 - 15*x^9 + 105*x^8 - 455*x^7 + 1353*x^6 - 2861*x^5 + 4275*x^4 - 4305*x^3 + 2606*x^2 - 704*x
>>> graphs.CompleteBipartiteGraph(Integer(3),Integer(3)).chromatic_polynomial()
x^6 - 9*x^5 + 36*x^4 - 75*x^3 + 78*x^2 - 31*x
>>> for i in range(Integer(2),Integer(7)):
...     graphs.CompleteGraph(i).chromatic_polynomial().factor()
(x - 1) * x
(x - 2) * (x - 1) * x
(x - 3) * (x - 2) * (x - 1) * x
(x - 4) * (x - 3) * (x - 2) * (x - 1) * x
(x - 5) * (x - 4) * (x - 3) * (x - 2) * (x - 1) * x
>>> graphs.CycleGraph(Integer(5)).chromatic_polynomial().factor()
(x - 2) * (x - 1) * x * (x^2 - 2*x + 2)
>>> graphs.OctahedralGraph().chromatic_polynomial().factor()
(x - 2) * (x - 1) * x * (x^3 - 9*x^2 + 29*x - 32)
>>> graphs.WheelGraph(Integer(5)).chromatic_polynomial().factor()
(x - 2) * (x - 1) * x * (x^2 - 5*x + 7)
>>> graphs.WheelGraph(Integer(6)).chromatic_polynomial().factor()
(x - 3) * (x - 2) * (x - 1) * x * (x^2 - 4*x + 5)
>>> __tmp__=var("x"); C = symbolic_expression(graphs.LCFGraph(Integer(24), [Integer(12),Integer(7),-Integer(7)], Integer(8)).chromatic_polynomial()  ).function(x)# long time (6s on sage.math, 2011)
>>> C(Integer(2))  # long time
0

By definition, the chromatic number of a graph G is the least integer k such that the chromatic polynomial of G is strictly positive at k:

Sage

sage: G = graphs.PetersenGraph()
sage: P = G.chromatic_polynomial()
sage: min(i for i in range(11) if P(i) > 0) == G.chromatic_number()
True

sage: G = graphs.RandomGNP(10,0.7)
sage: P = G.chromatic_polynomial()
sage: min(i for i in range(11) if P(i) > 0) == G.chromatic_number()
True

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> P = G.chromatic_polynomial()
>>> min(i for i in range(Integer(11)) if P(i) > Integer(0)) == G.chromatic_number()
True

>>> G = graphs.RandomGNP(Integer(10),RealNumber('0.7'))
>>> P = G.chromatic_polynomial()
>>> min(i for i in range(Integer(11)) if P(i) > Integer(0)) == G.chromatic_number()
True

Check that algorithms 'C' and 'Python' return the same results:

Sage

sage: G = graphs.RandomGNP(8, randint(1, 9)*0.1)
sage: c = G.chromatic_polynomial(algorithm='C')
sage: p = G.chromatic_polynomial(algorithm='Python')
sage: c == p
True

Python

>>> from sage.all import *
>>> G = graphs.RandomGNP(Integer(8), randint(Integer(1), Integer(9))*RealNumber('0.1'))
>>> c = G.chromatic_polynomial(algorithm='C')
>>> p = G.chromatic_polynomial(algorithm='Python')
>>> c == p
True

chromatic_quasisymmetric_function(t=None, R=None)[source]¶

Return the chromatic quasisymmetric function of self.

Let \(G\) be a graph whose vertex set is totally ordered. The chromatic quasisymmetric function \(X_G(t)\) was first described in [SW2012]. We use the equivalent definition given in [BC2018]:

\[X_G(t) = \sum_{\sigma=(\sigma_1,\ldots,\sigma_n)} t^{\operatorname{asc}(\sigma)} M_{|\sigma_1|,\ldots,|\sigma_n|},\]

where we sum over all ordered set partitions of the vertex set of \(G\) such that each block \(\sigma_i\) is an independent (i.e., stable) set of \(G\), and where \(\operatorname{asc}(\sigma)\) denotes the number of edges \(\{u, v\}\) of \(G\) such that \(u < v\) and \(v\) appears in a later part of \(\sigma\) than \(u\).

INPUT:

t – (optional) the parameter \(t\); uses the variable \(t\) in \(\ZZ[t]\) by default
R – (optional) the base ring for the quasisymmetric functions; uses the parent of \(t\) by default

EXAMPLES:

Sage

sage: # needs sage.combinat sage.modules
sage: G = Graph([[1,2,3], [[1,3], [2,3]]])
sage: G.chromatic_quasisymmetric_function()
(2*t^2+2*t+2)*M[1, 1, 1] + M[1, 2] + t^2*M[2, 1]
sage: G = graphs.PathGraph(4)
sage: XG = G.chromatic_quasisymmetric_function(); XG
(t^3+11*t^2+11*t+1)*M[1, 1, 1, 1] + (3*t^2+3*t)*M[1, 1, 2]
 + (3*t^2+3*t)*M[1, 2, 1] + (3*t^2+3*t)*M[2, 1, 1]
 + (t^2+t)*M[2, 2]
sage: XG.to_symmetric_function()
(t^3+11*t^2+11*t+1)*m[1, 1, 1, 1] + (3*t^2+3*t)*m[2, 1, 1]
 + (t^2+t)*m[2, 2]
sage: G = graphs.CompleteGraph(4)
sage: G.chromatic_quasisymmetric_function()
(t^6+3*t^5+5*t^4+6*t^3+5*t^2+3*t+1)*M[1, 1, 1, 1]

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.modules
>>> G = Graph([[Integer(1),Integer(2),Integer(3)], [[Integer(1),Integer(3)], [Integer(2),Integer(3)]]])
>>> G.chromatic_quasisymmetric_function()
(2*t^2+2*t+2)*M[1, 1, 1] + M[1, 2] + t^2*M[2, 1]
>>> G = graphs.PathGraph(Integer(4))
>>> XG = G.chromatic_quasisymmetric_function(); XG
(t^3+11*t^2+11*t+1)*M[1, 1, 1, 1] + (3*t^2+3*t)*M[1, 1, 2]
 + (3*t^2+3*t)*M[1, 2, 1] + (3*t^2+3*t)*M[2, 1, 1]
 + (t^2+t)*M[2, 2]
>>> XG.to_symmetric_function()
(t^3+11*t^2+11*t+1)*m[1, 1, 1, 1] + (3*t^2+3*t)*m[2, 1, 1]
 + (t^2+t)*m[2, 2]
>>> G = graphs.CompleteGraph(Integer(4))
>>> G.chromatic_quasisymmetric_function()
(t^6+3*t^5+5*t^4+6*t^3+5*t^2+3*t+1)*M[1, 1, 1, 1]

Not all chromatic quasisymmetric functions are symmetric:

Sage

sage: G = Graph([[1,2], [1,5], [3,4], [3,5]])
sage: G.chromatic_quasisymmetric_function().is_symmetric()                  # needs sage.combinat sage.modules
False

Python

>>> from sage.all import *
>>> G = Graph([[Integer(1),Integer(2)], [Integer(1),Integer(5)], [Integer(3),Integer(4)], [Integer(3),Integer(5)]])
>>> G.chromatic_quasisymmetric_function().is_symmetric()                  # needs sage.combinat sage.modules
False

We check that at \(t = 1\), we recover the usual chromatic symmetric function:

Sage

sage: p = SymmetricFunctions(QQ).p()                                        # needs sage.combinat sage.modules
sage: G = graphs.CycleGraph(5)
sage: XG = G.chromatic_quasisymmetric_function(t=1); XG                     # needs sage.combinat sage.modules
120*M[1, 1, 1, 1, 1] + 30*M[1, 1, 1, 2] + 30*M[1, 1, 2, 1]
 + 30*M[1, 2, 1, 1] + 10*M[1, 2, 2] + 30*M[2, 1, 1, 1]
 + 10*M[2, 1, 2] + 10*M[2, 2, 1]
sage: p(XG.to_symmetric_function())                                         # needs sage.combinat sage.modules
p[1, 1, 1, 1, 1] - 5*p[2, 1, 1, 1] + 5*p[2, 2, 1]
 + 5*p[3, 1, 1] - 5*p[3, 2] - 5*p[4, 1] + 4*p[5]

sage: G = graphs.ClawGraph()
sage: XG = G.chromatic_quasisymmetric_function(t=1); XG                     # needs sage.combinat sage.modules
24*M[1, 1, 1, 1] + 6*M[1, 1, 2] + 6*M[1, 2, 1] + M[1, 3]
 + 6*M[2, 1, 1] + M[3, 1]
sage: p(XG.to_symmetric_function())                                         # needs sage.combinat sage.modules
p[1, 1, 1, 1] - 3*p[2, 1, 1] + 3*p[3, 1] - p[4]

Python

>>> from sage.all import *
>>> p = SymmetricFunctions(QQ).p()                                        # needs sage.combinat sage.modules
>>> G = graphs.CycleGraph(Integer(5))
>>> XG = G.chromatic_quasisymmetric_function(t=Integer(1)); XG                     # needs sage.combinat sage.modules
120*M[1, 1, 1, 1, 1] + 30*M[1, 1, 1, 2] + 30*M[1, 1, 2, 1]
 + 30*M[1, 2, 1, 1] + 10*M[1, 2, 2] + 30*M[2, 1, 1, 1]
 + 10*M[2, 1, 2] + 10*M[2, 2, 1]
>>> p(XG.to_symmetric_function())                                         # needs sage.combinat sage.modules
p[1, 1, 1, 1, 1] - 5*p[2, 1, 1, 1] + 5*p[2, 2, 1]
 + 5*p[3, 1, 1] - 5*p[3, 2] - 5*p[4, 1] + 4*p[5]

>>> G = graphs.ClawGraph()
>>> XG = G.chromatic_quasisymmetric_function(t=Integer(1)); XG                     # needs sage.combinat sage.modules
24*M[1, 1, 1, 1] + 6*M[1, 1, 2] + 6*M[1, 2, 1] + M[1, 3]
 + 6*M[2, 1, 1] + M[3, 1]
>>> p(XG.to_symmetric_function())                                         # needs sage.combinat sage.modules
p[1, 1, 1, 1] - 3*p[2, 1, 1] + 3*p[3, 1] - p[4]

chromatic_symmetric_function(R=None)[source]¶

Return the chromatic symmetric function of self.

Let \(G\) be a graph. The chromatic symmetric function \(X_G\) was described in [Sta1995], specifically Theorem 2.5 states that

\[X_G = \sum_{F \subseteq E(G)} (-1)^{|F|} p_{\lambda(F)},\]

where \(\lambda(F)\) is the partition of the sizes of the connected components of the subgraph induced by the edges \(F\) and \(p_{\mu}\) is the powersum symmetric function.

INPUT:

R – (optional) the base ring for the symmetric functions; this uses \(\ZZ\) by default

ALGORITHM:

We traverse a binary tree whose leaves correspond to subsets of edges, and whose internal vertices at depth \(d\) correspond to a choice of whether to include the \(d\)-th edge in a given subset. The components of the induced subgraph are incrementally updated using a disjoint-set forest. If the next edge would introduce a cycle to the subset, we prune the branch as the terms produced by the two subtrees cancel in this case.

EXAMPLES:

Sage

sage: s = SymmetricFunctions(ZZ).s()                                        # needs sage.combinat sage.modules
sage: G = graphs.CycleGraph(5)
sage: XG = G.chromatic_symmetric_function(); XG                             # needs sage.combinat sage.modules
p[1, 1, 1, 1, 1] - 5*p[2, 1, 1, 1] + 5*p[2, 2, 1]
 + 5*p[3, 1, 1] - 5*p[3, 2] - 5*p[4, 1] + 4*p[5]
sage: s(XG)                                                                 # needs sage.combinat sage.modules
30*s[1, 1, 1, 1, 1] + 10*s[2, 1, 1, 1] + 10*s[2, 2, 1]

Python

>>> from sage.all import *
>>> s = SymmetricFunctions(ZZ).s()                                        # needs sage.combinat sage.modules
>>> G = graphs.CycleGraph(Integer(5))
>>> XG = G.chromatic_symmetric_function(); XG                             # needs sage.combinat sage.modules
p[1, 1, 1, 1, 1] - 5*p[2, 1, 1, 1] + 5*p[2, 2, 1]
 + 5*p[3, 1, 1] - 5*p[3, 2] - 5*p[4, 1] + 4*p[5]
>>> s(XG)                                                                 # needs sage.combinat sage.modules
30*s[1, 1, 1, 1, 1] + 10*s[2, 1, 1, 1] + 10*s[2, 2, 1]

Not all graphs have a positive Schur expansion:

Sage

sage: G = graphs.ClawGraph()
sage: XG = G.chromatic_symmetric_function(); XG                             # needs sage.combinat sage.modules
p[1, 1, 1, 1] - 3*p[2, 1, 1] + 3*p[3, 1] - p[4]
sage: s(XG)                                                                 # needs sage.combinat sage.modules
8*s[1, 1, 1, 1] + 5*s[2, 1, 1] - s[2, 2] + s[3, 1]

Python

>>> from sage.all import *
>>> G = graphs.ClawGraph()
>>> XG = G.chromatic_symmetric_function(); XG                             # needs sage.combinat sage.modules
p[1, 1, 1, 1] - 3*p[2, 1, 1] + 3*p[3, 1] - p[4]
>>> s(XG)                                                                 # needs sage.combinat sage.modules
8*s[1, 1, 1, 1] + 5*s[2, 1, 1] - s[2, 2] + s[3, 1]

We show that given a triangle \(\{e_1, e_2, e_3\}\), we have \(X_G = X_{G - e_1} + X_{G - e_2} - X_{G - e_1 - e_2}\):

Sage

sage: # needs sage.combinat sage.modules
sage: G = Graph([[1,2],[1,3],[2,3]])
sage: XG = G.chromatic_symmetric_function()
sage: G1 = copy(G)
sage: G1.delete_edge([1,2])
sage: XG1 = G1.chromatic_symmetric_function()
sage: G2 = copy(G)
sage: G2.delete_edge([1,3])
sage: XG2 = G2.chromatic_symmetric_function()
sage: G3 = copy(G1)
sage: G3.delete_edge([1,3])
sage: XG3 = G3.chromatic_symmetric_function()
sage: XG == XG1 + XG2 - XG3
True

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.modules
>>> G = Graph([[Integer(1),Integer(2)],[Integer(1),Integer(3)],[Integer(2),Integer(3)]])
>>> XG = G.chromatic_symmetric_function()
>>> G1 = copy(G)
>>> G1.delete_edge([Integer(1),Integer(2)])
>>> XG1 = G1.chromatic_symmetric_function()
>>> G2 = copy(G)
>>> G2.delete_edge([Integer(1),Integer(3)])
>>> XG2 = G2.chromatic_symmetric_function()
>>> G3 = copy(G1)
>>> G3.delete_edge([Integer(1),Integer(3)])
>>> XG3 = G3.chromatic_symmetric_function()
>>> XG == XG1 + XG2 - XG3
True

cleave(G, cut_vertices=None, virtual_edges=True, solver=None, verbose=0, integrality_tolerance=0.001)[source]¶

Return the connected subgraphs separated by the input vertex cut.

Given a connected (multi)graph \(G\) and a vertex cut \(X\), this method computes the list of subgraphs of \(G\) induced by each connected component \(c\) of \(G\setminus X\) plus \(X\), i.e., \(G[c\cup X]\).

INPUT:

G – a Graph
cut_vertices – iterable container of vertices (default: None); a set of vertices representing a vertex cut of G. If no vertex cut is given, the method will compute one via a call to vertex_connectivity().
virtual_edges – boolean (default: True); whether to add virtual edges to the sides of the cut or not. A virtual edge is an edge between a pair of vertices of the cut that are not connected by an edge in G.
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT: a triple \((S, C, f)\), where

\(S\) is a list of the graphs that are sides of the vertex cut.
\(C\) is the graph of the cocycles. For each pair of vertices of the cut, if there exists an edge between them, \(C\) has one copy of each edge connecting them in G per sides of the cut plus one extra copy. Furthermore, when virtual_edges == True, if a pair of vertices of the cut is not connected by an edge in G, then it has one virtual edge between them per sides of the cut.
\(f\) is the complement of the subgraph of G induced by the vertex cut. Hence, its vertex set is the vertex cut, and its edge set is the set of virtual edges (i.e., edges between pairs of vertices of the cut that are not connected by an edge in G). When virtual_edges == False, the edge set is empty.

EXAMPLES:

If there is an edge between cut vertices:

Sage

sage: from sage.graphs.connectivity import cleave
sage: G = Graph(2)
sage: for _ in range(3):
....:     G.add_clique([0, 1, G.add_vertex(), G.add_vertex()])
sage: S1,C1,f1 = cleave(G, cut_vertices=[0, 1])
sage: [g.order() for g in S1]
[4, 4, 4]
sage: C1.order(), C1.size()
(2, 4)
sage: f1.vertices(sort=True), f1.edges(sort=True)
([0, 1], [])

Python

>>> from sage.all import *
>>> from sage.graphs.connectivity import cleave
>>> G = Graph(Integer(2))
>>> for _ in range(Integer(3)):
...     G.add_clique([Integer(0), Integer(1), G.add_vertex(), G.add_vertex()])
>>> S1,C1,f1 = cleave(G, cut_vertices=[Integer(0), Integer(1)])
>>> [g.order() for g in S1]
[4, 4, 4]
>>> C1.order(), C1.size()
(2, 4)
>>> f1.vertices(sort=True), f1.edges(sort=True)
([0, 1], [])

If virtual_edges == False and there is an edge between cut vertices:

Sage

sage: G.subgraph([0, 1]).complement() == Graph([[0, 1], []])
True
sage: S2,C2,f2 = cleave(G, cut_vertices=[0, 1], virtual_edges=False)
sage: (S1 == S2, C1 == C2, f1 == f2)
(True, True, True)

Python

>>> from sage.all import *
>>> G.subgraph([Integer(0), Integer(1)]).complement() == Graph([[Integer(0), Integer(1)], []])
True
>>> S2,C2,f2 = cleave(G, cut_vertices=[Integer(0), Integer(1)], virtual_edges=False)
>>> (S1 == S2, C1 == C2, f1 == f2)
(True, True, True)

If cut vertices doesn’t have edge between them:

Sage

sage: G.delete_edge(0, 1)
sage: S1,C1,f1 = cleave(G, cut_vertices=[0, 1])
sage: [g.order() for g in S1]
[4, 4, 4]
sage: C1.order(), C1.size()
(2, 3)
sage: f1.vertices(sort=True), f1.edges(sort=True)
([0, 1], [(0, 1, None)])

Python

>>> from sage.all import *
>>> G.delete_edge(Integer(0), Integer(1))
>>> S1,C1,f1 = cleave(G, cut_vertices=[Integer(0), Integer(1)])
>>> [g.order() for g in S1]
[4, 4, 4]
>>> C1.order(), C1.size()
(2, 3)
>>> f1.vertices(sort=True), f1.edges(sort=True)
([0, 1], [(0, 1, None)])

If virtual_edges == False and the cut vertices are not connected by an edge:

Sage

sage: G.subgraph([0, 1]).complement() == Graph([[0, 1], []])
False
sage: S2,C2,f2 = cleave(G, cut_vertices=[0, 1], virtual_edges=False)
sage: [g.order() for g in S2]
[4, 4, 4]
sage: C2.order(), C2.size()
(2, 0)
sage: f2.vertices(sort=True), f2.edges(sort=True)
([0, 1], [])
sage: (S1 == S2, C1 == C2, f1 == f2)
(False, False, False)

Python

>>> from sage.all import *
>>> G.subgraph([Integer(0), Integer(1)]).complement() == Graph([[Integer(0), Integer(1)], []])
False
>>> S2,C2,f2 = cleave(G, cut_vertices=[Integer(0), Integer(1)], virtual_edges=False)
>>> [g.order() for g in S2]
[4, 4, 4]
>>> C2.order(), C2.size()
(2, 0)
>>> f2.vertices(sort=True), f2.edges(sort=True)
([0, 1], [])
>>> (S1 == S2, C1 == C2, f1 == f2)
(False, False, False)

If \(G\) is a biconnected multigraph:

Sage

sage: G = graphs.CompleteBipartiteGraph(2, 3)
sage: G.add_edge(2, 3)
sage: G.allow_multiple_edges(True)
sage: G.add_edges(G.edge_iterator())
sage: G.add_edges([(0, 1), (0, 1), (0, 1)])
sage: S,C,f = cleave(G, cut_vertices=[0, 1])
sage: for g in S:
....:     print(g.edges(sort=True, labels=0))
[(0, 1), (0, 1), (0, 1), (0, 2), (0, 2), (0, 3), (0, 3), (1, 2), (1, 2), (1, 3), (1, 3), (2, 3), (2, 3)]
[(0, 1), (0, 1), (0, 1), (0, 4), (0, 4), (1, 4), (1, 4)]

Python

>>> from sage.all import *
>>> G = graphs.CompleteBipartiteGraph(Integer(2), Integer(3))
>>> G.add_edge(Integer(2), Integer(3))
>>> G.allow_multiple_edges(True)
>>> G.add_edges(G.edge_iterator())
>>> G.add_edges([(Integer(0), Integer(1)), (Integer(0), Integer(1)), (Integer(0), Integer(1))])
>>> S,C,f = cleave(G, cut_vertices=[Integer(0), Integer(1)])
>>> for g in S:
...     print(g.edges(sort=True, labels=Integer(0)))
[(0, 1), (0, 1), (0, 1), (0, 2), (0, 2), (0, 3), (0, 3), (1, 2), (1, 2), (1, 3), (1, 3), (2, 3), (2, 3)]
[(0, 1), (0, 1), (0, 1), (0, 4), (0, 4), (1, 4), (1, 4)]

clique_complex()[source]¶

Return the clique complex of self.

This is the largest simplicial complex on the vertices of self whose 1-skeleton is self.

This is only makes sense for undirected simple graphs.

EXAMPLES:

Sage

sage: g = Graph({0:[1,2],1:[2],4:[]})
sage: g.clique_complex()
Simplicial complex with vertex set (0, 1, 2, 4) and facets {(4,), (0, 1, 2)}

sage: h = Graph({0:[1,2,3,4],1:[2,3,4],2:[3]})
sage: x = h.clique_complex()
sage: x
Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(0, 1, 4), (0, 1, 2, 3)}
sage: i = x.graph()
sage: i==h
True
sage: x==i.clique_complex()
True

Python

>>> from sage.all import *
>>> g = Graph({Integer(0):[Integer(1),Integer(2)],Integer(1):[Integer(2)],Integer(4):[]})
>>> g.clique_complex()
Simplicial complex with vertex set (0, 1, 2, 4) and facets {(4,), (0, 1, 2)}

>>> h = Graph({Integer(0):[Integer(1),Integer(2),Integer(3),Integer(4)],Integer(1):[Integer(2),Integer(3),Integer(4)],Integer(2):[Integer(3)]})
>>> x = h.clique_complex()
>>> x
Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(0, 1, 4), (0, 1, 2, 3)}
>>> i = x.graph()
>>> i==h
True
>>> x==i.clique_complex()
True

clique_maximum(algorithm, solver='Cliquer', verbose=None, integrality_tolerance=0)[source]¶

Return the vertex set of a maximal order complete subgraph.

INPUT:

algorithm – the algorithm to be used :
- If algorithm = "Cliquer" (default), wraps the C program Cliquer [NO2003].
- If algorithm = "MILP", the problem is solved through a Mixed Integer Linear Program.
  
  (see MixedIntegerLinearProgram)
- If algorithm = "mcqd", uses the MCQD solver (http://www.sicmm.org/~konc/maxclique/). Note that the MCQD package must be installed.
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

Parameters solver and verbose are used only when algorithm="MILP".

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:

Using Cliquer (default):

Sage

sage: C = graphs.PetersenGraph()
sage: C.clique_maximum()
[7, 9]
sage: C = Graph('DJ{')
sage: C.clique_maximum()
[1, 2, 3, 4]

Python

>>> from sage.all import *
>>> C = graphs.PetersenGraph()
>>> C.clique_maximum()
[7, 9]
>>> C = Graph('DJ{')
>>> C.clique_maximum()
[1, 2, 3, 4]

Through a Linear Program:

Sage

sage: len(C.clique_maximum(algorithm='MILP'))
4

Python

>>> from sage.all import *
>>> len(C.clique_maximum(algorithm='MILP'))
4

clique_number(algorithm, cliques='Cliquer', solver=None, verbose=None, integrality_tolerance=0)[source]¶

Return the order of the largest clique of the graph.

This is also called as the clique number.

Note

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

INPUT:

algorithm – the algorithm to be used :
- If algorithm = "Cliquer", wraps the C program Cliquer [NO2003].
- If algorithm = "networkx", uses the NetworkX’s implementation of the Bron and Kerbosch Algorithm [BK1973].
- If algorithm = "MILP", the problem is solved through a Mixed Integer Linear Program.
  
  (see MixedIntegerLinearProgram)
- If algorithm = "mcqd", uses the MCQD solver (http://insilab.org/maxclique/). Note that the MCQD package must be installed.
cliques – an optional list of cliques that can be input if already computed. Ignored unless algorithm=="networkx".
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

ALGORITHM:

This function is based on Cliquer [NO2003] and [BK1973].

EXAMPLES:

Sage

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

Python

>>> 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

By definition the clique number of a complete graph is its order:

Sage

sage: all(graphs.CompleteGraph(i).clique_number() == i for i in range(1,15))
True

Python

>>> from sage.all import *
>>> all(graphs.CompleteGraph(i).clique_number() == i for i in range(Integer(1),Integer(15)))
True

A non-empty graph without edges has a clique number of 1:

Sage

sage: all((i*graphs.CompleteGraph(1)).clique_number() == 1
....:     for i in range(1,15))
True

Python

>>> from sage.all import *
>>> all((i*graphs.CompleteGraph(Integer(1))).clique_number() == Integer(1)
...     for i in range(Integer(1),Integer(15)))
True

A complete multipartite graph with k parts has clique number k:

Sage

sage: all((i*graphs.CompleteMultipartiteGraph(i*[5])).clique_number() == i
....:     for i in range(1,6))
True

Python

>>> from sage.all import *
>>> all((i*graphs.CompleteMultipartiteGraph(i*[Integer(5)])).clique_number() == i
...     for i in range(Integer(1),Integer(6)))
True

clique_polynomial(t=None)[source]¶

Return the clique polynomial of self.

This is the polynomial where the coefficient of \(t^n\) is the number of cliques in the graph with \(n\) vertices. The constant term of the clique polynomial is always taken to be one.

EXAMPLES:

Sage

sage: g = Graph()
sage: g.clique_polynomial()
1
sage: g = Graph({0:[1]})
sage: g.clique_polynomial()
t^2 + 2*t + 1
sage: g = graphs.CycleGraph(4)
sage: g.clique_polynomial()
4*t^2 + 4*t + 1

Python

>>> from sage.all import *
>>> g = Graph()
>>> g.clique_polynomial()
1
>>> g = Graph({Integer(0):[Integer(1)]})
>>> g.clique_polynomial()
t^2 + 2*t + 1
>>> g = graphs.CycleGraph(Integer(4))
>>> g.clique_polynomial()
4*t^2 + 4*t + 1

cliques_containing_vertex(vertices=None, cliques=None)[source]¶

Return the cliques containing each vertex, represented as a dictionary of lists of lists, keyed by vertex.

Returns a single list if only one input vertex.

Note

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

INPUT:

vertices – the vertices to inspect (default: entire graph)
cliques – list of cliques (if already computed)

EXAMPLES:

Sage

sage: # needs networkx
sage: C = Graph('DJ{')
sage: C.cliques_containing_vertex()
{0: [[0, 4]],
 1: [[1, 2, 3, 4]],
 2: [[1, 2, 3, 4]],
 3: [[1, 2, 3, 4]],
 4: [[0, 4], [1, 2, 3, 4]]}
sage: C.cliques_containing_vertex(4)
[[0, 4], [1, 2, 3, 4]]
sage: C.cliques_containing_vertex([0, 1])
{0: [[0, 4]], 1: [[1, 2, 3, 4]]}
sage: E = C.cliques_maximal(); E
[[0, 4], [1, 2, 3, 4]]
sage: C.cliques_containing_vertex(cliques=E)
{0: [[0, 4]],
 1: [[1, 2, 3, 4]],
 2: [[1, 2, 3, 4]],
 3: [[1, 2, 3, 4]],
 4: [[0, 4], [1, 2, 3, 4]]}

sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])                                                 # needs sage.plot
sage: G.cliques_containing_vertex()                                         # needs networkx
{0: [[0, 1, 2], [0, 1, 3]],
 1: [[0, 1, 2], [0, 1, 3]],
 2: [[0, 1, 2]],
 3: [[0, 1, 3]]}

Python

>>> from sage.all import *
>>> # needs networkx
>>> C = Graph('DJ{')
>>> C.cliques_containing_vertex()
{0: [[0, 4]],
 1: [[1, 2, 3, 4]],
 2: [[1, 2, 3, 4]],
 3: [[1, 2, 3, 4]],
 4: [[0, 4], [1, 2, 3, 4]]}
>>> C.cliques_containing_vertex(Integer(4))
[[0, 4], [1, 2, 3, 4]]
>>> C.cliques_containing_vertex([Integer(0), Integer(1)])
{0: [[0, 4]], 1: [[1, 2, 3, 4]]}
>>> E = C.cliques_maximal(); E
[[0, 4], [1, 2, 3, 4]]
>>> C.cliques_containing_vertex(cliques=E)
{0: [[0, 4]],
 1: [[1, 2, 3, 4]],
 2: [[1, 2, 3, 4]],
 3: [[1, 2, 3, 4]],
 4: [[0, 4], [1, 2, 3, 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.cliques_containing_vertex()                                         # needs networkx
{0: [[0, 1, 2], [0, 1, 3]],
 1: [[0, 1, 2], [0, 1, 3]],
 2: [[0, 1, 2]],
 3: [[0, 1, 3]]}

Since each clique of a 2 dimensional grid corresponds to an edge, the number of cliques in which a vertex is involved equals its degree:

Sage

sage: # needs networkx
sage: F = graphs.Grid2dGraph(2,3)
sage: d = F.cliques_containing_vertex()
sage: all(F.degree(u) == len(cliques) for u,cliques in d.items())
True
sage: d = F.cliques_containing_vertex(vertices=[(0, 1)])
sage: list(d)
[(0, 1)]
sage: sorted(sorted(x for x in L) for L in d[(0, 1)])
[[(0, 0), (0, 1)], [(0, 1), (0, 2)], [(0, 1), (1, 1)]]

Python

>>> from sage.all import *
>>> # needs networkx
>>> F = graphs.Grid2dGraph(Integer(2),Integer(3))
>>> d = F.cliques_containing_vertex()
>>> all(F.degree(u) == len(cliques) for u,cliques in d.items())
True
>>> d = F.cliques_containing_vertex(vertices=[(Integer(0), Integer(1))])
>>> list(d)
[(0, 1)]
>>> sorted(sorted(x for x in L) for L in d[(Integer(0), Integer(1))])
[[(0, 0), (0, 1)], [(0, 1), (0, 2)], [(0, 1), (1, 1)]]

cliques_get_clique_bipartite(**kwds)[source]¶

Return the vertex-clique bipartite graph of self.

In the returned bipartite graph, the left vertices are the vertices of self and the right vertices represent the maximal cliques of self. There is an edge from vertex \(v\) to clique \(C\) in the bipartite graph if and only if \(v\) belongs to \(C\).

Note

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

EXAMPLES:

Sage

sage: CBG = graphs.ChvatalGraph().cliques_get_clique_bipartite(); CBG
Bipartite graph on 36 vertices
sage: CBG.show(figsize=[2,2], vertex_size=20, vertex_labels=False)          # needs sage.plot
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])                                                 # needs sage.plot
sage: G.cliques_get_clique_bipartite()
Bipartite graph on 6 vertices
sage: G.cliques_get_clique_bipartite().show(figsize=[2,2])                  # needs sage.plot

Python

>>> from sage.all import *
>>> CBG = graphs.ChvatalGraph().cliques_get_clique_bipartite(); CBG
Bipartite graph on 36 vertices
>>> CBG.show(figsize=[Integer(2),Integer(2)], vertex_size=Integer(20), vertex_labels=False)          # needs sage.plot
>>> 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_get_clique_bipartite()
Bipartite graph on 6 vertices
>>> G.cliques_get_clique_bipartite().show(figsize=[Integer(2),Integer(2)])                  # needs sage.plot

cliques_get_max_clique_graph()[source]¶

Return the clique graph.

Vertices of the result are the maximal cliques of the graph, and edges of the result are between maximal cliques with common members in the original graph.

For more information, see the Wikipedia article Clique_graph.

Note

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

EXAMPLES:

Sage

sage: MCG = graphs.ChvatalGraph().cliques_get_max_clique_graph(); MCG
Graph on 24 vertices
sage: MCG.show(figsize=[2,2], vertex_size=20, vertex_labels=False)          # needs sage.plot
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])                                                 # needs sage.plot
sage: G.cliques_get_max_clique_graph()
Graph on 2 vertices
sage: G.cliques_get_max_clique_graph().show(figsize=[2,2])                  # needs sage.plot

Python

>>> from sage.all import *
>>> MCG = graphs.ChvatalGraph().cliques_get_max_clique_graph(); MCG
Graph on 24 vertices
>>> MCG.show(figsize=[Integer(2),Integer(2)], vertex_size=Integer(20), vertex_labels=False)          # needs sage.plot
>>> 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_get_max_clique_graph()
Graph on 2 vertices
>>> G.cliques_get_max_clique_graph().show(figsize=[Integer(2),Integer(2)])                  # needs sage.plot

cliques_maximal(algorithm='native')[source]¶

Return the list of all maximal cliques.

Each clique is represented by a list of vertices. A clique is an induced complete subgraph, and a maximal clique is one not contained in a larger one.

INPUT:

algorithm – can be set to 'native' (default) to use Sage’s own implementation, or to "NetworkX" to use NetworkX’ implementation of the Bron and Kerbosch Algorithm [BK1973]

Note

This method sorts its output before returning it. If you prefer to save the extra time, you can call sage.graphs.independent_sets.IndependentSets directly.

Note

Sage’s implementation of the enumeration of maximal independent sets is not much faster than NetworkX’ (expect a 2x speedup), which is surprising as it is written in Cython. This being said, the algorithm from NetworkX appears to be slightly different from this one, and that would be a good thing to explore if one wants to improve the implementation.

ALGORITHM:

This function is based on NetworkX’s implementation of the Bron and Kerbosch Algorithm [BK1973].

EXAMPLES:

Sage

sage: graphs.ChvatalGraph().cliques_maximal()
[[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_maximal()
[[0, 1, 2], [0, 1, 3]]
sage: C = graphs.PetersenGraph()
sage: C.cliques_maximal()
[[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_maximal()
[[0, 4], [1, 2, 3, 4]]

Python

>>> from sage.all import *
>>> graphs.ChvatalGraph().cliques_maximal()
[[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_maximal()
[[0, 1, 2], [0, 1, 3]]
>>> C = graphs.PetersenGraph()
>>> C.cliques_maximal()
[[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_maximal()
[[0, 4], [1, 2, 3, 4]]

Comparing the two implementations:

Sage

sage: g = graphs.RandomGNP(20,.7)
sage: s1 = Set(map(Set, g.cliques_maximal(algorithm="NetworkX")))           # needs networkx
sage: s2 = Set(map(Set, g.cliques_maximal(algorithm='native')))
sage: s1 == s2                                                              # needs networkx
True

Python

>>> from sage.all import *
>>> g = graphs.RandomGNP(Integer(20),RealNumber('.7'))
>>> s1 = Set(map(Set, g.cliques_maximal(algorithm="NetworkX")))           # needs networkx
>>> s2 = Set(map(Set, g.cliques_maximal(algorithm='native')))
>>> s1 == s2                                                              # needs networkx
True

cliques_maximum(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

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]]

Python

>>> 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]]

cliques_number_of(vertices=None, cliques=None)[source]¶

Return a dictionary of the number of maximal cliques containing each vertex, keyed by vertex.

This returns a single value if only one input vertex.

Note

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

INPUT:

vertices – the vertices to inspect (default: entire graph)
cliques – list of cliques (if already computed)

EXAMPLES:

Sage

sage: C = Graph('DJ{')
sage: C.cliques_number_of()
{0: 1, 1: 1, 2: 1, 3: 1, 4: 2}
sage: E = C.cliques_maximal(); E
[[0, 4], [1, 2, 3, 4]]
sage: C.cliques_number_of(cliques=E)
{0: 1, 1: 1, 2: 1, 3: 1, 4: 2}
sage: F = graphs.Grid2dGraph(2,3)
sage: F.cliques_number_of()
{(0, 0): 2, (0, 1): 3, (0, 2): 2, (1, 0): 2, (1, 1): 3, (1, 2): 2}
sage: F.cliques_number_of(vertices=[(0, 1), (1, 2)])
{(0, 1): 3, (1, 2): 2}
sage: F.cliques_number_of(vertices=(0, 1))
3
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])                                                 # needs sage.plot
sage: G.cliques_number_of()
{0: 2, 1: 2, 2: 1, 3: 1}

Python

>>> from sage.all import *
>>> C = Graph('DJ{')
>>> C.cliques_number_of()
{0: 1, 1: 1, 2: 1, 3: 1, 4: 2}
>>> E = C.cliques_maximal(); E
[[0, 4], [1, 2, 3, 4]]
>>> C.cliques_number_of(cliques=E)
{0: 1, 1: 1, 2: 1, 3: 1, 4: 2}
>>> F = graphs.Grid2dGraph(Integer(2),Integer(3))
>>> F.cliques_number_of()
{(0, 0): 2, (0, 1): 3, (0, 2): 2, (1, 0): 2, (1, 1): 3, (1, 2): 2}
>>> F.cliques_number_of(vertices=[(Integer(0), Integer(1)), (Integer(1), Integer(2))])
{(0, 1): 3, (1, 2): 2}
>>> F.cliques_number_of(vertices=(Integer(0), Integer(1)))
3
>>> 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_number_of()
{0: 2, 1: 2, 2: 1, 3: 1}

cliques_vertex_clique_number(algorithm='cliquer', vertices=None, cliques=None)[source]¶

Return a dictionary of sizes of the largest maximal cliques containing each vertex, keyed by vertex.

Returns a single value if only one input vertex.

Note

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

INPUT:

algorithm – either cliquer or networkx
- cliquer – this wraps the C program Cliquer [NO2003]
- networkx – this function is based on NetworkX’s implementation of the Bron and Kerbosch Algorithm [BK1973]
vertices – the vertices to inspect (default: entire graph). Ignored unless algorithm=='networkx'.
cliques – list of cliques (if already computed). Ignored unless algorithm=='networkx'.

EXAMPLES:

Sage

sage: C = Graph('DJ{')
sage: C.cliques_vertex_clique_number()                                      # needs sage.plot
{0: 2, 1: 4, 2: 4, 3: 4, 4: 4}
sage: E = C.cliques_maximal(); E
[[0, 4], [1, 2, 3, 4]]
sage: C.cliques_vertex_clique_number(cliques=E, algorithm='networkx')       # needs networkx
{0: 2, 1: 4, 2: 4, 3: 4, 4: 4}

sage: F = graphs.Grid2dGraph(2,3)
sage: F.cliques_vertex_clique_number(algorithm='networkx')                  # needs networkx
{(0, 0): 2, (0, 1): 2, (0, 2): 2, (1, 0): 2, (1, 1): 2, (1, 2): 2}
sage: F.cliques_vertex_clique_number(vertices=[(0, 1), (1, 2)])             # needs sage.plot
{(0, 1): 2, (1, 2): 2}

sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])                                                 # needs sage.plot
sage: G.cliques_vertex_clique_number()                                      # needs sage.plot
{0: 3, 1: 3, 2: 3, 3: 3}

Python

>>> from sage.all import *
>>> C = Graph('DJ{')
>>> C.cliques_vertex_clique_number()                                      # needs sage.plot
{0: 2, 1: 4, 2: 4, 3: 4, 4: 4}
>>> E = C.cliques_maximal(); E
[[0, 4], [1, 2, 3, 4]]
>>> C.cliques_vertex_clique_number(cliques=E, algorithm='networkx')       # needs networkx
{0: 2, 1: 4, 2: 4, 3: 4, 4: 4}

>>> F = graphs.Grid2dGraph(Integer(2),Integer(3))
>>> F.cliques_vertex_clique_number(algorithm='networkx')                  # needs networkx
{(0, 0): 2, (0, 1): 2, (0, 2): 2, (1, 0): 2, (1, 1): 2, (1, 2): 2}
>>> F.cliques_vertex_clique_number(vertices=[(Integer(0), Integer(1)), (Integer(1), Integer(2))])             # needs sage.plot
{(0, 1): 2, (1, 2): 2}

>>> 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_vertex_clique_number()                                      # needs sage.plot
{0: 3, 1: 3, 2: 3, 3: 3}

coloring(algorithm, hex_colors='DLX', solver=False, verbose=None, integrality_tolerance=0)[source]¶

Return the first (optimal) proper vertex-coloring found.

INPUT:

algorithm – select an algorithm from the following supported algorithms:
- If algorithm="DLX" (default), the coloring is computed using the dancing link algorithm.
- If algorithm="MILP", the coloring is computed using a mixed integer linear program. The performance of this implementation is affected by whether optional MILP solvers have been installed (see the MILP module).
hex_colors – boolean (default: False); if True, return a dictionary which can easily be used for plotting
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

See also

For more functions related to graph coloring, see the module sage.graphs.graph_coloring.

EXAMPLES:

Sage

sage: G = Graph("Fooba")
sage: P = G.coloring(algorithm='MILP')
sage: Q = G.coloring(algorithm='DLX')
sage: def are_equal_colorings(A, B):
....:     return Set(map(Set, A)) == Set(map(Set, B))
sage: are_equal_colorings(P, [[1, 2, 3], [0, 5, 6], [4]])
True
sage: are_equal_colorings(P, Q)
True

sage: # needs sage.plot
sage: G.plot(partition=P)
Graphics object consisting of 16 graphics primitives
sage: G.coloring(hex_colors=True, algorithm='MILP')
{'#0000ff': [4], '#00ff00': [0, 6, 5], '#ff0000': [2, 1, 3]}
sage: H = G.coloring(hex_colors=True, algorithm='DLX'); H
{'#0000ff': [4], '#00ff00': [1, 2, 3], '#ff0000': [0, 5, 6]}
sage: G.plot(vertex_colors=H)
Graphics object consisting of 16 graphics primitives

Python

>>> from sage.all import *
>>> G = Graph("Fooba")
>>> P = G.coloring(algorithm='MILP')
>>> Q = G.coloring(algorithm='DLX')
>>> def are_equal_colorings(A, B):
...     return Set(map(Set, A)) == Set(map(Set, B))
>>> are_equal_colorings(P, [[Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(5), Integer(6)], [Integer(4)]])
True
>>> are_equal_colorings(P, Q)
True

>>> # needs sage.plot
>>> G.plot(partition=P)
Graphics object consisting of 16 graphics primitives
>>> G.coloring(hex_colors=True, algorithm='MILP')
{'#0000ff': [4], '#00ff00': [0, 6, 5], '#ff0000': [2, 1, 3]}
>>> H = G.coloring(hex_colors=True, algorithm='DLX'); H
{'#0000ff': [4], '#00ff00': [1, 2, 3], '#ff0000': [0, 5, 6]}
>>> G.plot(vertex_colors=H)
Graphics object consisting of 16 graphics primitives

common_neighbors_matrix(vertices, nonedgesonly=None, base_ring=True, **kwds)[source]¶

Return a matrix of numbers of common neighbors between each pairs.

The \((i , j)\) entry of the matrix gives the number of common neighbors between vertices \(i\) and \(j\).

This method is only valid for simple (no loops, no multiple edges) graphs.

INPUT:

nonedgesonly – boolean (default: True); if True, assigns \(0\) value to adjacent vertices.
vertices – list (default: None); the ordering of the vertices defining how they should appear in the matrix. By default, the ordering given by GenericGraph.vertices() is used.
base_ring – a ring (default: None); the base ring of the matrix space to use
**kwds – other keywords to pass to matrix()

OUTPUT: matrix

EXAMPLES:

The common neighbors matrix for a straight linear 2-tree counting only non-adjacent vertex pairs

Sage

sage: G1 = Graph()
sage: G1.add_edges([(0,1),(0,2),(1,2),(1,3),(3,5),(2,4),(2,3),(3,4),(4,5)])
sage: G1.common_neighbors_matrix(nonedgesonly=True)                         # needs sage.modules
[0 0 0 2 1 0]
[0 0 0 0 2 1]
[0 0 0 0 0 2]
[2 0 0 0 0 0]
[1 2 0 0 0 0]
[0 1 2 0 0 0]

Python

>>> from sage.all import *
>>> G1 = Graph()
>>> G1.add_edges([(Integer(0),Integer(1)),(Integer(0),Integer(2)),(Integer(1),Integer(2)),(Integer(1),Integer(3)),(Integer(3),Integer(5)),(Integer(2),Integer(4)),(Integer(2),Integer(3)),(Integer(3),Integer(4)),(Integer(4),Integer(5))])
>>> G1.common_neighbors_matrix(nonedgesonly=True)                         # needs sage.modules
[0 0 0 2 1 0]
[0 0 0 0 2 1]
[0 0 0 0 0 2]
[2 0 0 0 0 0]
[1 2 0 0 0 0]
[0 1 2 0 0 0]

We now show the common neighbors matrix which includes adjacent vertices

Sage

sage: G1.common_neighbors_matrix(nonedgesonly=False)                        # needs sage.modules
[0 1 1 2 1 0]
[1 0 2 1 2 1]
[1 2 0 2 1 2]
[2 1 2 0 2 1]
[1 2 1 2 0 1]
[0 1 2 1 1 0]

Python

>>> from sage.all import *
>>> G1.common_neighbors_matrix(nonedgesonly=False)                        # needs sage.modules
[0 1 1 2 1 0]
[1 0 2 1 2 1]
[1 2 0 2 1 2]
[2 1 2 0 2 1]
[1 2 1 2 0 1]
[0 1 2 1 1 0]

The common neighbors matrix for a fan on 6 vertices counting only non-adjacent vertex pairs

Sage

sage: H = Graph([(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,2),(2,3),(3,4),(4,5)])
sage: H.common_neighbors_matrix()                                           # needs sage.modules
[0 0 0 0 0 0 0]
[0 0 0 2 1 1 1]
[0 0 0 0 2 1 1]
[0 2 0 0 0 2 1]
[0 1 2 0 0 0 1]
[0 1 1 2 0 0 1]
[0 1 1 1 1 1 0]

Python

>>> from sage.all import *
>>> H = Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(0),Integer(4)),(Integer(0),Integer(5)),(Integer(0),Integer(6)),(Integer(1),Integer(2)),(Integer(2),Integer(3)),(Integer(3),Integer(4)),(Integer(4),Integer(5))])
>>> H.common_neighbors_matrix()                                           # needs sage.modules
[0 0 0 0 0 0 0]
[0 0 0 2 1 1 1]
[0 0 0 0 2 1 1]
[0 2 0 0 0 2 1]
[0 1 2 0 0 0 1]
[0 1 1 2 0 0 1]
[0 1 1 1 1 1 0]

A different base ring:

Sage

sage: H.common_neighbors_matrix(base_ring=RDF)                              # needs sage.modules
[0.0 0.0 0.0 0.0 0.0 0.0 0.0]
[0.0 0.0 0.0 2.0 1.0 1.0 1.0]
[0.0 0.0 0.0 0.0 2.0 1.0 1.0]
[0.0 2.0 0.0 0.0 0.0 2.0 1.0]
[0.0 1.0 2.0 0.0 0.0 0.0 1.0]
[0.0 1.0 1.0 2.0 0.0 0.0 1.0]
[0.0 1.0 1.0 1.0 1.0 1.0 0.0]

Python

>>> from sage.all import *
>>> H.common_neighbors_matrix(base_ring=RDF)                              # needs sage.modules
[0.0 0.0 0.0 0.0 0.0 0.0 0.0]
[0.0 0.0 0.0 2.0 1.0 1.0 1.0]
[0.0 0.0 0.0 0.0 2.0 1.0 1.0]
[0.0 2.0 0.0 0.0 0.0 2.0 1.0]
[0.0 1.0 2.0 0.0 0.0 0.0 1.0]
[0.0 1.0 1.0 2.0 0.0 0.0 1.0]
[0.0 1.0 1.0 1.0 1.0 1.0 0.0]

It is an error to input anything other than a simple graph:

Sage

sage: G = Graph([(0,0)], loops=True)
sage: G.common_neighbors_matrix()                                           # needs sage.modules
Traceback (most recent call last):
...
ValueError: This method is not known to work on graphs with loops.
Perhaps this method can be updated to handle them, but in the
meantime if you want to use it please disallow loops using
allow_loops().

Python

>>> from sage.all import *
>>> G = Graph([(Integer(0),Integer(0))], loops=True)
>>> G.common_neighbors_matrix()                                           # needs sage.modules
Traceback (most recent call last):
...
ValueError: This method is not known to work on graphs with loops.
Perhaps this method can be updated to handle them, but in the
meantime if you want to use it please disallow loops using
allow_loops().

See also

most_common_neighbors() – returns node pairs with most shared neighbors

convexity_properties()[source]¶

Return a ConvexityProperties object corresponding to self.

This object contains the methods related to convexity in graphs (convex hull, hull number) and caches useful information so that it becomes comparatively cheaper to compute the convex hull of many different sets of the same graph.

See also

In order to know what can be done through this object, please refer to module sage.graphs.convexity_properties.

Note

If you want to compute many convex hulls, keep this object in memory! When it is created, it builds a table of useful information to compute convex hulls. As a result

Sage

sage: # needs sage.numerical.mip
sage: g = graphs.PetersenGraph()
sage: g.convexity_properties().hull([1, 3])
[1, 2, 3]
sage: g.convexity_properties().hull([3, 7])
[2, 3, 7]

Python

>>> from sage.all import *
>>> # needs sage.numerical.mip
>>> g = graphs.PetersenGraph()
>>> g.convexity_properties().hull([Integer(1), Integer(3)])
[1, 2, 3]
>>> g.convexity_properties().hull([Integer(3), Integer(7)])
[2, 3, 7]

is a terrible waste of computations, while

Sage

sage: # needs sage.numerical.mip
sage: g = graphs.PetersenGraph()
sage: CP = g.convexity_properties()
sage: CP.hull([1, 3])
[1, 2, 3]
sage: CP.hull([3, 7])
[2, 3, 7]

Python

>>> from sage.all import *
>>> # needs sage.numerical.mip
>>> g = graphs.PetersenGraph()
>>> CP = g.convexity_properties()
>>> CP.hull([Integer(1), Integer(3)])
[1, 2, 3]
>>> CP.hull([Integer(3), Integer(7)])
[2, 3, 7]

makes perfect sense.

cores(k=None, with_labels=False)[source]¶

Return the core number for each vertex in an ordered list.

(for homomorphisms cores, see the Graph.has_homomorphism_to() method)

DEFINITIONS:

K-cores in graph theory were introduced by Seidman in 1983 and by Bollobas in 1984 as a method of (destructively) simplifying graph topology to aid in analysis and visualization. They have been more recently defined as the following by Batagelj et al:

Given a graph `G` with vertices set `V` and edges set `E`, the `k`-core of `G` is the graph obtained from `G` by recursively removing the vertices with degree less than `k`, for as long as there are any.

This operation can be useful to filter or to study some properties of the graphs. For instance, when you compute the 2-core of graph G, you are cutting all the vertices which are in a tree part of graph. (A tree is a graph with no loops). See the Wikipedia article K-core.

[PSW1996] defines a \(k\)-core of \(G\) as the largest subgraph (it is unique) of \(G\) with minimum degree at least \(k\).
Core number of a vertex

The core number of a vertex \(v\) is the largest integer \(k\) such that \(v\) belongs to the \(k\)-core of \(G\).
Degeneracy

The degeneracy of a graph \(G\), usually denoted \(\delta^*(G)\), is the smallest integer \(k\) such that the graph \(G\) can be reduced to the empty graph by iteratively removing vertices of degree \(\leq k\). Equivalently, \(\delta^*(G) = k - 1\) if \(k\) is the smallest integer such that the \(k\)-core of \(G\) is empty.

IMPLEMENTATION:

This implementation is based on the NetworkX implementation of the algorithm described in [BZ2003].

INPUT:

k – integer (default: None)
- If k = None (default), returns the core number for each vertex.
- If k is an integer, returns a pair (ordering, core), where core is the list of vertices in the \(k\)-core of self, and ordering is an elimination order for the other vertices such that each vertex is of degree strictly less than \(k\) when it is to be eliminated from the graph.
with_labels – boolean (default: False); when set to False, and k = None, the method returns a list whose \(i\) th element is the core number of the \(i\) th vertex. When set to True, the method returns a dictionary whose keys are vertices, and whose values are the corresponding core numbers.

See also

Graph cores is also a notion related to graph homomorphisms. For this second meaning, see Graph.has_homomorphism_to().
Wikipedia article Degeneracy_(graph_theory)

EXAMPLES:

Sage

sage: (graphs.FruchtGraph()).cores()
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
sage: (graphs.FruchtGraph()).cores(with_labels=True)
{0: 3, 1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3, 7: 3, 8: 3, 9: 3, 10: 3, 11: 3}

sage: # needs sage.modules
sage: set_random_seed(0)
sage: a = random_matrix(ZZ, 20, x=2, sparse=True, density=.1)
sage: b = Graph(20)
sage: b.add_edges(a.nonzero_positions(), loops=False)
sage: cores = b.cores(with_labels=True); cores
{0: 3, 1: 3, 2: 3, 3: 3, 4: 2, 5: 2, 6: 3, 7: 1, 8: 3, 9: 3, 10: 3,
 11: 3, 12: 3, 13: 3, 14: 2, 15: 3, 16: 3, 17: 3, 18: 3, 19: 3}
sage: [v for v,c in cores.items() if c >= 2]  # the vertices in the 2-core
[0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Python

>>> from sage.all import *
>>> (graphs.FruchtGraph()).cores()
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
>>> (graphs.FruchtGraph()).cores(with_labels=True)
{0: 3, 1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3, 7: 3, 8: 3, 9: 3, 10: 3, 11: 3}

>>> # needs sage.modules
>>> set_random_seed(Integer(0))
>>> a = random_matrix(ZZ, Integer(20), x=Integer(2), sparse=True, density=RealNumber('.1'))
>>> b = Graph(Integer(20))
>>> b.add_edges(a.nonzero_positions(), loops=False)
>>> cores = b.cores(with_labels=True); cores
{0: 3, 1: 3, 2: 3, 3: 3, 4: 2, 5: 2, 6: 3, 7: 1, 8: 3, 9: 3, 10: 3,
 11: 3, 12: 3, 13: 3, 14: 2, 15: 3, 16: 3, 17: 3, 18: 3, 19: 3}
>>> [v for v,c in cores.items() if c >= Integer(2)]  # the vertices in the 2-core
[0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Checking the 2-core of a random lobster is indeed the empty set:

Sage

sage: g = graphs.RandomLobster(20, .5, .5)                                  # needs networkx
sage: ordering, core = g.cores(2)                                           # needs networkx
sage: len(core) == 0                                                        # needs networkx
True

Python

>>> from sage.all import *
>>> g = graphs.RandomLobster(Integer(20), RealNumber('.5'), RealNumber('.5'))                                  # needs networkx
>>> ordering, core = g.cores(Integer(2))                                           # needs networkx
>>> len(core) == Integer(0)                                                        # needs networkx
True

Checking the cores of a bull graph:

Sage

sage: G = graphs.BullGraph()
sage: G.cores(with_labels=True)
{0: 2, 1: 2, 2: 2, 3: 1, 4: 1}
sage: G.cores(k=2)
([3, 4], [0, 1, 2])

Python

>>> from sage.all import *
>>> G = graphs.BullGraph()
>>> G.cores(with_labels=True)
{0: 2, 1: 2, 2: 2, 3: 1, 4: 1}
>>> G.cores(k=Integer(2))
([3, 4], [0, 1, 2])

Graphs with multiple edges:

Sage

sage: G.allow_multiple_edges(True)
sage: G.add_edges(G.edges(sort=False))
sage: G.cores(with_labels=True)
{0: 4, 1: 4, 2: 4, 3: 2, 4: 2}
sage: G.cores(k=4)
([3, 4], [0, 1, 2])

Python

>>> from sage.all import *
>>> G.allow_multiple_edges(True)
>>> G.add_edges(G.edges(sort=False))
>>> G.cores(with_labels=True)
{0: 4, 1: 4, 2: 4, 3: 2, 4: 2}
>>> G.cores(k=Integer(4))
([3, 4], [0, 1, 2])

cutwidth(G, algorithm='exponential', cut_off=0, solver=None, verbose=False, integrality_tolerance=0.001)[source]¶

Return the cutwidth of the graph and the corresponding vertex ordering.

INPUT:

G – a Graph or a DiGraph
algorithm – string (default: 'exponential'); algorithm to use among:
- exponential – use an exponential time and space algorithm based on dynamic programming. This algorithm only works on graphs with strictly less than 32 vertices.
- MILP – use a mixed integer linear programming formulation. This algorithm has no size restriction but could take a very long time
cut_off – integer (default: 0); used to stop the search as soon as a solution with width at most cut_off is found, if any. If this bound cannot be reached, the best solution found is returned.
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – boolean (default: False); whether to display information on the computations
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

A pair (cost, ordering) representing the optimal ordering of the vertices and its cost.

EXAMPLES:

Cutwidth of a Complete Graph:

Sage

sage: from sage.graphs.graph_decompositions.cutwidth import cutwidth
sage: G = graphs.CompleteGraph(5)
sage: cw,L = cutwidth(G); cw
6
sage: K = graphs.CompleteGraph(6)
sage: cw,L = cutwidth(K); cw
9
sage: cw,L = cutwidth(K+K); cw
9

Python

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.cutwidth import cutwidth
>>> G = graphs.CompleteGraph(Integer(5))
>>> cw,L = cutwidth(G); cw
6
>>> K = graphs.CompleteGraph(Integer(6))
>>> cw,L = cutwidth(K); cw
9
>>> cw,L = cutwidth(K+K); cw
9

The cutwidth of a \(p\times q\) Grid Graph with \(p\leq q\) is \(p+1\):

Sage

sage: from sage.graphs.graph_decompositions.cutwidth import cutwidth
sage: G = graphs.Grid2dGraph(3,3)
sage: cw,L = cutwidth(G); cw
4
sage: G = graphs.Grid2dGraph(3,5)
sage: cw,L = cutwidth(G); cw
4

Python

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.cutwidth import cutwidth
>>> G = graphs.Grid2dGraph(Integer(3),Integer(3))
>>> cw,L = cutwidth(G); cw
4
>>> G = graphs.Grid2dGraph(Integer(3),Integer(5))
>>> cw,L = cutwidth(G); cw
4

degree_constrained_subgraph(bounds, solver, verbose=None, integrality_tolerance=0)[source]¶

Return a degree-constrained subgraph.

Given a graph \(G\) and two functions \(f, g:V(G)\rightarrow \mathbb Z\) such that \(f \leq g\), a degree-constrained subgraph in \(G\) is a subgraph \(G' \subseteq G\) such that for any vertex \(v \in G\), \(f(v) \leq d_{G'}(v) \leq g(v)\).

INPUT:

bounds – (default: None) two possibilities:
- A dictionary whose keys are the vertices, and values a pair of real values (min,max) corresponding to the values \((f(v),g(v))\).
- A function associating to each vertex a pair of real values (min,max) corresponding to the values \((f(v),g(v))\).
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

When a solution exists, this method outputs the degree-constrained subgraph as a Graph object.
When no solution exists, returns False.

Note

This algorithm computes the degree-constrained subgraph of minimum weight.
If the graph’s edges are weighted, these are taken into account.
This problem can be solved in polynomial time.

EXAMPLES:

Is there a perfect matching in an even cycle?

Sage

sage: g = graphs.CycleGraph(6)
sage: bounds = lambda x: [1,1]
sage: m = g.degree_constrained_subgraph(bounds=bounds)                      # needs sage.numerical.mip
sage: m.size()                                                              # needs sage.numerical.mip
3

Python

>>> from sage.all import *
>>> g = graphs.CycleGraph(Integer(6))
>>> bounds = lambda x: [Integer(1),Integer(1)]
>>> m = g.degree_constrained_subgraph(bounds=bounds)                      # needs sage.numerical.mip
>>> m.size()                                                              # needs sage.numerical.mip
3

diameter(by_weight=False, algorithm=None, weight_function=None, check_weight=True)[source]¶

Return the diameter of the graph.

The diameter is defined to be the maximum distance between two vertices. It is infinite if the graph is not connected.

For more information and examples on how to use input variables, see shortest_paths() and eccentricity()

INPUT:

by_weight – boolean (default: False); if True, edge weights are taken into account; if False, all edges have weight 1
algorithm – string (default: None); one of the following algorithms:
- 'BFS': the computation is done through a BFS centered on each vertex successively. Works only if by_weight==False.
- 'Floyd-Warshall-Cython': a Cython implementation of the Floyd-Warshall algorithm. Works only if by_weight==False and v is None.
- 'Floyd-Warshall-Python': a Python implementation of the Floyd-Warshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed). However, v must be None.
- 'Dijkstra_NetworkX': the Dijkstra algorithm, implemented in NetworkX. It works with weighted graphs, but no negative weight is allowed.
- 'DHV' – diameter computation is done using the algorithm proposed in [Dragan2018]. Works only for nonnegative edge weights For more information see method sage.graphs.distances_all_pairs.diameter_DHV() and sage.graphs.base.boost_graph.diameter_DHV().
- 'standard', '2sweep', 'multi-sweep', 'iFUB': these algorithms are implemented in sage.graphs.distances_all_pairs.diameter() They work only if by_weight==False. See the function documentation for more information.
- 'Dijkstra_Boost': the Dijkstra algorithm, implemented in Boost (works only with positive weights).
- 'Johnson_Boost': the Johnson algorithm, implemented in Boost (works also with negative weights, if there is no negative cycle).
- None (default): Sage chooses the best algorithm: 'iFUB' for unweighted graphs, 'Dijkstra_Boost' if all weights are positive, 'Johnson_Boost' otherwise.
weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight, if l is not None, else 1 as a weight.
check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge

EXAMPLES:

The more symmetric a graph is, the smaller (diameter - radius) is:

Sage

sage: G = graphs.BarbellGraph(9, 3)
sage: G.radius()
3
sage: G.diameter()
6

Python

>>> from sage.all import *
>>> G = graphs.BarbellGraph(Integer(9), Integer(3))
>>> G.radius()
3
>>> G.diameter()
6

Sage

sage: G = graphs.OctahedralGraph()
sage: G.radius()
2
sage: G.diameter()
2

Python

>>> from sage.all import *
>>> G = graphs.OctahedralGraph()
>>> G.radius()
2
>>> G.diameter()
2

distance_graph(dist)[source]¶

Return the graph on the same vertex set as the original graph but vertices are adjacent in the returned graph if and only if they are at specified distances in the original graph.

INPUT:

dist – nonnegative integer or a list of nonnegative integers; specified distance(s) for the connecting vertices. Infinity may be used here to describe vertex pairs in separate components.

OUTPUT:

The returned value is an undirected graph. The vertex set is identical to the calling graph, but edges of the returned graph join vertices whose distance in the calling graph are present in the input dist. Loops will only be present if distance 0 is included. If the original graph has a position dictionary specifying locations of vertices for plotting, then this information is copied over to the distance graph. In some instances this layout may not be the best, and might even be confusing when edges run on top of each other due to symmetries chosen for the layout.

EXAMPLES:

Sage

sage: G = graphs.CompleteGraph(3)
sage: H = G.cartesian_product(graphs.CompleteGraph(2))
sage: K = H.distance_graph(2)
sage: K.am()                                                                # needs sage.modules
[0 0 0 1 0 1]
[0 0 1 0 1 0]
[0 1 0 0 0 1]
[1 0 0 0 1 0]
[0 1 0 1 0 0]
[1 0 1 0 0 0]

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(3))
>>> H = G.cartesian_product(graphs.CompleteGraph(Integer(2)))
>>> K = H.distance_graph(Integer(2))
>>> K.am()                                                                # needs sage.modules
[0 0 0 1 0 1]
[0 0 1 0 1 0]
[0 1 0 0 0 1]
[1 0 0 0 1 0]
[0 1 0 1 0 0]
[1 0 1 0 0 0]

To obtain the graph where vertices are adjacent if their distance apart is d or less use a range() command to create the input, using d + 1 as the input to range. Notice that this will include distance 0 and hence place a loop at each vertex. To avoid this, use range(1, d + 1):

Sage

sage: G = graphs.OddGraph(4)
sage: d = G.diameter()
sage: n = G.num_verts()
sage: H = G.distance_graph(list(range(d+1)))
sage: H.is_isomorphic(graphs.CompleteGraph(n))
False
sage: H = G.distance_graph(list(range(1,d+1)))
sage: H.is_isomorphic(graphs.CompleteGraph(n))
True

Python

>>> from sage.all import *
>>> G = graphs.OddGraph(Integer(4))
>>> d = G.diameter()
>>> n = G.num_verts()
>>> H = G.distance_graph(list(range(d+Integer(1))))
>>> H.is_isomorphic(graphs.CompleteGraph(n))
False
>>> H = G.distance_graph(list(range(Integer(1),d+Integer(1))))
>>> H.is_isomorphic(graphs.CompleteGraph(n))
True

A complete collection of distance graphs will have adjacency matrices that sum to the matrix of all ones:

Sage

sage: P = graphs.PathGraph(20)
sage: all_ones = sum([P.distance_graph(i).am() for i in range(20)])         # needs sage.modules
sage: all_ones == matrix(ZZ, 20, 20, [1]*400)                               # needs sage.modules
True

Python

>>> from sage.all import *
>>> P = graphs.PathGraph(Integer(20))
>>> all_ones = sum([P.distance_graph(i).am() for i in range(Integer(20))])         # needs sage.modules
>>> all_ones == matrix(ZZ, Integer(20), Integer(20), [Integer(1)]*Integer(400))                               # needs sage.modules
True

Four-bit strings differing in one bit is the same as four-bit strings differing in three bits:

Sage

sage: G = graphs.CubeGraph(4)
sage: H = G.distance_graph(3)
sage: G.is_isomorphic(H)
True

Python

>>> from sage.all import *
>>> G = graphs.CubeGraph(Integer(4))
>>> H = G.distance_graph(Integer(3))
>>> G.is_isomorphic(H)
True

The graph of eight-bit strings, adjacent if different in an odd number of bits:

Sage

sage: # long time, needs sage.symbolic
sage: G = graphs.CubeGraph(8)
sage: H = G.distance_graph([1,3,5,7])
sage: degrees = [0]*sum([binomial(8,j) for j in [1,3,5,7]])
sage: degrees.append(2^8)
sage: degrees == H.degree_histogram()
True

Python

>>> from sage.all import *
>>> # long time, needs sage.symbolic
>>> G = graphs.CubeGraph(Integer(8))
>>> H = G.distance_graph([Integer(1),Integer(3),Integer(5),Integer(7)])
>>> degrees = [Integer(0)]*sum([binomial(Integer(8),j) for j in [Integer(1),Integer(3),Integer(5),Integer(7)]])
>>> degrees.append(Integer(2)**Integer(8))
>>> degrees == H.degree_histogram()
True

An example of using Infinity as the distance in a graph that is not connected:

Sage

sage: G = graphs.CompleteGraph(3)
sage: H = G.disjoint_union(graphs.CompleteGraph(2))
sage: L = H.distance_graph(Infinity)
sage: L.am()                                                                # needs sage.modules
[0 0 0 1 1]
[0 0 0 1 1]
[0 0 0 1 1]
[1 1 1 0 0]
[1 1 1 0 0]
sage: L.is_isomorphic(graphs.CompleteBipartiteGraph(3, 2))
True

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(3))
>>> H = G.disjoint_union(graphs.CompleteGraph(Integer(2)))
>>> L = H.distance_graph(Infinity)
>>> L.am()                                                                # needs sage.modules
[0 0 0 1 1]
[0 0 0 1 1]
[0 0 0 1 1]
[1 1 1 0 0]
[1 1 1 0 0]
>>> L.is_isomorphic(graphs.CompleteBipartiteGraph(Integer(3), Integer(2)))
True

AUTHOR:

Rob Beezer, 2009-11-25, Issue #7533

ear_decomposition()[source]¶

Return an Ear decomposition of the graph.

An ear of an undirected graph \(G\) is a path \(P\) where the two endpoints of the path may coincide (i.e., form a cycle), but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of \(P\) has degree two in \(P\).

An ear decomposition of an undirected graph \(G\) is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear.

For more information, see the Wikipedia article Ear_decomposition.

This method implements the linear time algorithm presented in [Sch2013].

OUTPUT:

A nested list representing the cycles and chains of the ear decomposition of the graph.

EXAMPLES:

Ear decomposition of an outer planar graph of order 13:

Sage

sage: g = Graph('LlCG{O@?GBOMW?')
sage: g.ear_decomposition()
[[0, 3, 2, 1, 0],
 [0, 7, 4, 3],
 [0, 11, 9, 8, 7],
 [1, 12, 2],
 [3, 6, 5, 4],
 [4, 6],
 [7, 10, 8],
 [7, 11],
 [8, 11]]

Python

>>> from sage.all import *
>>> g = Graph('LlCG{O@?GBOMW?')
>>> g.ear_decomposition()
[[0, 3, 2, 1, 0],
 [0, 7, 4, 3],
 [0, 11, 9, 8, 7],
 [1, 12, 2],
 [3, 6, 5, 4],
 [4, 6],
 [7, 10, 8],
 [7, 11],
 [8, 11]]

Ear decomposition of a biconnected graph:

Sage

sage: g = graphs.CycleGraph(4)
sage: g.ear_decomposition()
[[0, 3, 2, 1, 0]]

Python

>>> from sage.all import *
>>> g = graphs.CycleGraph(Integer(4))
>>> g.ear_decomposition()
[[0, 3, 2, 1, 0]]

Ear decomposition of a connected but not biconnected graph:

Sage

sage: G = Graph()
sage: G.add_cycle([0,1,2])
sage: G.add_edge(0,3)
sage: G.add_cycle([3,4,5,6])
sage: G.ear_decomposition()
[[0, 2, 1, 0], [3, 6, 5, 4, 3]]

Python

>>> from sage.all import *
>>> G = Graph()
>>> G.add_cycle([Integer(0),Integer(1),Integer(2)])
>>> G.add_edge(Integer(0),Integer(3))
>>> G.add_cycle([Integer(3),Integer(4),Integer(5),Integer(6)])
>>> G.ear_decomposition()
[[0, 2, 1, 0], [3, 6, 5, 4, 3]]

The ear decomposition of a multigraph with loops is the same as the ear decomposition of the underlying simple graph:

Sage

sage: g = graphs.BullGraph()
sage: g.allow_multiple_edges(True)
sage: g.add_edges(g.edges(sort=False))
sage: g.allow_loops(True)
sage: u = g.random_vertex()
sage: g.add_edge(u, u)
sage: g
Bull graph: Looped multi-graph on 5 vertices
sage: h = g.to_simple()
sage: g.ear_decomposition() == h.ear_decomposition()
True

Python

>>> from sage.all import *
>>> g = graphs.BullGraph()
>>> g.allow_multiple_edges(True)
>>> g.add_edges(g.edges(sort=False))
>>> g.allow_loops(True)
>>> u = g.random_vertex()
>>> g.add_edge(u, u)
>>> g
Bull graph: Looped multi-graph on 5 vertices
>>> h = g.to_simple()
>>> g.ear_decomposition() == h.ear_decomposition()
True

eccentricity(v=None, by_weight=False, algorithm=None, weight_function=None, check_weight=True, dist_dict=None, with_labels=False)[source]¶

Return the eccentricity of vertex (or vertices) v.

The eccentricity of a vertex is the maximum distance to any other vertex.

For more information and examples on how to use input variables, see shortest_path_all_pairs(), shortest_path_lengths() and shortest_paths()

INPUT:

v – either a single vertex or a list of vertices. If it is not specified, then it is taken to be all vertices
by_weight – boolean (default: False); if True, edge weights are taken into account; if False, all edges have weight 1
algorithm – string (default: None); one of the following algorithms:
- 'BFS' – the computation is done through a BFS centered on each vertex successively. Works only if by_weight==False
- 'DHV' – the computation is done using the algorithm proposed in [Dragan2018]. Works only if self has nonnegative edge weights and v is None or v should contain all vertices of self. For more information see method sage.graphs.distances_all_pairs.eccentricity() and sage.graphs.base.boost_graph.eccentricity_DHV().
- 'Floyd-Warshall-Cython' – a Cython implementation of the Floyd-Warshall algorithm. Works only if by_weight==False and v is None or v should contain all vertices of self.
- 'Floyd-Warshall-Python' – a Python implementation of the Floyd-Warshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed). However, v must be None or v should contain all vertices of self.
- 'Dijkstra_NetworkX' – the Dijkstra algorithm, implemented in NetworkX. It works with weighted graphs, but no negative weight is allowed.
- 'Dijkstra_Boost' – the Dijkstra algorithm, implemented in Boost (works only with positive weights)
- 'Johnson_Boost' – the Johnson algorithm, implemented in Boost (works also with negative weights, if there is no negative cycle). Works only if v is None or v should contain all vertices of self.
- 'From_Dictionary' – uses the (already computed) distances, that are provided by input variable dist_dict
- None (default): Sage chooses the best algorithm: 'From_Dictionary' if dist_dict is not None, 'BFS' for unweighted graphs, 'Dijkstra_Boost' if all weights are positive, 'Johnson_Boost' otherwise.
weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight, if l is not None, else 1 as a weight.
check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge
dist_dict – dictionary (default: None); a dict of dicts of distances (used only if algorithm=='From_Dictionary')
with_labels – boolean (default: False); whether to return a list or a dictionary keyed by vertices

EXAMPLES:

Sage

sage: G = graphs.KrackhardtKiteGraph()
sage: G.eccentricity()
[4, 4, 4, 4, 4, 3, 3, 2, 3, 4]
sage: G.vertices(sort=True)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: G.eccentricity(7)
2
sage: G.eccentricity([7,8,9])
[2, 3, 4]
sage: G.eccentricity([7, 8, 9], with_labels=True) == {8: 3, 9: 4, 7: 2}
True
sage: G = Graph({0: [], 1: [], 2: [1]})
sage: G.eccentricity()
[+Infinity, +Infinity, +Infinity]
sage: G = Graph({0:[]})
sage: G.eccentricity(with_labels=True)
{0: 0}
sage: G = Graph({0:[], 1:[]})
sage: G.eccentricity(with_labels=True)
{0: +Infinity, 1: +Infinity}
sage: G = Graph([(0, 1, 1), (1, 2, 1), (0, 2, 3)])
sage: G.eccentricity(algorithm='BFS')
[1, 1, 1]
sage: G.eccentricity(algorithm='Floyd-Warshall-Cython')
[1, 1, 1]
sage: G.eccentricity(by_weight=True, algorithm='Dijkstra_NetworkX')         # needs networkx
[2, 1, 2]
sage: G.eccentricity(by_weight=True, algorithm='Dijkstra_Boost')
[2, 1, 2]
sage: G.eccentricity(by_weight=True, algorithm='Johnson_Boost')
[2, 1, 2]
sage: G.eccentricity(by_weight=True, algorithm='Floyd-Warshall-Python')
[2, 1, 2]
sage: G.eccentricity(dist_dict=G.shortest_path_all_pairs(by_weight=True)[0])
[2, 1, 2]
sage: G.eccentricity(by_weight=False, algorithm='DHV')
[1, 1, 1]
sage: G.eccentricity(by_weight=True, algorithm='DHV')
[2.0, 1.0, 2.0]

Python

>>> from sage.all import *
>>> G = graphs.KrackhardtKiteGraph()
>>> G.eccentricity()
[4, 4, 4, 4, 4, 3, 3, 2, 3, 4]
>>> G.vertices(sort=True)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> G.eccentricity(Integer(7))
2
>>> G.eccentricity([Integer(7),Integer(8),Integer(9)])
[2, 3, 4]
>>> G.eccentricity([Integer(7), Integer(8), Integer(9)], with_labels=True) == {Integer(8): Integer(3), Integer(9): Integer(4), Integer(7): Integer(2)}
True
>>> G = Graph({Integer(0): [], Integer(1): [], Integer(2): [Integer(1)]})
>>> G.eccentricity()
[+Infinity, +Infinity, +Infinity]
>>> G = Graph({Integer(0):[]})
>>> G.eccentricity(with_labels=True)
{0: 0}
>>> G = Graph({Integer(0):[], Integer(1):[]})
>>> G.eccentricity(with_labels=True)
{0: +Infinity, 1: +Infinity}
>>> G = Graph([(Integer(0), Integer(1), Integer(1)), (Integer(1), Integer(2), Integer(1)), (Integer(0), Integer(2), Integer(3))])
>>> G.eccentricity(algorithm='BFS')
[1, 1, 1]
>>> G.eccentricity(algorithm='Floyd-Warshall-Cython')
[1, 1, 1]
>>> G.eccentricity(by_weight=True, algorithm='Dijkstra_NetworkX')         # needs networkx
[2, 1, 2]
>>> G.eccentricity(by_weight=True, algorithm='Dijkstra_Boost')
[2, 1, 2]
>>> G.eccentricity(by_weight=True, algorithm='Johnson_Boost')
[2, 1, 2]
>>> G.eccentricity(by_weight=True, algorithm='Floyd-Warshall-Python')
[2, 1, 2]
>>> G.eccentricity(dist_dict=G.shortest_path_all_pairs(by_weight=True)[Integer(0)])
[2, 1, 2]
>>> G.eccentricity(by_weight=False, algorithm='DHV')
[1, 1, 1]
>>> G.eccentricity(by_weight=True, algorithm='DHV')
[2.0, 1.0, 2.0]

edge_isoperimetric_number(g)[source]¶

Return the edge-isoperimetric number of the graph.

The edge-isoperimetric number of a graph \(G = (V,E)\) is also sometimes called the isoperimetric number. It is defined as the minimum of \(|\partial S| / |S|\) where \(\partial S\) is the edge boundary of \(S\) (number of edges with one end in \(S\) and one end in \(V \setminus S\)) and the minimum is taken over all subsets of vertices whose cardinality does not exceed half the size \(|V|\) of the graph.

See also

Alternative but similar quantities can be obtained via the methods cheeger_constant() and vertex_isoperimetric_number().

EXAMPLES:

The edge-isoperimetric number of a complete graph on \(n\) vertices is \(\lceil n/2 \rceil\):

Sage

sage: [graphs.CompleteGraph(n).edge_isoperimetric_number() for n in range(2,10)]
[1, 2, 2, 3, 3, 4, 4, 5]

Python

>>> from sage.all import *
>>> [graphs.CompleteGraph(n).edge_isoperimetric_number() for n in range(Integer(2),Integer(10))]
[1, 2, 2, 3, 3, 4, 4, 5]

The edge-isoperimetric constant of a cycle on \(n\) vertices is \(2/\lfloor n/2 \rfloor\):

Sage

sage: [graphs.CycleGraph(n).edge_isoperimetric_number() for n in range(2,15)]
[1, 2, 1, 1, 2/3, 2/3, 1/2, 1/2, 2/5, 2/5, 1/3, 1/3, 2/7]

Python

>>> from sage.all import *
>>> [graphs.CycleGraph(n).edge_isoperimetric_number() for n in range(Integer(2),Integer(15))]
[1, 2, 1, 1, 2/3, 2/3, 1/2, 1/2, 2/5, 2/5, 1/3, 1/3, 2/7]

In general, for \(d\)-regular graphs the edge-isoperimetric number is \(d\) times larger than the Cheeger constant of the graph:

Sage

sage: g = graphs.RandomRegular(3, 10)                                           # needs networkx
sage: g.edge_isoperimetric_number() == g.cheeger_constant() * 3                 # needs networkx
True

Python

>>> from sage.all import *
>>> g = graphs.RandomRegular(Integer(3), Integer(10))                                           # needs networkx
>>> g.edge_isoperimetric_number() == g.cheeger_constant() * Integer(3)                 # needs networkx
True

And the edge-isoperimetric constant of a disconnected graph is \(0\):

Sage

sage: Graph([[1,2,3,4],[(1,2),(3,4)]]).edge_isoperimetric_number()
0

Python

>>> from sage.all import *
>>> Graph([[Integer(1),Integer(2),Integer(3),Integer(4)],[(Integer(1),Integer(2)),(Integer(3),Integer(4))]]).edge_isoperimetric_number()
0

effective_resistance(i, j, base_ring)[source]¶

Return the effective resistance between nodes \(i\) and \(j\).

The resistance distance between vertices \(i\) and \(j\) of a simple connected graph \(G\) is defined as the effective resistance between the two vertices on an electrical network constructed from \(G\) replacing each edge of the graph by a unit (1 ohm) resistor.

See the Wikipedia article Resistance_distance for more information.

INPUT:

i, j – vertices of the graph
base_ring – a ring (default: None); the base ring of the matrix space to use

OUTPUT: rational number denoting resistance between nodes \(i\) and \(j\)

EXAMPLES:

Effective resistances in a straight linear 2-tree on 6 vertices

Sage

sage: # needs sage.modules
sage: G = Graph([(0,1),(0,2),(1,2),(1,3),(3,5),(2,4),(2,3),(3,4),(4,5)])
sage: G.effective_resistance(0,1)
34/55
sage: G.effective_resistance(0,3)
49/55
sage: G.effective_resistance(1,4)
9/11
sage: G.effective_resistance(0,5)
15/11

Python

>>> from sage.all import *
>>> # needs sage.modules
>>> G = Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2)),(Integer(1),Integer(2)),(Integer(1),Integer(3)),(Integer(3),Integer(5)),(Integer(2),Integer(4)),(Integer(2),Integer(3)),(Integer(3),Integer(4)),(Integer(4),Integer(5))])
>>> G.effective_resistance(Integer(0),Integer(1))
34/55
>>> G.effective_resistance(Integer(0),Integer(3))
49/55
>>> G.effective_resistance(Integer(1),Integer(4))
9/11
>>> G.effective_resistance(Integer(0),Integer(5))
15/11

Effective resistances in a fan on 6 vertices

Sage

sage: # needs sage.modules
sage: H = Graph([(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,2),(2,3),(3,4),(4,5)])
sage: H.effective_resistance(1,5)
6/5
sage: H.effective_resistance(1,3)
49/55
sage: H.effective_resistance(1,1)
0

Python

>>> from sage.all import *
>>> # needs sage.modules
>>> H = Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(0),Integer(4)),(Integer(0),Integer(5)),(Integer(0),Integer(6)),(Integer(1),Integer(2)),(Integer(2),Integer(3)),(Integer(3),Integer(4)),(Integer(4),Integer(5))])
>>> H.effective_resistance(Integer(1),Integer(5))
6/5
>>> H.effective_resistance(Integer(1),Integer(3))
49/55
>>> H.effective_resistance(Integer(1),Integer(1))
0

Using a different base ring:

Sage

sage: H.effective_resistance(1, 5, base_ring=RDF)   # abs tol 1e-14         # needs numpy sage.modules
1.2000000000000000
sage: H.effective_resistance(1, 1, base_ring=RDF)                           # needs sage.modules
0.0

Python

>>> from sage.all import *
>>> H.effective_resistance(Integer(1), Integer(5), base_ring=RDF)   # abs tol 1e-14         # needs numpy sage.modules
1.2000000000000000
>>> H.effective_resistance(Integer(1), Integer(1), base_ring=RDF)                           # needs sage.modules
0.0

See also

effective_resistance_matrix() – a similar method giving a matrix full of all effective resistances between all nodes
least_effective_resistance() – gives node pairs with least effective resistances
See Wikipedia article Resistance_distance for more details.

effective_resistance_matrix(vertices, nonedgesonly=None, base_ring=True, **kwds)[source]¶

Return a matrix whose (\(i\) , \(j\)) entry gives the effective resistance between vertices \(i\) and \(j\).

By default, the matrix returned is over the rationals.

INPUT:

nonedgesonly – boolean (default: True); if True assign zero resistance to pairs of adjacent vertices.
vertices – list (default: None); the ordering of the vertices defining how they should appear in the matrix. By default, the ordering given by GenericGraph.vertices() is used.
base_ring – a ring (default: None); the base ring of the matrix space to use
**kwds – other keywords to pass to matrix()

OUTPUT: matrix

EXAMPLES:

The effective resistance matrix for a straight linear 2-tree counting only non-adjacent vertex pairs

Sage

sage: G = Graph([(0,1),(0,2),(1,2),(1,3),(3,5),(2,4),(2,3),(3,4),(4,5)])
sage: G.effective_resistance_matrix()                                       # needs sage.modules
[    0     0     0 49/55 59/55 15/11]
[    0     0     0     0  9/11 59/55]
[    0     0     0     0     0 49/55]
[49/55     0     0     0     0     0]
[59/55  9/11     0     0     0     0]
[15/11 59/55 49/55     0     0     0]

Python

>>> from sage.all import *
>>> G = Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2)),(Integer(1),Integer(2)),(Integer(1),Integer(3)),(Integer(3),Integer(5)),(Integer(2),Integer(4)),(Integer(2),Integer(3)),(Integer(3),Integer(4)),(Integer(4),Integer(5))])
>>> G.effective_resistance_matrix()                                       # needs sage.modules
[    0     0     0 49/55 59/55 15/11]
[    0     0     0     0  9/11 59/55]
[    0     0     0     0     0 49/55]
[49/55     0     0     0     0     0]
[59/55  9/11     0     0     0     0]
[15/11 59/55 49/55     0     0     0]

The same effective resistance matrix, this time including adjacent vertices

Sage

sage: G.effective_resistance_matrix(nonedgesonly=False)                     # needs sage.modules
[    0 34/55 34/55 49/55 59/55 15/11]
[34/55     0 26/55 31/55  9/11 59/55]
[34/55 26/55     0  5/11 31/55 49/55]
[49/55 31/55  5/11     0 26/55 34/55]
[59/55  9/11 31/55 26/55     0 34/55]
[15/11 59/55 49/55 34/55 34/55     0]

Python

>>> from sage.all import *
>>> G.effective_resistance_matrix(nonedgesonly=False)                     # needs sage.modules
[    0 34/55 34/55 49/55 59/55 15/11]
[34/55     0 26/55 31/55  9/11 59/55]
[34/55 26/55     0  5/11 31/55 49/55]
[49/55 31/55  5/11     0 26/55 34/55]
[59/55  9/11 31/55 26/55     0 34/55]
[15/11 59/55 49/55 34/55 34/55     0]

This example illustrates the common neighbors matrix for a fan on 6 vertices counting only non-adjacent vertex pairs

Sage

sage: H = Graph([(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,2),(2,3),(3,4),(4,5)])
sage: H.effective_resistance_matrix()                                       # needs sage.modules
[    0     0     0     0     0     0     0]
[    0     0     0 49/55 56/55   6/5 89/55]
[    0     0     0     0   4/5 56/55 81/55]
[    0 49/55     0     0     0 49/55 16/11]
[    0 56/55   4/5     0     0     0 81/55]
[    0   6/5 56/55 49/55     0     0 89/55]
[    0 89/55 81/55 16/11 81/55 89/55     0]

Python

>>> from sage.all import *
>>> H = Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(0),Integer(4)),(Integer(0),Integer(5)),(Integer(0),Integer(6)),(Integer(1),Integer(2)),(Integer(2),Integer(3)),(Integer(3),Integer(4)),(Integer(4),Integer(5))])
>>> H.effective_resistance_matrix()                                       # needs sage.modules
[    0     0     0     0     0     0     0]
[    0     0     0 49/55 56/55   6/5 89/55]
[    0     0     0     0   4/5 56/55 81/55]
[    0 49/55     0     0     0 49/55 16/11]
[    0 56/55   4/5     0     0     0 81/55]
[    0   6/5 56/55 49/55     0     0 89/55]
[    0 89/55 81/55 16/11 81/55 89/55     0]

A different base ring:

Sage

sage: H.effective_resistance_matrix(base_ring=RDF)[0, 0].parent()           # needs numpy sage.modules
Real Double Field

Python

>>> from sage.all import *
>>> H.effective_resistance_matrix(base_ring=RDF)[Integer(0), Integer(0)].parent()           # needs numpy sage.modules
Real Double Field

See also

least_effective_resistance() – gives node pairs with least effective resistances
effective_resistance() – computes effective resistance for a single node pair
See Wikipedia article Resistance_Distance for more details.

eulerian_orientation(G)[source]¶

Return a DiGraph which is an Eulerian orientation of the graph \(G\).

An Eulerian graph being a graph such that any vertex has an even degree, an Eulerian orientation of a graph is an orientation of its edges such that each vertex \(v\) verifies \(d^+(v)=d^-(v)=d(v)/2\), where \(d^+\) and \(d^-\) respectively represent the out-degree and the in-degree of a vertex.

If the graph is not Eulerian, the orientation verifies for any vertex \(v\) that \(| d^+(v)-d^-(v) | \leq 1\).

INPUT:

G – an undirected graph

ALGORITHM:

This algorithm is a random walk through the edges of the graph, which orients the edges according to the walk. When a vertex is reached which has no non-oriented edge (this vertex must have odd degree), the walk resumes at another vertex of odd degree, if any.

This algorithm has time complexity in \(O(n+m)\) for SparseGraph and \(O(n^2)\) for DenseGraph, where \(m\) is the number of edges in the graph and \(n\) is the number of vertices in the graph.

EXAMPLES:

The CubeGraph with parameter 4, which is regular of even degree, has an Eulerian orientation such that \(d^+ = d^-\):

Sage

sage: g = graphs.CubeGraph(4)
sage: g.degree()
[4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
sage: o = g.eulerian_orientation()
sage: o.in_degree()
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
sage: o.out_degree()
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

Python

>>> from sage.all import *
>>> g = graphs.CubeGraph(Integer(4))
>>> g.degree()
[4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
>>> o = g.eulerian_orientation()
>>> o.in_degree()
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
>>> o.out_degree()
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

Secondly, the Petersen Graph, which is 3 regular has an orientation such that the difference between \(d^+\) and \(d^-\) is at most 1:

Sage

sage: g = graphs.PetersenGraph()
sage: o = g.eulerian_orientation()
sage: o.in_degree()
[2, 2, 2, 2, 2, 1, 1, 1, 1, 1]
sage: o.out_degree()
[1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

Python

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> o = g.eulerian_orientation()
>>> o.in_degree()
[2, 2, 2, 2, 2, 1, 1, 1, 1, 1]
>>> o.out_degree()
[1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

folded_graph(check=False)[source]¶

Return the antipodal fold of this graph.

Given an antipodal graph \(G\) let \(G_d\) be its distance-\(d\) graph. Then the folded graph of \(G\) has a vertex for each maximal clique of \(G_d\) and two cliques are adjacent if there is an edge in \(G\) connecting the two.

See also

sage.graphs.graph.is_antipodal()

INPUT:

check – boolean (default: False); whether to check if the graph is antipodal. If check is True and the graph is not antipodal, then return False.

OUTPUT: this function returns a new graph and self is not touched

Note

The input is expected to be an antipodal graph. You can check that a graph is antipodal using sage.graphs.graph.is_antipodal().

EXAMPLES:

Sage

sage: G = graphs.JohnsonGraph(10, 5)
sage: H = G.folded_graph(); H
Folded Johnson graph with parameters 10,5: Graph on 126 vertices
sage: Gd = G.distance_graph(G.diameter())
sage: all(i == 1 for i in Gd.degree())
True
sage: H.is_distance_regular(True)
([25, 16, None], [None, 1, 4])

Python

>>> from sage.all import *
>>> G = graphs.JohnsonGraph(Integer(10), Integer(5))
>>> H = 

Undirected graphs¶

Graph Format¶

Supported formats¶

Generators¶

Labels¶

Database¶

Visualization¶

Mutability¶

Methods¶