Generic graphs (common to directed/undirected)¶
This module implements the base class for graphs and digraphs, and methods that can be applied on both. Here is what it can do:
Basic Graph operations:
networkx_graph() 
Create a new NetworkX graph from the Sage graph 
igraph_graph() 
Create a new igraph graph from the Sage graph 
to_dictionary() 
Create a dictionary encoding the graph. 
copy() 
Return a copy of the graph. 
export_to_file() 
Export the graph to a file. 
adjacency_matrix() 
Return the adjacency matrix of the (di)graph. 
incidence_matrix() 
Return an incidence matrix of the (di)graph 
distance_matrix() 
Return the distance matrix of the (strongly) connected (di)graph 
weighted_adjacency_matrix() 
Return the weighted adjacency matrix of the graph 
kirchhoff_matrix() 
Return the Kirchhoff matrix (a.k.a. the Laplacian) of the graph. 
has_loops() 
Return whether there are loops in the (di)graph 
allows_loops() 
Return whether loops are permitted in the (di)graph 
allow_loops() 
Change whether loops are permitted in the (di)graph 
loops() 
Return a list of all loops in the (di)graph 
loop_edges() 
Return a list of all loops in the (di)graph 
number_of_loops() 
Return the number of edges that are loops 
loop_vertices() 
Return a list of vertices with loops 
remove_loops() 
Remove loops on vertices in vertices. If vertices is None, removes all loops. 
has_multiple_edges() 
Return whether there are multiple edges in the (di)graph. 
allows_multiple_edges() 
Return whether multiple edges are permitted in the (di)graph. 
allow_multiple_edges() 
Change whether multiple edges are permitted in the (di)graph. 
multiple_edges() 
Return any multiple edges in the (di)graph. 
name() 
Return or sets the graph’s name. 
is_immutable() 
Return whether the graph is immutable. 
weighted() 
Whether the (di)graph is to be considered as a weighted (di)graph. 
antisymmetric() 
Test whether the graph is antisymmetric 
density() 
Return the density 
order() 
Return the number of vertices. 
size() 
Return the number of edges. 
add_vertex() 
Create an isolated vertex. 
add_vertices() 
Add vertices to the (di)graph from an iterable container 
delete_vertex() 
Delete a vertex, removing all incident edges. 
delete_vertices() 
Remove vertices from the (di)graph taken from an iterable container of vertices. 
has_vertex() 
Return True if vertex is one of the vertices of this graph. 
random_vertex() 
Return a random vertex of self. 
random_vertex_iterator() 
Return an iterator over random vertices of self. 
random_edge() 
Return a random edge of self. 
random_edge_iterator() 
Return an iterator over random edges of self. 
vertex_boundary() 
Return a list of all vertices in the external boundary of vertices1, intersected with vertices2. 
set_vertices() 
Associate arbitrary objects with each vertex 
set_vertex() 
Associate an arbitrary object with a vertex. 
get_vertex() 
Retrieve the object associated with a given vertex. 
get_vertices() 
Return a dictionary of the objects associated to each vertex. 
vertex_iterator() 
Return an iterator over the vertices. 
neighbor_iterator() 
Return an iterator over neighbors of vertex. 
vertices() 
Return a list of the vertices. 
neighbors() 
Return a list of neighbors (in and out if directed) of vertex. 
merge_vertices() 
Merge vertices. 
add_edge() 
Add an edge from u and v. 
add_edges() 
Add edges from an iterable container. 
subdivide_edge() 
Subdivide an edge \(k\) times. 
subdivide_edges() 
Subdivide k times edges from an iterable container. 
delete_edge() 
Delete the edge from u to v 
delete_edges() 
Delete edges from an iterable container. 
contract_edge() 
Contract an edge from \(u\) to \(v\). 
contract_edges() 
Contract edges from an iterable container. 
delete_multiedge() 
Delete all edges from u and v. 
set_edge_label() 
Set the edge label of a given edge. 
has_edge() 
Return True if (u, v) is an edge, False otherwise. 
edges() 
Return a list of edges. 
edge_boundary() 
Return a list of edges \((u,v,l)\) with \(u\) in vertices1 
edge_iterator() 
Return an iterator over edges. 
edges_incident() 
Return incident edges to some vertices. 
edge_label() 
Return the label of an edge. 
edge_labels() 
Return a list of edge labels. 
remove_multiple_edges() 
Remove all multiple edges, retaining one edge for each. 
clear() 
Empty the graph of vertices and edges and removes name, associated objects, and position information. 
degree() 
Return the degree (in + out for digraphs) of a vertex or of vertices. 
average_degree() 
Return the average degree of the graph. 
degree_histogram() 
Return a list, whose ith entry is the frequency of degree i. 
degree_iterator() 
Return an iterator over the degrees of the (di)graph. 
degree_sequence() 
Return the degree sequence of this (di)graph. 
random_subgraph() 
Return a random subgraph that contains each vertex with prob. p. 
add_clique() 
Add a clique to the graph with the given vertices. 
add_cycle() 
Add a cycle to the graph with the given vertices. 
add_path() 
Add a cycle to the graph with the given vertices. 
complement() 
Return the complement of the (di)graph. 
line_graph() 
Return the line graph of the (di)graph. 
to_simple() 
Return a simple version of itself (i.e., undirected and loops and multiple edges are removed). 
disjoint_union() 
Return the disjoint union of self and other. 
union() 
Return the union of self and other. 
relabel() 
Relabel the vertices of self 
degree_to_cell() 
Return the number of edges from vertex to an edge in cell. 
subgraph() 
Return the subgraph containing the given vertices and edges. 
is_subgraph() 
Test whether self is a subgraph of other. 
Graph products:
cartesian_product() 
Return the Cartesian product of self and other. 
tensor_product() 
Return the tensor product, also called the categorical product, of self and other. 
lexicographic_product() 
Return the lexicographic product of self and other. 
strong_product() 
Return the strong product of self and other. 
disjunctive_product() 
Return the disjunctive product of self and other. 
Paths and cycles:
eulerian_orientation() 
Return a DiGraph which is an Eulerian orientation of the current graph. 
eulerian_circuit() 
Return a list of edges forming an Eulerian circuit if one exists. 
cycle_basis() 
Return a list of cycles which form a basis of the cycle space of self . 
all_paths() 
Return a list of all paths (also lists) between a pair of vertices in the (di)graph. 
triangles_count() 
Return the number of triangles in the (di)graph. 
Linear algebra:
spectrum() 
Return a list of the eigenvalues of the adjacency matrix. 
eigenvectors() 
Return the right eigenvectors of the adjacency matrix of the graph. 
eigenspaces() 
Return the right eigenspaces of the adjacency matrix of the graph. 
Some metrics:
cluster_triangles() 
Return the number of triangles for nbunch of vertices as a dictionary keyed by vertex. 
clustering_average() 
Return the average clustering coefficient. 
clustering_coeff() 
Return the clustering coefficient for each vertex in nbunch 
cluster_transitivity() 
Return the transitivity (fraction of transitive triangles) of the graph. 
szeged_index() 
Return the Szeged index of the graph. 
Automorphism group:
coarsest_equitable_refinement() 
Return the coarsest partition which is finer than the input partition, and equitable with respect to self. 
automorphism_group() 
Return the largest subgroup of the automorphism group of the (di)graph whose orbit partition is finer than the partition given. 
is_vertex_transitive() 
Return whether the automorphism group of self is transitive within the partition provided 
is_isomorphic() 
Test for isomorphism between self and other. 
canonical_label() 
Return the canonical graph. 
is_cayley() 
Check whether the graph is a Cayley graph. 
Graph properties:
is_eulerian() 
Return True if the graph has a (closed) tour that visits each edge exactly once. 
is_planar() 
Test whether the graph is planar. 
is_circular_planar() 
Test whether the graph is circular planar (outerplanar) 
is_regular() 
Return True if this graph is (\(k\))regular. 
is_chordal() 
Test whether the given graph is chordal. 
is_bipartite() 
Test whether the given graph is bipartite. 
is_circulant() 
Test whether the graph is a circulant graph. 
is_interval() 
Check whether the graph is an interval graph. 
is_gallai_tree() 
Return whether the current graph is a Gallai tree. 
is_clique() 
Test whether a set of vertices is a clique 
is_cycle() 
Test whether self is a (directed) cycle graph. 
is_independent_set() 
Test whether a set of vertices is an independent set 
is_transitively_reduced() 
Test whether the digraph is transitively reduced. 
is_equitable() 
Check whether the given partition is equitable with respect to self. 
is_self_complementary() 
Check whether the graph is selfcomplementary. 
Traversals:
breadth_first_search() 
Return an iterator over the vertices in a breadthfirst ordering. 
depth_first_search() 
Return an iterator over the vertices in a depthfirst ordering. 
lex_BFS() 
Perform a Lex BFS on the graph. 
Distances:
centrality_betweenness() 
Return the betweenness centrality 
centrality_closeness() 
Returns the closeness centrality (1/average distance to all vertices) 
distance() 
Return the (directed) distance from u to v in the (di)graph 
distance_all_pairs() 
Return the distances between all pairs of vertices. 
distances_distribution() 
Return the distances distribution of the (di)graph in a dictionary. 
eccentricity() 
Return the eccentricity of vertex (or vertices) v. 
radius() 
Return the radius of the (di)graph. 
center() 
Return the set of vertices in the center of the graph 
diameter() 
Return the largest distance between any two vertices. 
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. 
girth() 
Compute the girth of the graph. 
periphery() 
Return the set of vertices in the periphery 
shortest_path() 
Return a list of vertices representing some shortest path from \(u\) to \(v\) 
shortest_path_length() 
Return the minimal length of paths from u to v 
shortest_paths() 
Return a dictionary associating to each vertex v a shortest path from u to v, if it exists. 
shortest_path_lengths() 
Return a dictionary of shortest path lengths keyed by targets that are connected by a path from u. 
shortest_path_all_pairs() 
Compute a shortest path between each pair of vertices. 
wiener_index() 
Return the Wiener index of the graph. 
average_distance() 
Return the average distance between vertices of the graph. 
Flows, connectivity, trees:
is_connected() 
Test whether the (di)graph is connected. 
connected_components() 
Return the list of connected components 
connected_components_number() 
Return the number of connected components. 
connected_components_subgraphs() 
Return a list of connected components as graph objects. 
connected_component_containing_vertex() 
Return a list of the vertices connected to vertex. 
connected_components_sizes() 
Return the sizes of the connected components as a list. 
blocks_and_cut_vertices() 
Compute the blocks and cut vertices of the graph. 
blocks_and_cuts_tree() 
Compute the blocksandcuts tree of the graph. 
is_cut_edge() 
Return True if the input edge is a cutedge or a bridge. 
is_cut_vertex() 
Return True if the input vertex is a cutvertex. 
edge_cut() 
Return a minimum edge cut between vertices \(s\) and \(t\) 
vertex_cut() 
Return a minimum vertex cut between nonadjacent vertices \(s\) and \(t\) 
flow() 
Return a maximum flow in the graph from x to y 
nowhere_zero_flow() 
Return a \(k\)nowhere zero flow of the (di)graph. 
edge_disjoint_paths() 
Return a list of edgedisjoint paths between two vertices 
vertex_disjoint_paths() 
Return a list of vertexdisjoint paths between two vertices 
edge_connectivity() 
Return the edge connectivity of the graph. 
vertex_connectivity() 
Return the vertex connectivity of the graph. 
transitive_closure() 
Compute the transitive closure of a graph and returns it. 
transitive_reduction() 
Return a transitive reduction of a graph. 
min_spanning_tree() 
Return the edges of a minimum spanning tree. 
spanning_trees_count() 
Return the number of spanning trees in a graph. 
dominator_tree() 
Returns a dominator tree of the graph. 
connected_subgraph_iterator() 
Iterator over the induced connected subgraphs of order at most \(k\) 
Plot/embeddingrelated methods:
set_embedding() 
Set a combinatorial embedding dictionary to _embedding attribute. 
get_embedding() 
Return the attribute _embedding if it exists. 
faces() 
Return the faces of an embedded graph. 
planar_dual() 
Return the planar dual of an embedded graph. 
get_pos() 
Return the position dictionary 
set_pos() 
Set the position dictionary. 
set_planar_positions() 
Compute a planar layout for self using Schnyder’s algorithm 
layout_planar() 
Use Schnyder’s algorithm to compute a planar layout for self. 
is_drawn_free_of_edge_crossings() 
Test whether the position dictionary gives a planar embedding. 
latex_options() 
Return an instance of GraphLatex for the graph. 
set_latex_options() 
Set multiple options for rendering a graph with LaTeX. 
layout() 
Return a layout for the vertices of this graph. 
layout_spring() 
Compute a spring layout for this graph 
layout_ranked() 
Compute a ranked layout for this graph 
layout_extend_randomly() 
Extend randomly a partial layout 
layout_circular() 
Compute a circular layout for this graph 
layout_tree() 
Compute an ordered tree layout for this graph, which should be a tree (no nonoriented cycles). 
layout_graphviz() 
Call graphviz to compute a layout of the vertices of this graph. 
_circle_embedding() 
Sets some vertices on a circle in the embedding of this graph. 
_line_embedding() 
Sets some vertices on a line in the embedding of this graph. 
graphplot() 
Return a GraphPlot object. 
plot() 
Return a graphics object representing the (di)graph. 
show() 
Show the (di)graph. 
plot3d() 
Plot the graph in three dimensions. 
show3d() 
Plot the graph using Tachyon, and shows the resulting plot. 
graphviz_string() 
Return a representation in the dot language. 
graphviz_to_file_named() 
Write a representation in the dot in a file. 
Algorithmically hard stuff:
steiner_tree() 
Return a tree of minimum weight connecting the given set of vertices. 
edge_disjoint_spanning_trees() 
Return the desired number of edgedisjoint spanning trees/arborescences. 
feedback_vertex_set() 
Compute the minimum feedback vertex set of a (di)graph. 
multiway_cut() 
Return a minimum edge multiway cut 
max_cut() 
Return a maximum edge cut of the graph. 
longest_path() 
Return a longest path of self . 
traveling_salesman_problem() 
Solve the traveling salesman problem (TSP) 
is_hamiltonian() 
Test whether the current graph is Hamiltonian. 
hamiltonian_cycle() 
Return a Hamiltonian cycle/circuit of the current graph/digraph 
hamiltonian_path() 
Return a Hamiltonian path of the current graph/digraph 
multicommodity_flow() 
Solve a multicommodity flow problem. 
disjoint_routed_paths() 
Return a set of disjoint routed paths. 
dominating_set() 
Return a minimum dominating set of the graph 
subgraph_search() 
Return a copy of G in self . 
subgraph_search_count() 
Return the number of labelled occurrences of G in self . 
subgraph_search_iterator() 
Return an iterator over the labelled copies of G in self . 
characteristic_polynomial() 
Return the characteristic polynomial of the adjacency matrix of the (di)graph. 
genus() 
Return the minimal genus of the graph. 
crossing_number() 
Return the minimum number of edge crossings needed to draw the graph. 
Methods¶

class
sage.graphs.generic_graph.
GenericGraph
¶ Bases:
sage.graphs.generic_graph_pyx.GenericGraph_pyx
Base class for graphs and digraphs.

__eq__
(other)¶ Compare self and other for equality.
Do not call this method directly. That is, for
G.__eq__(H)
writeG == H
. Two graphs are considered equal if the following hold:
 they are either both directed, or both undirected;
 they have the same settings for loops, multiedges, and weightedness;
 they have the same set of vertices;
 they have the same (multi)set of arrows/edges, where labels
of arrows/edges are taken into account if and only if
the graphs are considered weighted. See
weighted()
.
Note that this is not an isomorphism test.
EXAMPLES:
sage: G = graphs.EmptyGraph() sage: H = Graph() sage: G == H True sage: G.to_directed() == H.to_directed() True sage: G = graphs.RandomGNP(8,.9999) sage: H = graphs.CompleteGraph(8) sage: G == H # most often true True sage: G = Graph( {0:[1,2,3,4,5,6,7]} ) sage: H = Graph( {1:[0], 2:[0], 3:[0], 4:[0], 5:[0], 6:[0], 7:[0]} ) sage: G == H True sage: G.allow_loops(True) sage: G == H False sage: G = graphs.RandomGNP(9,.3).to_directed() sage: H = graphs.RandomGNP(9,.3).to_directed() sage: G == H # most often false False sage: G = Graph(multiedges=True, sparse=True) sage: G.add_edge(0,1) sage: H = copy(G) sage: H.add_edge(0,1) sage: G == H False
Note that graphs must be considered weighted, or Sage will not pay attention to edge label data in equality testing:
sage: foo = Graph(sparse=True) sage: foo.add_edges([(0, 1, 1), (0, 2, 2)]) sage: bar = Graph(sparse=True) sage: bar.add_edges([(0, 1, 2), (0, 2, 1)]) sage: foo == bar True sage: foo.weighted(True) sage: foo == bar False sage: bar.weighted(True) sage: foo == bar False

add_clique
(vertices, loops=False)¶ Add a clique to the graph with the given vertices.
If the vertices are already present, only the edges are added.
INPUT:
vertices
– an iterable with vertices for the clique to be added, e.g. a list, set, graph, etc.loops
– (boolean, default:False
) whether to add edges from every given vertex to itself. This is allowed only if the (di)graph allows loops.
EXAMPLES:
sage: G = Graph() sage: G.add_clique(range(4)) sage: G.is_isomorphic(graphs.CompleteGraph(4)) True sage: D = DiGraph() sage: D.add_clique(range(4)) sage: D.is_isomorphic(digraphs.Complete(4)) True sage: D = DiGraph(loops=True) sage: D.add_clique(range(4), loops=True) sage: D.is_isomorphic(digraphs.Complete(4, loops=True)) True sage: D = DiGraph(loops=False) sage: D.add_clique(range(4), loops=True) Traceback (most recent call last): ... ValueError: cannot add edge from 0 to 0 in graph without loops
If the list of vertices contains repeated elements, a loop will be added at that vertex, even if
loops=False
:sage: G = Graph(loops=True) sage: G.add_clique([1,1]) sage: G.edges() [(1, 1, None)]
This is equivalent to:
sage: G = Graph(loops=True) sage: G.add_clique([1], loops=True) sage: G.edges() [(1, 1, None)]

add_cycle
(vertices)¶ Add a cycle to the graph with the given vertices.
If the vertices are already present, only the edges are added.
For digraphs, adds the directed cycle, whose orientation is determined by the list. Adds edges (vertices[u], vertices[u+1]) and (vertices[1], vertices[0]).
INPUT:
vertices
– a list of indices for the vertices of the cycle to be added.
EXAMPLES:
sage: G = Graph() sage: G.add_vertices(range(10)); G Graph on 10 vertices sage: show(G) sage: G.add_cycle(list(range(10,20))) sage: show(G) sage: G.add_cycle(list(range(10))) sage: show(G)
sage: D = DiGraph() sage: D.add_cycle(list(range(4))) sage: D.edges() [(0, 1, None), (1, 2, None), (2, 3, None), (3, 0, None)]

add_edge
(u, v=None, label=None)¶ Adds an edge from u and v.
INPUT: The following forms are all accepted:
 G.add_edge( 1, 2 )
 G.add_edge( (1, 2) )
 G.add_edges( [ (1, 2) ])
 G.add_edge( 1, 2, ‘label’ )
 G.add_edge( (1, 2, ‘label’) )
 G.add_edges( [ (1, 2, ‘label’) ] )
WARNING: The following intuitive input results in nonintuitive output:
sage: G = Graph() sage: G.add_edge((1,2), 'label') sage: G.networkx_graph().adj # random output order {'label': {(1, 2): None}, (1, 2): {'label': None}}
Use one of these instead:
sage: G = Graph() sage: G.add_edge((1,2), label="label") sage: G.networkx_graph().adj # random output order {1: {2: 'label'}, 2: {1: 'label'}}
sage: G = Graph() sage: G.add_edge(1,2,'label') sage: G.networkx_graph().adj # random output order {1: {2: 'label'}, 2: {1: 'label'}}
The following syntax is supported, but note that you must use the
label
keyword:sage: G = Graph() sage: G.add_edge((1,2), label='label') sage: G.edges() [(1, 2, 'label')] sage: G = Graph() sage: G.add_edge((1,2), 'label') sage: G.edges() [('label', (1, 2), None)]
Vertex name cannot be None, so:
sage: G = Graph() sage: G.add_edge(None, 4) sage: G.vertices() [0, 4]

add_edges
(edges, loops=True)¶ Add edges from an iterable container.
INPUT:
edges
– an iterable of edges, given either as(u, v)
or(u, v, label)
.loops
– (default:True
) ifFalse
, remove all loops(v, v)
from the input iterator. IfNone
, remove loops unless the graph allows loops.
EXAMPLES:
sage: G = graphs.DodecahedralGraph() sage: H = Graph() sage: H.add_edges( G.edge_iterator() ); H Graph on 20 vertices sage: G = graphs.DodecahedralGraph().to_directed() sage: H = DiGraph() sage: H.add_edges( G.edge_iterator() ); H Digraph on 20 vertices sage: H.add_edges(iter([])) sage: H = Graph() sage: H.add_edges([(0, 1), (0, 2, "label")]) sage: H.edges() [(0, 1, None), (0, 2, 'label')]
We demonstrate the
loops
argument:sage: H = Graph() sage: H.add_edges([(0,0)], loops=False); H.edges() [] sage: H.add_edges([(0,0)], loops=None); H.edges() [] sage: H.add_edges([(0,0)]); H.edges() Traceback (most recent call last): ... ValueError: cannot add edge from 0 to 0 in graph without loops sage: H = Graph(loops=True) sage: H.add_edges([(0,0)], loops=False); H.edges() [] sage: H.add_edges([(0,0)], loops=None); H.edges() [(0, 0, None)] sage: H.add_edges([(0,0)]); H.edges() [(0, 0, None)]

add_path
(vertices)¶ Add a path to the graph with the given vertices.
If the vertices are already present, only the edges are added.
For digraphs, adds the directed path vertices[0], …, vertices[1].
INPUT:
vertices
 a list of indices for the vertices of the path to be added.
EXAMPLES:
sage: G = Graph() sage: G.add_vertices(range(10)); G Graph on 10 vertices sage: show(G) sage: G.add_path(list(range(10,20))) sage: show(G) sage: G.add_path(list(range(10))) sage: show(G)
sage: D = DiGraph() sage: D.add_path(list(range(4))) sage: D.edges() [(0, 1, None), (1, 2, None), (2, 3, None)]

add_vertex
(name=None)¶ Creates an isolated vertex. If the vertex already exists, then nothing is done.
INPUT:
name
 Name of the new vertex. If no name is specified, then the vertex will be represented by the least integer not already representing a vertex. Name must be an immutable object, and cannot be None.
As it is implemented now, if a graph \(G\) has a large number of vertices with numeric labels, then G.add_vertex() could potentially be slow, if name is None.
OUTPUT:
If
name``=``None
, the new vertex name is returned.None
otherwise.EXAMPLES:
sage: G = Graph(); G.add_vertex(); G 0 Graph on 1 vertex
sage: D = DiGraph(); D.add_vertex(); D 0 Digraph on 1 vertex

add_vertices
(vertices)¶ Add vertices to the (di)graph from an iterable container of vertices. Vertices that already exist in the graph will not be added again.
INPUT:
vertices
: iterator of vertex labels. A new label is created, used and returned in the output list for allNone
values invertices
.
OUTPUT:
Generated names of new vertices if there is at least one
None
value present invertices
.None
otherwise.EXAMPLES:
sage: d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7,8], 6: [8,9], 7: [9]} sage: G = Graph(d) sage: G.add_vertices([10,11,12]) sage: G.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] sage: G.add_vertices(graphs.CycleGraph(25).vertices()) sage: G.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
sage: G = Graph() sage: G.add_vertices([1,2,3]) sage: G.add_vertices([4,None,None,5]) [0, 6]

adjacency_matrix
(sparse=None, vertices=None)¶ Returns the adjacency matrix of the (di)graph.
The matrix returned is over the integers. If a different ring is desired, use either the
sage.matrix.matrix0.Matrix.change_ring()
method or thematrix()
function.INPUT:
sparse
 whether to represent with a sparse matrixvertices
(list) – the ordering of the vertices defining how they should appear in the matrix. By default, the ordering given byGenericGraph.vertices()
is used.
EXAMPLES:
sage: G = graphs.CubeGraph(4) sage: G.adjacency_matrix() [0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0] [1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0] [1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0] [0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0] [1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0] [0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0] [0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0] [0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1] [1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0] [0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0] [0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0] [0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1] [0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0] [0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1] [0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1] [0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]
sage: matrix(GF(2),G) # matrix over GF(2) [0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0] [1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0] [1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0] [0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0] [1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0] [0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0] [0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0] [0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1] [1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0] [0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0] [0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0] [0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1] [0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0] [0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1] [0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1] [0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.adjacency_matrix() [0 1 1 1 0 0] [1 0 1 0 0 0] [0 0 0 1 0 0] [0 0 0 0 1 0] [1 0 0 0 0 1] [0 1 0 0 0 0]
A different ordering of the vertices:
sage: graphs.PathGraph(5).adjacency_matrix(vertices=[2,4,1,3,0]) [0 0 1 1 0] [0 0 0 1 0] [1 0 0 0 1] [1 1 0 0 0] [0 0 1 0 0]

all_paths
(start, end)¶ Return the list of all paths between a pair of vertices.
If
start
is the same vertex asend
, then[[start]]
is returned – a list containing the 1vertex, 0edge path “start
”.INPUT:
start
, a vertex of a graph – where to startend
, a vertex of a graph – where to end
EXAMPLES:
sage: eg1 = Graph({0:[1,2], 1:[4], 2:[3,4], 4:[5], 5:[6]}) sage: eg1.all_paths(0,6) [[0, 1, 4, 5, 6], [0, 2, 4, 5, 6]] sage: eg2 = graphs.PetersenGraph() sage: sorted(eg2.all_paths(1,4)) [[1, 0, 4], [1, 0, 5, 7, 2, 3, 4], [1, 0, 5, 7, 2, 3, 8, 6, 9, 4], [1, 0, 5, 7, 9, 4], [1, 0, 5, 7, 9, 6, 8, 3, 4], [1, 0, 5, 8, 3, 2, 7, 9, 4], [1, 0, 5, 8, 3, 4], [1, 0, 5, 8, 6, 9, 4], [1, 0, 5, 8, 6, 9, 7, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 8, 5, 0, 4], [1, 2, 3, 8, 5, 7, 9, 4], [1, 2, 3, 8, 6, 9, 4], [1, 2, 3, 8, 6, 9, 7, 5, 0, 4], [1, 2, 7, 5, 0, 4], [1, 2, 7, 5, 8, 3, 4], [1, 2, 7, 5, 8, 6, 9, 4], [1, 2, 7, 9, 4], [1, 2, 7, 9, 6, 8, 3, 4], [1, 2, 7, 9, 6, 8, 5, 0, 4], [1, 6, 8, 3, 2, 7, 5, 0, 4], [1, 6, 8, 3, 2, 7, 9, 4], [1, 6, 8, 3, 4], [1, 6, 8, 5, 0, 4], [1, 6, 8, 5, 7, 2, 3, 4], [1, 6, 8, 5, 7, 9, 4], [1, 6, 9, 4], [1, 6, 9, 7, 2, 3, 4], [1, 6, 9, 7, 2, 3, 8, 5, 0, 4], [1, 6, 9, 7, 5, 0, 4], [1, 6, 9, 7, 5, 8, 3, 4]] sage: dg = DiGraph({0:[1,3], 1:[3], 2:[0,3]}) sage: sorted(dg.all_paths(0,3)) [[0, 1, 3], [0, 3]] sage: ug = dg.to_undirected() sage: sorted(ug.all_paths(0,3)) [[0, 1, 3], [0, 2, 3], [0, 3]]

allow_loops
(new, check=True)¶ Change whether loops are permitted in the (di)graph
INPUT:
new
 boolean.
EXAMPLES:
sage: G = Graph(loops=True); G Looped graph on 0 vertices sage: G.has_loops() False sage: G.allows_loops() True sage: G.add_edge((0,0)) sage: G.has_loops() True sage: G.loops() [(0, 0, None)] sage: G.allow_loops(False); G Graph on 1 vertex sage: G.has_loops() False sage: G.edges() [] sage: D = DiGraph(loops=True); D Looped digraph on 0 vertices sage: D.has_loops() False sage: D.allows_loops() True sage: D.add_edge((0,0)) sage: D.has_loops() True sage: D.loops() [(0, 0, None)] sage: D.allow_loops(False); D Digraph on 1 vertex sage: D.has_loops() False sage: D.edges() []

allow_multiple_edges
(new, check=True, keep_label='any')¶ Changes whether multiple edges are permitted in the (di)graph.
INPUT:
new
(boolean): ifTrue
, the new graph will allow multiple edges.check
(boolean): ifTrue
andnew
isFalse
, we remove all multiple edges from the graph.keep_label
('any','min','max'
): used only ifnew
isFalse
andcheck
isTrue
. If there are multiple edges with different labels, this variable defines which label should be kept: any label ('any'
), the smallest label ('min'
), or the largest ('max'
).
EXAMPLES:
The standard behavior with undirected graphs:
sage: G = Graph(multiedges=True,sparse=True); G Multigraph on 0 vertices sage: G.has_multiple_edges() False sage: G.allows_multiple_edges() True sage: G.add_edges([(0,1,1), (0,1,2), (0,1,3)]) sage: G.has_multiple_edges() True sage: G.multiple_edges(sort=True) [(0, 1, 1), (0, 1, 2), (0, 1, 3)] sage: G.allow_multiple_edges(False); G Graph on 2 vertices sage: G.has_multiple_edges() False sage: G.edges() [(0, 1, 1)]
If we ask for the minimum label:
sage: G = Graph([(0, 1, 1), (0, 1, 2), (0, 1, 3)], multiedges=True,sparse=True) sage: G.allow_multiple_edges(False, keep_label='min') sage: G.edges() [(0, 1, 1)]
If we ask for the maximum label:
sage: G = Graph([(0, 1, 1), (0, 1, 2), (0, 1, 3)], multiedges=True,sparse=True) sage: G.allow_multiple_edges(False, keep_label='max') sage: G.edges() [(0, 1, 3)]
The standard behavior with digraphs:
sage: D = DiGraph(multiedges=True,sparse=True); D Multidigraph on 0 vertices sage: D.has_multiple_edges() False sage: D.allows_multiple_edges() True sage: D.add_edges([(0,1)]*3) sage: D.has_multiple_edges() True sage: D.multiple_edges() [(0, 1, None), (0, 1, None), (0, 1, None)] sage: D.allow_multiple_edges(False); D Digraph on 2 vertices sage: D.has_multiple_edges() False sage: D.edges() [(0, 1, None)]

allows_loops
()¶ Return whether loops are permitted in the (di)graph
EXAMPLES:
sage: G = Graph(loops=True); G Looped graph on 0 vertices sage: G.has_loops() False sage: G.allows_loops() True sage: G.add_edge((0,0)) sage: G.has_loops() True sage: G.loops() [(0, 0, None)] sage: G.allow_loops(False); G Graph on 1 vertex sage: G.has_loops() False sage: G.edges() [] sage: D = DiGraph(loops=True); D Looped digraph on 0 vertices sage: D.has_loops() False sage: D.allows_loops() True sage: D.add_edge((0,0)) sage: D.has_loops() True sage: D.loops() [(0, 0, None)] sage: D.allow_loops(False); D Digraph on 1 vertex sage: D.has_loops() False sage: D.edges() []

allows_multiple_edges
()¶ Returns whether multiple edges are permitted in the (di)graph.
EXAMPLES:
sage: G = Graph(multiedges=True,sparse=True); G Multigraph on 0 vertices sage: G.has_multiple_edges() False sage: G.allows_multiple_edges() True sage: G.add_edges([(0,1)]*3) sage: G.has_multiple_edges() True sage: G.multiple_edges() [(0, 1, None), (0, 1, None), (0, 1, None)] sage: G.allow_multiple_edges(False); G Graph on 2 vertices sage: G.has_multiple_edges() False sage: G.edges() [(0, 1, None)] sage: D = DiGraph(multiedges=True,sparse=True); D Multidigraph on 0 vertices sage: D.has_multiple_edges() False sage: D.allows_multiple_edges() True sage: D.add_edges([(0,1)]*3) sage: D.has_multiple_edges() True sage: D.multiple_edges() [(0, 1, None), (0, 1, None), (0, 1, None)] sage: D.allow_multiple_edges(False); D Digraph on 2 vertices sage: D.has_multiple_edges() False sage: D.edges() [(0, 1, None)]

am
(sparse=None, vertices=None)¶ Returns the adjacency matrix of the (di)graph.
The matrix returned is over the integers. If a different ring is desired, use either the
sage.matrix.matrix0.Matrix.change_ring()
method or thematrix()
function.INPUT:
sparse
 whether to represent with a sparse matrixvertices
(list) – the ordering of the vertices defining how they should appear in the matrix. By default, the ordering given byGenericGraph.vertices()
is used.
EXAMPLES:
sage: G = graphs.CubeGraph(4) sage: G.adjacency_matrix() [0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0] [1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0] [1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0] [0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0] [1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0] [0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0] [0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0] [0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1] [1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0] [0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0] [0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0] [0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1] [0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0] [0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1] [0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1] [0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]
sage: matrix(GF(2),G) # matrix over GF(2) [0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0] [1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0] [1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0] [0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0] [1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0] [0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0] [0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0] [0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1] [1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0] [0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0] [0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0] [0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1] [0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0] [0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1] [0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1] [0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.adjacency_matrix() [0 1 1 1 0 0] [1 0 1 0 0 0] [0 0 0 1 0 0] [0 0 0 0 1 0] [1 0 0 0 0 1] [0 1 0 0 0 0]
A different ordering of the vertices:
sage: graphs.PathGraph(5).adjacency_matrix(vertices=[2,4,1,3,0]) [0 0 1 1 0] [0 0 0 1 0] [1 0 0 0 1] [1 1 0 0 0] [0 0 1 0 0]

antisymmetric
()¶ Tests whether the graph is antisymmetric.
A graph represents an antisymmetric relation if there being a path from a vertex x to a vertex y implies that there is not a path from y to x unless x=y.
A directed acyclic graph is antisymmetric. An undirected graph is never antisymmetric unless it is just a union of isolated vertices.
sage: graphs.RandomGNP(20,0.5).antisymmetric() False sage: digraphs.RandomDirectedGNR(20,0.5).antisymmetric() True

automorphism_group
(partition=None, verbosity=0, edge_labels=False, order=False, return_group=True, orbits=False, algorithm=None)¶ Return the automorphism group of the graph.
With
partition
this can also return the largest subgroup of the automorphism group of the (di)graph whose orbit partition is finer than the partition given.INPUT:
partition
 default is the unit partition, otherwise computes the subgroup of the full automorphism group respecting the partition.edge_labels
 default False, otherwise allows only permutations respecting edge labels.order
 (default False) if True, compute the order of the automorphism groupreturn_group
 default Trueorbits
 returns the orbits of the group acting on the vertices of the graphalgorithm
 Ifalgorithm = "bliss"
the automorphism group is computed using the optional package bliss (http://www.tcs.tkk.fi/Software/bliss/index.html). Setting it to “sage” uses Sage’s implementation. If set toNone
(default), bliss is used when available.
OUTPUT: The order of the output is group, order, orbits. However, there are options to turn each of these on or off.
EXAMPLES:
Graphs:
sage: graphs_query = GraphQuery(display_cols=['graph6'],num_vertices=4) sage: L = graphs_query.get_graphs_list() sage: graphs_list.show_graphs(L) sage: for g in L: ....: G = g.automorphism_group() ....: G.order(), G.gens() (24, [(2,3), (1,2), (0,1)]) (4, [(2,3), (0,1)]) (2, [(1,2)]) (6, [(1,2), (0,1)]) (6, [(2,3), (1,2)]) (8, [(1,2), (0,1)(2,3)]) (2, [(0,1)(2,3)]) (2, [(1,2)]) (8, [(2,3), (0,1), (0,2)(1,3)]) (4, [(2,3), (0,1)]) (24, [(2,3), (1,2), (0,1)]) sage: C = graphs.CubeGraph(4) sage: G = C.automorphism_group() sage: M = G.character_table() # random order of rows, thus abs() below sage: QQ(M.determinant()).abs() 712483534798848 sage: G.order() 384
sage: D = graphs.DodecahedralGraph() sage: G = D.automorphism_group() sage: A5 = AlternatingGroup(5) sage: Z2 = CyclicPermutationGroup(2) sage: H = A5.direct_product(Z2)[0] #see documentation for direct_product to explain the [0] sage: G.is_isomorphic(H) True
Multigraphs:
sage: G = Graph(multiedges=True,sparse=True) sage: G.add_edge(('a', 'b')) sage: G.add_edge(('a', 'b')) sage: G.add_edge(('a', 'b')) sage: G.automorphism_group() Permutation Group with generators [('a','b')]
Digraphs:
sage: D = DiGraph( { 0:[1], 1:[2], 2:[3], 3:[4], 4:[0] } ) sage: D.automorphism_group() Permutation Group with generators [(0,1,2,3,4)]
Edge labeled graphs:
sage: G = Graph(sparse=True) sage: G.add_edges( [(0,1,'a'),(1,2,'b'),(2,3,'c'),(3,4,'b'),(4,0,'a')] ) sage: G.automorphism_group(edge_labels=True) Permutation Group with generators [(1,4)(2,3)] sage: G.automorphism_group(edge_labels=True, algorithm="bliss") # optional  bliss Permutation Group with generators [(1,4)(2,3)] sage: G.automorphism_group(edge_labels=True, algorithm="sage") Permutation Group with generators [(1,4)(2,3)]
sage: G = Graph({0 : {1 : 7}}) sage: G.automorphism_group(edge_labels=True) Permutation Group with generators [(0,1)] sage: foo = Graph(sparse=True) sage: bar = Graph(implementation='c_graph',sparse=True) sage: foo.add_edges([(0,1,1),(1,2,2), (2,3,3)]) sage: bar.add_edges([(0,1,1),(1,2,2), (2,3,3)]) sage: foo.automorphism_group(edge_labels=True) Permutation Group with generators [()] sage: foo.automorphism_group() Permutation Group with generators [(0,3)(1,2)] sage: bar.automorphism_group(edge_labels=True) Permutation Group with generators [()]
You can also ask for just the order of the group:
sage: G = graphs.PetersenGraph() sage: G.automorphism_group(return_group=False, order=True) 120
Or, just the orbits (note that each graph here is vertex transitive)
sage: G = graphs.PetersenGraph() sage: G.automorphism_group(return_group=False, orbits=True,algorithm='sage') [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]] sage: G.automorphism_group(partition=[[0],list(range(1,10))], return_group=False, orbits=True,algorithm='sage') [[0], [2, 3, 6, 7, 8, 9], [1, 4, 5]] sage: C = graphs.CubeGraph(3) sage: C.automorphism_group(orbits=True, return_group=False,algorithm='sage') [['000', '001', '010', '011', '100', '101', '110', '111']]
One can also use the faster algorithm for computing the automorphism group of the graph  bliss:
sage: G = graphs.HallJankoGraph() # optional  bliss sage: A1 = G.automorphism_group() # optional  bliss sage: A2 = G.automorphism_group(algorithm='bliss') # optional  bliss sage: A1.is_isomorphic(A2) # optional  bliss True

average_degree
()¶ Returns the average degree of the graph.
The average degree of a graph \(G=(V,E)\) is equal to
\frac {2E}{V}
.EXAMPLES:
The average degree of a regular graph is equal to the degree of any vertex:
sage: g = graphs.CompleteGraph(5) sage: g.average_degree() == 4 True
The average degree of a tree is always strictly less than \(2\):
sage: g = graphs.RandomGNP(20,.5) sage: tree = Graph() sage: tree.add_edges(g.min_spanning_tree()) sage: tree.average_degree() < 2 True
For any graph, it is equal to
\frac {2E}{V}
:sage: g = graphs.RandomGNP(50,.8) sage: g.average_degree() == 2*g.size()/g.order() True

average_distance
(by_weight=False, algorithm=None, weight_function=None)¶ Returns the average distance between vertices of the graph.
Formally, for a graph \(G\) this value is equal to \(\frac 1 {n(n1)} \sum_{u,v\in G} d(u,v)\) where \(d(u,v)\) denotes the distance between vertices \(u\) and \(v\) and \(n\) is the number of vertices in \(G\).
For more information on the input variables and more examples, we refer to
wiener_index()
andshortest_path_all_pairs()
, which have very similar input variables.INPUT:
by_weight
(boolean)  ifTrue
, the edges in the graph are weighted; ifFalse
, all edges have weight 1.algorithm
(string)  one of the following algorithms:'BFS'
 the computation is done through a BFS centered on each vertex successively. Works only ifby_weight==False
.'FloydWarshallCython'
 the Cython implementation of the FloydWarshall algorithm. Works only ifby_weight==False
.'FloydWarshallPython'
 the Python implementation of the FloydWarshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed).'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).None
(default): Sage chooses the best algorithm:'BFS'
for unweighted graphs,'Dijkstra_Boost'
if all weights are positive,'Johnson_Boost'
, otherwise.
weight_function
(function)  a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
as a weight.check_weight
(boolean)  ifTrue
, we check that the weight_function outputs a number for each edge.
EXAMPLES:
From [GYLL93]:
sage: g=graphs.PathGraph(10) sage: w=lambda x: (x*(x*x 1)/6)/(x*(x1)/2) sage: g.average_distance()==w(10) True
REFERENCE:
[GYLL93] I. Gutman, Y.N. Yeh, S.L. Lee, and Y.L. Luo. Some recent results in the theory of the Wiener number. Indian Journal of Chemistry, 32A:651–661, 1993.

blocks_and_cut_vertices
(G, algorithm='Tarjan_Boost')¶ Compute the blocks and cut vertices of the graph.
In the case of a digraph, this computation is done on the underlying graph.
A cut vertex is one whose deletion increases the number of connected components. A block is a maximal induced subgraph which itself has no cut vertices. Two distinct blocks cannot overlap in more than a single cut vertex.
INPUT:
algorithm
– The algorithm to use in computing the blocksand cut vertices of
G
. The following algorithms are supported:
"Tarjan_Boost"
(default) – Tarjan’s algorithm (Boost implementation)."Tarjan_Sage"
– Tarjan’s algorithm (Sage implementation).
OUTPUT:
(B, C)
, whereB
is a list of blocks  each is a list of vertices and the blocks are the corresponding induced subgraphs  andC
is a list of cut vertices.ALGORITHM:
We implement the algorithm proposed by Tarjan in [Tarjan72]. The original version is recursive. We emulate the recursion using a stack.See also
EXAMPLES:
We construct a trivial example of a graph with one cut vertex:
sage: from sage.graphs.connectivity import blocks_and_cut_vertices sage: rings = graphs.CycleGraph(10) sage: rings.merge_vertices([0, 5]) sage: blocks_and_cut_vertices(rings) ([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0]) sage: rings.blocks_and_cut_vertices() ([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0]) sage: blocks_and_cut_vertices(rings, algorithm="Tarjan_Sage") ([[0, 1, 2, 3, 4], [0, 6, 7, 8, 9]], [0])
The Petersen graph is biconnected, hence has no cut vertices:
sage: blocks_and_cut_vertices(graphs.PetersenGraph()) ([[0, 1, 4, 5, 2, 6, 3, 7, 8, 9]], [])
Decomposing paths to pairs:
sage: g = graphs.PathGraph(4) + graphs.PathGraph(5) sage: blocks_and_cut_vertices(g) ([[2, 3], [1, 2], [0, 1], [7, 8], [6, 7], [5, 6], [4, 5]], [1, 2, 5, 6, 7])
A disconnected graph:
sage: g = Graph({1:{2:28, 3:10}, 2:{1:10, 3:16}, 4:{}, 5:{6:3, 7:10, 8:4}}) sage: blocks_and_cut_vertices(g) ([[1, 2, 3], [5, 6], [5, 7], [5, 8], [4]], [5])
A directed graph with Boost’s algorithm (trac ticket #25994):
sage: rings = graphs.CycleGraph(10) sage: rings.merge_vertices([0, 5]) sage: rings = rings.to_directed() sage: blocks_and_cut_vertices(rings, algorithm="Tarjan_Boost") ([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0])

blocks_and_cuts_tree
(G)¶ Returns the blocksandcuts tree of
self
.This new graph has two different kinds of vertices, some representing the blocks (type B) and some other the cut vertices of the graph
self
(type C).There is an edge between a vertex \(u\) of type B and a vertex \(v\) of type C if the cutvertex corresponding to \(v\) is in the block corresponding to \(u\).
The resulting graph is a tree, with the additional characteristic property that the distance between two leaves is even. When
self
is not connected, the resulting graph is a forest.When
self
is biconnected, the tree is reduced to a single node of type \(B\).We referred to [HarPri] and [Gallai] for blocks and cuts tree.
EXAMPLES:
sage: from sage.graphs.connectivity import blocks_and_cuts_tree sage: T = blocks_and_cuts_tree(graphs.KrackhardtKiteGraph()); T Graph on 5 vertices sage: T.is_isomorphic(graphs.PathGraph(5)) True sage: from sage.graphs.connectivity import blocks_and_cuts_tree sage: T = graphs.KrackhardtKiteGraph().blocks_and_cuts_tree(); T Graph on 5 vertices
The distance between two leaves is even:
sage: T = blocks_and_cuts_tree(graphs.RandomTree(40)) sage: T.is_tree() True sage: leaves = [v for v in T if T.degree(v) == 1] sage: all(T.distance(u,v) % 2 == 0 for u in leaves for v in leaves) True
The tree of a biconnected graph has a single vertex, of type \(B\):
sage: T = blocks_and_cuts_tree(graphs.PetersenGraph()) sage: T.vertices() [('B', (0, 1, 4, 5, 2, 6, 3, 7, 8, 9))]

breadth_first_search
(start, ignore_direction=False, distance=None, neighbors=None, report_distance=False)¶ Return an iterator over the vertices in a breadthfirst ordering.
INPUT:
start
– vertex or list of vertices from which to start the traversal.ignore_direction
– (defaultFalse
) only applies to directed graphs. IfTrue
, searches across edges in either direction.distance
– the maximum distance from thestart
nodes to traverse. Thestart
nodes are distance zero from themselves.neighbors
– a function giving the neighbors of a vertex. The function should take a vertex and return a list of vertices. For a graph,neighbors
is by default theneighbors()
function of the graph. For a digraph, theneighbors
function defaults to theneighbor_out_iterator()
function of the graph.report_distance
– (defaultFalse
) IfTrue
, reports pairs (vertex, distance) where distance is the distance from thestart
nodes. IfFalse
only the vertices are reported.
See also
breadth_first_search
– breadthfirst search for fast compiled graphs.depth_first_search
– depthfirst search for fast compiled graphs.depth_first_search()
– depthfirst search for generic graphs.
EXAMPLES:
sage: G = Graph( { 0: [1], 1: [2], 2: [3], 3: [4], 4: [0]} ) sage: list(G.breadth_first_search(0)) [0, 1, 4, 2, 3]
By default, the edge direction of a digraph is respected, but this can be overridden by the
ignore_direction
parameter:sage: D = DiGraph( { 0: [1,2,3], 1: [4,5], 2: [5], 3: [6], 5: [7], 6: [7], 7: [0]}) sage: list(D.breadth_first_search(0)) [0, 1, 2, 3, 4, 5, 6, 7] sage: list(D.breadth_first_search(0, ignore_direction=True)) [0, 1, 2, 3, 7, 4, 5, 6]
You can specify a maximum distance in which to search. A distance of zero returns the
start
vertices:sage: D = DiGraph( { 0: [1,2,3], 1: [4,5], 2: [5], 3: [6], 5: [7], 6: [7], 7: [0]}) sage: list(D.breadth_first_search(0,distance=0)) [0] sage: list(D.breadth_first_search(0,distance=1)) [0, 1, 2, 3]
Multiple starting vertices can be specified in a list:
sage: D = DiGraph( { 0: [1,2,3], 1: [4,5], 2: [5], 3: [6], 5: [7], 6: [7], 7: [0]}) sage: list(D.breadth_first_search([0])) [0, 1, 2, 3, 4, 5, 6, 7] sage: list(D.breadth_first_search([0,6])) [0, 6, 1, 2, 3, 7, 4, 5] sage: list(D.breadth_first_search([0,6],distance=0)) [0, 6] sage: list(D.breadth_first_search([0,6],distance=1)) [0, 6, 1, 2, 3, 7] sage: list(D.breadth_first_search(6,ignore_direction=True,distance=2)) [6, 3, 7, 0, 5]
More generally, you can specify a
neighbors
function. For example, you can traverse the graph backwards by settingneighbors
to be theneighbors_in()
function of the graph:sage: D = DiGraph( { 0: [1,2,3], 1: [4,5], 2: [5], 3: [6], 5: [7], 6: [7], 7: [0]}) sage: list(D.breadth_first_search(5,neighbors=D.neighbors_in, distance=2)) [5, 1, 2, 0] sage: list(D.breadth_first_search(5,neighbors=D.neighbors_out, distance=2)) [5, 7, 0] sage: list(D.breadth_first_search(5,neighbors=D.neighbors, distance=2)) [5, 1, 2, 7, 0, 4, 6]
It is possible (trac ticket #16470) using the keyword
report_distance
to get pairs (vertex, distance) encoding the distance to the starting vertices:sage: G = graphs.PetersenGraph() sage: list(G.breadth_first_search(0, report_distance=True)) [(0, 0), (1, 1), (4, 1), (5, 1), (2, 2), (6, 2), (3, 2), (9, 2), (7, 2), (8, 2)] sage: list(G.breadth_first_search(0, report_distance=False)) [0, 1, 4, 5, 2, 6, 3, 9, 7, 8] sage: D = DiGraph({0:[1, 3], 1:[0, 2], 2:[0, 3], 3:[4]}) sage: D.show() sage: list(D.breadth_first_search(4, neighbors=D.neighbor_in_iterator, report_distance=True)) [(4, 0), (3, 1), (0, 2), (2, 2), (1, 3)] sage: C = graphs.CycleGraph(4) sage: list(C.breadth_first_search([0,1], report_distance=True)) [(0, 0), (1, 0), (3, 1), (2, 1)]

canonical_label
(partition=None, certificate=False, verbosity=0, edge_labels=False, algorithm=None, return_graph=True)¶ Return the canonical graph.
A canonical graph is the representative graph of an isomorphism class by some canonization function \(c\). If \(G\) and \(H\) are graphs, then \(G \cong c(G)\), and \(c(G) == c(H)\) if and only if \(G \cong H\).
See the Wikipedia article Graph_canonization for more information.
INPUT:
partition
– if given, the canonical label with respect to this set partition will be computed. The default is the unit set partition.certificate
– boolean (default:False
). When set toTrue
, a dictionary mapping from the vertices of the (di)graph to its canonical label will also be returned.edge_labels
– boolean (default:False
). When set toTrue
, allows only permutations respecting edge labels.algorithm
– a string (default:None
). The algorithm to use; currently available:'bliss'
: use the optional package bliss (http://www.tcs.tkk.fi/Software/bliss/index.html);'sage'
: always use Sage’s implementation.None
(default): use bliss when available and possibleNote
Make sure you always compare canonical forms obtained by the same algorithm.
return_graph
– boolean (default:True
). When set toFalse
, returns the list of edges of the the canonical graph instead of the canonical graph; only available when'bliss'
is explicitly set as algorithm.verbosity
– deprecated, does nothing
EXAMPLES:
Canonization changes isomorphism to equality:
sage: g1 = graphs.GridGraph([2,3]) sage: g2 = Graph({1: [2, 4], 3: [2, 6], 5: [4, 2, 6]}) sage: g1 == g2 False sage: g1.is_isomorphic(g2) True sage: g1.canonical_label() == g2.canonical_label() True
We can get the relabeling used for canonization:
sage: g, c = g1.canonical_label(algorithm='sage', certificate=True) sage: g Grid Graph for [2, 3]: Graph on 6 vertices sage: c {(0, 0): 3, (0, 1): 4, (0, 2): 2, (1, 0): 0, (1, 1): 5, (1, 2): 1}
Multigraphs and directed graphs work too:
sage: G = Graph(multiedges=True,sparse=True) sage: G.add_edge((0,1)) sage: G.add_edge((0,1)) sage: G.add_edge((0,1)) sage: G.canonical_label() Multigraph on 2 vertices sage: Graph('A?', implementation='c_graph').canonical_label() Graph on 2 vertices sage: P = graphs.PetersenGraph() sage: DP = P.to_directed() sage: DP.canonical_label(algorithm='sage').adjacency_matrix() [0 0 0 0 0 0 0 1 1 1] [0 0 0 0 1 0 1 0 0 1] [0 0 0 1 0 0 1 0 1 0] [0 0 1 0 0 1 0 0 0 1] [0 1 0 0 0 1 0 0 1 0] [0 0 0 1 1 0 0 1 0 0] [0 1 1 0 0 0 0 1 0 0] [1 0 0 0 0 1 1 0 0 0] [1 0 1 0 1 0 0 0 0 0] [1 1 0 1 0 0 0 0 0 0]
Edge labeled graphs:
sage: G = Graph(sparse=True) sage: G.add_edges( [(0,1,'a'),(1,2,'b'),(2,3,'c'),(3,4,'b'),(4,0,'a')] ) sage: G.canonical_label(edge_labels=True) Graph on 5 vertices sage: G.canonical_label(edge_labels=True, algorithm="bliss", certificate=True) # optional  bliss (Graph on 5 vertices, {0: 4, 1: 3, 2: 1, 3: 0, 4: 2}) sage: G.canonical_label(edge_labels=True, algorithm="sage", certificate=True) (Graph on 5 vertices, {0: 4, 1: 3, 2: 0, 3: 1, 4: 2})
Another example where different canonization algorithms give different graphs:
sage: g = Graph({'a': ['b'], 'c': ['d']}) sage: g_sage = g.canonical_label(algorithm='sage') sage: g_bliss = g.canonical_label(algorithm='bliss') # optional  bliss sage: g_sage.edges(labels=False) [(0, 3), (1, 2)] sage: g_bliss.edges(labels=False) # optional  bliss [(0, 1), (2, 3)]

cartesian_product
(other)¶ Returns the Cartesian product of self and other.
The Cartesian product of \(G\) and \(H\) is the graph \(L\) with vertex set \(V(L)\) equal to the Cartesian product of the vertices \(V(G)\) and \(V(H)\), and \(((u,v), (w,x))\) is an edge iff either  \((u, w)\) is an edge of self and \(v = x\), or  \((v, x)\) is an edge of other and \(u = w\).
See also
is_cartesian_product()
– factorization of graphs according to the Cartesian productgraph_products
– a module on graph products.

categorical_product
(other)¶ Returns the tensor product of self and other.
The tensor product of \(G\) and \(H\) is the graph \(L\) with vertex set \(V(L)\) equal to the Cartesian product of the vertices \(V(G)\) and \(V(H)\), and \(((u,v), (w,x))\) is an edge iff  \((u, w)\) is an edge of self, and  \((v, x)\) is an edge of other.
The tensor product is also known as the categorical product and the kronecker product (refering to the kronecker matrix product). See the Wikipedia article Kronecker_product.
EXAMPLES:
sage: Z = graphs.CompleteGraph(2) sage: C = graphs.CycleGraph(5) sage: T = C.tensor_product(Z); T Graph on 10 vertices sage: T.size() 10 sage: T.plot() # long time Graphics object consisting of 21 graphics primitives
sage: D = graphs.DodecahedralGraph() sage: P = graphs.PetersenGraph() sage: T = D.tensor_product(P); T Graph on 200 vertices sage: T.size() 900 sage: T.plot() # long time Graphics object consisting of 1101 graphics primitives

center
(by_weight=False, algorithm=None, weight_function=None, check_weight=True)¶ Returns the set of vertices in the center, i.e. whose eccentricity is equal to the radius of the (di)graph.
In other words, the center is the set of vertices achieving the minimum eccentricity.
For more information and examples on how to use input variables, see
shortest_paths()
andeccentricity()
INPUT:
by_weight
 ifTrue
, edge weights are taken into account; if False, all edges have weight 1.algorithm
(string)  one of the following algorithms:'BFS'
 the computation is done through a BFS centered on each vertex successively. Works only ifby_weight==False
.'FloydWarshallCython'
 a Cython implementation of the FloydWarshall algorithm. Works only ifby_weight==False
.'FloydWarshallPython'
 a Python implementation of the FloydWarshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed).'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).None
(default): Sage chooses the best algorithm:'BFS'
for unweighted graphs,'Dijkstra_Boost'
if all weights are positive,'Johnson_Boost'
, otherwise.
weight_function
(function)  a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
as a weight.check_weight
(boolean)  ifTrue
, 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: A = graphs.AfricaMap(continental=True) sage: sorted(A.center()) ['Cameroon', 'Central Africa']
Some other graphs. Center can be the whole graph:
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]

centrality_betweenness
(k=None, normalized=True, weight=None, endpoints=False, seed=None, exact=False, algorithm=None)¶ Returns the betweenness centrality (fraction of number of shortest paths that go through each vertex) as a dictionary keyed by vertices. The betweenness is normalized by default to be in range (0,1).
Measures of the centrality of a vertex within a graph determine the relative importance of that vertex to its graph. Vertices that occur on more shortest paths between other vertices have higher betweenness than vertices that occur on less.
INPUT:
normalized
 boolean (default True)  if set to False, result is not normalized.k
 integer or None (default None)  if set to an integer, usek
node samples to estimate betweenness. Higher values give better approximations. Not available whenalgorithm="Sage"
.weight
 None or string. If set to a string, use that attribute of the nodes as weight.weight = True
is equivalent toweight = "weight"
. Not available whenalgorithm="Sage"
.endpoints
 Boolean. If set to True it includes the endpoints in the shortest paths count. Not available whenalgorithm="Sage"
.exact
(boolean, default:False
) – whether to compute over rationals or ondouble
C variables. Not available whenalgorithm="NetworkX"
.algorithm
(default:None
) – can be either"Sage"
(seecentrality
),"NetworkX"
or"None"
. In the latter case, Sage’s algorithm will be used whenever possible.
EXAMPLES:
sage: g = graphs.ChvatalGraph() sage: g.centrality_betweenness() # abs tol 1e10 {0: 0.06969696969696969, 1: 0.06969696969696969, 2: 0.0606060606060606, 3: 0.0606060606060606, 4: 0.06969696969696969, 5: 0.06969696969696969, 6: 0.0606060606060606, 7: 0.0606060606060606, 8: 0.0606060606060606, 9: 0.0606060606060606, 10: 0.0606060606060606, 11: 0.0606060606060606} sage: g.centrality_betweenness(normalized=False) # abs tol 1e10 {0: 3.833333333333333, 1: 3.833333333333333, 2: 3.333333333333333, 3: 3.333333333333333, 4: 3.833333333333333, 5: 3.833333333333333, 6: 3.333333333333333, 7: 3.333333333333333, 8: 3.333333333333333, 9: 3.333333333333333, 10: 3.333333333333333, 11: 3.333333333333333} sage: D = DiGraph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: D.show(figsize=[2,2]) sage: D = D.to_undirected() sage: D.show(figsize=[2,2]) sage: D.centrality_betweenness() # abs tol abs 1e10 {0: 0.16666666666666666, 1: 0.16666666666666666, 2: 0.0, 3: 0.0}

centrality_closeness
(vert=None, by_weight=False, algorithm=None, weight_function=None, check_weight=True)¶ Returns the closeness centrality of all vertices in variable
vert
.In a (strongly) connected graph, the closeness centrality of a vertex \(v\) is equal to the inverse of the average distance between \(v\) and other vertices. If the graph is disconnected, the closeness centrality of \(v\) is multiplied by the fraction of reachable vertices in the graph: this way, central vertices should also reach several other vertices in the graph [OLJ14]. In formulas,
\[c(v)=\frac{r(v)1}{\sum_{w \in R(v)} d(v,w)}\frac{r(v)1}{n1}\]where \(R(v)\) is the set of vertices reachable from \(v\), and \(r(v)\) is the cardinality of \(R(v)\).
‘Closeness centrality may be defined as the total graphtheoretic distance of a given vertex from all other vertices… Closeness is an inverse measure of centrality in that a larger value indicates a less central actor while a smaller value indicates a more central actor,’ [Borgatti95].
For more information, see the Wikipedia article Centrality.
INPUT:
vert
 the vertex or the list of vertices we want to analyze. IfNone
(default), all vertices are considered.by_weight
(boolean)  ifTrue
, the edges in the graph are weighted; ifFalse
, all edges have weight 1.algorithm
(string)  one of the following algorithms:'BFS'
: performs a BFS from each vertex that has to be analyzed. Does not work with edge weights.'NetworkX'
: the NetworkX algorithm (works only with positive weights).'Dijkstra_Boost'
: the Dijkstra algorithm, implemented in Boost (works only with positive weights).'FloydWarshallCython'
 the Cython implementation of the FloydWarshall algorithm. Works only ifby_weight==False
and all centralities are needed.'FloydWarshallPython'
 the Python implementation of the FloydWarshall algorithm. Works only if all centralities are needed, but it can deal with weighted graphs, even with negative weights (but no negative cycle is allowed).'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:'BFS'
ifby_weight
isFalse
,'Dijkstra_Boost'
if all weights are positive,'Johnson_Boost'
otherwise.
weight_function
(function)  a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
as a weight.check_weight
(boolean)  ifTrue
, we check that the weight_function outputs a number for each edge.
OUTPUT:
If
vert
is a vertex, the closeness centrality of that vertex. Otherwise, a dictionary associating to each vertex invert
its closeness centrality. If a vertex has (out)degree 0, its closeness centrality is not defined, and the vertex is not included in the output.REFERENCES:
[Borgatti95] Stephen P. Borgatti. (1995). Centrality and AIDS. [Online] Available: http://www.analytictech.com/networks/centaids.htm [OLJ14] Paul W. Olsen, Alan G. Labouseur, JeongHyon Hwang. Efficient Topk Closeness Centrality Search Proceedings of the IEEE 30th International Conference on Data Engineering (ICDE), 2014 EXAMPLES:
Standard examples:
sage: (graphs.ChvatalGraph()).centrality_closeness() {0: 0.61111111111111..., 1: 0.61111111111111..., 2: 0.61111111111111..., 3: 0.61111111111111..., 4: 0.61111111111111..., 5: 0.61111111111111..., 6: 0.61111111111111..., 7: 0.61111111111111..., 8: 0.61111111111111..., 9: 0.61111111111111..., 10: 0.61111111111111..., 11: 0.61111111111111...} sage: D = DiGraph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: D.show(figsize=[2,2]) sage: D.centrality_closeness(vert=[0,1]) {0: 1.0, 1: 0.3333333333333333} sage: D = D.to_undirected() sage: D.show(figsize=[2,2]) sage: D.centrality_closeness() {0: 1.0, 1: 1.0, 2: 0.75, 3: 0.75}
In a (strongly) connected (di)graph, the closeness centrality of \(v\) is inverse of the average distance between \(v\) and all other vertices:
sage: g = graphs.PathGraph(5) sage: g.centrality_closeness(0) 0.4 sage: dist = g.shortest_path_lengths(0).values() sage: float(len(dist)1) / sum(dist) 0.4 sage: d = g.to_directed() sage: d.centrality_closeness(0) 0.4 sage: dist = d.shortest_path_lengths(0).values() sage: float(len(dist)1) / sum(dist) 0.4
If a vertex has (out)degree 0, its closeness centrality is not defined:
sage: g = Graph(5) sage: g.centrality_closeness() {} sage: print(g.centrality_closeness(0)) None
Weighted graphs:
sage: D = graphs.GridGraph([2,2]) sage: weight_function = lambda e:10 sage: D.centrality_closeness([(0,0),(0,1)]) # tol abs 1e12 {(0, 0): 0.75, (0, 1): 0.75} sage: D.centrality_closeness((0,0), weight_function=weight_function) # tol abs 1e12 0.075

characteristic_polynomial
(var='x', laplacian=False)¶ Returns the characteristic polynomial of the adjacency matrix of the (di)graph.
Let \(G\) be a (simple) graph with adjacency matrix \(A\). Let \(I\) be the identity matrix of dimensions the same as \(A\). The characteristic polynomial of \(G\) is defined as the determinant \(\det(xI  A)\).
Note
characteristic_polynomial
andcharpoly
are aliases and thus provide exactly the same method.INPUT:
x
– (default:'x'
) the variable of the characteristic polynomial.laplacian
– (default:False
) ifTrue
, use the Laplacian matrix.
See also
EXAMPLES:
sage: P = graphs.PetersenGraph() sage: P.characteristic_polynomial() x^10  15*x^8 + 75*x^6  24*x^5  165*x^4 + 120*x^3 + 120*x^2  160*x + 48 sage: P.charpoly() x^10  15*x^8 + 75*x^6  24*x^5  165*x^4 + 120*x^3 + 120*x^2  160*x + 48 sage: P.characteristic_polynomial(laplacian=True) x^10  30*x^9 + 390*x^8  2880*x^7 + 13305*x^6  39882*x^5 + 77640*x^4  94800*x^3 + 66000*x^2  20000*x

charpoly
(var='x', laplacian=False)¶ Returns the characteristic polynomial of the adjacency matrix of the (di)graph.
Let \(G\) be a (simple) graph with adjacency matrix \(A\). Let \(I\) be the identity matrix of dimensions the same as \(A\). The characteristic polynomial of \(G\) is defined as the determinant \(\det(xI  A)\).
Note
characteristic_polynomial
andcharpoly
are aliases and thus provide exactly the same method.INPUT:
x
– (default:'x'
) the variable of the characteristic polynomial.laplacian
– (default:False
) ifTrue
, use the Laplacian matrix.
See also
EXAMPLES:
sage: P = graphs.PetersenGraph() sage: P.characteristic_polynomial() x^10  15*x^8 + 75*x^6  24*x^5  165*x^4 + 120*x^3 + 120*x^2  160*x + 48 sage: P.charpoly() x^10  15*x^8 + 75*x^6  24*x^5  165*x^4 + 120*x^3 + 120*x^2  160*x + 48 sage: P.characteristic_polynomial(laplacian=True) x^10  30*x^9 + 390*x^8  2880*x^7 + 13305*x^6  39882*x^5 + 77640*x^4  94800*x^3 + 66000*x^2  20000*x

clear
()¶ Empties the graph of vertices and edges and removes name, associated objects, and position information.
EXAMPLES:
sage: G=graphs.CycleGraph(4); G.set_vertices({0:'vertex0'}) sage: G.order(); G.size() 4 4 sage: len(G._pos) 4 sage: G.name() 'Cycle graph' sage: G.get_vertex(0) 'vertex0' sage: H = G.copy(implementation='c_graph', sparse=True) sage: H.clear() sage: H.order(); H.size() 0 0 sage: len(H._pos) 0 sage: H.name() '' sage: H.get_vertex(0) sage: H = G.copy(implementation='c_graph', sparse=False) sage: H.clear() sage: H.order(); H.size() 0 0 sage: len(H._pos) 0 sage: H.name() '' sage: H.get_vertex(0)

cluster_transitivity
()¶ Returns the transitivity (fraction of transitive triangles) of the graph.
Transitivity is the fraction of all existing triangles and all connected triples (triads), \(T = 3\times\text{triangles} / \text{triads}\).
See also section “Clustering” in chapter “Algorithms” of [HSSNX].
EXAMPLES:
sage: (graphs.FruchtGraph()).cluster_transitivity() 0.25

cluster_triangles
(nbunch=None, with_labels=False)¶ Returns the number of triangles for the set \(nbunch\) of vertices as a dictionary keyed by vertex.
See also section “Clustering” in chapter “Algorithms” of [HSSNX].
INPUT:
nbunch
 The vertices to inspect. Ifnbunch=None
, returns data for all vertices in the graph.
REFERENCE:
[HSSNX] (1, 2, 3, 4) Aric Hagberg, Dan Schult and Pieter Swart. NetworkX documentation. [Online] Available: http://networkx.github.io/documentation/latest/reference/index.html EXAMPLES:
sage: list((graphs.FruchtGraph()).cluster_triangles().values()) [1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0] sage: (graphs.FruchtGraph()).cluster_triangles() {0: 1, 1: 1, 2: 0, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 0, 9: 1, 10: 1, 11: 0} sage: (graphs.FruchtGraph()).cluster_triangles(nbunch=[0,1,2]) {0: 1, 1: 1, 2: 0}

clustering_average
(implementation=None)¶ Returns the average clustering coefficient.
The clustering coefficient of a node \(i\) is the fraction of existing triangles containing node \(i\) and all possible triangles containing \(i\): \(c_i = T(i) / \binom {k_i} 2\) where \(T(i)\) is the number of existing triangles through \(i\), and \(k_i\) is the degree of vertex \(i\).
A coefficient for the whole graph is the average of the \(c_i\).
See also section “Clustering” in chapter “Algorithms” of [HSSNX].
INPUT:
implementation
 one of'boost'
,'sparse_copy'
,'dense_copy'
,'networkx'
orNone
(default). In the latter case, the best algorithm available is used. Note that only'networkx'
supports directed graphs.
EXAMPLES:
sage: (graphs.FruchtGraph()).clustering_average() 1/4 sage: (graphs.FruchtGraph()).clustering_average(implementation='networkx') 0.25

clustering_coeff
(nodes=None, weight=False, implementation=None)¶ Returns the clustering coefficient for each vertex in
nodes
as a dictionary keyed by vertex.For an unweighted graph, the clustering coefficient of a node \(i\) is the fraction of existing triangles containing node \(i\) and all possible triangles containing \(i\): \(c_i = T(i) / \binom {k_i} 2\) where \(T(i)\) is the number of existing triangles through \(i\), and \(k_i\) is the degree of vertex \(i\).
For weighted graphs the clustering is defined as the geometric average of the subgraph edge weights, normalized by the maximum weight in the network.
The value of \(c_i\) is assigned \(0\) if \(k_i < 2\).
See also section “Clustering” in chapter “Algorithms” of [HSSNX].
INPUT:
nodes
 the vertices to inspect (defaultNone
, returns data on all vertices in graph)weight
 string or boolean (default isFalse
). If it is a string it used the indicated edge property as weight.weight = True
is equivalent toweight = 'weight'
implementation
 one of'boost'
,'sparse_copy'
,'dense_copy'
,'networkx'
orNone
(default). In the latter case, the best algorithm available is used. Note that only'networkx'
supports directed or weighted graphs, and that'sparse_copy'
and'dense_copy'
do not supportnode
different fromNone
EXAMPLES:
sage: graphs.FruchtGraph().clustering_coeff() {0: 1/3, 1: 1/3, 2: 0, 3: 1/3, 4: 1/3, 5: 1/3, 6: 1/3, 7: 1/3, 8: 0, 9: 1/3, 10: 1/3, 11: 0} sage: (graphs.FruchtGraph()).clustering_coeff(weight=True) {0: 0.3333333333333333, 1: 0.3333333333333333, 2: 0, 3: 0.3333333333333333, 4: 0.3333333333333333, 5: 0.3333333333333333, 6: 0.3333333333333333, 7: 0.3333333333333333, 8: 0, 9: 0.3333333333333333, 10: 0.3333333333333333, 11: 0} sage: (graphs.FruchtGraph()).clustering_coeff(nodes=[0,1,2]) {0: 0.3333333333333333, 1: 0.3333333333333333, 2: 0.0} sage: (graphs.FruchtGraph()).clustering_coeff(nodes=[0,1,2], ....: weight=True) {0: 0.3333333333333333, 1: 0.3333333333333333, 2: 0} sage: (graphs.GridGraph([5,5])).clustering_coeff(nodes=[(0,0),(0,1),(2,2)]) {(0, 0): 0.0, (0, 1): 0.0, (2, 2): 0.0}

coarsest_equitable_refinement
(partition, sparse=True)¶ Returns the coarsest partition which is finer than the input partition, and equitable with respect to self.
A partition is equitable with respect to a graph if for every pair of cells C1, C2 of the partition, the number of edges from a vertex of C1 to C2 is the same, over all vertices in C1.
A partition P1 is finer than P2 (P2 is coarser than P1) if every cell of P1 is a subset of a cell of P2.
INPUT:
partition
 a list of listssparse
 (default False) whether to use sparse or dense representation for small graphs, use dense for speed
EXAMPLES:
sage: G = graphs.PetersenGraph() sage: G.coarsest_equitable_refinement([[0],list(range(1,10))]) [[0], [2, 3, 6, 7, 8, 9], [1, 4, 5]] sage: G = graphs.CubeGraph(3) sage: verts = G.vertices() sage: Pi = [verts[:1], verts[1:]] sage: Pi [['000'], ['001', '010', '011', '100', '101', '110', '111']] sage: G.coarsest_equitable_refinement(Pi) [['000'], ['011', '101', '110'], ['111'], ['001', '010', '100']]
Note that given an equitable partition, this function returns that partition:
sage: P = graphs.PetersenGraph() sage: prt = [[0], [1, 4, 5], [2, 3, 6, 7, 8, 9]] sage: P.coarsest_equitable_refinement(prt) [[0], [1, 4, 5], [2, 3, 6, 7, 8, 9]]
sage: ss = (graphs.WheelGraph(6)).line_graph(labels=False) sage: prt = [[(0, 1)], [(0, 2), (0, 3), (0, 4), (1, 2), (1, 4)], [(2, 3), (3, 4)]] sage: ss.coarsest_equitable_refinement(prt) Traceback (most recent call last): ... TypeError: Partition ([[(0, 1)], [(0, 2), (0, 3), (0, 4), (1, 2), (1, 4)], [(2, 3), (3, 4)]]) is not valid for this graph: vertices are incorrect.
sage: ss = (graphs.WheelGraph(5)).line_graph(labels=False) sage: ss.coarsest_equitable_refinement(prt) [[(0, 1)], [(1, 2), (1, 4)], [(0, 3)], [(0, 2), (0, 4)], [(2, 3), (3, 4)]]
ALGORITHM: Brendan D. McKay’s Master’s Thesis, University of Melbourne, 1976.

complement
()¶ Returns the complement of the (di)graph.
The complement of a graph has the same vertices, but exactly those edges that are not in the original graph. This is not well defined for graphs with multiple edges.
EXAMPLES:
sage: P = graphs.PetersenGraph() sage: P.plot() # long time Graphics object consisting of 26 graphics primitives sage: PC = P.complement() sage: PC.plot() # long time Graphics object consisting of 41 graphics primitives
sage: graphs.TetrahedralGraph().complement().size() 0 sage: graphs.CycleGraph(4).complement().edges() [(0, 2, None), (1, 3, None)] sage: graphs.CycleGraph(4).complement() complement(Cycle graph): Graph on 4 vertices sage: G = Graph(multiedges=True, sparse=True) sage: G.add_edges([(0,1)]*3) sage: G.complement() Traceback (most recent call last): ... ValueError: This method is not known to work on graphs with multiedges. Perhaps this method can be updated to handle them, but in the meantime if you want to use it please disallow multiedges using allow_multiple_edges().

connected_component_containing_vertex
(G, vertex, sort=True)¶ Return a list of the vertices connected to vertex.
INPUT:
G
(generic_graph) – the input graph.v
– the vertex to search for.sort
– boolean (defaultTrue
) whether to sort vertices inside the component
EXAMPLES:
sage: from sage.graphs.connectivity import connected_component_containing_vertex sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: connected_component_containing_vertex(G,0) [0, 1, 2, 3] sage: G.connected_component_containing_vertex(0) [0, 1, 2, 3] sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: connected_component_containing_vertex(D,0) [0, 1, 2, 3]

connected_components
(G, sort=True)¶ Return the list of connected components.
This returns a list of lists of vertices, each list representing a connected component. The list is ordered from largest to smallest component.
INPUT:
G
(generic_graph) – the input graph.sort
– boolean (defaultTrue
) whether to sort vertices inside each component
EXAMPLES:
sage: from sage.graphs.connectivity import connected_components sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: connected_components(G) [[0, 1, 2, 3], [4, 5, 6]] sage: G.connected_components() [[0, 1, 2, 3], [4, 5, 6]] sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: connected_components(D) [[0, 1, 2, 3], [4, 5, 6]]

connected_components_number
(G)¶ Return the number of connected components.
INPUT:
G
(generic_graph) – the input graph.
EXAMPLES:
sage: from sage.graphs.connectivity import connected_components_number sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: connected_components_number(G) 2 sage: G.connected_components_number() 2 sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: connected_components_number(D) 2

connected_components_sizes
(G)¶ Return the sizes of the connected components as a list.
The list is sorted from largest to lower values.
EXAMPLES:
sage: from sage.graphs.connectivity import connected_components_sizes sage: for x in graphs(3): print(connected_components_sizes(x)) [1, 1, 1] [2, 1] [3] [3] sage: for x in graphs(3): print(x.connected_components_sizes()) [1, 1, 1] [2, 1] [3] [3]

connected_components_subgraphs
(G)¶ Return a list of connected components as graph objects.
EXAMPLES:
sage: from sage.graphs.connectivity import connected_components_subgraphs sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: L = connected_components_subgraphs(G) sage: graphs_list.show_graphs(L) sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: L = connected_components_subgraphs(D) sage: graphs_list.show_graphs(L) sage: L = D.connected_components_subgraphs() sage: graphs_list.show_graphs(L)

connected_subgraph_iterator
(G, k=None, vertices_only=False)¶ Iterator over the induced connected subgraphs of order at most \(k\).
This method implements a iterator over the induced connected subgraphs of the input (di)graph. An induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset (Wikipedia article Induced_subgraph).
As for method
sage.graphs.generic_graph.connected_components()
, edge orientation is ignored. Hence, the directed graph with a single arc \(0 \to 1\) is considered connected.INPUT:
G
– aGraph
or aDiGraph
; loops and multiple edges are allowedk
– (optional) integer; maximum order of the connected subgraphs to report; by default, the method iterates over all connected subgraphs (equivalent tok == n
)vertices_only
– (default:False
) boolean; whether to return (Di)Graph or list of vertices
EXAMPLES:
sage: G = DiGraph([(1, 2), (2, 3), (3, 4), (4, 2)]) sage: list(G.connected_subgraph_iterator()) [Subgraph of (): Digraph on 1 vertex, Subgraph of (): Digraph on 2 vertices, Subgraph of (): Digraph on 3 vertices, Subgraph of (): Digraph on 4 vertices, Subgraph of (): Digraph on 3 vertices, Subgraph of (): Digraph on 1 vertex, Subgraph of (): Digraph on 2 vertices, Subgraph of (): Digraph on 3 vertices, Subgraph of (): Digraph on 2 vertices, Subgraph of (): Digraph on 1 vertex, Subgraph of (): Digraph on 2 vertices, Subgraph of (): Digraph on 1 vertex] sage: list(G.connected_subgraph_iterator(vertices_only=True)) [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]] sage: list(G.connected_subgraph_iterator(k=2)) [Subgraph of (): Digraph on 1 vertex, Subgraph of (): Digraph on 2 vertices, Subgraph of (): Digraph on 1 vertex, Subgraph of (): Digraph on 2 vertices, Subgraph of (): Digraph on 2 vertices, Subgraph of (): Digraph on 1 vertex, Subgraph of (): Digraph on 2 vertices, Subgraph of (): Digraph on 1 vertex] sage: list(G.connected_subgraph_iterator(k=2, vertices_only=True)) [[1], [1, 2], [2], [2, 3], [2, 4], [3], [3, 4], [4]] sage: G = DiGraph([(1, 2), (2, 1)]) sage: list(G.connected_subgraph_iterator()) [Subgraph of (): Digraph on 1 vertex, Subgraph of (): Digraph on 2 vertices, Subgraph of (): Digraph on 1 vertex] sage: list(G.connected_subgraph_iterator(vertices_only=True)) [[1], [1, 2], [2]]

contract_edge
(u, v=None, label=None)¶ Contract an edge from \(u\) to \(v\).
This method returns silently if the edge does not exist.
INPUT: The following forms are all accepted:
 G.contract_edge( 1, 2 )
 G.contract_edge( (1, 2) )
 G.contract_edge( [ (1, 2) ] )
 G.contract_edge( 1, 2, ‘label’ )
 G.contract_edge( (1, 2, ‘label’) )
 G.contract_edge( [ (1, 2, ‘label’) ] )
EXAMPLES:
sage: G = graphs.CompleteGraph(4) sage: G.contract_edge((0,1)); G.edges() [(0, 2, None), (0, 3, None), (2, 3, None)] sage: G = graphs.CompleteGraph(4) sage: G.allow_loops(True); G.allow_multiple_edges(True) sage: G.contract_edge((0,1)); G.edges() [(0, 2, None), (0, 2, None), (0, 3, None), (0, 3, None), (2, 3, None)] sage: G.contract_edge((0,2)); G.edges() [(0, 0, None), (0, 3, None), (0, 3, None), (0, 3, None)]
sage: G = graphs.CompleteGraph(4).to_directed() sage: G.allow_loops(True) sage: G.contract_edge(0,1); G.edges() [(0, 0, None), (0, 2, None), (0, 3, None), (2, 0, None), (2, 3, None), (3, 0, None), (3, 2, None)]

contract_edges
(edges)¶ Contract edges from an iterable container.
If \(e\) is an edge that is not contracted but the vertices of \(e\) are merged by contraction of other edges, then \(e\) will become a loop.
INPUT:
edges
– a list containing 2tuples or 3tuples that represent edges
EXAMPLES:
sage: G = graphs.CompleteGraph(4) sage: G.allow_loops(True); G.allow_multiple_edges(True) sage: G.contract_edges([(0,1),(1,2),(0,2)]); G.edges() [(0, 3, None), (0, 3, None), (0, 3, None)] sage: G.contract_edges([(1,3),(2,3)]); G.edges() [(0, 3, None), (0, 3, None), (0, 3, None)] sage: G = graphs.CompleteGraph(4) sage: G.allow_loops(True); G.allow_multiple_edges(True) sage: G.contract_edges([(0,1),(1,2),(0,2),(1,3),(2,3)]); G.edges() [(0, 0, None)]
sage: D = graphs.CompleteGraph(4).to_directed() sage: D.allow_loops(True); D.allow_multiple_edges(True) sage: D.contract_edges([(0,1),(1,0),(0,2)]); D.edges() [(0, 0, None), (0, 0, None), (0, 0, None), (0, 3, None), (0, 3, None), (0, 3, None), (3, 0, None), (3, 0, None), (3, 0, None)]
sage: edgelist = [(0,1,0), (0,1,1), (0,1,2)] sage: G = Graph(edgelist, loops=True, multiedges=True) sage: G.contract_edges([(0,1), (0,1,2)]); G.edges() Traceback (most recent call last): ... ValueError: edge tuples in input should have the same length
sage: G = graphs.CompleteGraph(4) sage: G.allow_loops(True); G.allow_multiple_edges(True) sage: for e in G.edges(): ....: G.set_edge_label(e[0], e[1], (e[0] + e[1])) sage: H = G.copy() sage: G.contract_edges([(0,1), (0,2)]); G.edges() [(0, 0, 3), (0, 3, 3), (0, 3, 4), (0, 3, 5)] sage: H.contract_edges([(0,1,1), (0,2,3)]); H.edges() [(0, 2, 2), (0, 2, 3), (0, 3, 3), (0, 3, 4), (2, 3, 5)]

copy
(weighted=None, implementation='c_graph', data_structure=None, sparse=None, immutable=None)¶ Change the graph implementation
INPUT:
weighted
boolean (default:None
) – weightedness for the copy. Might change the equality class if notNone
.sparse
(boolean) –sparse=True
is an alias fordata_structure="sparse"
, andsparse=False
is an alias fordata_structure="dense"
. Only used whenimplementation='c_graph'
anddata_structure=None
.data_structure
– one of"sparse"
,"static_sparse"
, or"dense"
. See the documentation ofGraph
orDiGraph
. Only used whenimplementation='c_graph'
.immutable
(boolean) – whether to create a mutable/immutable copy. Only used whenimplementation='c_graph'
anddata_structure=None
.immutable=None
(default) means that the graph and its copy will behave the same way.immutable=True
is a shortcut fordata_structure='static_sparse'
andimplementation='c_graph'
immutable=False
setsimplementation
to'c_graph'
. Whenimmutable=False
is used to copy an immutable graph, the data structure used is"sparse"
unless anything else is specified.
Note
If the graph uses
StaticSparseBackend
and the_immutable
flag, thenself
is returned rather than a copy (unless one of the optional arguments is used).OUTPUT:
A Graph object.
Warning
Please use this method only if you need to copy but change the underlying implementation or weightedness. Otherwise simply do
copy(g)
instead ofg.copy()
.Warning
If
weighted
is passed and is not the weightedness of the original, then the copy will not equal the original.EXAMPLES:
sage: g=Graph({0:[0,1,1,2]},loops=True,multiedges=True,sparse=True) sage: g==copy(g) True sage: g=DiGraph({0:[0,1,1,2],1:[0,1]},loops=True,multiedges=True,sparse=True) sage: g==copy(g) True
Note that vertex associations are also kept:
sage: d = {0 : graphs.DodecahedralGraph(), 1 : graphs.FlowerSnark(), 2 : graphs.MoebiusKantorGraph(), 3 : graphs.PetersenGraph() } sage: T = graphs.TetrahedralGraph() sage: T.set_vertices(d) sage: T2 = copy(T) sage: T2.get_vertex(0) Dodecahedron: Graph on 20 vertices
Notice that the copy is at least as deep as the objects:
sage: T2.get_vertex(0) is T.get_vertex(0) False
Examples of the keywords in use:
sage: G = graphs.CompleteGraph(19) sage: H = G.copy(implementation='c_graph') sage: H == G; H is G True False sage: G1 = G.copy(sparse=True) sage: G1==G True sage: G1 is G False sage: G2 = copy(G) sage: G2 is G False
Argument
weighted
affects the equality class:sage: G = graphs.CompleteGraph(5) sage: H1 = G.copy(weighted=False) sage: H2 = G.copy(weighted=True) sage: [G.weighted(), H1.weighted(), H2.weighted()] [False, False, True] sage: [G == H1, G == H2, H1 == H2] [True, False, False] sage: G.weighted(True) sage: [G == H1, G == H2, H1 == H2] [False, True, False]

crossing_number
()¶ Return the crossing number of the graph.
The crossing number of a graph is the minimum number of edge crossings needed to draw the graph on a plane. It can be seen as a measure of nonplanarity; a planar graph has crossing number zero.
See the Wikipedia article Crossing_number for more information.
EXAMPLES:
sage: P = graphs.PetersenGraph() sage: P.crossing_number() 2
ALGORITHM:
This is slow brute force implementation: for every \(k\) pairs of edges try adding a new vertex for a crossing point for them. If the result is not planar in any of those, try \(k+1\) pairs.
Computing the crossing number is NPhard problem.

cycle_basis
(output='vertex')¶ Returns a list of cycles which form a basis of the cycle space of
self
.A basis of cycles of a graph is a minimal collection of cycles (considered as sets of edges) such that the edge set of any cycle in the graph can be written as a \(Z/2Z\) sum of the cycles in the basis.
INPUT:
output
('vertex'
(default) or'edge'
) – whether every cycle is given as a list of vertices or a list of edges.
OUTPUT:
A list of lists, each of them representing the vertices (or the edges) of a cycle in a basis.
ALGORITHM:
Uses the NetworkX library for graphs without multiple edges.
Otherwise, by the standard algorithm using a spanning tree.
EXAMPLES:
A cycle basis in Petersen’s Graph
sage: g = graphs.PetersenGraph() sage: g.cycle_basis() [[1, 2, 7, 5, 0], [8, 3, 2, 7, 5], [4, 3, 2, 7, 5, 0], [4, 9, 7, 5, 0], [8, 6, 9, 7, 5], [1, 6, 9, 7, 5, 0]]
One can also get the result as a list of lists of edges:
sage: g.cycle_basis(output='edge') [[(1, 2, None), (2, 7, None), (7, 5, None), (5, 0, None), (0, 1, None)], [(8, 3, None), (3, 2, None), (2, 7, None), (7, 5, None), (5, 8, None)], [(4, 3, None), (3, 2, None), (2, 7, None), (7, 5, None), (5, 0, None), (0, 4, None)], [(4, 9, None), (9, 7, None), (7, 5, None), (5, 0, None), (0, 4, None)], [(8, 6, None), (6, 9, None), (9, 7, None), (7, 5, None), (5, 8, None)], [(1, 6, None), (6, 9, None), (9, 7, None), (7, 5, None), (5, 0, None), (0, 1, None)]]
Checking the given cycles are algebraically free:
sage: g = graphs.RandomGNP(30,.4) sage: basis = g.cycle_basis()
Building the space of (directed) edges over \(Z/2Z\). On the way, building a dictionary associating an unique vector to each undirected edge:
sage: m = g.size() sage: edge_space = VectorSpace(FiniteField(2),m) sage: edge_vector = dict( zip( g.edges(labels = False), edge_space.basis() ) ) sage: for (u,v),vec in list(edge_vector.items()): ....: edge_vector[(v,u)] = vec
Defining a lambda function associating a vector to the vertices of a cycle:
sage: vertices_to_edges = lambda x : zip( x, x[1:] + [x[0]] ) sage: cycle_to_vector = lambda x : sum( edge_vector[e] for e in vertices_to_edges(x) )
Finally checking the cycles are a free set:
sage: basis_as_vectors = [cycle_to_vector(_) for _ in basis] sage: edge_space.span(basis_as_vectors).rank() == len(basis) True
For undirected graphs with multiple edges:
sage: G = Graph([(0,2,'a'),(0,2,'b'),(0,1,'c'),(1,2,'d')], multiedges=True) sage: G.cycle_basis() [[0, 2], [2, 1, 0]] sage: G.cycle_basis(output='edge') [[(0, 2, 'a'), (2, 0, 'b')], [(2, 1, 'd'), (1, 0, 'c'), (0, 2, 'a')]]
Disconnected graph:
sage: G.add_cycle(["Hey", "Wuuhuu", "Really ?"]) sage: G.cycle_basis() [['Really ?', 'Hey', 'Wuuhuu'], [0, 2], [2, 1, 0]] sage: G.cycle_basis(output='edge') [[('Really ?', 'Hey', None), ('Hey', 'Wuuhuu', None), ('Wuuhuu', 'Really ?', None)], [(0, 2, 'a'), (2, 0, 'b')], [(2, 1, 'd'), (1, 0, 'c'), (0, 2, 'a')]]
Graph that allows multiple edges but does not contain any:
sage: G = graphs.CycleGraph(3) sage: G.allow_multiple_edges(True) sage: G.cycle_basis() [[2, 1, 0]]
Not yet implemented for directed graphs with multiple edges:
sage: G = DiGraph([(0,2,'a'),(0,2,'b'),(0,1,'c'),(1,2,'d')], multiedges=True) sage: G.cycle_basis() Traceback (most recent call last): ... NotImplementedError: not implemented for directed graphs with multiple edges

degree
(vertices=None, labels=False)¶ Gives the degree (in + out for digraphs) of a vertex or of vertices.
INPUT:
vertices
 If vertices is a single vertex, returns the number of neighbors of vertex. If vertices is an iterable container of vertices, returns a list of degrees. If vertices is None, same as listing all vertices.labels
 see OUTPUT
OUTPUT: Single vertex an integer. Multiple vertices a list of integers. If labels is True, then returns a dictionary mapping each vertex to its degree.
EXAMPLES:
sage: P = graphs.PetersenGraph() sage: P.degree(5) 3
sage: K = graphs.CompleteGraph(9) sage: K.degree() [8, 8, 8, 8, 8, 8, 8, 8, 8]
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.degree(vertices = [0,1,2], labels=True) {0: 5, 1: 4, 2: 3} sage: D.degree() [5, 4, 3, 3, 3, 2]

degree_histogram
()¶ Return a list, whose ith entry is the frequency of degree i.
EXAMPLES:
sage: G = graphs.Grid2dGraph(9,12) sage: G.degree_histogram() [0, 0, 4, 34, 70]
sage: G = graphs.Grid2dGraph(9,12).to_directed() sage: G.degree_histogram() [0, 0, 0, 0, 4, 0, 34, 0, 70]

degree_iterator
(vertices=None, labels=False)¶ Returns an iterator over the degrees of the (di)graph.
In the case of a digraph, the degree is defined as the sum of the indegree and the outdegree, i.e. the total number of edges incident to a given vertex.
INPUT:
labels
(boolean) – if set toFalse
(default) the method returns an iterator over degrees. Otherwise it returns an iterator over tuples (vertex, degree).vertices
 if specified, restrict to this subset.
EXAMPLES:
sage: G = graphs.Grid2dGraph(3,4) sage: for i in G.degree_iterator(): ....: print(i) 3 4 2 ... 2 4 sage: for i in G.degree_iterator(labels=True): ....: print(i) ((0, 1), 3) ((1, 2), 4) ((0, 0), 2) ... ((0, 3), 2) ((1, 1), 4)
sage: D = graphs.Grid2dGraph(2,4).to_directed() sage: for i in D.degree_iterator(): ....: print(i) 6 6 ... 4 6 sage: for i in D.degree_iterator(labels=True): ....: print(i) ((0, 1), 6) ((1, 2), 6) ... ((1, 0), 4) ((0, 2), 6)

degree_sequence
()¶ Return the degree sequence of this (di)graph.
EXAMPLES:
The degree sequence of an undirected graph:
sage: g = Graph({1: [2, 5], 2: [1, 5, 3, 4], 3: [2, 5], 4: [3], 5: [2, 3]}) sage: g.degree_sequence() [4, 3, 3, 2, 2]
The degree sequence of a digraph:
sage: g = DiGraph({1: [2, 5, 6], 2: [3, 6], 3: [4, 6], 4: [6], 5: [4, 6]}) sage: g.degree_sequence() [5, 3, 3, 3, 3, 3]
Degree sequences of some common graphs:
sage: graphs.PetersenGraph().degree_sequence() [3, 3, 3, 3, 3, 3, 3, 3, 3, 3] sage: graphs.HouseGraph().degree_sequence() [3, 3, 2, 2, 2] sage: graphs.FlowerSnark().degree_sequence() [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

degree_to_cell
(vertex, cell)¶ Returns the number of edges from vertex to an edge in cell. In the case of a digraph, returns a tuple (in_degree, out_degree).
EXAMPLES:
sage: G = graphs.CubeGraph(3) sage: cell = G.vertices()[:3] sage: G.degree_to_cell('011', cell) 2 sage: G.degree_to_cell('111', cell) 0
sage: D = DiGraph({ 0:[1,2,3], 1:[3,4], 3:[4,5]}) sage: cell = [0,1,2] sage: D.degree_to_cell(5, cell) (0, 0) sage: D.degree_to_cell(3, cell) (2, 0) sage: D.degree_to_cell(0, cell) (0, 2)

delete_edge
(u, v=None, label=None)¶ Delete the edge from u to v, returning silently if vertices or edge does not exist.
INPUT: The following forms are all accepted:
 G.delete_edge( 1, 2 )
 G.delete_edge( (1, 2) )
 G.delete_edges( [ (1, 2) ] )
 G.delete_edge( 1, 2, ‘label’ )
 G.delete_edge( (1, 2, ‘label’) )
 G.delete_edges( [ (1, 2, ‘label’) ] )
EXAMPLES:
sage: G = graphs.CompleteGraph(19).copy(implementation='c_graph') sage: G.size() 171 sage: G.delete_edge( 1, 2 ) sage: G.delete_edge( (3, 4) ) sage: G.delete_edges( [ (5, 6), (7, 8) ] ) sage: G.size() 167
sage: G.delete_edge( 9, 10, 'label' ) sage: G.delete_edge( (11, 12, 'label') ) sage: G.delete_edges( [ (13, 14, 'label') ] ) sage: G.size() 167
sage: C = graphs.CompleteGraph(19).to_directed(sparse=True) sage: C.size() 342 sage: C.delete_edge( 1, 2 ) sage: C.delete_edge( (3, 4) ) sage: C.delete_edges( [ (5, 6), (7, 8) ] )
sage: C.delete_edge( 9, 10, 'label' ) sage: C.delete_edge( (11, 12, 'label') ) sage: C.delete_edges( [ (13, 14, 'label') ] ) sage: C.size() # correct! 338 sage: C.has_edge( (11, 12) ) # correct! True

delete_edges
(edges)¶ Delete edges from an iterable container.
EXAMPLES:
sage: K12 = graphs.CompleteGraph(12) sage: K4 = graphs.CompleteGraph(4) sage: K12.size() 66 sage: K12.delete_edges(K4.edge_iterator()) sage: K12.size() 60
sage: K12 = graphs.CompleteGraph(12).to_directed() sage: K4 = graphs.CompleteGraph(4).to_directed() sage: K12.size() 132 sage: K12.delete_edges(K4.edge_iterator()) sage: K12.size() 120

delete_multiedge
(u, v)¶ Deletes all edges from u and v.
EXAMPLES:
sage: G = Graph(multiedges=True,sparse=True) sage: G.add_edges([(0,1), (0,1), (0,1), (1,2), (2,3)]) sage: G.edges() [(0, 1, None), (0, 1, None), (0, 1, None), (1, 2, None), (2, 3, None)] sage: G.delete_multiedge( 0, 1 ) sage: G.edges() [(1, 2, None), (2, 3, None)]
sage: D = DiGraph(multiedges=True,sparse=True) sage: D.add_edges([(0,1,1), (0,1,2), (0,1,3), (1,0,None), (1,2,None), (2,3,None)]) sage: D.edges() [(0, 1, 1), (0, 1, 2), (0, 1, 3), (1, 0, None), (1, 2, None), (2, 3, None)] sage: D.delete_multiedge( 0, 1 ) sage: D.edges() [(1, 0, None), (1, 2, None), (2, 3, None)]

delete_vertex
(vertex, in_order=False)¶ Deletes vertex, removing all incident edges. Deleting a nonexistent vertex will raise an exception.
INPUT:
in_order
 (default False) If True, this deletes the ith vertex in the sorted list of vertices, i.e. G.vertices()[i]
EXAMPLES:
sage: G = Graph(graphs.WheelGraph(9)) sage: G.delete_vertex(0); G.show()
sage: D = DiGraph({0:[1,2,3,4,5],1:[2],2:[3],3:[4],4:[5],5:[1]}) sage: D.delete_vertex(0); D Digraph on 5 vertices sage: D.vertices() [1, 2, 3, 4, 5] sage: D.delete_vertex(0) Traceback (most recent call last): ... RuntimeError: Vertex (0) not in the graph.
sage: G = graphs.CompleteGraph(4).line_graph(labels=False) sage: G.vertices() [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] sage: G.delete_vertex(0, in_order=True) sage: G.vertices() [(0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] sage: G = graphs.PathGraph(5) sage: G.set_vertices({0: 'no delete', 1: 'delete'}) sage: G.delete_vertex(1) sage: G.get_vertices() {0: 'no delete', 2: None, 3: None, 4: None} sage: G.get_pos() {0: (0, 0), 2: (2, 0), 3: (3, 0), 4: (4, 0)}

delete_vertices
(vertices)¶ Remove vertices from the (di)graph taken from an iterable container of vertices. Deleting a nonexistent vertex will raise an exception.
EXAMPLES:
sage: D = DiGraph({0:[1,2,3,4,5],1:[2],2:[3],3:[4],4:[5],5:[1]}) sage: D.delete_vertices([1,2,3,4,5]); D Digraph on 1 vertex sage: D.vertices() [0] sage: D.delete_vertices([1]) Traceback (most recent call last): ... RuntimeError: Vertex (1) not in the graph.

density
()¶ Returns the density (number of edges divided by number of possible edges).
In the case of a multigraph, raises an error, since there is an infinite number of possible edges.
EXAMPLES:
sage: d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7, 8], 6: [8,9], 7: [9]} sage: G = Graph(d); G.density() 1/3 sage: G = Graph({0:[1,2], 1:[0] }); G.density() 2/3 sage: G = DiGraph({0:[1,2], 1:[0] }); G.density() 1/2
Note that there are more possible edges on a looped graph:
sage: G.allow_loops(True) sage: G.density() 1/3

depth_first_search
(start, ignore_direction=False, distance=None, neighbors=None)¶ Return an iterator over the vertices in a depthfirst ordering.
INPUT:
start
 vertex or list of vertices from which to start the traversalignore_direction
 (default False) only applies to directed graphs. If True, searches across edges in either direction.distance
 Deprecated. Broken, do not use.neighbors
 a function giving the neighbors of a vertex. The function should take a vertex and return a list of vertices. For a graph,neighbors
is by default theneighbors()
function of the graph. For a digraph, theneighbors
function defaults to theneighbor_out_iterator()
function of the graph.
See also
breadth_first_search()
breadth_first_search
– breadthfirst search for fast compiled graphs.depth_first_search
– depthfirst search for fast compiled graphs.
EXAMPLES:
sage: G = Graph( { 0: [1], 1: [2], 2: [3], 3: [4], 4: [0]} ) sage: list(G.depth_first_search(0)) [0, 4, 3, 2, 1]
By default, the edge direction of a digraph is respected, but this can be overridden by the
ignore_direction
parameter:sage: D = DiGraph( { 0: [1,2,3], 1: [4,5], 2: [5], 3: [6], 5: [7], 6: [7], 7: [0]}) sage: list(D.depth_first_search(0)) [0, 3, 6, 7, 2, 5, 1, 4] sage: list(D.depth_first_search(0, ignore_direction=True)) [0, 7, 6, 3, 5, 2, 1, 4]
Multiple starting vertices can be specified in a list:
sage: D = DiGraph( { 0: [1,2,3], 1: [4,5], 2: [5], 3: [6], 5: [7], 6: [7], 7: [0]}) sage: list(D.depth_first_search([0])) [0, 3, 6, 7, 2, 5, 1, 4] sage: list(D.depth_first_search([0,6])) [0, 3, 6, 7, 2, 5, 1, 4]
More generally, you can specify a
neighbors
function. For example, you can traverse the graph backwards by settingneighbors
to be theneighbors_in()
function of the graph:sage: D = digraphs.Path(10) sage: D.add_path([22,23,24,5]) sage: D.add_path([5,33,34,35]) sage: list(D.depth_first_search(5, neighbors=D.neighbors_in)) [5, 4, 3, 2, 1, 0, 24, 23, 22] sage: list(D.breadth_first_search(5, neighbors=D.neighbors_in)) [5, 24, 4, 23, 3, 22, 2, 1, 0] sage: list(D.depth_first_search(5, neighbors=D.neighbors_out)) [5, 6, 7, 8, 9, 33, 34, 35] sage: list(D.breadth_first_search(5, neighbors=D.neighbors_out)) [5, 33, 6, 34, 7, 35, 8, 9]

diameter
(by_weight=False, algorithm=None, weight_function=None, check_weight=True)¶ Returns the diameter of the (di)graph.
The diameter is defined to be the maximum distance between two vertices. It is infinite if the (di)graph is not (strongly) connected.
For more information and examples on how to use input variables, see
shortest_paths()
andeccentricity()
INPUT:
by_weight
 ifTrue
, edge weights are taken into account; if False, all edges have weight 1.algorithm
(string)  one of the following algorithms:'BFS'
 the computation is done through a BFS centered on each vertex successively. Works only ifby_weight==False
.'FloydWarshallCython'
 a Cython implementation of the FloydWarshall algorithm. Works only ifby_weight==False
.'FloydWarshallPython'
 a Python implementation of the FloydWarshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed).'Dijkstra_NetworkX'
: the Dijkstra algorithm, implemented in NetworkX. It works with weighted graphs, but no negative weight is allowed.'standard'
,'2sweep'
,'multisweep'
,'iFUB'
: these algorithms are implemented insage.graphs.distances_all_pairs.diameter()
They work only ifby_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'
ifby_weight
isFalse
,'Dijkstra_Boost'
if all weights are positive,'Johnson_Boost'
, otherwise.
weight_function
(function)  a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
as a weight.check_weight
(boolean)  ifTrue
, 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: G = graphs.BarbellGraph(9, 3) sage: G.radius() 3 sage: G.diameter() 6
sage: G = graphs.OctahedralGraph() sage: G.radius() 2 sage: G.diameter() 2

disjoint_routed_paths
(pairs, solver=None, verbose=0)¶ Return a set of disjoint routed paths.
Given a set of pairs \((s_i,t_i)\), a set of disjoint routed paths is a set of \(s_it_i\) paths which can intersect at their endpoints and are vertexdisjoint otherwise.
INPUT:
pairs
– list of pairs of verticessolver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
(integer) – sets the level of verbosity. Set to \(0\) by default (quiet).
EXAMPLES:
Given a grid, finding two vertexdisjoint paths, the first one from the topleft corner to the bottomleft corner, and the second from the topright corner to the bottomright corner is easy
sage: g = graphs.GridGraph([5,5]) sage: p1,p2 = g.disjoint_routed_paths( [((0,0), (0,4)), ((4,4), (4,0))])
Though there is obviously no solution to the problem in which each corner is sending information to the opposite one:
sage: g = graphs.GridGraph([5,5]) sage: p1,p2 = g.disjoint_routed_paths( [((0,0), (4,4)), ((0,4), (4,0))]) Traceback (most recent call last): ... EmptySetError: The disjoint routed paths do not exist.

disjoint_union
(other, labels='pairs', immutable=None)¶ Return the disjoint union of self and other.
INPUT:
labels
 (defaults to ‘pairs’) If set to ‘pairs’, each elementv
in the first graph will be named(0,v)
and each elementu
inother
will be named(1,u)
in the result. If set to ‘integers’, the elements of the result will be relabeled with consecutive integers.immutable
(boolean) – whether to create a mutable/immutable disjoint union.immutable=None
(default) means that the graphs and their disjoint union will behave the same way.
EXAMPLES:
sage: G = graphs.CycleGraph(3) sage: H = graphs.CycleGraph(4) sage: J = G.disjoint_union(H); J Cycle graph disjoint_union Cycle graph: Graph on 7 vertices sage: J.vertices() [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (1, 3)] sage: J = G.disjoint_union(H, labels='integers'); J Cycle graph disjoint_union Cycle graph: Graph on 7 vertices sage: J.vertices() [0, 1, 2, 3, 4, 5, 6] sage: (G+H).vertices() # '+'operator is a shortcut [0, 1, 2, 3, 4, 5, 6]
sage: G=Graph({'a': ['b']}) sage: G.name("Custom path") sage: G.name() 'Custom path' sage: H=graphs.CycleGraph(3) sage: J=G.disjoint_union(H); J Custom path disjoint_union Cycle graph: Graph on 5 vertices sage: J.vertices() [(0, 'a'), (0, 'b'), (1, 0), (1, 1), (1, 2)]

disjunctive_product
(other)¶ Returns the disjunctive product of self and other.
The disjunctive product of \(G\) and \(H\) is the graph \(L\) with vertex set \(V(L)=V(G)\times V(H)\), and \(((u,v), (w,x))\) is an edge iff either :
 \((u, w)\) is an edge of \(G\), or
 \((v, x)\) is an edge of \(H\).
EXAMPLES:
sage: Z = graphs.CompleteGraph(2) sage: D = Z.disjunctive_product(Z); D Graph on 4 vertices sage: D.plot() # long time Graphics object consisting of 11 graphics primitives
sage: C = graphs.CycleGraph(5) sage: D = C.disjunctive_product(Z); D Graph on 10 vertices sage: D.plot() # long time Graphics object consisting of 46 graphics primitives

distance
(u, v, by_weight=False)¶ Returns the (directed) distance from u to v in the (di)graph, i.e. the length of the shortest path from u to v.
This method simply calls
shortest_path_length()
, with default arguments. For more information, and for more option, we refer to that method.INPUT:
by_weight
 ifFalse
, the graph is considered unweighted, and the distance is the number of edges in a shortest path. IfTrue
, the distance is the sum of edge labels (which are assumed to be numbers).
EXAMPLES:
sage: G = graphs.CycleGraph(9) sage: G.distance(0,1) 1 sage: G.distance(0,4) 4 sage: G.distance(0,5) 4 sage: G = Graph({0:[], 1:[]}) sage: G.distance(0,1) +Infinity sage: G = Graph({ 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2}}, sparse = True) sage: G.plot(edge_labels=True).show() # long time sage: G.distance(0, 3) 2 sage: G.distance(0, 3, by_weight=True) 3

distance_all_pairs
(by_weight=False, algorithm=None, weight_function=None, check_weight=True)¶ Returns the distances between all pairs of vertices.
INPUT:
by_weight
(boolean)  ifTrue
, the edges in the graph are weighted; ifFalse
, all edges have weight 1.algorithm
(string)  one of the following algorithms:'BFS'
 the computation is done through a BFS centered on each vertex successively. Works only ifby_weight==False
.'FloydWarshallCython'
 the Cython implementation of the FloydWarshall algorithm. Works only ifby_weight==False
.'FloydWarshallPython'
 the Python implementation of the FloydWarshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed).'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).None
(default): Sage chooses the best algorithm:'BFS'
ifby_weight
isFalse
,'Dijkstra_Boost'
if all weights are positive,'FloydWarshallCython'
otherwise.
weight_function
(function)  a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
as a weight.check_weight
(boolean)  ifTrue
, we check that the weight_function outputs a number for each edge.
OUTPUT:
A doubly indexed dictionary
Note
There is a Cython version of this method that is usually much faster for large graphs, as most of the time is actually spent building the final double dictionary. Everything on the subject is to be found in the
distances_all_pairs
module.Note
This algorithm simply calls
GenericGraph.shortest_path_all_pairs()
, and we suggest to look at that method for more information and examples.EXAMPLES:
The Petersen Graph:
sage: g = graphs.PetersenGraph() sage: print(g.distance_all_pairs()) {0: {0: 0, 1: 1, 2: 2, 3: 2, 4: 1, 5: 1, 6: 2, 7: 2, 8: 2, 9: 2}, 1: {0: 1, 1: 0, 2: 1, 3: 2, 4: 2, 5: 2, 6: 1, 7: 2, 8: 2, 9: 2}, 2: {0: 2, 1: 1, 2: 0, 3: 1, 4: 2, 5: 2, 6: 2, 7: 1, 8: 2, 9: 2}, 3: {0: 2, 1: 2, 2: 1, 3: 0, 4: 1, 5: 2, 6: 2, 7: 2, 8: 1, 9: 2}, 4: {0: 1, 1: 2, 2: 2, 3: 1, 4: 0, 5: 2, 6: 2, 7: 2, 8: 2, 9: 1}, 5: {0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 0, 6: 2, 7: 1, 8: 1, 9: 2}, 6: {0: 2, 1: 1, 2: 2, 3: 2, 4: 2, 5: 2, 6: 0, 7: 2, 8: 1, 9: 1}, 7: {0: 2, 1: 2, 2: 1, 3: 2, 4: 2, 5: 1, 6: 2, 7: 0, 8: 2, 9: 1}, 8: {0: 2, 1: 2, 2: 2, 3: 1, 4: 2, 5: 1, 6: 1, 7: 2, 8: 0, 9: 2}, 9: {0: 2, 1: 2, 2: 2, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 8: 2, 9: 0}}
Testing on Random Graphs:
sage: g = graphs.RandomGNP(20,.3) sage: distances = g.distance_all_pairs() sage: all([g.distance(0,v) == distances[0][v] for v in g]) True

distance_graph
(dist)¶ Returns 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
is a nonnegative integer or a list of nonnegative integers.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: G = graphs.CompleteGraph(3) sage: H = G.cartesian_product(graphs.CompleteGraph(2)) sage: K = H.distance_graph(2) sage: K.am() [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 arange()
command to create the input, usingd+1
as the input torange
. Notice that this will include distance 0 and hence place a loop at each vertex. To avoid this, userange(1,d+1)
.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
A complete collection of distance graphs will have adjacency matrices that sum to the matrix of all ones.
sage: P = graphs.PathGraph(20) sage: all_ones = sum([P.distance_graph(i).am() for i in range(20)]) sage: all_ones == matrix(ZZ, 20, 20, [1]*400) True
Fourbit strings differing in one bit is the same as fourbit strings differing in three bits.
sage: G = graphs.CubeGraph(4) sage: H = G.distance_graph(3) sage: G.is_isomorphic(H) True
The graph of eightbit strings, adjacent if different in an odd number of bits.
sage: G = graphs.CubeGraph(8) # long time sage: H = G.distance_graph([1,3,5,7]) # long time sage: degrees = [0]*sum([binomial(8,j) for j in [1,3,5,7]]) # long time sage: degrees.append(2^8) # long time sage: degrees == H.degree_histogram() # long time True
An example of using
Infinity
as the distance in a graph that is not connected.sage: G = graphs.CompleteGraph(3) sage: H = G.disjoint_union(graphs.CompleteGraph(2)) sage: L = H.distance_graph(Infinity) sage: L.am() [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]
AUTHOR:
Rob Beezer, 20091125

distance_matrix
()¶ Return the distance matrix of (di)graph.
The (di)graph is expected to be (strongly) connected.
The distance matrix of a (strongly) connected (di)graph is a matrix whose rows and columns are indexed with the positions of the vertices of the (di)graph in the ordering
G.vertices()
. The intersection of a row and a column contains the respective distance between the vertices indexed at these positions.Note that even when the vertices are consecutive integers starting from one, usually the vertex is not equal to it’s index.
EXAMPLES:
sage: d = DiGraph({1: [2, 3], 2: [3], 3: [4], 4: [1]}) sage: d.distance_matrix() [0 1 1 2] [1 0 1 2] [1 1 0 1] [2 2 1 0] sage: G = graphs.CubeGraph(3) sage: G.distance_matrix() [0 1 1 2 1 2 2 3] [1 0 2 1 2 1 3 2] [1 2 0 1 2 3 1 2] [2 1 1 0 3 2 2 1] [1 2 2 3 0 1 1 2] [2 1 3 2 1 0 2 1] [2 3 1 2 1 2 0 1] [3 2 2 1 2 1 1 0]
The well known result of Graham and Pollak states that the determinant of the distance matrix of any tree of order n is \((1)^{n1}(n1)2^{n2}\):
sage: all(T.distance_matrix().det() == (1)^9*(9)*2^8 for T in graphs.trees(10)) True
See also
distance_all_pairs()
– computes the distance between any two vertices.

distances_distribution
(G)¶ Returns the distances distribution of the (di)graph in a dictionary.
This method ignores all edge labels, so that the distance considered is the topological distance.
OUTPUT:
A dictionaryd
such that the number of pairs of vertices at distancek
(if any) is equal to \(d[k] \cdot V(G) \cdot (V(G)1)\).Note
We consider that two vertices that do not belong to the same connected component are at infinite distance, and we do not take the trivial pairs of vertices \((v, v)\) at distance \(0\) into account. Empty (di)graphs and (di)graphs of order 1 have no paths and so we return the empty dictionary
{}
.EXAMPLES:
An empty Graph:
sage: g = Graph() sage: g.distances_distribution() {}
A Graph of order 1:
sage: g = Graph() sage: g.add_vertex(1) sage: g.distances_distribution() {}
A Graph of order 2 without edge:
sage: g = Graph() sage: g.add_vertices([1,2]) sage: g.distances_distribution() {+Infinity: 1}
The Petersen Graph:
sage: g = graphs.PetersenGraph() sage: g.distances_distribution() {1: 1/3, 2: 2/3}
A graph with multiple disconnected components:
sage: g = graphs.PetersenGraph() sage: g.add_edge('good','wine') sage: g.distances_distribution() {1: 8/33, 2: 5/11, +Infinity: 10/33}
The de Bruijn digraph dB(2,3):
sage: D = digraphs.DeBruijn(2,3) sage: D.distances_distribution() {1: 1/4, 2: 11/28, 3: 5/14}

dominating_set
(independent=False, total=False, value_only=False, solver=None, verbose=0)¶ Return a minimum dominating set of the graph.
A minimum dominating set \(S\) of a graph \(G\) is a set of its vertices of minimal cardinality such that any vertex of \(G\) is in \(S\) or has one of its neighbors in \(S\). See the Wikipedia article Dominating_set.
As an optimization problem, it can be expressed as:
\[\begin{split}\mbox{Minimize : }&\sum_{v\in G} b_v\\ \mbox{Such that : }&\forall v \in G, b_v+\sum_{(u,v)\in G.edges()} b_u\geq 1\\ &\forall x\in G, b_x\mbox{ is a binary variable}\end{split}\]INPUT:
independent
– boolean (default:False
). Ifindependent=True
, computes a minimum independent dominating set.total
– boolean (default:False
). Iftotal=True
, computes a total dominating set.value_only
– boolean (default:False
) If
True
, only the cardinality of a minimum dominating set is returned.  If
False
(default), a minimum dominating set is returned as the list of its vertices.
 If
solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.
EXAMPLES:
A basic illustration on a
PappusGraph
:sage: g=graphs.PappusGraph() sage: g.dominating_set(value_only=True) 5
If we build a graph from two disjoint stars, then link their centers we will find a difference between the cardinality of an independent set and a stable independent set:
sage: g = 2 * graphs.StarGraph(5) sage: g.add_edge(0,6) sage: len(g.dominating_set()) 2 sage: len(g.dominating_set(independent=True)) 6
The total dominating set of the Petersen graph has cardinality 4:
sage: G = graphs.PetersenGraph() sage: G.dominating_set(total=True,value_only=True) 4
The dominating set is calculated for both the directed and undirected graphs (modification introduced in trac ticket #17905):
sage: g=digraphs.Path(3) sage: g.dominating_set(value_only=True) 2 sage: g=graphs.PathGraph(3) sage: g.dominating_set(value_only=True) 1

dominator_tree
(g, root, return_dict=False, reverse=False)¶ Uses Boost to compute the dominator tree of
g
, rooted atroot
.A node \(d\) dominates a node \(n\) if every path from the entry node
root
to \(n\) must go through \(d\). The immediate dominator of a node \(n\) is the unique node that strictly dominates \(n\) but does not dominate any other node that dominates \(n\). A dominator tree is a tree where each node’s children are those nodes it immediately dominates. For more information, see the Wikipedia article Dominator_(graph_theory).If the graph is connected and undirected, the parent of a vertex \(v\) is:
 the root if \(v\) is in the same biconnected component as the root;
 the first cut vertex in a path from \(v\) to the root, otherwise.
If the graph is not connected, the dominator tree of the whole graph is equal to the dominator tree of the connected component of the root.
If the graph is directed, computing a dominator tree is more complicated, and it needs time \(O(m\log m)\), where \(m\) is the number of edges. The implementation provided by Boost is the most general one, so it needs time \(O(m\log m)\) even for undirected graphs.
INPUT:
g
(generic_graph)  the input graph.root
(vertex)  the root of the dominator tree.return_dict
(boolean)  ifTrue
, the function returns a dictionary associating to each vertex its parent in the dominator tree. IfFalse
(default), it returns the whole tree, as aGraph
or aDiGraph
.reverse
 boolean (default:False
); when set toTrue
, computes the dominator tree in the reverse graph.
OUTPUT:
The dominator tree, as a graph or as a dictionary, depending on the value of
return_dict
. If the output is a dictionary, it will containNone
in correspondence ofroot
and of vertices that are not reachable fromroot
. If the output is a graph, it will not contain vertices that are not reachable fromroot
.EXAMPLES:
An undirected grid is biconnected, and its dominator tree is a star (everyone’s parent is the root):
sage: g = graphs.GridGraph([2,2]).dominator_tree((0,0)) sage: g.to_dictionary() {(0, 0): [(0, 1), (1, 0), (1, 1)], (0, 1): [(0, 0)], (1, 0): [(0, 0)], (1, 1): [(0, 0)]}
If the graph is made by two 3cycles \(C_1,C_2\) connected by an edge \((v,w)\), with \(v \in C_1\), \(w \in C_2\), the cut vertices are \(v\) and \(w\), the biconnected components are \(C_1\), \(C_2\), and the edge \((v,w)\). If the root is in \(C_1\), the parent of each vertex in \(C_1\) is the root, the parent of \(w\) is \(v\), and the parent of each vertex in \(C_2\) is \(w\):
sage: G = 2 * graphs.CycleGraph(3) sage: v = 0 sage: w = 3 sage: G.add_edge(v,w) sage: G.dominator_tree(1, return_dict=True) {0: 1, 1: None, 2: 1, 3: 0, 4: 3, 5: 3}
An example with a directed graph:
sage: g = digraphs.Circuit(10).dominator_tree(5) sage: g.to_dictionary() {0: [1], 1: [2], 2: [3], 3: [4], 4: [], 5: [6], 6: [7], 7: [8], 8: [9], 9: [0]} sage: g = digraphs.Circuit(10).dominator_tree(5, reverse=True) sage: g.to_dictionary() {0: [9], 1: [0], 2: [1], 3: [2], 4: [3], 5: [4], 6: [], 7: [6], 8: [7], 9: [8]}
If the output is a dictionary:
sage: graphs.GridGraph([2,2]).dominator_tree((0,0), return_dict=True) {(0, 0): None, (0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (0, 0)}

eccentricity
(v=None, by_weight=False, algorithm=None, weight_function=None, check_weight=True, dist_dict=None, with_labels=False)¶ 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_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
 ifTrue
, edge weights are taken into account; if False, all edges have weight 1.algorithm
(string)  one of the following algorithms:'BFS'
 the computation is done through a BFS centered on each vertex successively. Works only ifby_weight==False
.'FloydWarshallCython'
 a Cython implementation of the FloydWarshall algorithm. Works only ifby_weight==False
andv is None
.'FloydWarshallPython'
 a Python implementation of the FloydWarshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed). However,v
must beNone
.'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).'From_Dictionary'
: uses the (already computed) distances, that are provided by input variabledist_dict
.None
(default): Sage chooses the best algorithm:'From_Dictionary'
ifdist_dict
is not None,'BFS'
for unweighted graphs,'Dijkstra_Boost'
if all weights are positive,'Johnson_Boost'
otherwise.
weight_function
(function)  a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
as a weight.check_weight
(boolean)  ifTrue
, we check that the weight_function outputs a number for each edge.dist_dict
 used only ifalgorithm=='From_Dictionary'
 a dict of dicts of distances.with_labels
 Whether to return a list or a dict.
EXAMPLES:
sage: G = graphs.KrackhardtKiteGraph() sage: G.eccentricity() [4, 4, 4, 4, 4, 3, 3, 2, 3, 4] sage: G.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: G.eccentricity(7) 2 sage: G.eccentricity([7,8,9]) [3, 4, 2] 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 = 'FloydWarshallCython') [1, 1, 1] sage: G.eccentricity(by_weight = True, algorithm = 'Dijkstra_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 = 'FloydWarshallPython') [2, 1, 2] sage: G.eccentricity(dist_dict = G.shortest_path_all_pairs(by_weight = True)[0]) [2, 1, 2]

edge_boundary
(vertices1, vertices2=None, labels=True, sort=False)¶ Return a list of edges \((u,v,l)\) with \(u\) in
vertices1
and \(v\) invertices2
.If
vertices2
isNone
, then it is set to the complement ofvertices1
.In a digraph, the external boundary of a vertex \(v\) are those vertices \(u\) with an arc \((v, u)\).
INPUT:
labels
– ifFalse
, each edge is a tuple \((u,v)\) of vertices.sort
– boolean (defaultFalse
) whether to sort the result
EXAMPLES:
sage: K = graphs.CompleteBipartiteGraph(9,3) sage: len(K.edge_boundary( [0,1,2,3,4,5,6,7,8], [9,10,11] )) 27 sage: K.size() 27
Note that the edge boundary preserves direction:
sage: K = graphs.CompleteBipartiteGraph(9,3).to_directed() sage: len(K.edge_boundary( [0,1,2,3,4,5,6,7,8], [9,10,11] )) 27 sage: K.size() 54
sage: D = DiGraph({0:[1,2], 3:[0]}) sage: D.edge_boundary([0], sort=True) [(0, 1, None), (0, 2, None)] sage: D.edge_boundary([0], labels=False, sort=True) [(0, 1), (0, 2)]

edge_connectivity
(G, value_only=True, implementation=None, use_edge_labels=False, vertices=False, solver=None, verbose=0)¶ Returns the edge connectivity of the graph.
For more information, see the Wikipedia article Connectivity_(graph_theory).
Note
When the graph is a directed graph, this method actually computes the strong connectivity, (i.e. a directed graph is strongly \(k\)connected if there are \(k\) disjoint paths between any two vertices \(u, v\)). If you do not want to consider strong connectivity, the best is probably to convert your
DiGraph
object to aGraph
object, and compute the connectivity of this other graph.INPUT:
G
(generic_graph)  the input graph.value_only
– boolean (default:True
) When set to
True
(default), only the value is returned.  When set to
False
, both the value and a minimum edge cut are returned.
 When set to
implementation
– selects an implementation: When set to
None
(default): selects the best implementation available.  When set to
"boost"
, we use the Boost graph library (which is much more efficient). It is not available whenedge_labels=True
, and it is unreliable for directed graphs (see trac ticket #18753).  When set to
"Sage"
, we use Sage’s implementation.
 When set to
use_edge_labels
– boolean (default:False
) When set to
True
, computes a weighted minimum cut where each edge has a weight defined by its label. (If an edge has no label, \(1\) is assumed.). Impliesboost
=False
.  When set to
False
, each edge has weight \(1\).
 When set to
vertices
– boolean (default:False
) When set to
True
, also returns the two sets of vertices that are disconnected by the cut. Impliesvalue_only=False
.
 When set to
solver
– (default:None
) Specify a Linear Program (LP) solver to be used (ignored ifimplementation='boost'
). If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.
EXAMPLES:
A basic application on the PappusGraph:
sage: from sage.graphs.connectivity import edge_connectivity sage: g = graphs.PappusGraph() sage: edge_connectivity(g) 3 sage: g.edge_connectivity() 3
The edge connectivity of a complete graph ( and of a random graph ) is its minimum degree, and one of the two parts of the bipartition is reduced to only one vertex. The cutedges isomorphic to a Star graph:
sage: g = graphs.CompleteGraph(5) sage: [ value, edges, [ setA, setB ]] = edge_connectivity(g,vertices=True) sage: value 4 sage: len(setA) == 1 or len(setB) == 1 True sage: cut = Graph() sage: cut.add_edges(edges) sage: cut.is_isomorphic(graphs.StarGraph(4)) True
Even if obviously in any graph we know that the edge connectivity is less than the minimum degree of the graph:
sage: g = graphs.RandomGNP(10,.3) sage: min(g.degree()) >= edge_connectivity(g) True
If we build a tree then assign to its edges a random value, the minimum cut will be the edge with minimum value:
sage: g = graphs.RandomGNP(15,.5) sage: tree = Graph() sage: tree.add_edges(g.min_spanning_tree()) sage: for u,v in tree.edge_iterator(labels=None): ....: tree.set_edge_label(u,v,random()) sage: minimum = min([l for u,v,l in tree.edge_iterator()]) sage: [value, [(u,v,l)]] = edge_connectivity(tree, value_only=False, use_edge_labels=True) sage: l == minimum True
When
value_only = True
andimplementation="sage"
, this function is optimized for small connectivity values and does not need to build a linear program.It is the case for graphs which are not connected
sage: g = 2 * graphs.PetersenGraph() sage: edge_connectivity(g, implementation="sage") 0.0
For directed graphs, the strong connectivity is tested through the dedicated function
sage: g = digraphs.ButterflyGraph(3) sage: edge_connectivity(g, implementation="sage") 0.0
We check that the result with Boost is the same as the result without Boost
sage: g = graphs.RandomGNP(15,.3) sage: edge_connectivity(g) == edge_connectivity(g, implementation="sage") True
Boost interface also works with directed graphs
sage: edge_connectivity(digraphs.Circuit(10), implementation = "boost", vertices = True) [1, [(0, 1)], [{0}, {1, 2, 3, 4, 5, 6, 7, 8, 9}]]
However, the Boost algorithm is not reliable if the input is directed (see trac ticket #18753):
sage: g = digraphs.Path(3) sage: edge_connectivity(g) 0.0 sage: edge_connectivity(g, implementation="boost") 1 sage: g.add_edge(1,0) sage: edge_connectivity(g) 0.0 sage: edge_connectivity(g, implementation="boost") 0

edge_cut
(s, t, value_only=True, use_edge_labels=False, vertices=False, algorithm='FF', solver=None, verbose=0)¶ Return a minimum edge cut between vertices \(s\) and \(t\).
A minimum edge cut between two vertices \(s\) and \(t\) of self is a set \(A\) of edges of minimum weight such that the graph obtained by removing \(A\) from the graph is disconnected. For more information, see the Wikipedia article Cut_(graph_theory).
INPUT:
s
– source vertext
– sink vertexvalue_only
– boolean (default:True
). When set toTrue
, only the weight of a minimum cut is returned. Otherwise, a list of edges of a minimum cut is also returned.use_edge_labels
– boolean (default:False
). When set toTrue
, computes a weighted minimum cut where each edge has a weight defined by its label (if an edge has no label, \(1\) is assumed). Otherwise, each edge has weight \(1\).vertices
– boolean (default:False
). When set toTrue
, returns a list of edges in the edge cut and the two sets of vertices that are disconnected by the cut.Note:
vertices=True
impliesvalue_only=False
.algorithm
– algorithm to use: If
algorithm = "FF"
, a Python implementation of the FordFulkerson algorithm is used  If
algorithm = "LP"
, the flow problem is solved using Linear Programming.  If
algorithm = "igraph"
, the igraph implementation of the GoldbergTarjan algorithm is used (only available when igraph is installed)  If
algorithm = None
(default), we useLP
ifvertex_bound = True
, otherwise, we useigraph
if it is available,FF
if it is not available.
 If
solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.
Note
The use of Linear Programming for noninteger problems may possibly mean the presence of a (slight) numerical noise.
OUTPUT:
Real number or tuple, depending on the given arguments (examples are given below).
EXAMPLES:
A basic application in the Pappus graph:
sage: g = graphs.PappusGraph() sage: g.edge_cut(1, 2, value_only=True) 3
Or on Petersen’s graph, with the corresponding bipartition of the vertex set:
sage: g = graphs.PetersenGraph() sage: g.edge_cut(0, 3, vertices=True) [3, [(0, 1, None), (0, 4, None), (0, 5, None)], [[0], [1, 2, 3, 4, 5, 6, 7, 8, 9]]]
If the graph is a path with randomly weighted edges:
sage: g = graphs.PathGraph(15) sage: for (u,v) in g.edge_iterator(labels=None): ....: g.set_edge_label(u,v,random())
The edge cut between the two ends is the edge of minimum weight:
sage: minimum = min([l for u,v,l in g.edge_iterator()]) sage: minimum == g.edge_cut(0, 14, use_edge_labels=True) True sage: [value,[e]] = g.edge_cut(0, 14, use_edge_labels=True, value_only=False) sage: g.edge_label(e[0],e[1]) == minimum True
The two sides of the edge cut are obviously shorter paths:
sage: value,edges,[set1,set2] = g.edge_cut(0, 14, use_edge_labels=True, vertices=True) sage: g.subgraph(set1).is_isomorphic(graphs.PathGraph(len(set1))) True sage: g.subgraph(set2).is_isomorphic(graphs.PathGraph(len(set2))) True sage: len(set1) + len(set2) == g.order() True

edge_disjoint_paths
(s, t, algorithm='FF', solver=None, verbose=False)¶ Return a list of edgedisjoint paths between two vertices.
The edge version of Menger’s theorem asserts that the size of the minimum edge cut between two vertices \(s\) and`t` (the minimum number of edges whose removal disconnects \(s\) and \(t\)) is equal to the maximum number of pairwise edgeindependent paths from \(s\) to \(t\).
This function returns a list of such paths.
INPUT:
algorithm
– There are currently two different implementations of this method : If
algorithm = "FF"
(default), a Python implementation of the FordFulkerson algorithm is used.  If
algorithm = "LP"
, the flow problem is solved using Linear Programming.
 If
solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.
Note
This function is topological: it does not take the eventual weights of the edges into account.
EXAMPLES:
In a complete bipartite graph
sage: g = graphs.CompleteBipartiteGraph(2,3) sage: g.edge_disjoint_paths(0,1) [[0, 2, 1], [0, 3, 1], [0, 4, 1]]

edge_disjoint_spanning_trees
(k, root=None, solver=None, verbose=0)¶ Return the desired number of edgedisjoint spanning trees/arborescences.
INPUT:
k
(integer) – the required number of edgedisjoint spanning trees/arborescencesroot
(vertex) – root of the disjoint arborescences when the graph is directed. If set toNone
, the first vertex in the graph is picked.solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.
ALGORITHM:
Mixed Integer Linear Program. The formulation can be found in [LPForm].
There are at least two possible rewritings of this method which do not use Linear Programming:
 The algorithm presented in the paper entitled “A short proof of the treepacking theorem”, by Thomas Kaiser [KaisPacking].
 The implementation of a Matroid class and of the Matroid Union Theorem (see section 42.3 of [SchrijverCombOpt]), applied to the cycle Matroid (see chapter 51 of [SchrijverCombOpt]).
EXAMPLES:
The Petersen Graph does have a spanning tree (it is connected):
sage: g = graphs.PetersenGraph() sage: [T] = g.edge_disjoint_spanning_trees(1) sage: T.is_tree() True
Though, it does not have 2 edgedisjoint trees (as it has less than \(2(V1)\) edges):
sage: g.edge_disjoint_spanning_trees(2) Traceback (most recent call last): ... EmptySetError: This graph does not contain the required number of trees/arborescences !
By Edmond’s theorem, a graph which is \(k\)connected always has \(k\) edgedisjoint arborescences, regardless of the root we pick:
sage: g = digraphs.RandomDirectedGNP(28,.3) # reduced from 30 to 28, cf. #9584 sage: k = Integer(g.edge_connectivity()) sage: arborescences = g.edge_disjoint_spanning_trees(k) # long time (up to 15s on sage.math, 2011) sage: all([a.is_directed_acyclic() for a in arborescences]) # long time True sage: all([a.is_connected() for a in arborescences]) # long time True
In the undirected case, we can only ensure half of it:
sage: g = graphs.RandomGNP(30,.3) sage: k = floor(Integer(g.edge_connectivity())/2) sage: trees = g.edge_disjoint_spanning_trees(k) sage: all([t.is_tree() for t in trees]) True
REFERENCES:
[LPForm] Nathann Cohen, Several Graph problems and their Linear Program formulations, https://hal.archivesouvertes.fr/inria00504914/en [KaisPacking] Thomas Kaiser A short proof of the treepacking theorem Arxiv 0911.2809 [SchrijverCombOpt] (1, 2) Alexander Schrijver Combinatorial optimization: polyhedra and efficiency 2003

edge_iterator
(vertices=None, labels=True, ignore_direction=False)¶ Returns an iterator over edges.
The iterator returned is over the edges incident with any vertex given in the parameter
vertices
. If the graph is directed, iterates over edges going out only. If vertices is None, then returns an iterator over all edges. If self is directed, returns outgoing edges only.INPUT:
vertices
 (default: None) a vertex, a list of vertices or Nonelabels
 if False, each edge is a tuple (u,v) of vertices.ignore_direction
 bool (default: False)  only applies to directed graphs. If True, searches across edges in either direction.
EXAMPLES:
sage: for i in graphs.PetersenGraph().edge_iterator([0]): ....: print(i) (0, 1, None) (0, 4, None) (0, 5, None) sage: D = DiGraph( { 0 : [1,2], 1: [0] } ) sage: for i in D.edge_iterator([0]): ....: print(i) (0, 1, None) (0, 2, None)
sage: G = graphs.TetrahedralGraph() sage: list(G.edge_iterator(labels=False)) [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
sage: D = DiGraph({1:[0], 2:[0]}) sage: list(D.edge_iterator(0)) [] sage: list(D.edge_iterator(0, ignore_direction=True)) [(1, 0, None), (2, 0, None)]

edge_label
(u, v)¶ Return the label of an edge.
If the graph allows multiple edges, then the list of labels on the edges is returned.
See also
EXAMPLES:
sage: G = Graph({0 : {1 : 'edgelabel'}}) sage: G.edge_label(0, 1) 'edgelabel' sage: D = DiGraph({1 : {2: 'up'}, 2: {1: 'down'}}) sage: D.edge_label(2, 1) 'down'
sage: G = Graph(multiedges=True) sage: [G.add_edge(0, 1, i) for i in range(1, 6)] [None, None, None, None, None] sage: sorted(G.edge_label(0, 1)) [1, 2, 3, 4, 5]

edge_labels
()¶ Return a list of edge labels.
EXAMPLES:
sage: G = Graph({0:{1:'x',2:'z',3:'a'}, 2:{5:'out'}}, sparse=True) sage: G.edge_labels() ['x', 'z', 'a', 'out'] sage: G = DiGraph({0:{1:'x',2:'z',3:'a'}, 2:{5:'out'}}, sparse=True) sage: G.edge_labels() ['x', 'z', 'a', 'out']

edges
(labels=True, sort=True, key=None)¶ Return a list of edges.
Each edge is a triple (u,v,l) where u and v are vertices and l is a label. If the parameter
labels
is False then a list of couple (u,v) is returned where u and v are vertices.INPUT:
labels
 default:True
 ifFalse
, each edge is simply a pair (u,v) of vertices.sort
 default:True
 ifTrue
, edges are sorted according to the default ordering.key
 default:None
 a function takes an edge (a pair or a triple, according to thelabels
keyword) as its one argument and returns a value that can be used for comparisons in the sorting algorithm.
OUTPUT: A list of tuples. It is safe to change the returned list.
Warning
Since any object may be a vertex, there is no guarantee that any two vertices will be comparable, and thus no guarantee how two edges may compare. With default objects for vertices (all integers), or when all the vertices are of the same simple type, then there should not be a problem with how the vertices will be sorted. However, if you need to guarantee a total order for the sorting of the edges, use the
key
argument, as illustrated in the examples below.EXAMPLES:
sage: graphs.DodecahedralGraph().edges() [(0, 1, None), (0, 10, None), (0, 19, None), (1, 2, None), (1, 8, None), (2, 3, None), (2, 6, None), (3, 4, None), (3, 19, None), (4, 5, None), (4, 17, None), (5, 6, None), (5, 15, None), (6, 7, None), (7, 8, None), (7, 14, None), (8, 9, None), (9, 10, None), (9, 13, None), (10, 11, None), (11, 12, None), (11, 18, None), (12, 13, None), (12, 16, None), (13, 14, None), (14, 15, None), (15, 16, None), (16, 17, None), (17, 18, None), (18, 19, None)]
sage: graphs.DodecahedralGraph().edges(labels=False) [(0, 1), (0, 10), (0, 19), (1, 2), (1, 8), (2, 3), (2, 6), (3, 4), (3, 19), (4, 5), (4, 17), (5, 6), (5, 15), (6, 7), (7, 8), (7, 14), (8, 9), (9, 10), (9, 13), (10, 11), (11, 12), (11, 18), (12, 13), (12, 16), (13, 14), (14, 15), (15, 16), (16, 17), (17, 18), (18, 19)]
sage: D = graphs.DodecahedralGraph().to_directed() sage: D.edges() [(0, 1, None), (0, 10, None), (0, 19, None), (1, 0, None), (1, 2, None), (1, 8, None), (2, 1, None), (2, 3, None), (2, 6, None), (3, 2, None), (3, 4, None), (3, 19, None), (4, 3, None), (4, 5, None), (4, 17, None), (5, 4, None), (5, 6, None), (5, 15, None), (6, 2, None), (6, 5, None), (6, 7, None), (7, 6, None), (7, 8, None), (7, 14, None), (8, 1, None), (8, 7, None), (8, 9, None), (9, 8, None), (9, 10, None), (9, 13, None), (10, 0, None), (10, 9, None), (10, 11, None), (11, 10, None), (11, 12, None), (11, 18, None), (12, 11, None), (12, 13, None), (12, 16, None), (13, 9, None), (13, 12, None), (13, 14, None), (14, 7, None), (14, 13, None), (14, 15, None), (15, 5, None), (15, 14, None), (15, 16, None), (16, 12, None), (16, 15, None), (16, 17, None), (17, 4, None), (17, 16, None), (17, 18, None), (18, 11, None), (18, 17, None), (18, 19, None), (19, 0, None), (19, 3, None), (19, 18, None)] sage: D.edges(labels = False) [(0, 1), (0, 10), (0, 19), (1, 0), (1, 2), (1, 8), (2, 1), (2, 3), (2, 6), (3, 2), (3, 4), (3, 19), (4, 3), (4, 5), (4, 17), (5, 4), (5, 6), (5, 15), (6, 2), (6, 5), (6, 7), (7, 6), (7, 8), (7, 14), (8, 1), (8, 7), (8, 9), (9, 8), (9, 10), (9, 13), (10, 0), (10, 9), (10, 11), (11, 10), (11, 12), (11, 18), (12, 11), (12, 13), (12, 16), (13, 9), (13, 12), (13, 14), (14, 7), (14, 13), (14, 15), (15, 5), (15, 14), (15, 16), (16, 12), (16, 15), (16, 17), (17, 4), (17, 16), (17, 18), (18, 11), (18, 17), (18, 19), (19, 0), (19, 3), (19, 18)]
The default is to sort the returned list in the default fashion, as in the above examples. this can be overridden by specifying a key function. This first example just ignores the labels in the third component of the triple.
sage: G=graphs.CycleGraph(5) sage: G.edges(key = lambda x: (x[1],x[0])) [(0, 1, None), (1, 2, None), (2, 3, None), (3, 4, None), (0, 4, None)]
We set the labels to characters and then perform a default sort followed by a sort according to the labels.
sage: G=graphs.CycleGraph(5) sage: for e in G.edges(): ....: G.set_edge_label(e[0], e[1], chr(ord('A')+e[0]+5*e[1])) sage: G.edges(sort=True) [(0, 1, 'F'), (0, 4, 'U'), (1, 2, 'L'), (2, 3, 'R'), (3, 4, 'X')] sage: G.edges(key=lambda x: x[2]) [(0, 1, 'F'), (1, 2, 'L'), (2, 3, 'R'), (0, 4, 'U'), (3, 4, 'X')]

edges_incident
(vertices=None, labels=True, sort=False)¶ Return incident edges to some vertices.
If
vertices` is a vertex, then it returns the list of edges incident to that vertex. If ``vertices
is a list of vertices then it returns the list of all edges adjacent to those vertices. Ifvertices
isNone
, it returns a list of all edges in graph. For digraphs, only lists outward edges.INPUT:
vertices
– object (default:None
)  a vertex, a list of vertices orNone
.labels
– boolean (default:True
)  ifFalse
, each edge is a tuple (u,v) of vertices.
sort
– boolean (default:False
)  ifTrue
the returned list is sorted.
EXAMPLES:
sage: graphs.PetersenGraph().edges_incident([0,9], labels=False) [(0, 1), (0, 4), (0, 5), (4, 9), (6, 9), (7, 9)] sage: D = DiGraph({0:[1]}) sage: D.edges_incident([0]) [(0, 1, None)] sage: D.edges_incident([1]) []

eigenspaces
(laplacian=False)¶ Returns the right eigenspaces of the adjacency matrix of the graph.
INPUT:
laplacian
 if True, use the Laplacian matrix (seekirchhoff_matrix()
)
OUTPUT:
A list of pairs. Each pair is an eigenvalue of the adjacency matrix of the graph, followed by the vector space that is the eigenspace for that eigenvalue, when the eigenvectors are placed on the right of the matrix.
For some graphs, some of the eigenspaces are described exactly by vector spaces over a
NumberField()
. For numerical eigenvectors useeigenvectors()
.EXAMPLES:
sage: P = graphs.PetersenGraph() sage: P.eigenspaces() [ (3, Vector space of degree 10 and dimension 1 over Rational Field User basis matrix: [1 1 1 1 1 1 1 1 1 1]), (2, Vector space of degree 10 and dimension 4 over Rational Field User basis matrix: [ 1 0 0 0 1 1 1 0 1 1] [ 0 1 0 0 1 0 2 1 1 2] [ 0 0 1 0 1 1 1 2 0 2] [ 0 0 0 1 1 1 0 1 1 1]), (1, Vector space of degree 10 and dimension 5 over Rational Field User basis matrix: [ 1 0 0 0 0 1 1 0 0 1] [ 0 1 0 0 0 1 1 1 0 0] [ 0 0 1 0 0 0 1 1 1 0] [ 0 0 0 1 0 0 0 1 1 1] [ 0 0 0 0 1 1 0 0 1 1]) ]
Eigenspaces for the Laplacian should be identical since the Petersen graph is regular. However, since the output also contains the eigenvalues, the two outputs are slightly different.
sage: P.eigenspaces(laplacian=True) [ (0, Vector space of degree 10 and dimension 1 over Rational Field User basis matrix: [1 1 1 1 1 1 1 1 1 1]), (5, Vector space of degree 10 and dimension 4 over Rational Field User basis matrix: [ 1 0 0 0 1 1 1 0 1 1] [ 0 1 0 0 1 0 2 1 1 2] [ 0 0 1 0 1 1 1 2 0 2] [ 0 0 0 1 1 1 0 1 1 1]), (2, Vector space of degree 10 and dimension 5 over Rational Field User basis matrix: [ 1 0 0 0 0 1 1 0 0 1] [ 0 1 0 0 0 1 1 1 0 0] [ 0 0 1 0 0 0 1 1 1 0] [ 0 0 0 1 0 0 0 1 1 1] [ 0 0 0 0 1 1 0 0 1 1]) ]
Notice how one eigenspace below is described with a square root of 2. For the two possible values (positive and negative) there is a corresponding eigenspace.
sage: C = graphs.CycleGraph(8) sage: C.eigenspaces() [ (2, Vector space of degree 8 and dimension 1 over Rational Field User basis matrix: [1 1 1 1 1 1 1 1]), (2, Vector space of degree 8 and dimension 1 over Rational Field User basis matrix: [ 1 1 1 1 1 1 1 1]), (0, Vector space of degree 8 and dimension 2 over Rational Field User basis matrix: [ 1 0 1 0 1 0 1 0] [ 0 1 0 1 0 1 0 1]), (a3, Vector space of degree 8 and dimension 2 over Number Field in a3 with defining polynomial x^2  2 User basis matrix: [ 1 0 1 a3 1 0 1 a3] [ 0 1 a3 1 0 1 a3 1]) ]
A digraph may have complex eigenvalues and eigenvectors. For a 3cycle, we have:
sage: T = DiGraph({0:[1], 1:[2], 2:[0]}) sage: T.eigenspaces() [ (1, Vector space of degree 3 and dimension 1 over Rational Field User basis matrix: [1 1 1]), (a1, Vector space of degree 3 and dimension 1 over Number Field in a1 with defining polynomial x^2 + x + 1 User basis matrix: [ 1 a1 a1  1]) ]

eigenvectors
(laplacian=False)¶ Returns the right eigenvectors of the adjacency matrix of the graph.
INPUT:
laplacian
 if True, use the Laplacian matrix (seekirchhoff_matrix()
)
OUTPUT:
A list of triples. Each triple begins with an eigenvalue of the adjacency matrix of the graph. This is followed by a list of eigenvectors for the eigenvalue, when the eigenvectors are placed on the right side of the matrix. Together, the eigenvectors form a basis for the eigenspace. The triple concludes with the algebraic multiplicity of the eigenvalue.
For some graphs, the exact eigenspaces provided by
eigenspaces()
provide additional insight into the structure of the eigenspaces.EXAMPLES:
sage: P = graphs.PetersenGraph() sage: P.eigenvectors() [(3, [ (1, 1, 1, 1, 1, 1, 1, 1, 1, 1) ], 1), (2, [ (1, 0, 0, 0, 1, 1, 1, 0, 1, 1), (0, 1, 0, 0, 1, 0, 2, 1, 1, 2), (0, 0, 1, 0, 1, 1, 1, 2, 0, 2), (0, 0, 0, 1, 1, 1, 0, 1, 1, 1) ], 4), (1, [ (1, 0, 0, 0, 0, 1, 1, 0, 0, 1), (0, 1, 0, 0, 0, 1, 1, 1, 0, 0), (0, 0, 1, 0, 0, 0, 1, 1, 1, 0), (0, 0, 0, 1, 0, 0, 0, 1, 1, 1), (0, 0, 0, 0, 1, 1, 0, 0, 1, 1) ], 5)]
Eigenspaces for the Laplacian should be identical since the Petersen graph is regular. However, since the output also contains the eigenvalues, the two outputs are slightly different.
sage: P.eigenvectors(laplacian=True) [(0, [ (1, 1, 1, 1, 1, 1, 1, 1, 1, 1) ], 1), (5, [ (1, 0, 0, 0, 1, 1, 1, 0, 1, 1), (0, 1, 0, 0, 1, 0, 2, 1, 1, 2), (0, 0, 1, 0, 1, 1, 1, 2, 0, 2), (0, 0, 0, 1, 1, 1, 0, 1, 1, 1) ], 4), (2, [ (1, 0, 0, 0, 0, 1, 1, 0, 0, 1), (0, 1, 0, 0, 0, 1, 1, 1, 0, 0), (0, 0, 1, 0, 0, 0, 1, 1, 1, 0), (0, 0, 0, 1, 0, 0, 0, 1, 1, 1), (0, 0, 0, 0, 1, 1, 0, 0, 1, 1) ], 5)]
sage: C = graphs.CycleGraph(8) sage: C.eigenvectors() [(2, [ (1, 1, 1, 1, 1, 1, 1, 1) ], 1), (2, [ (1, 1, 1, 1, 1, 1, 1, 1) ], 1), (0, [ (1, 0, 1, 0, 1, 0, 1, 0), (0, 1, 0, 1, 0, 1, 0, 1) ], 2), (1.4142135623..., [(1, 0, 1, 1.4142135623..., 1, 0, 1, 1.4142135623...), (0, 1, 1.4142135623..., 1, 0, 1, 1.4142135623..., 1)], 2), (1.4142135623..., [(1, 0, 1, 1.4142135623..., 1, 0, 1, 1.4142135623...), (0, 1, 1.4142135623..., 1, 0, 1, 1.4142135623..., 1)], 2)]
A digraph may have complex eigenvalues. Previously, the complex parts of graph eigenvalues were being dropped. For a 3cycle, we have:
sage: T = DiGraph({0:[1], 1:[2], 2:[0]}) sage: T.eigenvectors() [(1, [ (1, 1, 1) ], 1), (0.5000000000...  0.8660254037...*I, [(1, 0.5000000000...  0.8660254037...*I, 0.5000000000... + 0.8660254037...*I)], 1), (0.5000000000... + 0.8660254037...*I, [(1, 0.5000000000... + 0.8660254037...*I, 0.5000000000...  0.8660254037...*I)], 1)]

eulerian_circuit
(return_vertices=False, labels=True, path=False)¶ Return a list of edges forming an Eulerian circuit if one exists. Otherwise return False.
This is implemented using Hierholzer’s algorithm.
INPUT:
return_vertices
– (default:False
) optionally provide a list of vertices for the pathlabels
– (default:True
) whether to return edges with labels (3tuples)path
– (default:False
) find an Eulerian path instead
OUTPUT:
either ([edges], [vertices]) or [edges] of an Eulerian circuit (or path)
EXAMPLES:
sage: g = graphs.CycleGraph(5) sage: g.eulerian_circuit() [(0, 4, None), (4, 3, None), (3, 2, None), (2, 1, None), (1, 0, None)] sage: g.eulerian_circuit(labels=False) [(0, 4), (4, 3), (3, 2), (2, 1), (1, 0)]
sage: g = graphs.CompleteGraph(7) sage: edges, vertices = g.eulerian_circuit(return_vertices=True) sage: vertices [0, 6, 5, 4, 6, 3, 5, 2, 4, 3, 2, 6, 1, 5, 0, 4, 1, 3, 0, 2, 1, 0]
sage: graphs.CompleteGraph(4).eulerian_circuit() False
A disconnected graph can be Eulerian:
sage: g = Graph({0: [], 1: [2], 2: [3], 3: [1], 4: []}) sage: g.eulerian_circuit(labels=False) [(1, 3), (3, 2), (2, 1)]
sage: g = DiGraph({0: [1], 1: [2, 4], 2:[3], 3:[1]}) sage: g.eulerian_circuit(labels=False, path=True) [(0, 1), (1, 2), (2, 3), (3, 1), (1, 4)]
sage: g = Graph({0:[1,2,3], 1:[2,3], 2:[3,4], 3:[4]}) sage: g.is_eulerian(path=True) (0, 1) sage: g.eulerian_circuit(labels=False, path=True) [(1, 3), (3, 4), (4, 2), (2, 3), (3, 0), (0, 2), (2, 1), (1, 0)]

eulerian_orientation
()¶ Returns a DiGraph which is an Eulerian orientation of the current graph.
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 outdegree and the indegree of a vertex.
If the graph is not Eulerian, the orientation verifies for any vertex \(v\) that \( d^+(v)d^(v)  \leq 1\).
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 nonoriented edge ( this vertex must have odd degree ), the walk resumes at another vertex of odd degree, if any.
This algorithm has complexity \(O(m)\), where \(m\) is the number of edges in the graph.
EXAMPLES:
The CubeGraph with parameter 4, which is regular of even degree, has an Eulerian orientation such that \(d^+=d^\):
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]
Secondly, the Petersen Graph, which is 3 regular has an orientation such that the difference between \(d^+\) and \(d^\) is at most 1:
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]

export_to_file
(filename, format=None, **kwds)¶ Export the graph to a file.
INPUT:
filename
(string) – a file name.format
(string) – select the output format explicitly. If set toNone
(default), the format is set to be the file extension offilename
. Admissible formats are:adjlist
,dot
,edgelist
,gexf
,gml
,graphml
,multiline_adjlist
,pajek
,yaml
.All other arguments are forwarded to the subfunction. For more information, see their respective documentation:
See also
save()
– save a Sage object to a ‘sobj’ file (preserves all its attributes).
Note
This functions uses the
write_*
functions defined in NetworkX (see http://networkx.lanl.gov/reference/readwrite.html).EXAMPLES:
sage: g = graphs.PetersenGraph() sage: filename = tmp_filename(ext=".pajek") sage: g.export_to_file(filename) sage: import networkx sage: G_networkx = networkx.read_pajek(filename) sage: Graph(G_networkx).is_isomorphic(g) True sage: filename = tmp_filename(ext=".edgelist") sage: g.export_to_file(filename, data=False) sage: h = Graph(networkx.read_edgelist(filename)) sage: g.is_isomorphic(h) True

faces
(embedding=None)¶ Return the faces of an embedded graph.
A combinatorial embedding of a graph is a clockwise ordering of the neighbors of each vertex. From this information one can define the faces of the embedding, which is what this method returns.
INPUT:
embedding
 a combinatorial embedding dictionary. Format:{v1:[v2,v3], v2:[v1], v3:[v1]}
(clockwise ordering of neighbors at each vertex). If set toNone
(default) the method will use the embedding stored asself._embedding
. If none is stored, the method will compute the set of faces from the embedding returned byis_planar()
(if the graph is, of course, planar).
Note
embedding
is an ordered list based on the hash order of the vertices of graph. To avoid confusion, it might be best to set the rot_sys based on a ‘nice_copy’ of the graph.EXAMPLES:
Providing an embedding:
sage: T = graphs.TetrahedralGraph() sage: T.faces({0: [1, 3, 2], 1: [0, 2, 3], 2: [0, 3, 1], 3: [0, 1, 2]}) [[(0, 1), (1, 2), (2, 0)], [(3, 2), (2, 1), (1, 3)], [(3, 0), (0, 2), (2, 3)], [(3, 1), (1, 0), (0, 3)]]
With no embedding provided:
sage: graphs.TetrahedralGraph().faces() [[(0, 1), (1, 2), (2, 0)], [(3, 2), (2, 1), (1, 3)], [(3, 0), (0, 2), (2, 3)], [(3, 1), (1, 0), (0, 3)]]
With no embedding provided (nonplanar graph):
sage: graphs.PetersenGraph().faces() Traceback (most recent call last): ... ValueError: No embedding is provided and the graph is not planar.

feedback_vertex_set
(value_only=False, solver=None, verbose=0, constraint_generation=True)¶ Return the minimum feedback vertex set of a (di)graph.
The minimum feedback vertex set of a (di)graph is a set of vertices that intersect all of its cycles. Equivalently, a minimum feedback vertex set of a (di)graph is a set \(S\) of vertices such that the digraph \(GS\) is acyclic. For more information, see the Wikipedia article Feedback_vertex_set.
INPUT:
value_only
– boolean (default:False
) When set to
True
, only the minimum cardinal of a minimum vertex set is returned.  When set to
False
, theSet
of vertices of a minimal feedback vertex set is returned.
 When set to
solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.constraint_generation
(boolean) – whether to use constraint generation when solving the Mixed Integer Linear Program (default:True
).
ALGORITHMS:
(Constraints generation)
When the parameter
constraint_generation
is enabled (default) the following MILP formulation is used to solve the problem:\[\begin{split}\mbox{Minimize : }&\sum_{v\in G} b_{v}\\ \mbox{Such that : }&\\ &\forall C\text{ circuits }\subseteq G, \sum_{v\in C}b_{v}\geq 1\\\end{split}\]As the number of circuits contained in a graph is exponential, this LP is solved through constraint generation. This means that the solver is sequentially asked to solve the problem, knowing only a portion of the circuits contained in \(G\), each time adding to the list of its constraints the circuit which its last answer had left intact.
(Another formulation based on an ordering of the vertices)
When the graph is directed, a second (and very slow) formulation is available, which should only be used to check the result of the first implementation in case of doubt.
\[\begin{split}\mbox{Minimize : }&\sum_{v\in G} b_v\\ \mbox{Such that : }&\\ &\forall (u,v)\in G, d_ud_v+nb_u+nb_v\geq 0\\ &\forall u\in G, 0\leq d_u\leq G\\\end{split}\]A brief explanation:
An acyclic digraph can be seen as a poset, and every poset has a linear extension. This means that in any acyclic digraph the vertices can be ordered with a total order \(<\) in such a way that if \((u,v)\in G\), then \(u<v\). Thus, this linear program is built in order to assign to each vertex \(v\) a number \(d_v\in [0,\dots,n1]\) such that if there exists an edge \((u,v)\in G\) then either \(d_v<d_u\) or one of \(u\) or \(v\) is removed. The number of vertices removed is then minimized, which is the objective.
EXAMPLES:
The necessary example:
sage: g = graphs.PetersenGraph() sage: fvs = g.feedback_vertex_set() sage: len(fvs) 3 sage: g.delete_vertices(fvs) sage: g.is_forest() True
In a digraph built from a graph, any edge is replaced by arcs going in the two opposite directions, thus creating a cycle of length two. Hence, to remove all the cycles from the graph, each edge must see one of its neighbors removed: a feedback vertex set is in this situation a vertex cover:
sage: cycle = graphs.CycleGraph(5) sage: dcycle = DiGraph(cycle) sage: cycle.vertex_cover(value_only=True) 3 sage: feedback = dcycle.feedback_vertex_set() sage: len(feedback) 3 sage: (u,v,l) = next(cycle.edge_iterator()) sage: u in feedback or v in feedback True
For a circuit, the minimum feedback arc set is clearly \(1\):
sage: circuit = digraphs.Circuit(5) sage: circuit.feedback_vertex_set(value_only=True) == 1 True

flow
(x, y, value_only=True, integer=False, use_edge_labels=True, vertex_bound=False, algorithm=None, solver=None, verbose=0)¶ Return a maximum flow in the graph from
x
toy
.The returned flow is represented by an optimal valuation of the edges. For more information, see the Wikipedia article Max_flow.
As an optimization problem, is can be expressed this way :
\[\begin{split}\mbox{Maximize : }&\sum_{e\in G.edges()} w_e b_e\\ \mbox{Such that : }&\forall v \in G, \sum_{(u,v)\in G.edges()} b_{(u,v)}\leq 1\\ &\forall x\in G, b_x\mbox{ is a binary variable}\end{split}\]INPUT:
x
– Source vertexy
– Sink vertexvalue_only
– boolean (default:True
) When set to
True
, only the value of a maximal flow is returned.  When set to
False
, is returned a pair whose first element is the value of the maximum flow, and whose second value is a flow graph (a copy of the current graph, such that each edge has the flow using it as a label, the edges without flow being omitted).
 When set to
integer
– boolean (default:True
) When set to
True
, computes an optimal solution under the constraint that the flow going through an edge has to be an integer.
 When set to
use_edge_labels
– boolean (default:True
) When set to
True
, computes a maximum flow where each edge has a capacity defined by its label. (If an edge has no label, \(1\) is assumed.)  When set to
False
, each edge has capacity \(1\).
 When set to
vertex_bound
– boolean (default:False
) When set to
True
, sets the maximum flow leaving a vertex different from \(x\) to \(1\) (useful for vertex connectivity parameters).
 When set to
algorithm
– There are currently three different implementations of this method: If
algorithm = "FF"
, a Python implementation of the FordFulkerson algorithm is used (only available whenvertex_bound = False
)  If
algorithm = "LP"
, the flow problem is solved using Linear Programming.  If
algorithm = "igraph"
, the igraph implementation of the GoldbergTarjan algorithm is used (only available when igraph is installed andvertex_bound = False
)  If
algorithm = None
(default), we useLP
ifvertex_bound = True
, otherwise, we useigraph
if it is available,FF
if it is not available.
 If
solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.Only useful when LP is used to solve the flow problem.
verbose
(integer) – sets the level of verbosity. Set to 0 by default (quiet).Only useful when LP is used to solve the flow problem.
Note
Even though the three different implementations are meant to return the same Flow values, they can not be expected to return the same Flow graphs.
Besides, the use of Linear Programming may possibly mean a (slight) numerical noise.
EXAMPLES:
Two basic applications of the flow method for the
PappusGraph
and theButterflyGraph
with parameter \(2\)sage: g=graphs.PappusGraph() sage: int(g.flow(1,2)) 3
sage: b=digraphs.ButterflyGraph(2) sage: int(b.flow(('00',1),('00',2))) 1
The flow method can be used to compute a matching in a bipartite graph by linking a source \(s\) to all the vertices of the first set and linking a sink \(t\) to all the vertices of the second set, then computing a maximum \(st\) flow
sage: g = DiGraph() sage: g.add_edges([('s',i) for i in range(4)]) sage: g.add_edges([(i,4+j) for i in range(4) for j in range(4)]) sage: g.add_edges([(4+i,'t') for i in range(4)]) sage: [cardinal, flow_graph] = g.flow('s','t',integer=True,value_only=False) sage: flow_graph.delete_vertices(['s','t']) sage: len(flow_graph.edges()) 4
The undirected case:
sage: g = Graph() sage: g.add_edges([('s',i) for i in range(4)]) sage: g.add_edges([(i,4+j) for i in range(4) for j in range(4)]) sage: g.add_edges([(4+i,'t') for i in range(4)]) sage: [cardinal, flow_graph] = g.flow('s','t',integer=True,value_only=False) sage: flow_graph.delete_vertices(['s','t']) sage: len(flow_graph.edges()) 4

genus
(set_embedding=True, on_embedding=None, minimal=True, maximal=False, circular=None, ordered=True)¶ Returns the minimal genus of the graph.
The genus of a compact surface is the number of handles it has. The genus of a graph is the minimal genus of the surface it can be embedded into. It can be seen as a measure of nonplanarity; a planar graph has genus zero.
Note  This function uses Euler’s formula and thus it is necessary to consider only connected graphs.
INPUT:
set_embedding (boolean)
 whether or not to store an embedding attribute of the computed (minimal) genus of the graph. (Default is True).on_embedding
(default:None
)  two kinds of input are allowed: a dictionary representing a combinatorial embedding on which the
genus should be computed. Note that this must be a valid embedding
for the graph. The dictionary structure is given by:
vertex1: [neighbor1, neighbor2, neighbor3], vertex2: [neighbor]
where there is a key for each vertex in the graph and a (clockwise) ordered list of each vertex’s neighbors as values. The value ofon_embedding
takes precedence over a stored_embedding
attribute if minimal is set toFalse
.  The value
True
, in order to indicate that the embedding stored as_embedding
should be used (see examples).
 a dictionary representing a combinatorial embedding on which the
genus should be computed. Note that this must be a valid embedding
for the graph. The dictionary structure is given by:
minimal (boolean)
 whether or not to compute the minimal genus of the graph (i.e., testing all embeddings). If minimal is False, then either maximal must be True or on_embedding must not be None. If on_embedding is not None, it will take priority over minimal. Similarly, if maximal is True, it will take priority over minimal.maximal (boolean)
 whether or not to compute the maximal genus of the graph (i.e., testing all embeddings). If maximal is False, then either minimal must be True or on_embedding must not be None. If on_embedding is not None, it will take priority over maximal. However, maximal takes priority over the default minimal.circular (list)
 ifcircular
is a list of vertices, the method computes the genus preserving a planar embedding of the this list. If circular is defined,on_embedding
is not a valid option. It is set toNone
by default.ordered (boolean)
 if circular is True, then whether or not the boundary order may be permuted. (Default is True, which means the boundary order is preserved.)
EXAMPLES:
sage: g = graphs.PetersenGraph() sage: g.genus() # tests for minimal genus by default 1 sage: g.genus(on_embedding=True, maximal=True) # on_embedding overrides minimal and maximal arguments 1 sage: g.genus(maximal=True) # setting maximal to True overrides default minimal=True 3 sage: g.genus(on_embedding=g.get_embedding()) # can also send a valid combinatorial embedding dict 3 sage: (graphs.CubeGraph(3)).genus() 0 sage: K23 = graphs.CompleteBipartiteGraph(2,3) sage: K23.genus() 0 sage: K33 = graphs.CompleteBipartiteGraph(3,3) sage: K33.genus() 1
Using the circular argument, we can compute the minimal genus preserving a planar, ordered boundary:
sage: cube = graphs.CubeGraph(2) sage: cube.genus(circular=['01','10']) 0 sage: cube.is_circular_planar() True sage: cube.genus(circular=['01','10']) 0 sage: cube.genus(circular=['01','10'], on_embedding=True) 0 sage: cube.genus(circular=['01','10'], maximal=True) Traceback (most recent call last): ... NotImplementedError: Cannot compute the maximal genus of a genus respecting a boundary.
Note: not everything works for multigraphs, looped graphs or digraphs. But the minimal genus is ultimately computable for every connected graph – but the embedding we obtain for the simple graph can’t be easily converted to an embedding of a nonsimple graph. Also, the maximal genus of a multigraph does not trivially correspond to that of its simple graph.
sage: G = DiGraph({ 0 : [0,1,1,1], 1 : [2,2,3,3], 2 : [1,3,3], 3:[0,3]}) sage: G.genus() Traceback (most recent call last): ... NotImplementedError: Can't work with embeddings of nonsimple graphs sage: G.to_simple().genus() 0 sage: G.genus(set_embedding=False) 0 sage: G.genus(maximal=True, set_embedding=False) Traceback (most recent call last): ... NotImplementedError: Can't compute the maximal genus of a graph with loops or multiple edges
We break graphs with cut vertices into their blocks, which greatly speeds up computation of minimal genus. This is not implemented for maximal genus.
sage: K5 = graphs.CompleteGraph(5) sage: G = K5.copy() sage: s = 4 sage: for i in range(1,100): ....: k = K5.relabel(list(range(s,s+5)),inplace=False) ....: G.add_edges(k.edges()) ....: s += 4 sage: G.genus() 100

get_embedding
()¶ Returns the attribute _embedding if it exists.
_embedding
is a dictionary organized with vertex labels as keys and a list of each vertex’s neighbors in clockwise order.Errorchecked to insure valid embedding is returned.
EXAMPLES:
sage: G = graphs.PetersenGraph() sage: G.genus() 1 sage: G.get_embedding() {0: [1, 4, 5], 1: [0, 2, 6], 2: [1, 3, 7], 3: [2, 4, 8], 4: [0, 3, 9], 5: [0, 7, 8], 6: [1, 9, 8], 7: [2, 5, 9], 8: [3, 6, 5], 9: [4, 6, 7]}

get_pos
(dim=2)¶ Returns the position dictionary, a dictionary specifying the coordinates of each vertex.
EXAMPLES: By default, the position of a graph is None:
sage: G = Graph() sage: G.get_pos() sage: G.get_pos() is None True sage: P = G.plot(save_pos=True) sage: G.get_pos() {}
Some of the named graphs come with a prespecified positioning:
sage: G = graphs.PetersenGraph() sage: G.get_pos() {0: (0.0, 1.0), ... 9: (0.475..., 0.154...)}

get_vertex
(vertex)¶ Retrieve the object associated with a given vertex.
INPUT:
vertex
 the given vertex
EXAMPLES:
sage: d = {0 : graphs.DodecahedralGraph(), 1 : graphs.FlowerSnark(), 2 : graphs.MoebiusKantorGraph(), 3 : graphs.PetersenGraph() } sage: d[2] MoebiusKantor Graph: Graph on 16 vertices sage: T = graphs.TetrahedralGraph() sage: T.vertices() [0, 1, 2, 3] sage: T.set_vertices(d) sage: T.get_vertex(1) Flower Snark: Graph on 20 vertices

get_vertices
(verts=None)¶ Return a dictionary of the objects associated to each vertex.
INPUT:
verts
 iterable container of vertices
EXAMPLES:
sage: d = {0 : graphs.DodecahedralGraph(), 1 : graphs.FlowerSnark(), 2 : graphs.MoebiusKantorGraph(), 3 : graphs.PetersenGraph() } sage: T = graphs.TetrahedralGraph() sage: T.set_vertices(d) sage: T.get_vertices([1,2]) {1: Flower Snark: Graph on 20 vertices, 2: MoebiusKantor Graph: Graph on 16 vertices}

girth
()¶ Computes the girth of the graph. For directed graphs, computes the girth of the undirected graph.
The girth is the length of the shortest cycle in the graph. Graphs without cycles have infinite girth.
EXAMPLES:
sage: graphs.TetrahedralGraph().girth() 3 sage: graphs.CubeGraph(3).girth() 4 sage: graphs.PetersenGraph().girth() 5 sage: graphs.HeawoodGraph().girth() 6 sage: next(graphs.trees(9)).girth() +Infinity
See also
odd_girth()
– computes the odd girth of a graph.

graphplot
(**options)¶ Returns a GraphPlot object.
EXAMPLES:
Creating a graphplot object uses the same options as graph.plot():
sage: g = Graph({}, loops=True, multiedges=True, sparse=True) sage: g.add_edges([(0,0,'a'),(0,0,'b'),(0,1,'c'),(0,1,'d'), ....: (0,1,'e'),(0,1,'f'),(0,1,'f'),(2,1,'g'),(2,2,'h')]) sage: GP = g.graphplot(edge_labels=True, color_by_label=True, edge_style='dashed') sage: GP.plot() Graphics object consisting of 26 graphics primitives
We can modify the graphplot object. Notice that the changes are cumulative:
sage: GP.set_edges(edge_style='solid') sage: GP.plot() Graphics object consisting of 26 graphics primitives sage: GP.set_vertices(talk=True) sage: GP.plot() Graphics object consisting of 26 graphics primitives

graphviz_string
(rankdir='down', edge_color=None, vertex_labels=True, edge_options=(), labels='string', color_by_label=False, edge_colors=None, edge_labels=False, subgraph_clusters=[], **options)¶ Return a representation in the \(dot\) language.
The \(dot\) language is a text based format for graphs. It is used by the software suite \(graphviz\). The specifications of the language are available on the web (see the reference [dotspec]).
INPUT:
labels
– “string” or “latex” (default: “string”). If labels is string latex command are not interpreted. This option stands for both vertex labels and edge labels.vertex_labels
– boolean (default: True) whether to add the labels on vertices.edge_labels
– boolean (default: False) whether to add the labels on edges.edge_color
– (default: None) specify a default color for the edges. The color could be one of a name given as a string such as
"blue"
or"orchid"
 a HSV sequence in a string such as
".52,.386,.22"
 an hexadecimal code such as
"#DA3305"
 a 3tuple of floating point (to be interpreted as RGB tuple). In this case the 3tuple is converted in hexadecimal code.
 a name given as a string such as
edge_colors
– (default: None) a dictionary whose keys are colors and values are list of edges. The list of edges need not to be complete in which case the default color is used. See the optionedge_color
for a description of valid color formats.color_by_label
– (default: False) a boolean or dictionary or function whether to color each edge with a different color according to its label; the colors are chosen along a rainbow, unless they are specified by a function or dictionary mapping labels to colors; this option is incompatible withedge_color
andedge_colors
. See the optionedge_color
for a description of valid color formats.edge_options
– a function (or tuple thereof) mapping edges to a dictionary of options for this edge.rankdir
– ‘left’, ‘right’, ‘up’, or ‘down’ (default: ‘down’, for consistency with \(graphviz\)): the preferred ranking direction for acyclic layouts; see the \(rankdir\) option of \(graphviz\).subgraph_clusters
– (default: []) a list of lists of vertices, From [dotspec]: “If supported, the layout engine will do the layout so that the nodes belonging to the cluster are drawn together, with the entire drawing of the cluster contained within a bounding rectangle. Note that, for good and bad, cluster subgraphs are not part of the DOT language, but solely a syntactic convention adhered to by certain of the layout engines.”
EXAMPLES:
sage: G = Graph({0:{1:None,2:None}, 1:{0:None,2:None}, 2:{0:None,1:None,3:'foo'}, 3:{2:'foo'}},sparse=True) sage: print(G.graphviz_string(edge_labels=True)) graph { node_0 [label="0"]; node_1 [label="1"]; node_2 [label="2"]; node_3 [label="3"]; node_0  node_1; node_0  node_2; node_1  node_2; node_2  node_3 [label="foo"]; }
A variant, with the labels in latex, for postprocessing with
dot2tex
:sage: print(G.graphviz_string(edge_labels=True,labels = "latex")) graph { node [shape="plaintext"]; node_0 [label=" ", texlbl="$0$"]; node_1 [label=" ", texlbl="$1$"]; node_2 [label=" ", texlbl="$2$"]; node_3 [label=" ", texlbl="$3$"]; node_0  node_1; node_0  node_2; node_1  node_2; node_2  node_3 [label=" ", texlbl="$\text{\texttt{foo}}$"]; }
Same, with a digraph and a color for edges:
sage: G = DiGraph({0:{1:None,2:None}, 1:{2:None}, 2:{3:'foo'}, 3:{}} ,sparse=True) sage: print(G.graphviz_string(edge_color="red")) digraph { node_0 [label="0"]; node_1 [label="1"]; node_2 [label="2"]; node_3 [label="3"]; edge [color="red"]; node_0 > node_1; node_0 > node_2; node_1 > node_2; node_2 > node_3; }
A digraph using latex labels for vertices and edges:
sage: f(x) = 1/x sage: g(x) = 1/(x+1) sage: G = DiGraph() sage: G.add_edges([(i,f(i),f) for i in (1,2,1/2,1/4)]) sage: G.add_edges([(i,g(i),g) for i in (1,2,1/2,1/4)]) sage: print(G.graphviz_string(labels="latex",edge_labels=True)) # random digraph { node [shape="plaintext"]; node_10 [label=" ", texlbl="$1$"]; node_11 [label=" ", texlbl="$2$"]; node_3 [label=" ", texlbl="$\frac{1}{2}$"]; node_6 [label=" ", texlbl="$\frac{1}{2}$"]; node_7 [label=" ", texlbl="$\frac{1}{2}$"]; node_5 [label=" ", texlbl="$\frac{1}{3}$"]; node_8 [label=" ", texlbl="$\frac{2}{3}$"]; node_4 [label=" ", texlbl="$\frac{1}{4}$"]; node_1 [label=" ", texlbl="$2$"]; node_9 [label=" ", texlbl="$\frac{4}{5}$"]; node_0 [label=" ", texlbl="$4$"]; node_2 [label=" ", texlbl="$1$"]; node_10 > node_2 [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$"]; node_10 > node_6 [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"]; node_11 > node_3 [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$"]; node_11 > node_5 [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"]; node_7 > node_1 [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$"]; node_7 > node_8 [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"]; node_4 > node_0 [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$"]; node_4 > node_9 [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x + 1}$"]; } sage: print(G.graphviz_string(labels="latex",color_by_label=True)) # random digraph { node [shape="plaintext"]; node_10 [label=" ", texlbl="$1$"]; node_11 [label=" ", texlbl="$2$"]; node_3 [label=" ", texlbl="$\frac{1}{2}$"]; node_6 [label=" ", texlbl="$\frac{1}{2}$"]; node_7 [label=" ", texlbl="$\frac{1}{2}$"]; node_5 [label=" ", texlbl="$\frac{1}{3}$"]; node_8 [label=" ", texlbl="$\frac{2}{3}$"]; node_4 [label=" ", texlbl="$\frac{1}{4}$"]; node_1 [label=" ", texlbl="$2$"]; node_9 [label=" ", texlbl="$\frac{4}{5}$"]; node_0 [label=" ", texlbl="$4$"]; node_2 [label=" ", texlbl="$1$"]; node_10 > node_2 [color = "#ff0000"]; node_10 > node_6 [color = "#00ffff"]; node_11 > node_3 [color = "#ff0000"]; node_11 > node_5 [color = "#00ffff"]; node_7 > node_1 [color = "#ff0000"]; node_7 > node_8 [color = "#00ffff"]; node_4 > node_0 [color = "#ff0000"]; node_4 > node_9 [color = "#00ffff"]; } sage: print(G.graphviz_string(labels="latex",color_by_label={ f: "red", g: "blue" })) # random digraph { node [shape="plaintext"]; node_10 [label=" ", texlbl="$1$"]; node_11 [label=" ", texlbl="$2$"]; node_3 [label=" ", texlbl="$\frac{1}{2}$"]; node_6 [label=" ", texlbl="$\frac{1}{2}$"]; node_7 [label=" ", texlbl="$\frac{1}{2}$"]; node_5 [label=" ", texlbl="$\frac{1}{3}$"]; node_8 [label=" ", texlbl="$\frac{2}{3}$"]; node_4 [label=" ", texlbl="$\frac{1}{4}$"]; node_1 [label=" ", texlbl="$2$"]; node_9 [label=" ", texlbl="$\frac{4}{5}$"]; node_0 [label=" ", texlbl="$4$"]; node_2 [label=" ", texlbl="$1$"]; node_10 > node_2 [color = "red"]; node_10 > node_6 [color = "blue"]; node_11 > node_3 [color = "red"]; node_11 > node_5 [color = "blue"]; node_7 > node_1 [color = "red"]; node_7 > node_8 [color = "blue"]; node_4 > node_0 [color = "red"]; node_4 > node_9 [color = "blue"]; }
By default
graphviz
renders digraphs using a hierarchical layout, ranking the vertices down from top to bottom. Here we specify alternative ranking directions for this layout:sage: D = DiGraph([[1,2]]) sage: print(D.graphviz_string(rankdir="up")) digraph { rankdir=BT node_0 [label="1"]; node_1 [label="2"]; node_0 > node_1; } sage: print(D.graphviz_string(rankdir="down")) digraph { node_0 [label="1"]; node_1 [label="2"]; node_0 > node_1; } sage: print(D.graphviz_string(rankdir="left")) digraph { rankdir=RL node_0 [label="1"]; node_1 [label="2"]; node_0 > node_1; } sage: print(D.graphviz_string(rankdir="right")) digraph { rankdir=LR node_0 [label="1"]; node_1 [label="2"]; node_0 > node_1; }
Edgespecific options can also be specified by providing a function (or tuple thereof) which maps each edge to a dictionary of options. Valid options are “color”, “backward” (a boolean), “dot” (a string containing a sequence of options in dot format), “label” (a string), “label_style” (“string” or “latex”), “edge_string” (“–” or “>”). Here we state that the graph should be laid out so that edges starting from
1
are going backward (e.g. going up instead of down):sage: def edge_options(data): ....: u, v, label = data ....: return { "backward": u == 1 } sage: print(G.graphviz_string(edge_options = edge_options)) # random digraph { node_10 [label="1"]; node_11 [label="2"]; node_3 [label="1/2"]; node_6 [label="1/2"]; node_7 [label="1/2"]; node_5 [label="1/3"]; node_8 [label="2/3"]; node_4 [label="1/4"]; node_1 [label="2"]; node_9 [label="4/5"]; node_0 [label="4"]; node_2 [label="1"]; node_2 > node_10 [dir=back]; node_6 > node_10 [dir=back]; node_11 > node_3; node_11 > node_5; node_7 > node_1; node_7 > node_8; node_4 > node_0; node_4 > node_9; }
We now test all options:
sage: def edge_options(data): ....: u, v, label = data ....: options = { "color": { f: "red", g: "blue" }[label] } ....: if (u,v) == (1/2, 2): options["label"] = "coucou"; options["label_style"] = "string" ....: if (u,v) == (1/2,2/3): options["dot"] = "x=1,y=2" ....: if (u,v) == (1, 1): options["label_style"] = "latex" ....: if (u,v) == (1, 1/2): options["edge_string"] = "<" ....: if (u,v) == (1/2, 1): options["backward"] = True ....: return options sage: print(G.graphviz_string(edge_options = edge_options)) # random digraph { node_10 [label="1"]; node_11 [label="2"]; node_3 [label="1/2"]; node_6 [label="1/2"]; node_7 [label="1/2"]; node_5 [label="1/3"]; node_8 [label="2/3"]; node_4 [label="1/4"]; node_1 [label="2"]; node_9 [label="4/5"]; node_0 [label="4"]; node_2 [label="1"]; node_10 > node_2 [label=" ", texlbl="$x \ {\mapsto}\ \frac{1}{x}$", color = "red"]; node_10 < node_6 [color = "blue"]; node_11 > node_3 [color = "red"]; node_11 > node_5 [color = "blue"]; node_7 > node_1 [label="coucou", color = "red"]; node_7 > node_8 [x=1,y=2, color = "blue"]; node_4 > node_0 [color = "red"]; node_4 > node_9 [color = "blue"]; }
REFERENCES:
[dotspec] (1, 2) http://www.graphviz.org/doc/info/lang.html

graphviz_to_file_named
(filename, **options)¶ Write a representation in the dot in a file.
The dot language is a plaintext format for graph structures. See the documentation of
graphviz_string()
for available options.INPUT:
filename
 the name of the file to write inoptions
 options for the graphviz stringEXAMPLES:
sage: G = Graph({0:{1:None,2:None}, 1:{0:None,2:None}, 2:{0:None,1:None,3:'foo'}, 3:{2:'foo'}},sparse=True) sage: tempfile = os.path.join(SAGE_TMP, 'temp_graphviz') sage: G.graphviz_to_file_named(tempfile, edge_labels=True) sage: print(open(tempfile).read()) graph { node_0 [label="0"]; node_1 [label="1"]; node_2 [label="2"]; node_3 [label="3"]; node_0  node_1; node_0  node_2; node_1  node_2; node_2  node_3 [label="foo"]; }

hamiltonian_cycle
(algorithm='tsp', solver=None, constraint_generation=None, verbose=0, verbose_constraints=False)¶ Return a Hamiltonian cycle/circuit of the current graph/digraph.
A graph (resp. digraph) is said to be Hamiltonian if it contains as a subgraph a cycle (resp. a circuit) going through all the vertices.
Computing a Hamiltonian cycle/circuit being NPComplete, this algorithm could run for some time depending on the instance.
ALGORITHM:
See
traveling_salesman_problem()
for ‘tsp’ algorithm andfind_hamiltonian()
fromsage.graphs.generic_graph_pyx
for ‘backtrack’ algorithm.INPUT:
algorithm
– one of ‘tsp’ or ‘backtrack’.solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.constraint_generation
(boolean) – whether to use constraint generation when solving the Mixed Integer Linear Program.When
constraint_generation = None
, constraint generation is used whenever the graph has a density larger than 70%.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.verbose_constraints
– whether to display which constraints are being generated.
OUTPUT:
If using the ‘tsp’ algorithm, returns a Hamiltonian cycle/circuit if it exists; otherwise, raises a
EmptySetError
exception. If using the ‘backtrack’ algorithm, returns a pair (B,P). If B is True then P is a Hamiltonian cycle and if B is False, P is a longest path found by the algorithm. Observe that if B is False, the graph may still be Hamiltonian. The ‘backtrack’ algorithm is only implemented for undirected graphs.Warning
The ‘backtrack’ algorithm may loop endlessly on graphs with vertices of degree 1.
NOTE:
This function, as
is_hamiltonian
, computes a Hamiltonian cycle if it exists: the user should NOT test for Hamiltonicity usingis_hamiltonian
before calling this function, as it would result in computing it twice.The backtrack algorithm is only implemented for undirected graphs.
EXAMPLES:
The Heawood Graph is known to be Hamiltonian
sage: g = graphs.HeawoodGraph() sage: g.hamiltonian_cycle() TSP from Heawood graph: Graph on 14 vertices
The Petersen Graph, though, is not
sage: g = graphs.PetersenGraph() sage: g.hamiltonian_cycle() Traceback (most recent call last): ... EmptySetError: The given graph is not Hamiltonian
Now, using the backtrack algorithm in the Heawood graph
sage: G=graphs.HeawoodGraph() sage: G.hamiltonian_cycle(algorithm='backtrack') (True, [11, 10, 1, 2, 3, 4, 9, 8, 7, 6, 5, 0, 13, 12])
And now in the Petersen graph
sage: G=graphs.PetersenGraph() sage: G.hamiltonian_cycle(algorithm='backtrack') (False, [6, 8, 5, 0, 1, 2, 7, 9, 4, 3])
Finally, we test the algorithm in a cube graph, which is Hamiltonian
sage: G=graphs.CubeGraph(3) sage: G.hamiltonian_cycle(algorithm='backtrack') (True, ['010', '110', '100', '000', '001', '101', '111', '011'])

hamiltonian_path
(s=None, t=None, use_edge_labels=False, maximize=False, algorithm='MILP', solver=None, verbose=0)¶ Return a Hamiltonian path of the current graph/digraph.
A path is Hamiltonian if it goes through all the vertices exactly once. Computing a Hamiltonian path being NPComplete, this algorithm could run for some time depending on the instance.
When
use_edge_labels == True
, this method returns either a minimum weight hamiltonian path or a maximum weight Hamiltonian path (ifmaximize == True
).See also
INPUT:
s
– vertex (optional); if specified, then forces the source of the path (the method then returns a Hamiltonian path starting ats
)t
– vertex (optional); if specified, then forces the destination of the path (the method then returns a Hamiltonian path ending att
)use_edge_labels
– boolean (default:False
); whether the labels on the edges are to be considered as weights (a label set toNone
or{}
being considered as a weight of \(1\))maximize
– boolean (default:False
); whether to compute a minimum (default) of a maximum (whenmaximize == True
) weight hamiltonian path. This parameter is considered only ifuse_edge_labels == True
.algorithm
– one of"MILP"
(default) or"backtrack"
; two remarks on this respect: While the MILP formulation returns an exact answer, the backtrack algorithm is a randomized heuristic.
 The backtrack algorithm does not support edge weighting, so setting
use_edge_labels=True
will force the use of the MILP algorithm.
solver
– (default:None
) specify the Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
verbose
– integer (default:0
); sets the level of verbosity with 0 meaning quiet
OUTPUT:
A subgraph of
self
corresponding to a (directed ifself
is directed) hamiltonian path. If no hamiltonian path is found, returnNone
. Ifuse_edge_labels == True
, a pairweight, path
is returned.EXAMPLES:
The \(3 \times 3\)grid has an Hamiltonian path, an hamiltonian path starting from vertex \((0, 0)\) and ending at vertex \((2, 2)\), but no Hamiltonian path starting from \((0, 0)\) and ending at \((0, 1)\):
sage: g = graphs.Grid2dGraph(3, 3) sage: g.hamiltonian_path() Hamiltonian path from 2D Grid Graph for [3, 3]: Graph on 9 vertices sage: g.hamiltonian_path(s=(0,0), t=(2,2)) Hamiltonian path from 2D Grid Graph for [3, 3]: Graph on 9 vertices sage: g.hamiltonian_path(s=(0,0), t=(2,2), use_edge_labels=True) (8, Hamiltonian path from 2D Grid Graph for [3, 3]: Graph on 9 vertices) sage: g.hamiltonian_path(s=(0,0), t=(0,1)) is None True sage: g.hamiltonian_path(s=(0,0), t=(0,1), use_edge_labels=True) (0, None)

has_edge
(u, v=None, label=None)¶ Returns True if (u, v) is an edge, False otherwise.
INPUT: The following forms are accepted by NetworkX:
 G.has_edge( 1, 2 )
 G.has_edge( (1, 2) )
 G.has_edge( 1, 2, ‘label’ )
 G.has_edge( (1, 2, ‘label’) )
EXAMPLES:
sage: graphs.EmptyGraph().has_edge(9,2) False sage: DiGraph().has_edge(9,2) False sage: G = Graph(sparse=True) sage: G.add_edge(0,1,"label") sage: G.has_edge(0,1,"different label") False sage: G.has_edge(0,1,"label") True

has_loops
()¶ Return whether there are loops in the (di)graph
EXAMPLES:
sage: G = Graph(loops=True); G Looped graph on 0 vertices sage: G.has_loops() False sage: G.allows_loops() True sage: G.add_edge((0,0)) sage: G.has_loops() True sage: G.loops() [(0, 0, None)] sage: G.allow_loops(False); G Graph on 1 vertex sage: G.has_loops() False sage: G.edges() [] sage: D = DiGraph(loops=True); D Looped digraph on 0 vertices sage: D.has_loops() False sage: D.allows_loops() True sage: D.add_edge((0,0)) sage: D.has_loops() True sage: D.loops() [(0, 0, None)] sage: D.allow_loops(False); D Digraph on 1 vertex sage: D.has_loops() False sage: D.edges() []

has_multiple_edges
(to_undirected=False)¶ Returns whether there are multiple edges in the (di)graph.
INPUT:
to_undirected
– (default: False) If True, runs the test on the undirected version of a DiGraph. Otherwise, treats DiGraph edges (u,v) and (v,u) as unique individual edges.
EXAMPLES:
sage: G = Graph(multiedges=True,sparse=True); G Multigraph on 0 vertices sage: G.has_multiple_edges() False sage: G.allows_multiple_edges() True sage: G.add_edges([(0,1)]*3) sage: G.has_multiple_edges() True sage: G.multiple_edges() [(0, 1, None), (0, 1, None), (0, 1, None)] sage: G.allow_multiple_edges(False); G Graph on 2 vertices sage: G.has_multiple_edges() False sage: G.edges() [(0, 1, None)] sage: D = DiGraph(multiedges=True,sparse=True); D Multidigraph on 0 vertices sage: D.has_multiple_edges() False sage: D.allows_multiple_edges() True sage: D.add_edges([(0,1)]*3) sage: D.has_multiple_edges() True sage: D.multiple_edges() [(0, 1, None), (0, 1, None), (0, 1, None)] sage: D.allow_multiple_edges(False); D Digraph on 2 vertices sage: D.has_multiple_edges() False sage: D.edges() [(0, 1, None)] sage: G = DiGraph({1:{2: 'h'}, 2:{1:'g'}},sparse=True) sage: G.has_multiple_edges() False sage: G.has_multiple_edges(to_undirected=True) True sage: G.multiple_edges() [] sage: G.multiple_edges(to_undirected=True) [(1, 2, 'h'), (2, 1, 'g')]
A loop is not a multiedge:
sage: g = Graph(loops=True,multiedges=True) sage: g.add_edge(0,0) sage: g.has_multiple_edges() False

has_vertex
(vertex)¶ Return True if vertex is one of the vertices of this graph.
INPUT:
vertex
 an integer
OUTPUT:
bool
 True or False
EXAMPLES:
sage: g = Graph({0:[1,2,3], 2:[4]}); g Graph on 5 vertices sage: 2 in g True sage: 10 in g False sage: graphs.PetersenGraph().has_vertex(99) False

igraph_graph
(vertex_attrs={}, edge_attrs={})¶ Converts the graph into an igraph graph.
Optionally, it is possible to add vertex attributes and edge attributes to the output graph.
Note
This routine needs the optional package igraph to be installed: to do so, it is enough to run
sage i python_igraph
. For more information on the Python version of igraph, see http://igraph.org/python/.INPUT:
vertex_attrs
(dictionary)  a dictionary where the key is a string (the attribute name), and the value is an iterable containing in position i the label of the ith vertex returned byvertices()
(see http://igraph.org/python/doc/igraph.Graphclass.html#__init__ for more information).edge_attrs
(dictionary)  a dictionary where the key is a string (the attribute name), and the value is an iterable containing in position i the label of the ith edge in the list outputted byedge_iterator()
(see http://igraph.org/python/doc/igraph.Graphclass.html#__init__ for more information).
Note
In igraph, a graph is weighted if the edge labels have attribute
weight
. Hence, to create a weighted graph, it is enough to add this attribute.Note
Often, Sage uses its own defined types for integer/floats. These types may not be igraphcompatible (see example below).
EXAMPLES:
Standard conversion:
sage: G = graphs.TetrahedralGraph() # optional  python_igraph sage: H = G.igraph_graph() # optional  python_igraph sage: H.summary() # optional  python_igraph 'IGRAPH U 4 6  ' sage: G = digraphs.Path(3) # optional  python_igraph sage: H = G.igraph_graph() # optional  python_igraph sage: H.summary() # optional  python_igraph 'IGRAPH D 3 2  '
Adding edge attributes:
sage: G = Graph([(1,2,'a'),(2,3,'b')]) # optional  python_igraph sage: H = G.igraph_graph(edge_attrs = {'label':[e[2] for e in G.edges()]}) # optional  python_igraph sage: H.es['label'] # optional  python_igraph ['a', 'b']
If edges have an attribute
weight
, the igraph graph is considered weighted:sage: G = Graph([(1,2,{'weight':1}),(2,3,{'weight':2})]) # optional  python_igraph sage: H = G.igraph_graph(edge_attrs = {'weight':[e[2]['weight'] for e in G.edges()]}) # optional  python_igraph sage: H.is_weighted() # optional  python_igraph True sage: H.es['weight'] # optional  python_igraph [1, 2]
Adding vertex attributes:
sage: G = graphs.GridGraph([2,2]) # optional  python_igraph sage: H = G.igraph_graph(vertex_attrs={'name':G.vertices()}) # optional  python_igraph sage: H.vs()['name'] # optional  python_igraph [(0, 0), (0, 1), (1, 0), (1, 1)]
Sometimes, Sage integer/floats are not compatible with igraph:
sage: G = Graph([(0,1,2)]) # optional  python_igraph sage: H = G.igraph_graph(edge_attrs = {'capacity':[e[2] for e in G.edges()]}) # optional  python_igraph sage: H.maxflow_value(0, 1, 'capacity') # optional  python_igraph 1.0 sage: H = G.igraph_graph(edge_attrs = {'capacity':[float(e[2]) for e in G.edges()]}) # optional  python_igraph sage: H.maxflow_value(0, 1, 'capacity') # optional  python_igraph 2.0

incidence_matrix
(oriented=None, sparse=True)¶ Return the incidence matrix of the (di)graph.
Each row is a vertex, and each column is an edge. The vertices as ordered as obtained by the method
vertices()
and the edges as obtained by the methodedge_iterator()
.If the graph is not directed, then return a matrix with entries in \(\{0,1,2\}\). Each column will either contain two \(1\) (at the position of the endpoint of the edge), or one \(2\) (if the corresponding edge is a loop).
If the graph is directed return a matrix in \(\{1,0,1\}\) where \(1\) and \(+1\) correspond respectively to the source and the target of the edge. A loop will correspond to a zero column. In particular, it is not possible to recover the loops of an oriented graph from its incidence matrix.
See the Wikipedia article Incidence_matrix for more information.
INPUT:
oriented
– an optional boolean. If set toTrue
, the matrix will be oriented (i.e. with entries in \(1\), \(0\), \(1\)) and if set toFalse
the matrix will be not oriented (i.e. with entries in \(0\), \(1\), \(2\)). By default, this argument is inferred from the graph type. Note that in the case the graph is not directed and with the optiondirected=True
, a somewhat random direction is chosen for each edge.sparse
– default toTrue
, whether to use a sparse or a dense matrix.
EXAMPLES:
sage: G = graphs.CubeGraph(3) sage: G.incidence_matrix() [0 1 0 0 0 1 0 1 0 0 0 0] [0 0 0 1 0 1 1 0 0 0 0 0] [1 1 1 0 0 0 0 0 0 0 0 0] [1 0 0 1 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 1 0 0 1 1] [0 0 0 0 0 0 1 0 0 1 0 1] [0 0 1 0 0 0 0 0 1 0 1 0] [0 0 0 0 1 0 0 0 1 1 0 0] sage: G.incidence_matrix(oriented=True) [ 0 1 0 0 0 1 0 1 0 0 0 0] [ 0 0 0 1 0 1 1 0 0 0 0 0] [1 1 1 0 0 0 0 0 0 0 0 0] [ 1 0 0 1 1 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 1 0 0 1 1] [ 0 0 0 0 0 0 1 0 0 1 0 1] [ 0 0 1 0 0 0 0 0 1 0 1 0] [ 0 0 0 0 1 0 0 0 1 1 0 0] sage: G = digraphs.Circulant(4, [1,3]) sage: G.incidence_matrix() [1 1 1 0 0 0 1 0] [ 1 0 1 1 1 0 0 0] [ 0 0 0 1 1 1 0 1] [ 0 1 0 0 0 1 1 1] sage: graphs.CompleteGraph(3).incidence_matrix() [1 1 0] [1 0 1] [0 1 1] sage: G = Graph([(0,0),(0,1),(0,1)], loops=True, multiedges=True) sage: G.incidence_matrix(oriented=False) [2 1 1] [0 1 1]
A well known result states that the product of the (oriented) incidence matrix with its transpose of a (nonoriented graph) is in fact the Kirchhoff matrix:
sage: G = graphs.PetersenGraph() sage: m = G.incidence_matrix(oriented=True) sage: m * m.transpose() == G.kirchhoff_matrix() True sage: K = graphs.CompleteGraph(3) sage: m = K.incidence_matrix(oriented=True) sage: m * m.transpose() == K.kirchhoff_matrix() True sage: H = Graph([(0,0),(0,1),(0,1)], loops=True, multiedges=True) sage: m = H.incidence_matrix(oriented=True) sage: m * m.transpose() == H.kirchhoff_matrix() True

is_bipartite
(certificate=False)¶ Returns
True
if graph \(G\) is bipartite,False
if not.Traverse the graph G with breadthfirstsearch and color nodes.
INPUT:
certificate
– whether to return a certificate (False
by default). If set toTrue
, the certificate returned in a proper 2coloring when \(G\) is bipartite, and an odd cycle otherwise.
EXAMPLES:
sage: graphs.CycleGraph(4).is_bipartite() True sage: graphs.CycleGraph(5).is_bipartite() False sage: graphs.RandomBipartite(100,100,0.7).is_bipartite() True
A random graph is very rarely bipartite:
sage: g = graphs.PetersenGraph() sage: g.is_bipartite() False sage: false, oddcycle = g.is_bipartite(certificate = True) sage: len(oddcycle) % 2 1
The method works identically with oriented graphs:
sage: g = DiGraph({0: [1, 2, 3], 2: [1], 3: [4]}) sage: g.is_bipartite() False sage: false, oddcycle = g.is_bipartite(certificate = True) sage: len(oddcycle) % 2 1 sage: graphs.CycleGraph(4).random_orientation().is_bipartite() True sage: graphs.CycleGraph(5).random_orientation().is_bipartite() False

is_cayley
(return_group=False, mapping=False, generators=False, allow_disconnected=False)¶ Check whether the graph is a Cayley graph.
If none of the parameters are
True
, return a boolean indicating whether the graph is a Cayley graph. Otherwise, return a tuple containing said boolean and the requested data. If the graph is not a Cayley graph, each of the data will beNone
.The empty graph is defined to be not a Cayley graph.
Note
For this routine to work on all graphs, the optional packages
gap_packages
anddatabase_gap
need to be installed: to do so, it is enough to runsage i gap_packages database_gap
.INPUT:
return_group
(boolean;False
) – If True, return a group for which the graph is a Cayley graph.mapping
(boolean;False
) – If True, return a mapping from vertices to group elements.generators
(boolean;False
) – If True, return the generating set of the Cayley graph.allow_disconnected
(boolean;False
) – If True, disconnected graphs are considered Cayley if they can be obtained from the Cayley construction with a generating set that does not generate the group.
ALGORITHM:
For connected graphs, find a regular subgroup of the automorphism group. For disconnected graphs, check that the graph is vertextransitive and perform the check on one of its connected components. If a simple graph has density over 1/2, perform the check on its complement as its disconnectedness may increase performance.
EXAMPLES:
A Petersen Graph is not a Cayley graph:
sage: g = graphs.PetersenGraph() sage: g.is_cayley() False
A Cayley digraph is a Cayley graph:
sage: C7 = groups.permutation.Cyclic(7) sage: S = [(1,2,3,4,5,6,7), (1,3,5,7,2,4,6), (1,5,2,6,3,7,4)] sage: d = C7.cayley_graph(generators=S) sage: d.is_cayley() True
Graphs with loops and multiedges will have identity and repeated elements, respectively, among the generators:
sage: g = Graph(graphs.PaleyGraph(9), loops=True, multiedges=True) sage: g.add_edges([(u, u) for u in g]) sage: g.add_edges([(u, u+1) for u in g]) sage: _, S = g.is_cayley(generators=True) sage: S # random [(), (0,2,1)(a,a + 2,a + 1)(2*a,2*a + 2,2*a + 1), (0,2,1)(a,a + 2,a + 1)(2*a,2*a + 2,2*a + 1), (0,1,2)(a,a + 1,a + 2)(2*a,2*a + 1,2*a + 2), (0,1,2)(a,a + 1,a + 2)(2*a,2*a + 1,2*a + 2), (0,2*a + 2,a + 1)(1,2*a,a + 2)(2,2*a + 1,a), (0,a + 1,2*a + 2)(1,a + 2,2*a)(2,a,2*a + 1)]

is_chordal
(certificate=False, algorithm='B')¶ Tests whether the given graph is chordal.
A Graph \(G\) is said to be chordal if it contains no induced hole (a cycle of length at least 4).
Alternatively, chordality can be defined using a Perfect Elimination Order :
A Perfect Elimination Order of a graph \(G\) is an ordering \(v_1,...,v_n\) of its vertex set such that for all \(i\), the neighbors of \(v_i\) whose index is greater that \(i\) induce a complete subgraph in \(G\). Hence, the graph \(G\) can be totally erased by successively removing vertices whose neighborhood is a clique (also called simplicial vertices) [Fulkerson65].
(It can be seen that if \(G\) contains an induced hole, then it can not have a perfect elimination order. Indeed, if we write \(h_1,...,h_k\) the \(k\) vertices of such a hole, then the first of those vertices to be removed would have two nonadjacent neighbors in the graph.)
A Graph is then chordal if and only if it has a Perfect Elimination Order.
INPUT:
certificate
(boolean) – Whether to return a certificate.If
certificate = False
(default), returnsTrue
orFalse
accordingly.If
certificate = True
, returns :(True, peo)
when the graph is chordal, wherepeo
is a perfect elimination order of its vertices.(False, Hole)
when the graph is not chordal, whereHole
(aGraph
object) is an induced subgraph ofself
isomorphic to a hole.
algorithm
– Two algorithms are available for this method (see next section), which can be selected by settingalgorithm = "A"
oralgorithm = "B"
(default). While they will agree on whether the given graph is chordal, they can not be expected to return the same certificates.
ALGORITHM:
This algorithm works through computing a Lex BFS on the graph, then checking whether the order is a Perfect Elimination Order by computing for each vertex \(v\) the subgraph induces by its nondeleted neighbors, then testing whether this graph is complete.
This problem can be solved in \(O(m)\) [Rose75] ( where \(m\) is the number of edges in the graph ) but this implementation is not linear because of the complexity of Lex BFS.
EXAMPLES:
The lexicographic product of a Path and a Complete Graph is chordal
sage: g = graphs.PathGraph(5).lexicographic_product(graphs.CompleteGraph(3)) sage: g.is_chordal() True
The same goes with the product of a random lobster ( which is a tree ) and a Complete Graph
sage: g = graphs.RandomLobster(10,.5,.5).lexicographic_product(graphs.CompleteGraph(3)) sage: g.is_chordal() True
The disjoint union of chordal graphs is still chordal:
sage: (2*g).is_chordal() True
Let us check the certificate given by Sage is indeed a perfect elimination order:
sage: (_, peo) = g.is_chordal(certificate = True) sage: for v in peo: ....: if not g.subgraph(g.neighbors(v)).is_clique(): ....: print("This should never happen !") ....: g.delete_vertex(v)
Of course, the Petersen Graph is not chordal as it has girth 5
sage: g = graphs.PetersenGraph() sage: g.girth() 5 sage: g.is_chordal() False
We can even obtain such a cycle as a certificate
sage: (_, hole) = g.is_chordal(certificate = True) sage: hole Subgraph of (Petersen graph): Graph on 5 vertices sage: hole.is_isomorphic(graphs.CycleGraph(5)) True
REFERENCES:
[Rose75] Rose, D.J. and Tarjan, R.E., Algorithmic aspects of vertex elimination, Proceedings of seventh annual ACM symposium on Theory of computing Page 254, ACM 1975 [Fulkerson65] Fulkerson, D.R. and Gross, OA Incidence matrices and interval graphs Pacific J. Math 1965 Vol. 15, number 3, pages 835–855

is_circulant
(certificate=False)¶ Tests whether the graph is circulant.
For more information, see Wikipedia article Circulant_graph.
INPUT:
certificate
(boolean) – whether to return a certificate for yesanswers. See OUTPUT section. Set toFalse
by default.
OUTPUT:
When
certificate
is set toFalse
(default) this method only returnsTrue
orFalse
answers. Whencertificate
is set toTrue
, the method either returns(False, None)
or(True, lists_of_parameters)
each element oflists_of_parameters
can be used to define the graph as a circulant graph.See the documentation of
CirculantGraph()
andCirculant()
for more information, and the examples below.See also
CirculantGraph()
– a constructor for circulant graphs.EXAMPLES:
The Petersen graph is not a circulant graph:
sage: g = graphs.PetersenGraph() sage: g.is_circulant() False
A cycle is obviously a circulant graph, but several sets of parameters can be used to define it:
sage: g = graphs.CycleGraph(5) sage: g.is_circulant(certificate = True) (True, [(5, [1, 4]), (5, [2, 3])])
The same goes for directed graphs:
sage: g = digraphs.Circuit(5) sage: g.is_circulant(certificate = True) (True, [(5, [1]), (5, [3]), (5, [2]), (5, [4])])
With this information, it is very easy to create (and plot) all possible drawings of a circulant graph:
sage: g = graphs.CirculantGraph(13, [2, 3, 10, 11]) sage: for param in g.is_circulant(certificate = True)[1]: ....: graphs.CirculantGraph(*param) Circulant graph ([2, 3, 10, 11]): Graph on 13 vertices Circulant graph ([1, 5, 8, 12]): Graph on 13 vertices Circulant graph ([4, 6, 7, 9]): Graph on 13 vertices

is_circular_planar
(on_embedding=None, kuratowski=False, set_embedding=True, boundary=None, ordered=False, set_pos=False)¶ Tests whether the graph is circular planar (outerplanar)
A graph is circular planar if it has a planar embedding in which all vertices can be drawn in order on a circle. This method can also be used to check the existence of a planar embedding in which the vertices of a specific set (the boundary) can be drawn on a circle, all other vertices being drawn inside of the circle. An order can be defined on the vertices of the boundary in order to define how they are to appear on the circle.
INPUT:
kuratowski
(boolean)  if set to True, returns a tuple with boolean first entry and the Kuratowski subgraph (i.e. an edge subdivision of \(K_5\) or \(K_{3,3}\)) as the second entry (see OUTPUT below). It is set toFalse
by default.on_embedding
(boolean)  the embedding dictionary to test planarity on. (i.e.: will returnTrue
orFalse
only for the given embedding). It is set toFalse
by default.set_embedding
(boolean)  whether or not to set the instance field variable that contains a combinatorial embedding (clockwise ordering of neighbors at each vertex). This value will only be set if a circular planar embedding is found. It is stored as a Python dict:v1: [n1,n2,n3]
wherev1
is a vertex andn1,n2,n3
are its neighbors. It is set toTrue
by default.boundary
 a set of vertices that are required to be drawn on the circle, all others being drawn inside of it. It is set toNone
by default, meaning that all vertices should be drawn on the boundary.ordered
(boolean)  whether or not to consider the order of the boundary. It is set toFalse
by default, and requiredboundary
to be defined.set_pos
 whether or not to set the position dictionary (for plotting) to reflect the combinatorial embedding. Note that this value will default to False if set_emb is set to False. Also, the position dictionary will only be updated if a circular planar embedding is found.
OUTPUT:
The method returns
True
if the graph is circular planar, andFalse
if it is not.If
kuratowski
is set toTrue
, then this function will return a tuple, whose first entry is a boolean and whose second entry is the Kuratowski subgraph (i.e. an edge subdivision of \(K_5\) or \(K_{3,3}\)) isolated by the BoyerMyrvold algorithm. Note that this graph might contain a vertex or edges that were not in the initial graph. These would be elements referred to below as parts of the wheel and the star, which were added to the graph to require that the boundary can be drawn on the boundary of a disc, with all other vertices drawn inside (and no edge crossings).ALGORITHM:
This is a linear time algorithm to test for circular planarity. It relies on the edgeaddition planarity algorithm due to BoyerMyrvold. We accomplish linear time for circular planarity by modifying the graph before running the general planarity algorithm.
REFERENCE:
[BM04] John M. Boyer and Wendy J. Myrvold, On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. Journal of Graph Algorithms and Applications, Vol. 8, No. 3, pp. 241273, 2004. EXAMPLES:
sage: g439 = Graph({1:[5,7], 2:[5,6], 3:[6,7], 4:[5,6,7]}) sage: g439.show() sage: g439.is_circular_planar(boundary = [1,2,3,4]) False sage: g439.is_circular_planar(kuratowski=True, boundary = [1,2,3,4]) (False, Graph on 8 vertices) sage: g439.is_circular_planar(kuratowski=True, boundary = [1,2,3]) (True, None) sage: g439.get_embedding() {1: [7, 5], 2: [5, 6], 3: [6, 7], 4: [7, 6, 5], 5: [1, 4, 2], 6: [2, 4, 3], 7: [3, 4, 1]}
Order matters:
sage: K23 = graphs.CompleteBipartiteGraph(2,3) sage: K23.is_circular_planar(boundary = [0,1,2,3]) True sage: K23.is_circular_planar(ordered=True, boundary = [0,1,2,3]) False
With a different order:
sage: K23.is_circular_planar(set_embedding=True, boundary = [0,2,1,3]) True

is_clique
(vertices=None, directed_clique=False, induced=True, loops=False)¶ Tests whether a set of vertices is a clique
A clique is a set of vertices such that there is exactly one edge between any two vertices.
INPUT:
vertices
– Vertices can be a single vertex or an iterable container of vertices, e.g. a list, set, graph, file or numeric array. If not passed, defaults to the entire graph.directed_clique
– (default:False
) If set toFalse
, only consider the underlying undirected graph. If set toTrue
and the graph is directed, only return True if all possible edges in _both_ directions exist.induced
– (default:True
) If set toTrue
, check that the graph has exactly one edge between any two vertices. If set toFalse
, check that the graph has at least one edge between any two vertices.loops
– (default:False
) If set toTrue
, check that each vertex of the graph has a loop, and exactly one if furthermoreinduced == True
. If set toFalse
, check that the graph has no loop wheninduced == True
, and ignore loops otherwise.
EXAMPLES:
sage: g = graphs.CompleteGraph(4) sage: g.is_clique([1,2,3]) True sage: g.is_clique() True sage: h = graphs.CycleGraph(4) sage: h.is_clique([1,2]) True sage: h.is_clique([1,2,3]) False sage: h.is_clique() False sage: i = graphs.CompleteGraph(4).to_directed() sage: i.delete_edge([0,1]) sage: i.is_clique(directed_clique=False, induced=True) False sage: i.is_clique(directed_clique=False, induced=False) True sage: i.is_clique(directed_clique=True) False

is_connected
(G)¶ Test whether the (di)graph is connected.
Note that in a graph, path connected is equivalent to connected.
INPUT:
G
(generic_graph) – the input graph.
See also
EXAMPLES:
sage: from sage.graphs.connectivity import is_connected sage: G = Graph( { 0 : [1, 2], 1 : [2], 3 : [4, 5], 4 : [5] } ) sage: is_connected(G) False sage: G.is_connected() False sage: G.add_edge(0,3) sage: is_connected(G) True sage: D = DiGraph( { 0 : [1, 2], 1 : [2], 3 : [4, 5], 4 : [5] } ) sage: is_connected(D) False sage: D.add_edge(0,3) sage: is_connected(D) True sage: D = DiGraph({1:[0], 2:[0]}) sage: is_connected(D) True

is_cut_edge
(G, u, v=None, label=None)¶ Returns True if the input edge is a cutedge or a bridge.
A cut edge (or bridge) is an edge that when removed increases the number of connected components. This function works with simple graphs as well as graphs with loops and multiedges. In a digraph, a cut edge is an edge that when removed increases the number of (weakly) connected components.
INPUT: The following forms are accepted
 is_cut_edge(G, 1, 2 )
 is_cut_edge(G, (1, 2) )
 is_cut_edge(G, 1, 2, ‘label’ )
 is_cut_edge(G, (1, 2, ‘label’) )
OUTPUT:
 Returns True if (u,v) is a cut edge, False otherwise
EXAMPLES:
sage: from sage.graphs.connectivity import is_cut_edge sage: G = graphs.CompleteGraph(4) sage: is_cut_edge(G,0,2) False sage: G.is_cut_edge(0,2) False sage: G = graphs.CompleteGraph(4) sage: G.add_edge((0,5,'silly')) sage: is_cut_edge(G,(0,5,'silly')) True sage: G = Graph([[0,1],[0,2],[3,4],[4,5],[3,5]]) sage: is_cut_edge(G,(0,1)) True sage: G = Graph([[0,1],[0,2],[1,1]], loops = True) sage: is_cut_edge(G,(1,1)) False sage: G = digraphs.Circuit(5) sage: is_cut_edge(G,(0,1)) False sage: G = graphs.CompleteGraph(6) sage: is_cut_edge(G,(0,7)) Traceback (most recent call last): ... ValueError: edge not in graph

is_cut_vertex
(G, u, weak=False)¶ Returns True if the input vertex is a cutvertex.
A vertex is a cutvertex if its removal from the (di)graph increases the number of (strongly) connected components. Isolated vertices or leafs are not cutvertices. This function works with simple graphs as well as graphs with loops and multiple edges.
INPUT:
G
(generic_graph)  the input graph.u
– a vertexweak
– (default:False
) boolean set to \(True\) if the connectivity of directed graphs is to be taken in the weak sense, that is ignoring edges orientations.
OUTPUT:
Returns True if
u
is a cutvertex, and False otherwise.EXAMPLES:
Giving a LollipopGraph(4,2), that is a complete graph with 4 vertices with a pending edge:
sage: from sage.graphs.connectivity import is_cut_vertex sage: G = graphs.LollipopGraph(4,2) sage: is_cut_vertex(G,0) False sage: is_cut_vertex(G,3) True sage: G.is_cut_vertex(3) True
Comparing the weak and strong connectivity of a digraph:
sage: from sage.graphs.connectivity import is_strongly_connected sage: D = digraphs.Circuit(6) sage: is_strongly_connected(D) True sage: is_cut_vertex(D,2) True sage: is_cut_vertex(D, 2, weak=True) False
Giving a vertex that is not in the graph:
sage: G = graphs.CompleteGraph(6) sage: is_cut_vertex(G,7) Traceback (most recent call last): ... ValueError: The input vertex is not in the vertex set.

is_cycle
(directed_cycle=True)¶ Test whether
self
is a (directed) cycle graph.We follow the definition provided in [BM2008] for undirected graphs. A cycle on three or more vertices is a simple graph whose vertices can be arranged in a cyclic order so that two vertices are adjacent if they are consecutive in the order, and not adjacent otherwise. A cycle on a vertex consists of a single vertex provided with a loop and a cycle with two vertices consists of two vertices connected by a pair of parallel edges. In other words, an undirected graph is a cycle if it is 2regular and connected. The empty graph is not a cycle.
For directed graphs, a directed cycle, or circuit, on two or more vertices is a strongly connected directed graph without loops nor multiple edges with has many arcs as vertices. A circuit on a vertex consists of a single vertex provided with a loop.
INPUT:
directed_cycle
– (defaultTrue
) If set toTrue
and the graph is directed, only returnTrue
ifself
is a directed cycle graph (i.e., a circuit). If set toFalse
, we ignore the direction of edges and so opposite arcs become multiple (parallel) edges. This parameter is ignored for undirected graphs.
EXAMPLES:
sage: G = graphs.PetersenGraph() sage: G.is_cycle() False sage: graphs.CycleGraph(5).is_cycle() True sage: Graph([(0,1)]).is_cycle() False sage: Graph([(0,1), (0,1)], multiedges=True).is_cycle() True sage: Graph([(0,1), (0,1), (0,1)], multiedges=True).is_cycle() False sage: Graph().is_cycle() False sage: G = Graph(); G.allow_loops(True); G.add_edge(0,0) sage: G.is_cycle() True sage: digraphs.Circuit(3).is_cycle() True sage: digraphs.Circuit(2).is_cycle() True sage: digraphs.Circuit(2).is_cycle(directed_cycle = False) True sage: D = DiGraph( graphs.CycleGraph(3) ) sage: D.is_cycle() False sage: D.is_cycle(directed_cycle = False) False sage: D.edges(labels = False) [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]

is_drawn_free_of_edge_crossings
()¶ Returns True is the position dictionary for this graph is set and that position dictionary gives a planar embedding.
This simply checks all pairs of edges that don’t share a vertex to make sure that they don’t intersect.
Note
This function require that _pos attribute is set. (Returns False otherwise.)
EXAMPLES:
sage: D = graphs.DodecahedralGraph() sage: D.set_planar_positions() sage: D.is_drawn_free_of_edge_crossings() True

is_equitable
(partition, quotient_matrix=False)¶ Checks whether the given partition is equitable with respect to self.
A partition is equitable with respect to a graph if for every pair of cells C1, C2 of the partition, the number of edges from a vertex of C1 to C2 is the same, over all vertices in C1.
INPUT:
partition
 a list of listsquotient_matrix
 (default False) if True, and the partition is equitable, returns a matrix over the integers whose rows and columns represent cells of the partition, and whose i,j entry is the number of vertices in cell j adjacent to each vertex in cell i (since the partition is equitable, this is well defined)
EXAMPLES:
sage: G = graphs.PetersenGraph() sage: G.is_equitable([[0,4],[1,3,5,9],[2,6,8],[7]]) False sage: G.is_equitable([[0,4],[1,3,5,9],[2,6,8,7]]) True sage: G.is_equitable([[0,4],[1,3,5,9],[2,6,8,7]], quotient_matrix=True) [1 2 0] [1 0 2] [0 2 1]
sage: ss = (graphs.WheelGraph(6)).line_graph(labels=False) sage: prt = [[(0, 1)], [(0, 2), (0, 3), (0, 4), (1, 2), (1, 4)], [(2, 3), (3, 4)]]
sage: ss.is_equitable(prt) Traceback (most recent call last): ... TypeError: Partition ([[(0, 1)], [(0, 2), (0, 3), (0, 4), (1, 2), (1, 4)], [(2, 3), (3, 4)]]) is not valid for this graph: vertices are incorrect.
sage: ss = (graphs.WheelGraph(5)).line_graph(labels=False) sage: ss.is_equitable(prt) False

is_eulerian
(path=False)¶ Return true if the graph has a (closed) tour that visits each edge exactly once.
INPUT:
path
– by default this function finds if the graph contains a closed tour visiting each edge once, i.e. an Eulerian cycle. If you want to test the existence of an Eulerian path, set this argument toTrue
. Graphs with this property are sometimes called semiEulerian.
OUTPUT:
True
orFalse
for the closed tour case. For an open tour search (path``=``True
) the function returnsFalse
if the graph is not semiEulerian, or a tuple (u, v) in the other case. This tuple defines the edge that would make the graph Eulerian, i.e. close an existing open tour. This edge may or may not be already present in the graph.EXAMPLES:
sage: graphs.CompleteGraph(4).is_eulerian() False sage: graphs.CycleGraph(4).is_eulerian() True sage: g = DiGraph({0:[1,2], 1:[2]}); g.is_eulerian() False sage: g = DiGraph({0:[2], 1:[3], 2:[0,1], 3:[2]}); g.is_eulerian() True sage: g = DiGraph({0:[1], 1:[2], 2:[0], 3:[]}); g.is_eulerian() True sage: g = Graph([(1,2), (2,3), (3,1), (4,5), (5,6), (6,4)]); g.is_eulerian() False
sage: g = DiGraph({0: [1]}); g.is_eulerian(path=True) (1, 0) sage: graphs.CycleGraph(4).is_eulerian(path=True) False sage: g = DiGraph({0: [1], 1: [2,3], 2: [4]}); g.is_eulerian(path=True) False
sage: g = Graph({0:[1,2,3], 1:[2,3], 2:[3,4], 3:[4]}, multiedges=True) sage: g.is_eulerian() False sage: e = g.is_eulerian(path=True); e (0, 1) sage: g.add_edge(e) sage: g.is_eulerian(path=False) True sage: g.is_eulerian(path=True) False

is_gallai_tree
()¶ Return whether the current graph is a Gallai tree.
A graph is a Gallai tree if and only if it is connected and its \(2\)connected components are all isomorphic to complete graphs or odd cycles.
A connected graph is not degreechoosable if and only if it is a Gallai tree [erdos1978choos].
REFERENCES:
[erdos1978choos] Erdos, P. and Rubin, A.L. and Taylor, H. Proc. West Coast Conf. on Combinatorics Graph Theory and Computing, Congressus Numerantium vol 26, pages 125–157, 1979 EXAMPLES:
A complete graph is, or course, a Gallai Tree:
sage: g = graphs.CompleteGraph(15) sage: g.is_gallai_tree() True
The Petersen Graph is not:
sage: g = graphs.PetersenGraph() sage: g.is_gallai_tree() False
A Graph built from vertexdisjoint complete graphs linked by one edge to a special vertex \(1\) is a ‘’starshaped’’ Gallai tree
sage: g = 8 * graphs.CompleteGraph(6) sage: g.add_edges([(1,c[0]) for c in g.connected_components()]) sage: g.is_gallai_tree() True

is_hamiltonian
(solver=None, constraint_generation=None, verbose=0, verbose_constraints=False)¶ Test whether the current graph is Hamiltonian.
A graph (resp. digraph) is said to be Hamiltonian if it contains as a subgraph a cycle (resp. a circuit) going through all the vertices.
Testing for Hamiltonicity being NPComplete, this algorithm could run for some time depending on the instance.
ALGORITHM:
See
traveling_salesman_problem()
.INPUT:
solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve()
of the classMixedIntegerLinearProgram
.constraint_generation
(boolean) – whether to use constraint generation when solving the Mixed Integer Linear Program. Whenconstraint_generation = None
, constraint generation is used whenever the graph has a density larger than 70%.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.verbose_constraints
– whether to display which constraints are being generated.
OUTPUT:
Returns
True
if a Hamiltonian cycle/circuit exists, andFalse
otherwise.NOTE:
This function, as
hamiltonian_cycle
andtraveling_salesman_problem
, computes a Hamiltonian cycle if it exists: the user should NOT test for Hamiltonicity usingis_hamiltonian
before callinghamiltonian_cycle
ortraveling_salesman_problem
as it would result in computing it twice.EXAMPLES:
The Heawood Graph is known to be Hamiltonian
sage: g = graphs.HeawoodGraph() sage: g.is_hamiltonian() True
The Petergraph, though, is not
sage: g = graphs.PetersenGraph() sage: g.is_hamiltonian() False

is_immutable
()¶ Returns whether the graph is immutable.
EXAMPLES:
sage: G = graphs.PetersenGraph() sage: G.is_immutable() False sage: Graph(G, immutable=True).is_immutable() True

is_independent_set
(vertices=None)¶ Returns True if the set
vertices
is an independent set, False if not. An independent set is a set of vertices such that there is no edge between any two vertices.INPUT:
vertices
 Vertices can be a single vertex or an iterable container of vertices, e.g. a list, set, graph, file or numeric array. If not passed, defaults to the entire graph.
EXAMPLES:
sage: graphs.CycleGraph(4).is_independent_set([1,3]) True sage: graphs.CycleGraph(4).is_independent_set([1,2,3]) False

is_interval
(certificate=False)¶ Check whether the graph is an interval graph.
An interval graph is one where every vertex can be seen as an interval on the real line so that there is an edge in the graph iff the corresponding intervals intersects.
See the Wikipedia article Interval_graph for more information.
INPUT:
certificate
(boolean) – The function returnsTrue
orFalse
according to the graph whencertificate=False
(default). Whencertificate=True
it returns either(False, None)
or(True, d)
whered
is a dictionary whose keys are the vertices and values are pairs of integers. They correspond to an embedding of the interval graph, each vertex being represented by an interval going from the first of the two values to the second.
ALGORITHM:
Through the use of PQTrees.
AUTHOR:
Nathann Cohen (implementation)
EXAMPLES:
sage: g = Graph({1: [2, 3, 4], 4: [2, 3]}) sage: g.is_interval() True sage: g.is_interval(certificate=True) (True, {1: (0, 5), 2: (4, 6), 3: (1, 3), 4: (2, 7)})
The Petersen Graph is not chordal, so it can’t be an interval graph:
sage: g = graphs.PetersenGraph() sage: g.is_interval() False
A chordal but still not an interval graph:
sage: g = Graph({1: [4, 2, 3], 2: [3, 5], 3: [6]}) sage: g.is_interval() False
See also
Interval Graph Recognition
.PQ
– Implementation of PQTrees.is_chordal()
IntervalGraph()
RandomIntervalGraph()

is_isomorphic
(other, certificate=False, verbosity=0, edge_labels=False)¶ Tests for isomorphism between self and other.
INPUT:
certificate
 if True, then output is \((a, b)\), where \(a\) is a boolean and \(b\) is either a map orNone
.edge_labels
 defaultFalse
, otherwise allows only permutations respecting edge labels.
OUTPUT:
 either a boolean or, if
certificate
isTrue
, a tuple consisting of a boolean and a map orNone
EXAMPLES:
Graphs:
sage: from sage.groups.perm_gps.permgroup_named import SymmetricGroup sage: D = graphs.DodecahedralGraph() sage: E = copy(D) sage: gamma = SymmetricGroup(20).random_element() sage: E.relabel(gamma) sage: D.is_isomorphic(E) True
sage: D = graphs.DodecahedralGraph() sage: S = SymmetricGroup(20) sage: gamma = S.random_element() sage: E = copy(D) sage: E.relabel(gamma) sage: a,b = D.is_isomorphic(E, certificate=True); a True sage: from sage.plot.graphics import GraphicsArray sage: from sage.graphs.generic_graph_pyx import spring_layout_fast sage: position_D = spring_layout_fast(D) sage: position_E = {} sage: for vert in position_D: ....: position_E[b[vert]] = position_D[vert] sage: GraphicsArray([D.plot(pos=position_D), E.plot(pos=position_E)]).show() # long time
sage: g=graphs.HeawoodGraph() sage: g.is_isomorphic(g) True
Multigraphs:
sage: G = Graph(multiedges=True,sparse=True) sage: G.add_edge((0,1,1)) sage: G.add_edge((0,1,2)) sage: G.add_edge((0,1,3)) sage: G.add_edge((0,1,4)) sage: H = Graph(multiedges=True,sparse=True) sage: H.add_edge((3,4)) sage: H.add_edge((3,4)) sage: H.add_edge((3,4)) sage: H.add_edge((3,4)) sage: G.is_isomorphic(H) True
Digraphs:
sage: A = DiGraph( { 0 : [1,2] } ) sage: B = DiGraph( { 1 : [0,2] } ) sage: A.is_isomorphic(B, certificate=True) (True, {0: 1, 1: 0, 2: 2})
Edge labeled graphs:
sage: G = Graph(sparse=True) sage: G.add_edges( [(0,1,'a'),(1,2,'b'),(2,3,'c'),(3,4,'b'),(4,0,'a')] ) sage: H = G.relabel([1,2,3,4,0], inplace=False) sage: G.is_isomorphic(H, edge_labels=True) True
Edge labeled digraphs:
sage: G = DiGraph() sage: G.add_edges( [(0,1,'a'),(1,2,'b'),(2,3,'c'),(3,4,'b'),(4,0,'a')] ) sage: H = G.relabel([1,2,3,4,0], inplace=False) sage: G.is_isomorphic(H, edge_labels=True) True sage: G.is_isomorphic(H, edge_labels=True, certificate=True) (True, {0: 1, 1: 2, 2: 3, 3: 4, 4: 0})

is_planar
(on_embedding=None, kuratowski=False, set_embedding=False, set_pos=False)¶ Test whether the graph is planar.
This wraps the reference implementation provided by John Boyer of the linear time planarity algorithm by edge addition due to Boyer Myrvold. (See reference code in
planarity
).Note
The argument on_embedding takes precedence over
set_embedding
. This means that only theon_embedding
combinatorial embedding will be tested for planarity and no_embedding
attribute will be set as a result of this function call, unlesson_embedding
is None.REFERENCE:
[1] John M. Boyer and Wendy J. Myrvold, On the Cutting Edge: Simplified \(O(n)\) Planarity by Edge Addition. Journal of Graph Algorithms and Applications, Vol. 8, No. 3, pp. 241273, 2004. See also
 “Almost planar graph”:
is_apex()
 “Measuring nonplanarity”:
genus()
,crossing_number()
planar_dual()
faces()
is_polyhedral()
INPUT:
kuratowski
 returns a tuple with boolean as first entry. If the graph is nonplanar, will return the Kuratowski subgraph (i.e. an edge subdivision of \(K_5\) or \(K_{3,3}\)) as the second tuple entry. If the graph is planar, returnsNone
as the second entry.on_embedding
 the embedding dictionary to test planarity on. (i.e.: will returnTrue
orFalse
only for the given embedding.)set_embedding
 whether or not to set the instance field variable that contains a combinatorial embedding (clockwise ordering of neighbors at each vertex). This value will only be set if a planar embedding is found. It is stored as a Python dict:v1: [n1,n2,n3]
wherev1
is a vertex andn1,n2,n3
are its neighbors.set_pos
 whether or not to set the position dictionary (for plotting) to reflect the combinatorial embedding. Note that this value will default to False if set_emb is set to False. Also, the position dictionary will only be updated if a planar embedding is found.
EXAMPLES:
sage: g = graphs.CubeGraph(4) sage: g.is_planar() False
sage: g = graphs.CircularLadderGraph(4) sage: g.is_planar(set_embedding=True) True sage: g.get_embedding() {0: [1, 4, 3], 1: [2, 5, 0], 2: [3, 6, 1], 3: [0, 7, 2], 4: [0, 5, 7], 5: [1, 6, 4], 6: [2, 7, 5], 7: [4, 6, 3]}
sage: g = graphs.PetersenGraph() sage: (g.is_planar(kuratowski=True))[1].adjacency_matrix() [0 1 0 0 0 1 0 0 0] [1 0 1 0 0 0 1 0 0] [0 1 0 1 0 0 0 1 0] [0 0 1 0 0 0 0 0 1] [0 0 0 0 0 0 1 1 0] [1 0 0 0 0 0 0 1 1] [0 1 0 0 1 0 0 0 1] [0 0 1 0 1 1 0 0 0] [0 0 0 1 0 1 1 0 0]
sage: k43 = graphs.CompleteBipartiteGraph(4,3) sage: result = k43.is_planar(kuratowski=True); result (False, Graph on 6 vertices) sage: result[1].is_isomorphic(graphs.CompleteBipartiteGraph(3,3)) True
Multiedged and looped graphs are partially supported:
sage: G = Graph({0:[1,1]}, multiedges=True) sage: G.is_planar() True sage: G.is_planar(on_embedding={}) Traceback (most recent call last): ... NotImplementedError: Cannot compute with embeddings of multipleedged or looped graphs. sage: G.is_planar(set_pos=True) Traceback (most recent call last): ... NotImplementedError: Cannot compute with embeddings of multipleedged or looped graphs. sage: G.is_planar(set_embedding=True) Traceback (most recent call last): ... NotImplementedError: Cannot compute with embeddings of multipleedged or looped graphs. sage: G.is_planar(kuratowski=True) (True, None)
sage: G = graphs.CompleteGraph(5) sage: G = Graph(G, multiedges=True) sage: G.add_edge(0,1) sage: G.is_planar() False sage: b,k = G.is_planar(kuratowski=True) sage: b False sage: k.vertices() [0, 1, 2, 3, 4]
 “Almost planar graph”:

is_regular
(k=None)¶ Return
True
if this graph is (\(k\))regular.INPUT:
k
(default:None
)  the degree of regularity to check for
EXAMPLES:
sage: G = graphs.HoffmanSingletonGraph() sage: G.is_regular() True sage: G.is_regular(9) False
So the HoffmanSingleton graph is regular, but not 9regular. In fact, we can now find the degree easily as follows:
sage: next(G.degree_iterator()) 7
The house graph is not regular:
sage: graphs.HouseGraph().is_regular() False
A graph without vertices is \(k\)regular for every \(k\):
sage: Graph().is_regular() True

is_self_complementary
()¶ Check whether the graph is selfcomplementary.
A (di)graph is selfcomplementary if it is isomorphic to its (di)graph complement. For instance, the path graph \(P_4\) and the cycle graph \(C_5\) are selfcomplementary.
See also
 Wikipedia article Selfcomplementary_graph
 OEIS sequence A000171 for the numbers of selfcomplementary graphs of order \(n\)
 OEIS sequence A003086 for the numbers of selfcomplementary digraphs of order \(n\).
EXAMPLES:
The only selfcomplementary path graph is \(P_4\):
sage: graphs.PathGraph(4).is_self_complementary() True sage: graphs.PathGraph(5).is_self_complementary() False
The only selfcomplementary directed path is \(P_2\):
sage: digraphs.Path(2).is_self_complementary() True sage: digraphs.Path(3).is_self_complementary() False
Every Paley graph is selfcomplementary:
sage: G = graphs.PaleyGraph(9) sage: G.is_self_complementary() True

is_subgraph
(other, induced=True)¶ Return
True
if the graph is a subgraph ofother
, andFalse
otherwise.Warning
Please note that this method does not check whether
self
contains a subgraph isomorphic toother
, but only if it directly contains it as a subgraph !By default
induced
isTrue
for backwards compatibility.INPUT:
induced
 boolean (default:True
) If set toTrue
tests whether the graph is an induced subgraph ofother
that is if the vertices of the graph are also vertices ofother
, and the edges of the graph are equal to the edges ofother
between the vertices contained in the graph.If set to
False
tests whether the graph is a subgraph ofother
that is if all vertices of the graph are also inother
and all edges of the graph are also inother
.
OUTPUT:
boolean –
True
iff the graph is a (possibly induced) subgraph ofother
.See also
If you are interested in the (possibly induced) subgraphs isomorphic to the graph in
other
, you are looking for the following methods:subgraph_search()
– Find a subgraph isomorphic toother
inside of the graph.subgraph_search_count()
– Count the number of such copies.subgraph_search_iterator()
– Iterate over all the copies ofother
contained in the graph.
EXAMPLES:
sage: P = graphs.PetersenGraph() sage: G = P.subgraph(list(range(6))) sage: G.is_subgraph(P) True sage: H = graphs.CycleGraph(5) sage: G = graphs.PathGraph(5) sage: G.is_subgraph(H) False sage: G.is_subgraph(H, induced=False) True sage: H.is_subgraph(G, induced=False) False

is_transitively_reduced
()¶ Tests whether the digraph is transitively reduced.
A digraph is transitively reduced if it is equal to its transitive reduction.
EXAMPLES:
sage: d = DiGraph({0:[1],1:[2],2:[3]}) sage: d.is_transitively_reduced() True sage: d = DiGraph({0:[1,2],1:[2]}) sage: d.is_transitively_reduced() False sage: d = DiGraph({0:[1,2],1:[2],2:[]}) sage: d.is_transitively_reduced() False

is_vertex_transitive
(partition=None, verbosity=0, edge_labels=False, order=False, return_group=True, orbits=False)¶ Returns whether the automorphism group of self is transitive within the partition provided, by default the unit partition of the vertices of self (thus by default tests for vertex transitivity in the usual sense).
EXAMPLES:
sage: G = Graph({0:[1],1:[2]}) sage: G.is_vertex_transitive() False sage: P = graphs.PetersenGraph() sage: P.is_vertex_transitive() True sage: D = graphs.DodecahedralGraph() sage: D.is_vertex_transitive() True sage: R = graphs.RandomGNP(2000, .01) sage: R.is_vertex_transitive() False

kirchhoff_matrix
(weighted=None, indegree=True, normalized=False, **kwds)¶ Returns the Kirchhoff matrix (a.k.a. the Laplacian) of the graph.
The Kirchhoff matrix is defined to be \(D  M\), where \(D\) is the diagonal degree matrix (each diagonal entry is the degree of the corresponding vertex), and \(M\) is the adjacency matrix. If
normalized
isTrue
, then the returned matrix is \(D^{1/2}(DM)D^{1/2}\).( In the special case of DiGraphs, \(D\) is defined as the diagonal indegree matrix or diagonal outdegree matrix according to the value of
indegree
)INPUT:
weighted
– Binary variable : If
True
, the weighted adjacency matrix is used for \(M\), and the diagonal matrix \(D\) takes into account the weight of edges (replace in the definition “degree” by “sum of the incident edges” ).  Else, each edge is assumed to have weight 1.
Default is to take weights into consideration if and only if the graph is weighted.
 If
indegree
– Binary variable :If
True
, each diagonal entry of \(D\) is equal to the indegree of the corresponding vertex.Else, each diagonal entry of \(D\) is equal to the outdegree of the corresponding vertex.
By default,
indegree
is set toTrue
( This variable only matters when the graph is a digraph )
normalized
– Binary variable : If
True
, the returned matrix is \(D^{1/2}(DM)D^{1/2}\), a normalized version of the Laplacian matrix. (More accurately, the normalizing matrix used is equal to \(D^{1/2}\) only for nonisolated vertices. If vertex \(i\) is isolated, then diagonal entry \(i\) in the matrix is 1, rather than a division by zero.)  Else, the matrix \(DM\) is returned
 If
Note that any additional keywords will be passed on to either the
adjacency_matrix
orweighted_adjacency_matrix
method.AUTHORS:
 Tom Boothby
 Jason Grout
EXAMPLES:
sage: G = Graph(sparse=True) sage: G.add_edges([(0,1,1),(1,2,2),(0,2,3),(0,3,4)]) sage: M = G.kirchhoff_matrix(weighted=True); M [ 8 1 3 4] [1 3 2 0] [3 2 5 0] [4 0 0 4] sage: M = G.kirchhoff_matrix(); M [ 3 1 1 1] [1 2 1 0] [1 1 2 0] [1 0 0 1] sage: M = G.laplacian_matrix(normalized=True); M [ 1 1/6*sqrt(3)*sqrt(2) 1/6*sqrt(3)*sqrt(2) 1/3*sqrt(3)] [1/6*sqrt(3)*sqrt(2) 1 1/2 0] [1/6*sqrt(3)*sqrt(2) 1/2 1 0] [ 1/3*sqrt(3) 0 0 1] sage: Graph({0:[],1:[2]}).laplacian_matrix(normalized=True) [ 0 0 0] [ 0 1 1] [ 0 1 1]
A weighted directed graph with loops, changing the variable
indegree
sage: G = DiGraph({1:{1:2,2:3}, 2:{1:4}}, weighted=True,sparse=True) sage: G.laplacian_matrix() [ 4 3] [4 3]
sage: G = DiGraph({1:{1:2,2:3}, 2:{1:4}}, weighted=True,sparse=True) sage: G.laplacian_matrix(indegree=False) [ 3 3] [4 4]

kronecker_product
(other)¶ Returns the tensor product of self and other.
The tensor product of \(G\) and \(H\) is the graph \(L\) with vertex set \(V(L)\) equal to the Cartesian product of the vertices \(V(G)\) and \(V(H)\), and \(((u,v), (w,x))\) is an edge iff  \((u, w)\) is an edge of self, and  \((v, x)\) is an edge of other.
The tensor product is also known as the categorical product and the kronecker product (refering to the kronecker matrix product). See the Wikipedia article Kronecker_product.
EXAMPLES:
sage: Z = graphs.CompleteGraph(2) sage: C = graphs.CycleGraph(5) sage: T = C.tensor_product(Z); T Graph on 10 vertices sage: T.size() 10 sage: T.plot() # long time Graphics object consisting of 21 graphics primitives
sage: D = graphs.DodecahedralGraph() sage: P = graphs.PetersenGraph() sage: T = D.tensor_product(P); T Graph on 200 vertices sage: T.size() 900 sage: T.plot() # long time Graphics object consisting of 1101 graphics primitives

laplacian_matrix
(weighted=None, indegree=True, normalized=False, **kwds)¶ Returns the Kirchhoff matrix (a.k.a. the Laplacian) of the graph.
The Kirchhoff matrix is defined to be \(D  M\), where \(D\) is the diagonal degree matrix (each diagonal entry is the degree of the corresponding vertex), and \(M\) is the adjacency matrix. If
normalized
isTrue
, then the returned matrix is \(D^{1/2}(DM)D^{1/2}\).( In the special case of DiGraphs, \(D\) is defined as the diagonal indegree matrix or diagonal outdegree matrix according to the value of
indegree
)INPUT:
weighted
– Binary variable : If
True
, the weighted adjacency matrix is used for \(M\), and the diagonal matrix \(D\) takes into account the weight of edges (replace in the definition “degree” by “sum of the incident edges” ).  Else, each edge is assumed to have weight 1.
Default is to take weights into consideration if and only if the graph is weighted.
 If
indegree
– Binary variable :If
True
, each diagonal entry of \(D\) is equal to the indegree of the corresponding vertex.Else, each diagonal entry of \(D\) is equal to the outdegree of the corresponding vertex.
By default,
indegree
is set toTrue
( This variable only matters when the graph is a digraph )
normalized
– Binary variable : If
True
, the returned matrix is \(D^{1/2}(DM)D^{1/2}\), a normalized version of the Laplacian matrix. (More accurately, the normalizing matrix used is equal to \(D^{1/2}\) only for nonisolated vertices. If vertex \(i\) is isolated, then diagonal entry \(i\) in the matrix is 1, rather than a division by zero.)  Else, the matrix \(DM\) is returned
 If
Note that any additional keywords will be passed on to either the
adjacency_matrix
orweighted_adjacency_matrix
method.AUTHORS:
 Tom Boothby
 Jason Grout
EXAMPLES:
sage: G = Graph(sparse=True) sage: G.add_edges([(0,1,1),(1,2,2),(0,2,3),(0,3,4)]) sage: M = G.kirchhoff_matrix(weighted=True); M [ 8 1 3 4] [1 3 2 0] [3 2 5 0] [4 0 0 4] sage: M = G.kirchhoff_matrix(); M [ 3 1 1 1] [1 2 1 0] [1 1 2 0] [1 0 0 1] sage: M = G.laplacian_matrix(normalized=True); M [ 1 1/6*sqrt(3)*sqrt(2) 1/6*sqrt(3)*sqrt(2) 1/3*sqrt(3)] [1/6*sqrt(3)*sqrt(2) 1 1/2 0] [1/6*sqrt(3)*sqrt(2) 1/2 1 0] [ 1/3*sqrt(3) 0 0 1] sage: Graph({0:[],1:[2]}).laplacian_matrix(normalized=True) [ 0 0 0] [ 0 1 1] [ 0 1 1]
A weighted directed graph with loops, changing the variable
indegree
sage: G = DiGraph({1:{1:2,2:3}, 2:{1:4}}, weighted=True,sparse=True) sage: G.laplacian_matrix() [ 4 3] [4 3]
sage: G = DiGraph({1:{1:2,2:3}, 2:{1:4}}, weighted=True,sparse=True) sage: G.laplacian_matrix(indegree=False) [ 3 3] [4 4]

latex_options
()¶ Returns an instance of
GraphLatex
for the graph.Changes to this object will affect the LaTeX version of the graph. For a full explanation of how to use LaTeX to render graphs, see the introduction to the
graph_latex
module.EXAMPLES:
sage: g = graphs.PetersenGraph() sage: opts = g.latex_options() sage: opts LaTeX options for Petersen graph: {} sage: opts.set_option('tkz_style', 'Classic') sage: opts LaTeX options for Petersen graph: {'tkz_style': 'Classic'}

layout
(layout=None, pos=None, dim=2, save_pos=False, **options)¶ Returns a layout for the vertices of this graph.
INPUT:
 layout – one of “acyclic”, “circular”, “ranked”, “graphviz”, “planar”, “spring”, or “tree”
 pos – a dictionary of positions or None (the default)
 save_pos – a boolean
 layout options – (see below)
If
layout=algorithm
is specified, this algorithm is used to compute the positions.Otherwise, if
pos
is specified, use the given positions.Otherwise, try to fetch previously computed and saved positions.
Otherwise use the default layout (usually the spring layout)
If
save_pos = True
, the layout is saved for later use.EXAMPLES:
sage: g = digraphs.ButterflyGraph(1) sage: g.layout() {('0', 0): [2.69..., 0.43...], ('0', 1): [1.35..., 0.86...], ('1', 0): [0.89..., 0.42...], ('1', 1): [2.26..., 0.87...]} sage: g.layout(layout="acyclic_dummy", save_pos=True) {('0', 0): [0.3..., 0], ('0', 1): [0.3..., 1], ('1', 0): [0.6..., 0], ('1', 1): [0.6..., 1]} sage: g.layout(dim = 3) {('0', 0): [0.68..., 0.50..., 0.24...], ('0', 1): [1.02..., 0.02..., 0.93...], ('1', 0): [2.06..., 0.49..., 0.23...], ('1', 1): [1.74..., 0.01..., 0.92...]}
Here is the list of all the available layout options:
sage: from sage.graphs.graph_plot import layout_options sage: for key, value in sorted(layout_options.items()): ....: print("option {} : {}".format(key, value)) option by_component : Whether to do the spring layout by connected component  a boolean. option dim : The dimension of the layout  2 or 3. option heights : A dictionary mapping heights to the list of vertices at this height. option iterations : The number of times to execute the spring layout algorithm. option layout : A layout algorithm  one of : "acyclic", "circular" (plots the graph with vertices evenly distributed on a circle), "ranked", "graphviz", "planar", "spring" (traditional spring layout, using the graph's current positions as initial positions), or "tree" (the tree will be plotted in levels, depending on minimum distance for the root). option prog : Which graphviz layout program to use  one of "circo", "dot", "fdp", "neato", or "twopi". option save_pos : Whether or not to save the computed position for the graph. option spring : Use spring layout to finalize the current layout. option tree_orientation : The direction of tree branches  'up', 'down', 'left' or 'right'. option tree_root : A vertex designation for drawing trees. A vertex of the tree to be used as the root for the ``layout='tree'`` option. If no root is specified, then one is chosen close to the center of the tree. Ignored unless ``layout='tree'``
Some of them only apply to certain layout algorithms. For details, see
layout_acyclic()
,layout_planar()
,layout_circular()
,layout_spring()
, …Warning
unknown optional arguments are silently ignored
Warning
graphviz
anddot2tex
are currently required to obtain a nice ‘acyclic’ layout. Seelayout_graphviz()
for installation instructions.A subclass may implement another layout algorithm \(blah\), by implementing a method
.layout_blah
. It may override the default layout by overridinglayout_default()
, and similarly override the predefined layouts.Todo
use this feature for all the predefined graphs classes (like for the Petersen graph, …), rather than systematically building the layout at construction time.

layout_circular
(dim=2, **options)¶ Computes a circular layout for this graph
OUTPUT: a dictionary mapping vertices to positions
EXAMPLES:
sage: G = graphs.CirculantGraph(7, [1, 3]) sage: G.layout_circular() {0: (0.0, 1.0), 1: (0.78..., 0.62...), 2: (0.97..., 0.22...), 3: (0.43..., 0.90...), 4: (0.43..., 0.90...), 5: (0.97..., 0.22...), 6: (0.78..., 0.62...)} sage: G.plot(layout = "circular") Graphics object consisting of 22 graphics primitives

layout_default
(by_component=True, **options)¶ Computes a spring layout for this graph
INPUT:
iterations
– a positive integerdim
– 2 or 3 (default: 2)
OUTPUT: a dictionary mapping vertices to positions
Returns a layout computed by randomly arranging the vertices along the given heights
EXAMPLES:
sage: g = graphs.LadderGraph(3) #TODO!!!! sage: g.layout_spring() {0: [0.73..., 0.29...], 1: [1.37..., 0.30...], 2: [2.08..., 0.89...], 3: [1.23..., 0.83...], 4: [1.88..., 0.30...], 5: [2.53..., 0.22...]} sage: g = graphs.LadderGraph(7) sage: g.plot(layout = "spring") Graphics object consisting of 34 graphics primitives

layout_extend_randomly
(pos, dim=2)¶ Extends randomly a partial layout
INPUT:
pos
: a dictionary mapping vertices to positions
OUTPUT: a dictionary mapping vertices to positions
The vertices not referenced in
pos
are assigned random positions within the box delimited by the other vertices.EXAMPLES:
sage: H = digraphs.ButterflyGraph(1) sage: H.layout_extend_randomly({('0',0): (0,0), ('1',1): (1,1)}) {('0', 0): (0, 0), ('0', 1): [0.0446..., 0.332...], ('1', 0): [0.111..., 0.514...], ('1', 1): (1, 1)}

layout_graphviz
(dim=2, prog='dot', **options)¶ Calls
graphviz
to compute a layout of the vertices of this graph.INPUT:
prog
– one of “dot”, “neato”, “twopi”, “circo”, or “fdp”
EXAMPLES:
sage: g = digraphs.ButterflyGraph(2) sage: g.layout_graphviz() # optional  dot2tex graphviz {('...', ...): [...,...], ('...', ...): [...,...], ('...', ...): [...,...], ('...', ...): [...,...], ('...', ...): [...,...], ('...', ...): [...,...], ('...', ...): [...,...], ('...', ...): [...,...], ('...', ...): [...,...], ('...', ...): [...,...], ('...', ...): [...,...], ('...', ...): [...,...]} sage: g.plot(layout = "graphviz") # optional  dot2tex graphviz Graphics object consisting of 29 graphics primitives
Note: the actual coordinates are not deterministic
By default, an acyclic layout is computed using
graphviz
’sdot
layout program. One may specify an alternative layout program:sage: g.plot(layout = "graphviz", prog = "dot") # optional  dot2tex graphviz Graphics object consisting of 29 graphics primitives sage: g.plot(layout = "graphviz", prog = "neato") # optional  dot2tex graphviz Graphics object consisting of 29 graphics primitives sage: g.plot(layout = "graphviz", prog = "twopi") # optional  dot2tex graphviz Graphics object consisting of 29 graphics primitives sage: g.plot(layout = "graphviz", prog = "fdp") # optional  dot2tex graphviz Graphics object consisting of 29 graphics primitives sage: g = graphs.BalancedTree(5,2) sage: g.plot(layout = "graphviz", prog = "circo") # optional  dot2tex graphviz Graphics object consisting of 62 graphics primitives
Todo
Put here some cool examples showcasing graphviz features.
This requires
graphviz
and thedot2tex
spkg. Here are some installation tips: Install graphviz >= 2.14 so that the programs dot, neato, … are in your path. The graphviz suite can be download from http://graphviz.org.
 Install dot2tex with
sage i dot2tex
Todo
Use the graphviz functionality of Networkx 1.0 once it will be merged into Sage.

layout_planar
(set_embedding=False, on_embedding=None, external_face=None, test=False, circular=False, **options)¶ Uses Schnyder’s algorithm to compute a planar layout for self, raising an error if self is not planar.
INPUT:
set_embedding
 if True, sets the combinatorial embedding used (see self.get_embedding())on_embedding
 dict: provide a combinatorial embeddingexternal_face
 ignoredtest
 if True, perform sanity tests along the waycircular
 ignored
EXAMPLES:
sage: g = graphs.PathGraph(10) sage: g.set_planar_positions(test=True) True sage: g = graphs.BalancedTree(3,4) sage: g.set_planar_positions(test=True) True sage: g = graphs.CycleGraph(7) sage: g.set_planar_positions(test=True) True sage: g = graphs.CompleteGraph(5) sage: g.set_planar_positions(test=True,set_embedding=True) Traceback (most recent call last): ... ValueError: Complete graph is not a planar graph

layout_ranked
(heights=None, dim=2, spring=False, **options)¶ Computes a ranked layout for this graph
INPUT:
 heights – a dictionary mapping heights to the list of vertices at this height
OUTPUT: a dictionary mapping vertices to positions
Returns a layout computed by randomly arranging the vertices along the given heights
EXAMPLES:
sage: g = graphs.LadderGraph(3) sage: g.layout_ranked(heights = dict( (i,[i, i+3]) for i in range(3) )) {0: [0.668..., 0], 1: [0.667..., 1], 2: [0.677..., 2], 3: [1.34..., 0], 4: [1.33..., 1], 5: [1.33..., 2]} sage: g = graphs.LadderGraph(7) sage: g.plot(layout = "ranked", heights = dict( (i,[i, i+7]) for i in range(7) )) Graphics object consisting of 34 graphics primitives

layout_spring
(by_component=True, **options)¶ Computes a spring layout for this graph
INPUT:
iterations
– a positive integerdim
– 2 or 3 (default: 2)
OUTPUT: a dictionary mapping vertices to positions
Returns a layout computed by randomly arranging the vertices along the given heights
EXAMPLES:
sage: g = graphs.LadderGraph(3) #TODO!!!! sage: g.layout_spring() {0: [0.73..., 0.29...], 1: [1.37..., 0.30...], 2: [2.08..., 0.89...], 3: [1.23..., 0.83...], 4: [1.88..., 0.30...], 5: [2.53..., 0.22...]} sage: g = graphs.LadderGraph(7) sage: g.plot(layout = "spring") Graphics object consisting of 34 graphics primitives

layout_tree
(tree_orientation='down', tree_root=None, dim=2, **options)¶ Compute an ordered tree layout for this graph, which should be a tree (no nonoriented cycles).
INPUT:
tree_root
– the root vertex. By defaultNone
. In this case, a vertex is chosen close to the center of the tree.tree_orientation
– the direction in which the tree is growing, can be'up'
,'down'
,'left'
or'right'
(default is'down'
)
If the tree has been given a planar embedding (fixed circular order on the set of neighbors of every vertex) using
set_embedding
, the algorithm will create a layout that respects this embedding.OUTPUT: a dictionary mapping vertices to positions
EXAMPLES:
sage: T = graphs.RandomLobster(25, 0.3, 0.3) sage: T.show(layout='tree', tree_orientation='up') sage: G = graphs.HoffmanSingletonGraph() sage: T = Graph() sage: T.add_edges(G.min_spanning_tree(starting_vertex=0)) sage: T.show(layout='tree', tree_root=0) sage: G = graphs.BalancedTree(2, 2) sage: G.layout_tree(tree_root=0) {0: (1.5, 0), 1: (2.5, 1), 2: (0.5, 1), 3: (3.0, 2), 4: (2.0, 2), 5: (1.0, 2), 6: (0.0, 2)} sage: G = graphs.BalancedTree(2,4) sage: G.plot(layout="tree", tree_root = 0, tree_orientation = "up") Graphics object consisting of 62 graphics primitives sage: G = graphs.RandomTree(80) sage: G.plot(layout="tree", tree_orientation = "right") Graphics object consisting of 160 graphics primitives
Using the embedding when it exists:
sage: T = Graph([[0,1],[0,6],[0,3],[1,2],[1,5],[3,4],[3,7],[3,8]]) sage: T.set_embedding({0:[1,6,3],1:[2,5,0],2:[1],3:[4,7,8,0], ....: 4:[3],5:[1],6:[0],7:[3],8:[3]}) sage: T.layout_tree() {0: (2.166..., 0), 1: (3.5, 1), 2: (4.0, 2), 3: (1.0, 1), 4: (2.0, 2), 5: (3.0, 2), 6: (2.0, 1), 7: (1.0, 2), 8: (0.0, 2)} sage: T.plot(layout="tree", tree_root=3) Graphics object consisting of 18 graphics primitives

lex_BFS
(reverse=False, tree=False, initial_vertex=None)¶ Performs a Lex BFS on the graph.
A Lex BFS ( or Lexicographic BreadthFirst Search ) is a Breadth First Search used for the recognition of Chordal Graphs. For more information, see the Wikipedia article Lexicographic_breadthfirst_search.
INPUT:
reverse
(boolean) – whether to return the vertices in discovery order, or the reverse.False
by default.tree
(boolean) – whether to return the discovery directed tree (each vertex being linked to the one that saw it for the first time)False
by default.initial_vertex
– the first vertex to consider.None
by default.
ALGORITHM:
This algorithm maintains for each vertex left in the graph a code corresponding to the vertices already removed. The vertex of maximal code ( according to the lexicographic order ) is then removed, and the codes are updated.
This algorithm runs in time \(O(n^2)\) ( where \(n\) is the number of vertices in the graph ), which is not optimal. An optimal algorithm would run in time \(O(m)\) ( where \(m\) is the number of edges in the graph ), and require the use of a doublylinked list which are not available in python and can not really be written efficiently. This could be done in Cython, though.
EXAMPLES:
A Lex BFS is obviously an ordering of the vertices:
sage: g = graphs.PetersenGraph() sage: len(g.lex_BFS()) == g.order() True
For a Chordal Graph, a reversed Lex BFS is a Perfect Elimination Order
sage: g = graphs.PathGraph(3).lexicographic_product(graphs.CompleteGraph(2)) sage: g.lex_BFS(reverse=True) [(2, 1), (2, 0), (1, 1), (1, 0), (0, 1), (0, 0)]
And the vertices at the end of the tree of discovery are, for chordal graphs, simplicial vertices (their neighborhood is a complete graph):
sage: g = graphs.ClawGraph().lexicographic_product(graphs.CompleteGraph(2)) sage: v = g.lex_BFS()[1] sage: peo, tree = g.lex_BFS(initial_vertex = v, tree=True) sage: leaves = [v for v in tree if tree.in_degree(v) ==0] sage: all([g.subgraph(g.neighbors(v)).is_clique() for v in leaves]) True

lexicographic_product
(other)¶ Returns the lexicographic product of self and other.
The lexicographic product of \(G\) and \(H\) is the graph \(L\) with vertex set \(V(L)=V(G)\times V(H)\), and \(((u,v), (w,x))\) is an edge iff :
 \((u, w)\) is an edge of \(G\), or
 \(u = w\) and \((v, x)\) is an edge of \(H\).
EXAMPLES:
sage: Z = graphs.CompleteGraph(2) sage: C = graphs.CycleGraph(5) sage: L = C.lexicographic_product(Z); L Graph on 10 vertices sage: L.plot() # long time Graphics object consisting of 36 graphics primitives
sage: D = graphs.DodecahedralGraph() sage: P = graphs.PetersenGraph() sage: L = D.lexicographic_product(P); L Graph on 200 vertices sage: L.plot() # long time Graphics object consisting of 3501 graphics primitives

line_graph
(labels=True)¶ Returns the line graph of the (di)graph.
INPUT:
labels
(boolean) – whether edge labels should be taken in consideration. Iflabels=True
, the vertices of the line graph will be triples(u,v,label)
, and pairs of vertices otherwise.This is set to
True
by default.
The line graph of an undirected graph G is an undirected graph H such that the vertices of H are the edges of G and two vertices e and f of H are adjacent if e and f share a common vertex in G. In other words, an edge in H represents a path of length 2 in G.
The line graph of a directed graph G is a directed graph H such that the vertices of H are the edges of G and two vertices e and f of H are adjacent if e and f share a common vertex in G and the terminal vertex of e is the initial vertex of f. In other words, an edge in H represents a (directed) path of length 2 in G.
Note
As a
Graph
object only accepts hashable objects as vertices (and as the vertices of the line graph are the edges of the graph), this code will fail if edge labels are not hashable. You can also set the argumentlabels=False
to ignore labels.See also
 The
line_graph
module. line_graph_forbidden_subgraphs()
– the forbidden subgraphs of a line graph.is_line_graph()
– tests whether a graph is a line graph.
EXAMPLES:
sage: g = graphs.CompleteGraph(4) sage: h = g.line_graph() sage: h.vertices() [(0, 1, None), (0, 2, None), (0, 3, None), (1, 2, None), (1, 3, None), (2, 3, None)] sage: h.am() [0 1 1 1 1 0] [1 0 1 1 0 1] [1 1 0 0 1 1] [1 1 0 0 1 1] [1 0 1 1 0 1] [0 1 1 1 1 0] sage: h2 = g.line_graph(labels=False) sage: h2.vertices() [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] sage: h2.am() == h.am() True sage: g = DiGraph([[1..4],lambda i,j: i<j]) sage: h = g.line_graph() sage: h.vertices() [(1, 2, None), (1, 3, None), (1, 4, None), (2, 3, None), (2, 4, None), (3, 4, None)] sage: h.edges() [((1, 2, None), (2, 3, None), None), ((1, 2, None), (2, 4, None), None), ((1, 3, None), (3, 4, None), None), ((2, 3, None), (3, 4, None), None)]

longest_path
(s=None, t=None, use_edge_labels=False, algorithm='MILP', solver=None, verbose=0)¶ Return a longest path of
self
.INPUT:
s
(vertex) – forces the source of the path (the method then returns the longest path starting ats
). The argument is set toNone
by default, which means that no constraint is set upon the first vertex in the path.t
(vertex) – forces the destination of the path (the method then returns the longest path ending att
). The argument is set toNone
by default, which means that no constraint is set upon the last vertex in the path.use_edge_labels
(boolean) – whether the labels on the edges are to be considered as weights (a label set toNone
or{}
being considered as a weight of \(1\)). Set toFalse
by default.algorithm
– one of"MILP"
(default) or"backtrack"
. Two remarks on this respect: While the MILP formulation returns an exact answer, the backtrack algorithm is a randomized heuristic.
 As the backtrack algorithm does not support edge weighting,
setting
use_edge_labels=True
will force the use of the MILP algorithm.
solver
– (default:None
) Specify the Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.
Note
The length of a path is assumed to be the number of its edges, or the sum of their labels.
OUTPUT:
A subgraph of
self
corresponding to a (directed ifself
is directed) longest path. Ifuse_edge_labels == True
, a pairweight, path
is returned.ALGORITHM:
Mixed Integer Linear Programming. (This problem is known to be NPHard).
EXAMPLES:
Petersen’s graph being hypohamiltonian, it has a longest path of length \(n2\):
sage: g = graphs.PetersenGraph() sage: lp = g.longest_path() sage: lp.order() >= g.order()  2 True
The heuristic totally agrees:
sage: g = graphs.PetersenGraph() sage: g.longest_path(algorithm="backtrack").edges(labels=False) [(0, 1), (1, 2), (2, 3), (3, 4), (4, 9), (5, 7), (5, 8), (6, 8), (6, 9)]
Let us compute longest paths on random graphs with random weights. Each time, we ensure the resulting graph is indeed a path:
sage: for i in range(20): ....: g = graphs.RandomGNP(15, 0.3) ....: for u, v in g.edges(labels=False): ....: g.set_edge_label(u, v, random()) ....: lp = g.longest_path() ....: if (not lp.is_forest() or ....: not max(lp.degree()) <= 2 or ....: not lp.is_connected()): ....: print("Error!") ....: break

loop_edges
(labels=True)¶ Return a list of all loops in the (di)graph
INPUT:
labels
– whether returned edges have labels ((u,v,l)
) or not ((u,v)
)
EXAMPLES:
sage: G = Graph(loops=True); G Looped graph on 0 vertices sage: G.has_loops() False sage: G.allows_loops() True sage: G.add_edges( [ (0,0), (1,1), (2,2), (3,3), (2,3) ] ) sage: G.loop_edges() [(0, 0, None), (1, 1, None), (2, 2, None), (3, 3, None)] sage: G.loop_edges(labels=False) [(0, 0), (1, 1), (2, 2), (3, 3)] sage: G.allows_loops() True sage: G.has_loops() True sage: G.allow_loops(False) sage: G.has_loops() False sage: G.loop_edges() [] sage: G.edges() [(2, 3, None)] sage: D = DiGraph(loops=True); D Looped digraph on 0 vertices sage: D.has_loops() False sage: D.allows_loops() True sage: D.add_edge((0,0)) sage: D.has_loops() True sage: D.loops() [(0, 0, None)] sage: D.allow_loops(False); D Digraph on 1 vertex sage: D.has_loops() False sage: D.edges() [] sage: G = graphs.PetersenGraph() sage: G.loops() []
sage: D = DiGraph(4, <
