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()	Return a new NetworkX graph from the Sage graph
igraph_graph()	Return an 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.
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 set 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 of vertices
delete_vertex()	Delete vertex, removing all incident edges.
delete_vertices()	Delete vertices from the (di)graph taken from an iterable container of vertices.
has_vertex()	Check 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 given 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 to 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 to v.
set_edge_label()	Set the edge label of a given edge.
has_edge()	Check whether (u, v) is an edge of the (di)graph.
edges()	Return a EdgesView 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 the labels of all edges in self.
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 containing each vertex with probability 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 path 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()	Check 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.
minimum_cycle_basis()	Return a minimum weight cycle basis of the graph.
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.
shortest_simple_paths()	Return an iterator over the simple paths between a pair of vertices.

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 the set 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.
katz_centrality()	Return the katz centrality of the vertex u of the graph.
katz_matrix()	Return the katz matrix of the graph.
pagerank()	Return the PageRank of the vertices of self.

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()	Check whether the graph is planar.
is_circular_planar()	Check whether the graph is circular planar (outerplanar)
is_regular()	Return True if this graph is (\(k\)-)regular.
is_chordal()	Check whether the given graph is chordal.
is_bipartite()	Test whether the given graph is bipartite.
is_circulant()	Check 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()	Check whether a set of vertices is a clique
is_cycle()	Check whether self is a (directed) cycle graph.
is_independent_set()	Check whether vertices is an independent set of self
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 self-complementary.

Traversals:

breadth_first_search()	Return an iterator over the vertices in a breadth-first ordering.
depth_first_search()	Return an iterator over the vertices in a depth-first ordering.
lex_BFS()	Perform a lexicographic breadth first search (LexBFS) on the graph.
lex_UP()	Perform a lexicographic UP search (LexUP) on the graph.
lex_DFS()	Perform a lexicographic depth first search (LexDFS) on the graph.
lex_DOWN()	Perform a lexicographic DOWN search (LexDOWN) 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.
girth()	Return the girth of the graph.
odd_girth()	Return the odd girth of the graph.
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 blocks-and-cuts tree of the graph.
is_cut_edge()	Return True if the input edge is a cut-edge or a bridge.
is_cut_vertex()	Return True if the input vertex is a cut-vertex.
edge_cut()	Return a minimum edge cut between vertices \(s\) and \(t\)
vertex_cut()	Return a minimum vertex cut between non-adjacent 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 edge-disjoint paths between two vertices
vertex_disjoint_paths()	Return a list of vertex-disjoint 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/embedding-related 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.
genus()	Return the number of 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.
layout_planar()	Compute a planar layout of the graph using Schnyder’s algorithm.
is_drawn_free_of_edge_crossings()	Check 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()	Return a spring layout for this graph
layout_ranked()	Return a ranked layout for this graph
layout_extend_randomly()	Extend randomly a partial layout
layout_circular()	Return a circular layout for this graph
layout_tree()	Return an ordered tree layout for this graph
layout_forest()	Return an ordered forest layout for this graph
layout_graphviz()	Call graphviz to compute a layout of the vertices of this graph.
_circle_embedding()	Set some vertices on a circle in the embedding of this graph.
_line_embedding()	Set 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 language 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 edge-disjoint 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
greedy_dominating_set()	Return a greedy distance-\(k\) 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 crossing number of the graph.

Miscellaneous

edge_polytope()	Return the edge polytope of self.
symmetric_edge_polytope()	Return the symmetric edge polytope of self.

Methods

class sage.graphs.generic_graph.GenericGraph

Bases: 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) write G == 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  # random - 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 container of 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(sort=True)
[(1, 1, None)]

This is equivalent to:

sage: G = Graph(loops=True)
sage: G.add_clique([1], loops=True)
sage: G.edges(sort=True)
[(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 – an ordered list of 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)                                                               # needs sage.plot
sage: G.add_cycle(list(range(10, 20)))
sage: show(G)                                                               # needs sage.plot
sage: G.add_cycle(list(range(10)))
sage: show(G)                                                               # needs sage.plot

sage: D = DiGraph()
sage: D.add_cycle(list(range(4)))
sage: D.edges(sort=True)
[(0, 1, None), (1, 2, None), (2, 3, None), (3, 0, None)]

add_edge(u, v=None, label=None)

Add an edge from u to 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.edges(sort=False)
[('label', (1, 2), None)]

You must either use the label keyword:

sage: G = Graph()
sage: G.add_edge((1, 2), label="label")
sage: G.edges(sort=False)
[(1, 2, 'label')]

Or use one of these:

sage: G = Graph()
sage: G.add_edge(1, 2, 'label')
sage: G.edges(sort=False)
[(1, 2, 'label')]
sage: G = Graph()
sage: G.add_edge((1, 2, 'label'))
sage: G.edges(sort=False)
[(1, 2, 'label')]

Vertex name cannot be None, so:

sage: G = Graph()
sage: G.add_edge(None, 4)
sage: G.vertices(sort=True)
[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 – boolean (default: True); if False, remove all loops (v, v) from the input iterator. If None, 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(sort=True)
[(0, 1, None), (0, 2, 'label')]

We demonstrate the loops argument:

sage: H = Graph()
sage: H.add_edges([(0, 0)], loops=False); H.edges(sort=True)
[]
sage: H.add_edges([(0, 0)], loops=None); H.edges(sort=True)
[]
sage: H.add_edges([(0, 0)]); H.edges(sort=True)
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(sort=True)
[]
sage: H.add_edges([(0, 0)], loops=None); H.edges(sort=True)
[(0, 0, None)]
sage: H.add_edges([(0, 0)]); H.edges(sort=True)
[(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 – an ordered list of 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)                                                               # needs sage.plot
sage: G.add_path(list(range(10, 20)))
sage: show(G)                                                               # needs sage.plot
sage: G.add_path(list(range(10)))
sage: show(G)                                                               # needs sage.plot

sage: D = DiGraph()
sage: D.add_path(list(range(4)))
sage: D.edges(sort=True)
[(0, 1, None), (1, 2, None), (2, 3, None)]

add_vertex(name=None)

Create an isolated vertex.

If the vertex already exists, then nothing is done.

INPUT:

• name – an immutable object (default: None); when no name is specified (default), then the new vertex will be represented by the least integer not already representing a vertex. name must be an immutable object (e.g., an integer, a tuple, etc.).

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=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 container of vertex labels. A new label is created, used and returned in the output list for all None values in vertices.

OUTPUT:

Generated names of new vertices if there is at least one None value present in vertices. 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(sort=True)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
sage: G.add_vertices(graphs.CycleGraph(25).vertex_iterator())
sage: G.vertices(sort=True)
[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, vertices=None, base_ring=None, **kwds)

Return the adjacency matrix of the (di)graph.

By default, the matrix returned is over the integers.

INPUT:

• sparse – boolean (default: None); whether to represent with a sparse matrix

• vertices – list (default: None); the ordering of the vertices defining how they should appear in the matrix. By default, the ordering given by GenericGraph.vertices() with sort=True is used. If the vertices are not comparable, the keyword vertices must be used to specify an ordering, or a TypeError exception will be raised.

• base_ring – a ring (default: ZZ); the base ring of the matrix space to use.

• **kwds – other keywords to pass to matrix().

EXAMPLES:

sage: G = graphs.CubeGraph(4)
sage: G.adjacency_matrix()                                                  # needs sage.modules
[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)                                 # needs sage.modules sage.rings.finite_rings
[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()                                                  # needs sage.modules
[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])        # needs sage.modules
[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]

A different base ring:

sage: graphs.PathGraph(5).adjacency_matrix(base_ring=RDF)                   # needs sage.modules
[0.0 1.0 0.0 0.0 0.0]
[1.0 0.0 1.0 0.0 0.0]
[0.0 1.0 0.0 1.0 0.0]
[0.0 0.0 1.0 0.0 1.0]
[0.0 0.0 0.0 1.0 0.0]
sage: type(_)                                                               # needs sage.modules
<class 'sage.matrix.matrix_real_double_dense.Matrix_real_double_dense'>

A different matrix implementation:

sage: graphs.PathGraph(5).adjacency_matrix(sparse=False,                    # needs sage.modules
....:                                      implementation='numpy')
[0 1 0 0 0]
[1 0 1 0 0]
[0 1 0 1 0]
[0 0 1 0 1]
[0 0 0 1 0]
sage: type(_)
<class 'sage.matrix.matrix_numpy_integer_dense.Matrix_numpy_integer_dense'>

As an immutable matrix:

sage: M = graphs.PathGraph(5).adjacency_matrix(sparse=False,                # needs sage.modules
....:                                          immutable=True); M
[0 1 0 0 0]
[1 0 1 0 0]
[0 1 0 1 0]
[0 0 1 0 1]
[0 0 0 1 0]
sage: M[2, 2] = 1                                                           # needs sage.modules
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead
(i.e., use copy(M) to change a copy of M).

all_paths(G, start, end, use_multiedges=False, report_edges=False, labels=False)

Return the list of all paths between a pair of vertices.

If start is the same vertex as end, then [[start]] is returned – a list containing the 1-vertex, 0-edge path “start”.

If G has multiple edges, a path will be returned as many times as the product of the multiplicity of the edges along that path depending on the value of the flag use_multiedges.

INPUT:

• start – a vertex of a graph, where to start

• end – a vertex of a graph, where to end

• use_multiedges – boolean (default: False); this parameter is used only if the graph has multiple edges.

  • If False, the graph is considered as simple and an edge label is arbitrarily selected for each edge as in sage.graphs.generic_graph.GenericGraph.to_simple() if report_edges is True

  • If True, a path will be reported as many times as the edges multiplicities along that path (when report_edges = False or labels = False), or with all possible combinations of edge labels (when report_edges = True and labels = True)

• report_edges – boolean (default: False); whether to report paths as list of vertices (default) or list of edges, if False then labels parameter is ignored

• labels – boolean (default: False); if False, each edge is simply a pair (u, v) of vertices. Otherwise a list of edges along with its edge labels are used to represent the path.

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

sage: g = Graph([(0, 1), (0, 1), (1, 2), (1, 2)], multiedges=True)
sage: g.all_paths(0, 2, use_multiedges=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]

sage: dg = DiGraph({0:[1, 2, 1], 3:[0, 0]}, multiedges=True)
sage: dg.all_paths(3, 1, use_multiedges=True)
[[3, 0, 1], [3, 0, 1], [3, 0, 1], [3, 0, 1]]

sage: g = Graph([(0, 1, 'a'), (0, 1, 'b'), (1, 2, 'c'), (1, 2, 'd')], multiedges=True)
sage: g.all_paths(0, 2, use_multiedges=False)
[[0, 1, 2]]
sage: g.all_paths(0, 2, use_multiedges=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
sage: g.all_paths(0, 2, use_multiedges=True, report_edges=True)
[[(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)]]
sage: g.all_paths(0, 2, use_multiedges=True, report_edges=True, labels=True)
[((0, 1, 'b'), (1, 2, 'd')),
 ((0, 1, 'b'), (1, 2, 'c')),
 ((0, 1, 'a'), (1, 2, 'd')),
 ((0, 1, 'a'), (1, 2, 'c'))]
sage: g.all_paths(0, 2, use_multiedges=False, report_edges=True, labels=True)
[((0, 1, 'b'), (1, 2, 'd'))]
sage: g.all_paths(0, 2, use_multiedges=False, report_edges=False, labels=True)
[[0, 1, 2]]
sage: g.all_paths(0, 2, use_multiedges=True, report_edges=False, labels=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]

allow_loops(new, check=True)

Change whether loops are permitted in the (di)graph

INPUT:

• new – boolean

• check – boolean (default: True); whether to remove existing loops from the (di)graph when the new status is False

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(sort=True)
[]

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(sort=True)
[]

allow_multiple_edges(new, check=True, keep_label='any')

Change whether multiple edges are permitted in the (di)graph.

INPUT:

• new – boolean; if True, the new graph will allow multiple edges

• check – boolean (default: True); if True and new is False, we remove all multiple edges from the graph

• keep_label – string (default: 'any'); used only if new is False and check is True. If there are multiple edges with different labels, this variable defines which label should be kept:

  • 'any' – any label

  • 'min' – the smallest label

  • 'max' – the largest label

Warning

'min' and 'max' only works if the labels can be compared. A TypeError might be raised when working with non-comparable objects in Python 3.

EXAMPLES:

The standard behavior with undirected graphs:

sage: G = Graph(multiedges=True, sparse=True); G
Multi-graph 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(sort=True)
[(0, 1, 3)]

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(sort=True)
[(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(sort=True)
[(0, 1, 3)]

The standard behavior with digraphs:

sage: D = DiGraph(multiedges=True, sparse=True); D
Multi-digraph 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(sort=True)
[(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(sort=True)
[]

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(sort=True)
[]

allows_multiple_edges()

Return whether multiple edges are permitted in the (di)graph.

EXAMPLES:

sage: G = Graph(multiedges=True, sparse=True); G
Multi-graph 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(sort=True)
[(0, 1, None)]

sage: D = DiGraph(multiedges=True, sparse=True); D
Multi-digraph 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(sort=True)
[(0, 1, None)]

am(sparse, vertices=None, base_ring=None, **kwds)

Return the adjacency matrix of the (di)graph.

By default, the matrix returned is over the integers.

INPUT:

• sparse – boolean (default: None); whether to represent with a sparse matrix

• vertices – list (default: None); the ordering of the vertices defining how they should appear in the matrix. By default, the ordering given by GenericGraph.vertices() with sort=True is used. If the vertices are not comparable, the keyword vertices must be used to specify an ordering, or a TypeError exception will be raised.

• base_ring – a ring (default: ZZ); the base ring of the matrix space to use.

• **kwds – other keywords to pass to matrix().

EXAMPLES:

sage: G = graphs.CubeGraph(4)
sage: G.adjacency_matrix()                                                  # needs sage.modules
[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)                                 # needs sage.modules sage.rings.finite_rings
[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()                                                  # needs sage.modules
[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])        # needs sage.modules
[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]

A different base ring:

sage: graphs.PathGraph(5).adjacency_matrix(base_ring=RDF)                   # needs sage.modules
[0.0 1.0 0.0 0.0 0.0]
[1.0 0.0 1.0 0.0 0.0]
[0.0 1.0 0.0 1.0 0.0]
[0.0 0.0 1.0 0.0 1.0]
[0.0 0.0 0.0 1.0 0.0]
sage: type(_)                                                               # needs sage.modules
<class 'sage.matrix.matrix_real_double_dense.Matrix_real_double_dense'>

A different matrix implementation:

sage: graphs.PathGraph(5).adjacency_matrix(sparse=False,                    # needs sage.modules
....:                                      implementation='numpy')
[0 1 0 0 0]
[1 0 1 0 0]
[0 1 0 1 0]
[0 0 1 0 1]
[0 0 0 1 0]
sage: type(_)
<class 'sage.matrix.matrix_numpy_integer_dense.Matrix_numpy_integer_dense'>

As an immutable matrix:

sage: M = graphs.PathGraph(5).adjacency_matrix(sparse=False,                # needs sage.modules
....:                                          immutable=True); M
[0 1 0 0 0]
[1 0 1 0 0]
[0 1 0 1 0]
[0 0 1 0 1]
[0 0 0 1 0]
sage: M[2, 2] = 1                                                           # needs sage.modules
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead
(i.e., use copy(M) to change a copy of M).

antisymmetric()

Check whether the graph is antisymmetric.

A graph represents an antisymmetric relation if the existence of a path from a vertex \(x\) to a vertex \(y\) implies that there is not a path from \(y\) to \(x\) unless \(x = y\).

EXAMPLES:

A directed acyclic graph is antisymmetric:

sage: G = digraphs.RandomDirectedGNR(20, 0.5)                               # needs networkx
sage: G.antisymmetric()                                                     # needs networkx
True

Loops are allowed:

sage: G.allow_loops(True)                                                   # needs networkx
sage: G.add_edge(0, 0)                                                      # needs networkx
sage: G.antisymmetric()                                                     # needs networkx
True

An undirected graph is never antisymmetric unless it is just a union of isolated vertices (with possible loops):

sage: graphs.RandomGNP(20, 0.5).antisymmetric()                             # needs networkx
False
sage: Graph(3).antisymmetric()
True
sage: Graph([(i, i) for i in range(3)], loops=True).antisymmetric()
True
sage: DiGraph([(i, i) for i in range(3)], loops=True).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 group

• return_group – default True

• orbits – returns the orbits of the group acting on the vertices of the graph

• algorithm – If algorithm = "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 to None (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: # needs sage.groups
sage: graphs_query = GraphQuery(display_cols=['graph6'],num_vertices=4)
sage: L = graphs_query.get_graphs_list()
sage: graphs_list.show_graphs(L)                                            # needs sage.plot
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: # needs sage.groups
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()                                                # needs sage.groups
Permutation Group with generators [('a','b')]

Digraphs:

sage: D = DiGraph( { 0:[1], 1:[2], 2:[3], 3:[4], 4:[0] } )
sage: D.automorphism_group()                                                # needs sage.groups
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)                                # needs sage.groups
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")              # needs sage.groups
Permutation Group with generators [(1,4)(2,3)]

sage: G = Graph({0 : {1 : 7}})
sage: G.automorphism_group(edge_labels=True)                                # needs sage.groups
Permutation Group with generators [(0,1)]

sage: # needs sage.groups
sage: foo = Graph(sparse=True)
sage: bar = 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)                  # needs sage.groups
120

Or, just the orbits (note that each graph here is vertex transitive)

sage: # needs sage.groups
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: orb = G.automorphism_group(partition=[[0],list(range(1,10))],
....:                            return_group=False, orbits=True, algorithm='sage')
sage: sorted([sorted(o) for o in orb], key=len)
[[0], [1, 4, 5], [2, 3, 6, 7, 8, 9]]
sage: C = graphs.CubeGraph(3)
sage: orb = C.automorphism_group(orbits=True, return_group=False, algorithm='sage')
sage: [sorted(o) for o in orb]
[['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: # optional - bliss
sage: G = graphs.HallJankoGraph()
sage: A1 = G.automorphism_group()                                           # needs sage.groups
sage: A2 = G.automorphism_group(algorithm='bliss')
sage: A1.is_isomorphic(A2)                                                  # needs sage.groups
True

average_degree()

Return the average degree of the graph.

The average degree of a graph \(G=(V,E)\) is equal to \(\frac{2|E|}{|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: tree = graphs.RandomTree(20)
sage: tree.average_degree() < 2
True

For any graph, it is equal to \(\frac{2|E|}{|V|}\):

sage: g = graphs.RandomGNP(20, .4)
sage: g.average_degree() == 2 * g.size() / g.order()
True

average_distance(by_weight=False, algorithm=None, weight_function=None, check_weight=True)

Return the average distance between vertices of the graph.

Formally, for a graph \(G\) this value is equal to \(\frac 1 {n(n-1)} \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() and shortest_path_all_pairs(), which have very similar input variables.

INPUT:

• by_weight – boolean (default: False); if True, the edges in the graph are weighted, otherwise all edges have weight 1

• algorithm – string (default: None); one of the algorithms available for method wiener_index()

• weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l, if l is not None, else 1 as a weight.

• check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge

EXAMPLES:

From [GYLL1993]:

sage: g=graphs.PathGraph(10)
sage: w=lambda x: (x*(x*x -1)/6)/(x*(x-1)/2)
sage: g.average_distance()==w(10)
True

Average distance of a circuit:

sage: g = digraphs.Circuit(6)
sage: g.average_distance()
3

blocks_and_cut_vertices(G, algorithm='Tarjan_Boost', sort=False, key=None)

Return 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 – string (default: "Tarjan_Boost"); the algorithm to use among:

  • "Tarjan_Boost" (default) – Tarjan’s algorithm (Boost implementation)

  • "Tarjan_Sage" – Tarjan’s algorithm (Sage implementation)

• sort – boolean (default: False); whether to sort vertices inside the components and the list of cut vertices currently only available for ``”Tarjan_Sage”``

• key – a function (default: None); a function that takes a vertex as its one argument and returns a value that can be used for comparisons in the sorting algorithm (we must have sort=True)

OUTPUT: (B, C), where B is a list of blocks - each is a list of vertices and the blocks are the corresponding induced subgraphs - and C 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

• blocks_and_cuts_tree()

• sage.graphs.base.boost_graph.blocks_and_cut_vertices()

• is_biconnected()

• bridges()

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: B, C = blocks_and_cut_vertices(rings, algorithm="Tarjan_Sage", sort=True)
sage: B, C
([[0, 1, 2, 3, 4], [0, 6, 7, 8, 9]], [0])
sage: B2, C2 = blocks_and_cut_vertices(rings, algorithm="Tarjan_Sage", sort=False)
sage: Set(map(Set, B)) == Set(map(Set, B2)) and set(C) == set(C2)
True

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 (github issue #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)

Return the blocks-and-cuts 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 (type C).

There is an edge between a vertex \(u\) of type B and a vertex \(v\) of type C if the cut-vertex 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.

See also

• blocks_and_cut_vertices()

• is_biconnected()

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(sort=True)
[('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, edges=False)

Return an iterator over the vertices in a breadth-first ordering.

INPUT:

• start – vertex or list of vertices from which to start the traversal

• ignore_direction – boolean (default: False); only applies to directed graphs. If True, searches across edges in either direction.

• distance – integer (default: None); the maximum distance from the start nodes to traverse. The start nodes are at distance zero from themselves.

• neighbors – function (default: None); a function that inputs a vertex and return a list of vertices. For an undirected graph, neighbors is by default the neighbors() function. For a digraph, the neighbors function defaults to the neighbor_out_iterator() function of the graph.

• report_distance – boolean (default: False); if True, reports pairs (vertex, distance) where distance is the distance from the start nodes. If False only the vertices are reported.

• edges – boolean (default: False); whether to return the edges of the BFS tree in the order of visit or the vertices (default). Edges are directed in root to leaf orientation of the tree.

  Note that parameters edges and report_distance cannot be True simultaneously.

See also

• breadth_first_search – breadth-first search for fast compiled graphs.

• depth_first_search – depth-first search for fast compiled graphs.

• depth_first_search() – depth-first 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 setting neighbors to be the neighbors_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 (github issue #16470) using the keyword report_distance to get pairs (vertex, distance) encoding the distance from 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()                                                              # needs sage.plot
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)]

You can get edges of the BFS tree instead of the vertices using the edges parameter:

sage: D = DiGraph({1:[2,3],2:[4],3:[4],4:[1],5:[2,6]})
sage: list(D.breadth_first_search(1, edges=True))
[(1, 2), (1, 3), (2, 4)]

canonical_label(partition=None, certificate=False, 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 to True, 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 to True, 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 possible

    Note

    Make sure you always compare canonical forms obtained by the same algorithm.

• return_graph – boolean (default: True). When set to False, returns the list of edges of the canonical graph instead of the canonical graph; only available when 'bliss' is explicitly set as algorithm.

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()
Multi-graph on 2 vertices
sage: Graph('A?').canonical_label()
Graph on 2 vertices

sage: P = graphs.PetersenGraph()
sage: DP = P.to_directed()
sage: DP.canonical_label(algorithm='sage').adjacency_matrix()               # needs sage.modules
[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",        # optional - bliss
....:                   certificate=True)
(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(sort=True, labels=False)
[(0, 3), (1, 2)]
sage: g_bliss.edges(sort=True, labels=False)                        # optional - bliss
[(0, 1), (2, 3)]

cartesian_product(other)

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

• graph_products – a module on graph products

categorical_product(other)

Return 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 (referring 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

centrality_betweenness(k=None, normalized=True, weight=None, endpoints=False, seed=None, exact=False, algorithm=None)

Return the betweenness centrality.

The betweenness centrality of a vertex is the fraction of number of shortest paths that go through each vertex. 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 (default: None); if set to an integer, use k node samples to estimate betweenness. Higher values give better approximations. Not available when algorithm="Sage".

• weight – string (default: None); if set to a string, use that attribute of the nodes as weight. weight = True is equivalent to weight = "weight". Not available when algorithm="Sage".

• endpoints – boolean (default: False); if set to True it includes the endpoints in the shortest paths count. Not available when algorithm="Sage".

• exact – boolean (default: False); whether to compute over rationals or on double C variables. Not available when algorithm="NetworkX".

• algorithm – string (default: None); can be either "Sage" (see centrality), "NetworkX" or "None". In the latter case, Sage’s algorithm will be used whenever possible.

See also

• centrality_degree()

• centrality_closeness()

EXAMPLES:

sage: g = graphs.ChvatalGraph()
sage: g.centrality_betweenness() # abs tol 1e-10
{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 1e-10
{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])                                                 # needs sage.plot
sage: D = D.to_undirected()
sage: D.show(figsize=[2,2])                                                 # needs sage.plot
sage: D.centrality_betweenness() # abs tol abs 1e-10
{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)

Return the closeness centrality of all vertices in 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 [OLJ2014]. In formulas,

\[c(v)=\frac{r(v)-1}{\sum_{w \in R(v)} d(v,w)}\frac{r(v)-1}{n-1}\]

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 graph-theoretic 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,’ [Bor1995].

For more information, see the Wikipedia article Centrality.

INPUT:

• vert – the vertex or the list of vertices we want to analyze. If None (default), all vertices are considered.

• by_weight – boolean (default: False); if True, the edges in the graph are weighted, and otherwise all edges have weight 1

• algorithm – string (default: None); 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).

  • 'Floyd-Warshall-Cython': the Cython implementation of the Floyd-Warshall algorithm. Works only if by_weight==False and all centralities are needed.

  • 'Floyd-Warshall-Python': the Python implementation of the Floyd-Warshall 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' if by_weight is False, 'Dijkstra_Boost' if all weights are positive, 'Johnson_Boost' otherwise.

• weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight, if l is not None, else 1 as a weight.

• check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge.

OUTPUT:

If vert is a vertex, the closeness centrality of that vertex. Otherwise, a dictionary associating to each vertex in vert 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.

See also

• centrality_closeness_top_k()

• centrality_degree()

• centrality_betweenness()

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])                                                 # needs sage.plot
sage: D.centrality_closeness(vert=[0,1])
{0: 1.0, 1: 0.3333333333333333}
sage: D = D.to_undirected()
sage: D.show(figsize=[2,2])                                                 # needs sage.plot
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 1e-12
{(0, 0): 0.75, (0, 1): 0.75}
sage: D.centrality_closeness((0,0), weight_function=weight_function) # tol abs 1e-12
0.075

characteristic_polynomial(var='x', laplacian=False)

Return 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 and charpoly are aliases and thus provide exactly the same method.

INPUT:

• x – (default: 'x'); the variable of the characteristic polynomial

• laplacian – boolean (default: False); if True, use the Laplacian matrix

See also

• kirchhoff_matrix()

• laplacian_matrix()

EXAMPLES:

sage: P = graphs.PetersenGraph()
sage: P.characteristic_polynomial()                                         # needs sage.modules
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()                                                          # needs sage.modules
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)                           # needs sage.modules
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)

Return 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 and charpoly are aliases and thus provide exactly the same method.

INPUT:

• x – (default: 'x'); the variable of the characteristic polynomial

• laplacian – boolean (default: False); if True, use the Laplacian matrix

See also

• kirchhoff_matrix()

• laplacian_matrix()

EXAMPLES:

sage: P = graphs.PetersenGraph()
sage: P.characteristic_polynomial()                                         # needs sage.modules
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()                                                          # needs sage.modules
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)                           # needs sage.modules
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)
sage: G.set_vertices({0:'vertex0'})
sage: print(G.order(), G.size())
4 4
sage: G.name()
'Cycle graph'
sage: G.get_vertex(0)
'vertex0'
sage: H = G.copy(sparse=True)
sage: H.clear()
sage: print(H.order(), H.size())
0 0
sage: H.name()
''
sage: H.get_vertex(0)
sage: H = G.copy(sparse=False)
sage: H.clear()
sage: print(H.order(), H.size())
0 0
sage: H.name()
''
sage: H.get_vertex(0)

cluster_transitivity()

Return the transitivity (fraction of transitive triangles) of the graph.

Transitivity is the fraction of all existing triangles over all connected triples (triads), \(T = 3\times\frac{\text{triangles}}{\text{triads}}\).

See also section “Clustering” in chapter “Algorithms” of [HSS].

EXAMPLES:

sage: graphs.FruchtGraph().cluster_transitivity()                           # needs networkx
0.25

cluster_triangles(nbunch=None, implementation=None)

Return the number of triangles for the set \(nbunch\) of vertices as a dictionary keyed by vertex.

See also section “Clustering” in chapter “Algorithms” of [HSS].

INPUT:

• nbunch – a list of vertices (default: None); the vertices to inspect. If ``nbunch=None, returns data for all vertices in the graph.

• implementation – string (default: None); one of 'sparse_copy', 'dense_copy', 'networkx' or None (default). In the latter case, the best algorithm available is used. Note that 'networkx' does not support directed graphs.

EXAMPLES:

sage: F = graphs.FruchtGraph()
sage: list(F.cluster_triangles().values())
[1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0]
sage: F.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: F.cluster_triangles(nbunch=[0, 1, 2])
{0: 1, 1: 1, 2: 0}

sage: G = graphs.RandomGNP(20, .3)
sage: d1 = G.cluster_triangles(implementation="networkx")                   # needs networkx
sage: d2 = G.cluster_triangles(implementation="dense_copy")
sage: d3 = G.cluster_triangles(implementation="sparse_copy")
sage: d1 == d2 and d1 == d3                                                 # needs networkx
True

clustering_average(implementation=None)

Return the average clustering coefficient.

The clustering coefficient of a node \(i\) is the fraction of existing triangles containing node \(i\) over 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 [HSS].

INPUT:

• implementation – string (default: None); one of 'boost', 'sparse_copy', 'dense_copy', 'networkx' or None (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')  # needs networkx
0.25

clustering_coeff(nodes=None, weight=False, implementation=None)

Return 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\) over 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 [HSS].

INPUT:

• nodes – an iterable container of vertices (default: None); the vertices to inspect. By default, returns data on all vertices in graph

• weight – string or boolean (default: False); if it is a string it uses the indicated edge property as weight. weight = True is equivalent to weight = 'weight'

• implementation – string (default: None); one of 'boost', 'sparse_copy', 'dense_copy', 'networkx' or None (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 support node different from None

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)                  # needs networkx
{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],                # needs networkx
....:                                         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)

Return 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 \(C_1\), \(C_2\) of the partition, the number of edges from a vertex of \(C_1\) to \(C_2\) is the same, over all vertices in \(C_1\).

A partition \(P_1\) is finer than \(P_2\) (\(P_2\) is coarser than \(P_1\)) if every cell of \(P_1\) is a subset of a cell of \(P_2\).

INPUT:

• partition – a list of lists

• sparse – boolean (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(sort=True)
sage: Pi = [verts[:1], verts[1:]]
sage: Pi
[['000'], ['001', '010', '011', '100', '101', '110', '111']]
sage: [sorted(cell) for cell in 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, 4), (0, 2)], [(2, 3), (3, 4)]]

ALGORITHM: Brendan D. McKay’s Master’s Thesis, University of Melbourne, 1976.

complement()

Return 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                             # needs sage.plot
Graphics object consisting of 26 graphics primitives
sage: PC = P.complement()
sage: PC.plot()                     # long time                             # needs sage.plot
Graphics object consisting of 41 graphics primitives

sage: graphs.TetrahedralGraph().complement().size()
0
sage: graphs.CycleGraph(4).complement().edges(sort=True)
[(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=None, key=None)

Return a list of the vertices connected to vertex.

INPUT:

• G – the input graph

• v – the vertex to search for

• sort – boolean (default: None); if True, vertices inside the component are sorted according to the default ordering

  As of github issue #35889, this argument must be explicitly specified (unless a key is given); otherwise a warning is printed and sort=True is used. The default will eventually be changed to False.

• key – a function (default: None); a function that takes a vertex as its one argument and returns a value that can be used for comparisons in the sorting algorithm (we must have sort=True)

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, sort=True)
[0, 1, 2, 3]
sage: G.connected_component_containing_vertex(0, sort=True)
[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, sort=True)
[0, 1, 2, 3]
sage: connected_component_containing_vertex(D, 0, sort=True, key=lambda x: -x)
[3, 2, 1, 0]

connected_components(G, sort=None, key=None)

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 – the input graph

• sort – boolean (default: None); if True, vertices inside each component are sorted according to the default ordering

  As of github issue #35889, this argument must be explicitly specified (unless a key is given); otherwise a warning is printed and sort=True is used. The default will eventually be changed to False.

• key – a function (default: None); a function that takes a vertex as its one argument and returns a value that can be used for comparisons in the sorting algorithm (we must have sort=True)

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, sort=True)
[[0, 1, 2, 3], [4, 5, 6]]
sage: G.connected_components(sort=True)
[[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, sort=True)
[[0, 1, 2, 3], [4, 5, 6]]
sage: connected_components(D, sort=True, key=lambda x: -x)
[[3, 2, 1, 0], [6, 5, 4]]

connected_components_number(G)

Return the number of connected components.

INPUT:

• G – 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)                                                # needs sage.plot
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)                                                # needs sage.plot
sage: L = D.connected_components_subgraphs()
sage: graphs_list.show_graphs(L)                                                # needs sage.plot

connected_subgraph_iterator(G, k=None, vertices_only=False, edges_only=False, labels=False, induced=True, exactly_k=False)

Return an terator 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 – a Graph or a DiGraph; loops and multiple edges are allowed

• k – (optional) integer; maximum order of the connected subgraphs to report; by default, the method iterates over all connected subgraphs (equivalent to k == n)

• vertices_only – boolean (default: False); whether to return (Di)Graph or list of vertices. This parameter is ignored when induced is True.

• edges_only – boolean (default: False); whether to return (Di)Graph or list of edges. When vertices_only is True, this parameter is ignored.

• labels – boolean (default: False); whether to return labelled edges or not. This parameter is used only when vertices_only is False and edges_only is True.

• induced – boolean (default: True); whether to return induced connected sub(di)graph only or also non-induced sub(di)graphs. This parameter can be set to False for simple (di)graphs only.

• exactly_k – boolean (default: False); True if we only return graphs of order \(k\), False if we return graphs of order at most \(k\).

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=3, vertices_only=True, exactly_k=True))
[[1, 2, 3], [1, 2, 4], [2, 3, 4]]
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]]

sage: G = graphs.CompleteGraph(3)
sage: len(list(G.connected_subgraph_iterator()))
7
sage: len(list(G.connected_subgraph_iterator(vertices_only=True)))
7
sage: len(list(G.connected_subgraph_iterator(edges_only=True)))
7
sage: len(list(G.connected_subgraph_iterator(induced=False)))
10

sage: G = DiGraph([(0, 1), (1, 0), (1, 2), (2, 1)])
sage: len(list(G.connected_subgraph_iterator()))
6
sage: len(list(G.connected_subgraph_iterator(vertices_only=True)))
6
sage: len(list(G.connected_subgraph_iterator(edges_only=True)))
6
sage: len(list(G.connected_subgraph_iterator(induced=False)))
18

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(sort=True)
[(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(sort=True)
[(0, 2, None), (0, 2, None), (0, 3, None), (0, 3, None), (2, 3, None)]
sage: G.contract_edge((0, 2)); G.edges(sort=True)
[(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(sort=True)
[(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 2-tuples or 3-tuples 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(sort=True)
[(0, 3, None), (0, 3, None), (0, 3, None)]
sage: G.contract_edges([(1, 3), (2, 3)]); G.edges(sort=True)
[(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(sort=True)
[(0, 0, None)]

sage: D = digraphs.Complete(4)
sage: D.allow_loops(True); D.allow_multiple_edges(True)
sage: D.contract_edges([(0, 1), (1, 0), (0, 2)]); D.edges(sort=True)
[(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)]

copy(weighted=None, data_structure=None, sparse=None, immutable=None, hash_labels=None)

Change the graph implementation

INPUT:

• weighted – boolean (default: None); weightedness for the copy. Might change the equality class if not None.

• sparse – boolean (default: None); sparse=True is an alias for data_structure="sparse", and sparse=False is an alias for data_structure="dense". Only used when data_structure=None.

• data_structure – string (default: None); one of "sparse", "static_sparse", or "dense". See the documentation of Graph or DiGraph.

• immutable – boolean (default: None); whether to create a mutable/immutable copy. Only used when data_structure=None.

  • immutable=None (default) means that the graph and its copy will behave the same way.

  • immutable=True is a shortcut for data_structure='static_sparse'

  • immutable=False means that the created graph is mutable. When used to copy an immutable graph, the data structure used is "sparse" unless anything else is specified.

• hash_labels – boolean (default: None); whether to include edge labels during hashing of the copy. This parameter defaults to True if the graph is weighted. This parameter is ignored when parameter immutable is not True. Beware that trying to hash unhashable labels will raise an error.

Note

If the graph uses StaticSparseBackend and the _immutable flag, then self 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 data structure or weightedness. Otherwise simply do copy(g) instead of g.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(9)
sage: H = G.copy()
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 non-planarity; 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 NP-hard problem.

cycle_basis(output='vertex')

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

See the Wikipedia article Cycle_basis for more information.

INPUT:

• output – string (default: 'vertex'); whether every cycle is given as a list of vertices (output == 'vertex') or a list of edges (output == 'edge')

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()                                                       # needs networkx
[[1, 6, 8, 5, 0], [4, 9, 6, 8, 5, 0], [7, 9, 6, 8, 5],
 [4, 3, 8, 5, 0], [1, 2, 3, 8, 5, 0], [7, 2, 3, 8, 5]]

One can also get the result as a list of lists of edges:

sage: g.cycle_basis(output='edge')                                          # needs networkx
[[(1, 6, None), (6, 8, None), (8, 5, None), (5, 0, None),
 (0, 1, None)], [(4, 9, None), (9, 6, None), (6, 8, None),
 (8, 5, None), (5, 0, None), (0, 4, None)], [(7, 9, None),
 (9, 6, None), (6, 8, None), (8, 5, None), (5, 7, None)],
 [(4, 3, None), (3, 8, None), (8, 5, None), (5, 0, None),
 (0, 4, None)], [(1, 2, None), (2, 3, None), (3, 8, None),
 (8, 5, None), (5, 0, None), (0, 1, None)], [(7, 2, None),
 (2, 3, None), (3, 8, None), (8, 5, None), (5, 7, None)]]

Checking the given cycles are algebraically free:

sage: g = graphs.RandomGNP(30, .4)                                          # needs networkx
sage: basis = g.cycle_basis()                                               # needs networkx

Building the space of (directed) edges over \(Z/2Z\). On the way, building a dictionary associating a unique vector to each undirected edge:

sage: m = g.size()
sage: edge_space = VectorSpace(FiniteField(2), m)                           # needs sage.modules sage.rings.finite_rings
sage: edge_vector = dict(zip(g.edges(labels=False, sort=False),             # needs sage.modules sage.rings.finite_rings
....:                        edge_space.basis()))
sage: for (u, v), vec in list(edge_vector.items()):                         # needs sage.modules sage.rings.finite_rings
....:    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]                # needs networkx sage.modules sage.rings.finite_rings
sage: edge_space.span(basis_as_vectors).rank() == len(basis)                # needs networkx sage.modules sage.rings.finite_rings
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()                                                       # needs networkx
[[0, 2], [2, 1, 0]]
sage: G.cycle_basis(output='edge')                                          # needs networkx
[[(0, 2, 'b'), (2, 0, 'a')], [(2, 1, 'd'), (1, 0, 'c'), (0, 2, 'a')]]
sage: H = Graph([(1, 2), (2, 3), (2, 3), (3, 4), (1, 4),
....:            (1, 4), (4, 5), (5, 6), (4, 6), (6, 7)], multiedges=True)
sage: H.cycle_basis()                                                       # needs networkx
[[1, 4], [2, 3], [4, 3, 2, 1], [6, 5, 4]]

Disconnected graph:

sage: G.add_cycle(["Hey", "Wuuhuu", "Really ?"])
sage: [sorted(c) for c in G.cycle_basis()]                                  # needs networkx
[['Hey', 'Really ?', 'Wuuhuu'], [0, 2], [0, 1, 2]]
sage: [sorted(c) for c in G.cycle_basis(output='edge')]                     # needs networkx
[[('Hey', 'Wuuhuu', None),
  ('Really ?', 'Hey', None),
  ('Wuuhuu', 'Really ?', None)],
 [(0, 2, 'a'), (2, 0, 'b')],
 [(0, 2, 'b'), (1, 0, 'c'), (2, 1, 'd')]]

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()                                                       # needs networkx
[[2, 1, 0]]

Not yet implemented for directed graphs:

sage: G = DiGraph([(0, 2, 'a'), (0, 1, 'c'), (1, 2, 'd')])
sage: G.cycle_basis()                                                       # needs networkx
Traceback (most recent call last):
...
NotImplementedError: not implemented for directed graphs

degree(vertices=None, labels=False)

Return the degree (in + out for digraphs) of a vertex or of vertices.

INPUT:

• vertices – a vertex or an iterable container of vertices (default: None); if vertices is a single vertex, returns the number of neighbors of that vertex. If vertices is an iterable container of vertices, returns a list of degrees. If vertices is None, same as listing all vertices.

• labels – boolean (default: False); when True, return a dictionary mapping each vertex in vertices to its degree. Otherwise, return the degree of a single vertex or a list of the degrees of each vertex in vertices

OUTPUT:

• When vertices is a single vertex and labels is False, returns the degree of that vertex as an integer

• When vertices is an iterable container of vertices (or None) and labels is False, returns a list of integers. The \(i\)-th value is the degree of the \(i\)-th vertex in the list vertices. When vertices is None, the \(i\)-th value is the degree of \(i\)-th vertex in the ordering list(self), which might be different from the ordering of the vertices given by g.vertices(sort=True).

• When labels is True, returns a dictionary mapping each vertex in vertices 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]

When vertices=None and labels=False, the \(i\)-th value of the returned list is the degree of the \(i\)-th vertex in the list list(self):

sage: # needs sage.combinat
sage: D = digraphs.DeBruijn(4, 2)
sage: D.delete_vertex('20')
sage: print(D.degree())
[7, 7, 6, 7, 8, 8, 7, 8, 8, 7, 8, 8, 8, 7, 8]
sage: print(D.degree(vertices=list(D)))
[7, 7, 6, 7, 8, 8, 7, 8, 8, 7, 8, 8, 8, 7, 8]
sage: print(D.degree(vertices=D.vertices(sort=False)))
[7, 7, 6, 7, 8, 8, 7, 8, 8, 7, 8, 8, 8, 7, 8]

degree_histogram()

Return a list, whose \(i\)-th 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)

Return an iterator over the degrees of the (di)graph.

In the case of a digraph, the degree is defined as the sum of the in-degree and the out-degree, i.e. the total number of edges incident to a given vertex.

INPUT:

• vertices – a vertex or an iterable container of vertices (default: None); if vertices is a single vertex, the iterator will yield the number of neighbors of that vertex. If vertices is an iterable container of vertices, return an iterator over the degrees of these vertices. If vertices is None, same as listing all vertices.

• labels – boolean (default: False); whether to return an iterator over degrees (labels=False), or over tuples (vertex, degree)

Note

The returned iterator yields values in order specified by list(vertices). When vertices is None, it yields values in the same order as list(self), which might be different from the ordering of the vertices given by g.vertices(sort=True).

EXAMPLES:

sage: G = graphs.Grid2dGraph(3, 4)
sage: for i in G.degree_iterator():
....:     print(i)
2
3
3
...
3
2
sage: for i in G.degree_iterator(labels=True):
....:     print(i)
((0, 0), 2)
((0, 1), 3)
((0, 2), 3)
...
((2, 2), 3)
((2, 3), 2)

sage: D = graphs.Grid2dGraph(2,4).to_directed()
sage: for i in D.degree_iterator():
....:     print(i)
4
6
...
6
4
sage: for i in D.degree_iterator(labels=True):
....:     print(i)
((0, 0), 4)
((0, 1), 6)
...
((1, 2), 6)
((1, 3), 4)

When vertices=None yields values in the order of list(D):

sage: V = list(D)
sage: D = digraphs.DeBruijn(4, 2)                                           # needs sage.combinat
sage: D.delete_vertex('20')                                                 # needs sage.combinat
sage: print(list(D.degree_iterator()))                                      # needs sage.combinat
[7, 7, 6, 7, 8, 8, 7, 8, 8, 7, 8, 8, 8, 7, 8]
sage: print([D.degree(v) for v in D])                                       # needs sage.combinat
[7, 7, 6, 7, 8, 8, 7, 8, 8, 7, 8, 8, 8, 7, 8]

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(sort=True)[: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.

This method returns 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(9)
sage: G.size()
36
sage: G.delete_edge( 1, 2 )
sage: G.delete_edge( (3, 4) )
sage: G.delete_edges( [ (5, 6), (7, 8) ] )
sage: G.size()
32

sage: G.delete_edge( 2, 3, 'label' )
sage: G.delete_edge( (4, 5, 'label') )
sage: G.delete_edges( [ (6, 7, 'label') ] )
sage: G.size()
32
sage: G.has_edge( (4, 5) ) # correct!
True
sage: G.has_edge( (4, 5, 'label') ) # correct!
False

sage: C = digraphs.Complete(9)
sage: C.size()
72
sage: C.delete_edge( 1, 2 )
sage: C.delete_edge( (3, 4) )
sage: C.delete_edges( [ (5, 6), (7, 8) ] )
sage: C.size()
68

sage: C.delete_edge( 2, 3, 'label' )
sage: C.delete_edge( (4, 5, 'label') )
sage: C.delete_edges( [ (6, 7, 'label') ] )
sage: C.size() # correct!
68
sage: C.has_edge( (4, 5) ) # correct!
True
sage: C.has_edge( (4, 5, 'label') ) # correct!
False

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 = digraphs.Complete(12)
sage: K4 = digraphs.Complete(4)
sage: K12.size()
132
sage: K12.delete_edges(K4.edge_iterator())
sage: K12.size()
120

delete_multiedge(u, v)

Delete all edges from u to 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(sort=True)
[(0, 1, None), (0, 1, None), (0, 1, None), (1, 2, None), (2, 3, None)]
sage: G.delete_multiedge(0, 1)
sage: G.edges(sort=True)
[(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(sort=True)
[(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(sort=True)
[(1, 0, None), (1, 2, None), (2, 3, None)]

delete_vertex(vertex, in_order=False)

Delete vertex, removing all incident edges.

Deleting a non-existent vertex will raise an exception.

INPUT:

• in_order – boolean (default: False); if True, this deletes the \(i\)-th vertex in the sorted list of vertices, i.e. G.vertices(sort=True)[i]

EXAMPLES:

sage: G = Graph(graphs.WheelGraph(9))
sage: G.delete_vertex(0)
sage: G.show()                                                              # needs sage.plot

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(sort=True)
[1, 2, 3, 4, 5]
sage: D.delete_vertex(0)
Traceback (most recent call last):
...
ValueError: vertex (0) not in the graph

sage: G = graphs.CompleteGraph(4).line_graph(labels=False)
sage: G.vertices(sort=True)
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
sage: G.delete_vertex(0, in_order=True)
sage: G.vertices(sort=True)
[(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)

Delete vertices from the (di)graph taken from an iterable container of vertices.

Deleting a non-existent vertex will raise an exception, in which case none of the vertices in vertices is deleted.

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(sort=False)
[0]
sage: D.delete_vertices([1])
Traceback (most recent call last):
...
ValueError: vertex (1) not in the graph

density()

Return the density of the (di)graph.

The density of a (di)graph is defined as the 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, neighbors=None, edges=False)

Return an iterator over the vertices in a depth-first ordering.

INPUT:

• start – vertex or list of vertices from which to start the traversal

• ignore_direction – boolean (default: False); only applies to directed graphs. If True, searches across edges in either direction.

• neighbors – function (default: None); a function that inputs a vertex and return a list of vertices. For an undirected graph, neighbors is by default the neighbors() function. For a digraph, the neighbors function defaults to the neighbor_out_iterator() function of the graph.

• edges – boolean (default: False); whether to return the edges of the DFS tree in the order of visit or the vertices (default). Edges are directed in root to leaf orientation of the tree.

See also

• breadth_first_search()

• breadth_first_search – breadth-first search for fast compiled graphs.

• depth_first_search – depth-first 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 setting neighbors to be the neighbors_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]

You can get edges of the DFS tree instead of the vertices using the edges parameter:

sage: D = digraphs.Path(5)
sage: list(D.depth_first_search(2, edges=True))
[(2, 3), (3, 4)]
sage: list(D.depth_first_search(2, edges=True, ignore_direction=True))
[(2, 3), (3, 4), (2, 1), (1, 0)]

disjoint_routed_paths(pairs, solver, verbose=None, integrality_tolerance=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_i-t_i\) paths which can intersect at their endpoints and are vertex-disjoint otherwise.

INPUT:

• pairs – list of pairs of vertices

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

EXAMPLES:

Given a grid, finding two vertex-disjoint paths, the first one from the top-left corner to the bottom-left corner, and the second from the top-right corner to the bottom-right corner is easy:

sage: g = graphs.Grid2dGraph(5, 5)
sage: p1,p2 = g.disjoint_routed_paths([((0, 0), (0, 4)), ((4, 4), (4, 0))])             # needs sage.numerical.mip

Though there is obviously no solution to the problem in which each corner is sending information to the opposite one:

sage: g = graphs.Grid2dGraph(5, 5)
sage: p1,p2 = g.disjoint_routed_paths([((0, 0), (4, 4)), ((0, 4), (4, 0))])             # needs sage.numerical.mip
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 – string (default: 'pairs'); if set to 'pairs', each element v in the first graph will be named (0, v) and each element u in other 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 (default: None); whether to create a mutable/immutable disjoint union. immutable=None (default) means that the graphs and their disjoint union will behave the same way.

See also

• union()

• join()

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(sort=True)
[(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(sort=True)
[0, 1, 2, 3, 4, 5, 6]
sage: (G + H).vertices(sort=True)  # '+'-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(sort=True)
[(0, 'a'), (0, 'b'), (1, 0), (1, 1), (1, 2)]

disjunctive_product(other)

Return 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, weight_function=None, check_weight=True)

Return the (directed) distance from u to v in the (di)graph.

The distance is 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 – boolean (default: False); if False, the graph is considered unweighted, and the distance is the number of edges in a shortest path. If True, the distance is the sum of edge labels (which are assumed to be numbers).

• weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l, if l is not None, else 1 as a weight.

• check_weight – boolean (default: True); whether to check that the weight_function outputs a number for each edge.

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)

Return the distances between all pairs of vertices.

INPUT:

• by_weight boolean (default: \(False`\)); if True, the edges in the graph are weighted; if False, all edges have weight 1.

• algorithm – string (default: None); one of the following algorithms:

  • 'BFS': the computation is done through a BFS centered on each vertex successively. Works only if by_weight==False.

  • 'Floyd-Warshall-Cython': the Cython implementation of the Floyd-Warshall algorithm. Works only if by_weight==False.

  • 'Floyd-Warshall-Python': the Python implementation of the Floyd-Warshall 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' if by_weight is False, 'Dijkstra_Boost' if all weights are positive, 'Floyd-Warshall-Cython' otherwise.

• weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l, if l is not None, else 1 as a weight.

• check_weight – boolean (default: True); whether to 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) == Infinity and v not in distances[0]) or
....:     g.distance(0,v) == distances[0][v] for v in g)
True

See also

• distance_matrix()

• shortest_path_all_pairs()

distance_matrix(vertices, base_ring=None, **kwds)

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 by default (vertices == None) indexed with the positions of the vertices of the (di)graph in the ordering vertices(). When vertices is set, the position of the vertices in this ordering is used. The intersection of row \(i\) and column \(j\) contains the shortest path distance from the vertex at the \(i\)-th position to the vertex at the \(j\)-th position.

Note that even when the vertices are consecutive integers starting from one, usually the vertex is not equal to its index.

INPUT:

• vertices – list (default: None); the ordering of the vertices defining how they should appear in the matrix. By default, the ordering given by vertices() is used. Because vertices() only works if the vertices can be sorted, using vertices is useful when working with possibly non-sortable objects in Python 3.

• base_ring – a ring (default: determined from the weights); the base ring of the matrix space to use.

• **kwds – other keywords to pass to the subfunction distance_all_pairs() or to matrix()

EXAMPLES:

sage: d = DiGraph({1: [2, 3], 2: [3], 3: [4], 4: [1]})
sage: d.distance_matrix()                                                   # needs sage.modules
[0 1 1 2]
[3 0 1 2]
[2 3 0 1]
[1 2 2 0]
sage: d.distance_matrix(vertices=[4, 3, 2, 1])                              # needs sage.modules
[0 2 2 1]
[1 0 3 2]
[2 1 0 3]
[2 1 1 0]

sage: G = graphs.CubeGraph(3)
sage: G.distance_matrix()                                                   # needs sage.modules
[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)^{n-1}(n-1)2^{n-2}\):

sage: all(T.distance_matrix().det() == (-1)^9*(9)*2^8                       # needs sage.modules
....:     for T in graphs.trees(10))
True

See also

• distance_all_pairs() – computes the distance between any two vertices.

distances_distribution(G)

Return 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 dictionary d such that the number of pairs of vertices at distance k (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)                                                # needs sage.combinat
sage: D.distances_distribution()                                                # needs sage.combinat
{1: 1/4, 2: 11/28, 3: 5/14}

dominating_set(g, k, independent=1, total=False, value_only=False, solver=False, verbose=None, integrality_tolerance=0)

Return a minimum distance-\(k\) 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.

A minimum distance-\(k\) dominating set is a set \(S\) of vertices of \(G\) of minimal cardinality such that any vertex of \(G\) is in \(S\) or at distance at most \(k\) from a vertex in \(S\). A distance-\(0\) dominating set is the set of vertices itself, and when \(k\) is the radius of the graph, any vertex dominates all the other vertices.

As an optimization problem, it can be expressed as follows, where \(N^k(u)\) denotes the set of vertices at distance at most \(k\) from \(u\) (the set of neighbors when \(k=1\)):

\[\begin{split}\mbox{Minimize : }&\sum_{v\in G} b_v\\ \mbox{Such that : }&\forall v \in G, b_v+\sum_{u \in N^k(v)} b_u\geq 1\\ &\forall x\in G, b_x\mbox{ is a binary variable}\end{split}\]

INPUT:

• k – a non-negative integer (default: 1); the domination distance

• independent – boolean (default: False); when True, computes a minimum independent dominating set, that is a minimum dominating set that is also an independent set (see also independent_set())

• total – boolean (default: False); when True, computes a total dominating set (see the See the Wikipedia article Dominating_set)

• value_only – boolean (default: False); whether to only return the cardinality of the computed dominating set, or to return its list of vertices (default)

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

EXAMPLES:

A basic illustration on a PappusGraph:

sage: g = graphs.PappusGraph()
sage: g.dominating_set(value_only=True)                                         # needs sage.numerical.mip
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())                                                   # needs sage.numerical.mip
2
sage: len(g.dominating_set(independent=True))                                   # needs sage.numerical.mip
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)                             # needs sage.numerical.mip
4

The dominating set is calculated for both the directed and undirected graphs (modification introduced in github issue #17905):

sage: g = digraphs.Path(3)
sage: g.dominating_set(value_only=True)                                         # needs sage.numerical.mip
2
sage: g = graphs.PathGraph(3)
sage: g.dominating_set(value_only=True)                                         # needs sage.numerical.mip
1

Cardinality of distance-\(k\) dominating sets:

sage: G = graphs.PetersenGraph()
sage: [G.dominating_set(k=k, value_only=True) for k in range(G.radius() + 1)]   # needs sage.numerical.mip
[10, 3, 1]
sage: G = graphs.PathGraph(5)
sage: [G.dominating_set(k=k, value_only=True) for k in range(G.radius() + 1)]   # needs sage.numerical.mip
[5, 2, 1]

dominating_sets(g, k, independent=1, total=False, solver=False, verbose=None, integrality_tolerance=0)

Return an iterator over the minimum distance-\(k\) dominating sets 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.

A minimum distance-\(k\) dominating set is a set \(S\) of vertices of \(G\) of minimal cardinality such that any vertex of \(G\) is in \(S\) or at distance at most \(k\) from a vertex in \(S\). A distance-\(0\) dominating set is the set of vertices itself, and when \(k\) is the radius of the graph, any vertex dominates all the other vertices.

As an optimization problem, it can be expressed as follows, where \(N^k(u)\) denotes the set of vertices at distance at most \(k\) from \(u\) (the set of neighbors when \(k=1\)):

\[\begin{split}\mbox{Minimize : }&\sum_{v\in G} b_v\\ \mbox{Such that : }&\forall v \in G, b_v+\sum_{u \in N^k(v)} b_u\geq 1\\ &\forall x\in G, b_x\mbox{ is a binary variable}\end{split}\]

We use constraints generation to iterate over the minimum distance-\(k\) dominating sets. That is, after reporting a solution, we add a constraint to discard it and solve the problem again until no more solution can be found.

INPUT:

• k – a non-negative integer (default: 1); the domination distance

• independent – boolean (default: False); when True, computes minimum independent dominating sets, that is minimum dominating sets that are also independent sets (see also independent_set())

• total – boolean (default: False); when True, computes total dominating sets (see the See the Wikipedia article Dominating_set)

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

EXAMPLES:

Number of distance-\(k\) dominating sets of a Path graph of order 10:

sage: g = graphs.PathGraph(10)
sage: [sum(1 for _ in g.dominating_sets(k=k)) for k in range(11)]               # needs sage.numerical.mip
[1, 13, 1, 13, 25, 2, 4, 6, 8, 10, 10]

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: [sum(1 for _ in g.dominating_sets(k=k)) for k in range(11)]               # needs sage.numerical.mip
[1, 1, 2, 12, 12, 12, 12, 12, 12, 12, 12]

The total dominating set of the Petersen graph has cardinality 4:

sage: G = graphs.PetersenGraph()
sage: G.dominating_set(total=True, value_only=True)                             # needs sage.numerical.mip
4
sage: sorted(G.dominating_sets(k=1))                                            # needs sage.numerical.mip
[[0, 2, 6],
 [0, 3, 9],
 [0, 7, 8],
 [1, 3, 7],
 [1, 4, 5],
 [1, 8, 9],
 [2, 4, 8],
 [2, 5, 9],
 [3, 5, 6],
 [4, 6, 7]]

Independent distance-\(k\) dominating sets of a Path graph:

sage: # needs sage.numerical.mip
sage: G = graphs.PathGraph(6)
sage: sorted(G.dominating_sets(k=1, independent=True))
[[1, 4]]
sage: sorted(G.dominating_sets(k=2, independent=True))
[[0, 3], [0, 4], [0, 5], [1, 3], [1, 4], [1, 5], [2, 4], [2, 5]]
sage: sorted(G.dominating_sets(k=3, independent=True))
[[2], [3]]

The dominating set is calculated for both the directed and undirected graphs (modification introduced in github issue #17905):

sage: # needs sage.numerical.mip
sage: g = digraphs.Path(3)
sage: g.dominating_set(value_only=True)
2
sage: list(g.dominating_sets())
[[0, 1], [0, 2]]
sage: list(g.dominating_sets(k=2))
[[0]]
sage: g = graphs.PathGraph(3)
sage: g.dominating_set(value_only=True)
1
sage: next(g.dominating_sets())
[1]

dominator_tree(g, root, return_dict=False, reverse=False)

Use Boost to compute the dominator tree of g, rooted at root.

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 – the input Sage (Di)Graph

• root – the root of the dominator tree

• return_dict – boolean (default: False); if True, the function returns a dictionary associating to each vertex its parent in the dominator tree. If False (default), it returns the whole tree, as a Graph or a DiGraph.

• reverse – boolean (default: False); when set to True, 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 contain None in correspondence of root and of vertices that are not reachable from root. If the output is a graph, it will not contain vertices that are not reachable from root.

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 3-cycles \(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)}

edge_boundary(vertices1, vertices2=None, labels=True, sort=False, key=None)

Return a list of edges (u,v,l) with u in vertices1 and v in vertices2.

If vertices2 is None, then it is set to the complement of vertices1.

In a digraph, the external boundary of a vertex \(v\) are those vertices \(u\) with an arc \((v, u)\).

INPUT:

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

• sort – boolean (default: False); whether to sort the result

• key – a function (default: None); a function that takes an edge as its one argument and returns a value that can be used for comparisons in the sorting algorithm (we must have sort=True)

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

Using the key argument to order multiple edges of incomparable types (see github issue #35903):

sage: G = Graph([(1, 'A', 4), (1, 2, 3)])
sage: G.edge_boundary([1], sort=True)
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for <: 'Integer Ring' and '<class 'str'>'
sage: G.edge_boundary([1], sort=True, key=str)
[('A', 1, 4), (1, 2, 3)]
sage: G.edge_boundary([1], sort=True, key=lambda e:e[2])
[(1, 2, 3), ('A', 1, 4)]
sage: G.edge_boundary([1], labels=False, sort=True, key=lambda e:e[2])
Traceback (most recent call last):
...
IndexError: tuple index out of range

edge_connectivity(G, value_only=True, implementation=None, use_edge_labels=False, vertices=False, solver=None, verbose=0, integrality_tolerance=0.001)

Return 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 a Graph object, and compute the connectivity of this other graph.

INPUT:

• G – the input Sage (Di)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 vertex cut are returned.

• implementation – string (default: None); selects an implementation:

  • None (default) – selects the best implementation available

  • "boost" – use the Boost graph library (which is much more efficient). It is not available when edge_labels=True, and it is unreliable for directed graphs (see github issue #18753).

  -"Sage" – use Sage’s implementation based on integer linear

  programming

• 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.). Implies boost = False.

  • When set to False, each edge has weight \(1\).

• vertices – boolean (default: False)

  • When set to True, also returns the two sets of vertices that are disconnected by the cut. Implies value_only=False.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

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 is its minimum degree, and one of the two parts of the bipartition is reduced to only one vertex. The graph of the cut edges is 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: tree = graphs.RandomTree(10)
sage: for u,v in tree.edge_iterator(labels=None):
....:      tree.set_edge_label(u, v, random())
sage: minimum = min(tree.edge_labels())
sage: [_, [(_, _, l)]] = edge_connectivity(tree, value_only=False, use_edge_labels=True)
sage: l == minimum
True

When value_only=True and implementation="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, implementation="boost") == 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 github issue #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, use_edge_labels=True, vertices=False, algorithm=False, solver='FF', verbose=None, integrality_tolerance=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 vertex

• t – sink vertex

• value_only – boolean (default: True); whether to return only the weight of a minimum cut (True) or a list of edges of a minimum cut (False)

• use_edge_labels – boolean (default: False); whether to compute a weighted minimum edge cut where the weight of an edge is defined by its label (if an edge has no label, \(1\) is assumed), or to compute a cut of minimum cardinality (i.e., edge weights are set to 1)

• vertices – boolean (default: False); whether set to True, return a list of edges in the edge cut and the two sets of vertices that are disconnected by the cut

  Note: vertices=True implies value_only=False.

• algorithm – string (default: 'FF'); algorithm to use:

  • If algorithm = "FF", a Python implementation of the Ford-Fulkerson algorithm is used

  • If algorithm = "LP", the problem is solved using Linear Programming.

  • If algorithm = "igraph", the igraph implementation of the Goldberg-Tarjan algorithm is used (only available when igraph is installed)

  • If algorithm = None, the problem is solved using the default maximum flow algorithm (see flow())

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

Note

The use of Linear Programming for non-integer 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(g.edge_labels())
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, solver='FF', verbose=None, integrality_tolerance=False)

Return a list of edge-disjoint 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 edge-independent paths from \(s\) to \(t\).

This function returns a list of such paths.

INPUT:

• algorithm – string (default: "FF"); the algorithm to use among:

  • "FF", a Python implementation of the Ford-Fulkerson algorithm

  • "LP", the flow problem is solved using Linear Programming

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

  Only used when \(àlgorithm`\) is "LP".

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

  Only used when \(àlgorithm`\) is "LP".

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

  Only used when \(àlgorithm`\) is "LP".

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, algorithm, root=None, solver=None, verbose=None, integrality_tolerance=0)

Return the desired number of edge-disjoint spanning trees/arborescences.

INPUT:

• k – integer; the required number of edge-disjoint spanning trees/arborescences

• algorithm – string (default: None); specify the algorithm to use among:

  • "Roskind-Tarjan" – use the algorithm proposed by Roskind and Tarjan [RT1985] for finding edge-disjoint spanning-trees in undirected simple graphs in time \(O(m\log{m} + k^2n^2)\).

  • "MILP" – use a mixed integer linear programming formulation. This is the default method for directed graphs.

  • None – use "Roskind-Tarjan" for undirected graphs and "MILP" for directed graphs.

• root – vertex (default: None); root of the disjoint arborescences when the graph is directed. If set to None, the first vertex in the graph is picked.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

ALGORITHM:

Mixed Integer Linear Program.

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 tree-packing theorem”, by Thomas Kaiser [Kai2012].

• The implementation of a Matroid class and of the Matroid Union Theorem (see section 42.3 of [Sch2003]), applied to the cycle Matroid (see chapter 51 of [Sch2003]).

EXAMPLES:

The Petersen Graph does have a spanning tree (it is connected):

sage: g = graphs.PetersenGraph()
sage: [T] = g.edge_disjoint_spanning_trees(1)                               # needs sage.numerical.mip
sage: T.is_tree()                                                           # needs sage.numerical.mip
True

Though, it does not have 2 edge-disjoint trees (as it has less than \(2(|V|-1)\) edges):

sage: g.edge_disjoint_spanning_trees(2)                                     # needs sage.numerical.mip
Traceback (most recent call last):
...
EmptySetError: this graph does not contain the required number of trees/arborescences

By Edmonds’ theorem, a graph which is \(k\)-connected always has \(k\) edge-disjoint arborescences, regardless of the root we pick:

sage: # needs sage.numerical.mip
sage: g = digraphs.RandomDirectedGNP(11, .3)  # reduced from 30 to 11, cf. #32169
sage: k = Integer(g.edge_connectivity())
sage: while not k:
....:     g = digraphs.RandomDirectedGNP(11, .3)
....:     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: # needs sage.numerical.mip
sage: g = graphs.RandomGNP(14, .3)  # reduced from 30 to 14, see #32169
sage: while not g.is_biconnected():
....:     g = graphs.RandomGNP(14, .3)
sage: k = Integer(g.edge_connectivity()) // 2
sage: trees = g.edge_disjoint_spanning_trees(k)
sage: all(t.is_tree() for t in trees)
True

Check the validity of the algorithms for undirected graphs:

sage: # needs sage.numerical.mip
sage: g = graphs.RandomGNP(12, .7)
sage: k = Integer(g.edge_connectivity()) // 2
sage: trees = g.edge_disjoint_spanning_trees(k, algorithm="MILP")
sage: all(t.is_tree() for t in trees)
True
sage: all(g.order() == t.size() + 1 for t in trees)
True
sage: trees = g.edge_disjoint_spanning_trees(k, algorithm="Roskind-Tarjan")
sage: all(t.is_tree() for t in trees)
True
sage: all(g.order() == t.size() + 1 for t in trees)
True

Example of github issue #32169:

sage: d6 = r'[E_S?_hKIH@eos[BSg???Q@FShGC?hTHUGM?IPug?JOEYCdOzdkQGo'
sage: d6 += r'@ADA@AAg?GAQW?[aIaSwHYcD@qQb@Dd?\hJTI@OHlJ_?C_OEIKoeC'
sage: d6 += r'R@_BC?Q??YBFosqITEA?IvCU_'
sage: G = DiGraph(d6, format='dig6')
sage: G.edge_connectivity()
5
sage: G.edge_disjoint_spanning_trees(5)     # long time                     # needs sage.numerical.mip
[Digraph on 28 vertices,
 Digraph on 28 vertices,
 Digraph on 28 vertices,
 Digraph on 28 vertices,
 Digraph on 28 vertices]

Small cases:

sage: # needs sage.numerical.mip
sage: Graph().edge_disjoint_spanning_trees(0)
[]
sage: Graph(1).edge_disjoint_spanning_trees(0)
[]
sage: Graph(2).edge_disjoint_spanning_trees(0)
[]
sage: Graph([(0, 1)]).edge_disjoint_spanning_trees(0)
[]
sage: Graph([(0, 1)]).edge_disjoint_spanning_trees(1)
[Graph on 2 vertices]
sage: Graph([(0, 1)]).edge_disjoint_spanning_trees(2)
Traceback (most recent call last):
...
EmptySetError: this graph does not contain the required number of trees/arborescences

edge_iterator(vertices=None, labels=True, ignore_direction=False, sort_vertices=True)

Return 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 – object (default: None); a vertex, a list of vertices or None

• labels – boolean (default: True); if False, each edge is

  a tuple \((u,v)\) of vertices

• ignore_direction – boolean (default: False); only applies to

  directed graphs. If True, searches across edges in either direction.

• sort_vertices – boolean (default: True); only applies to undirected graphs. If True, sort the ends of the edges. Not sorting the ends is faster.

Note

It is somewhat safe to modify the graph during iterating.

vertices must be specified if modifying the vertices.

Without multiedges, you can safely use this graph to relabel edges or delete some edges. If you add edges, they might later appear in the iterator or not (depending on the internal order of vertices).

In case of multiedges, all arcs from one vertex to another are internally cached. So the iterator will yield them, even if you delete them all after seeing the first one.

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: G = graphs.TetrahedralGraph()
sage: list(G.edge_iterator(labels=False, sort_vertices=False))
[(1, 0), (2, 0), (3, 0), (2, 1), (3, 1), (3, 2)]

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

• set_edge_label()

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 the labels of all edges in self.

The output list is not sorted.

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

edge_polytope(backend=None)

Return the edge polytope of self.

The edge polytope (EP) of a Graph on \(n\) vertices is the polytope in \(\ZZ^{n}\) defined as the convex hull of \(e_i + e_j\) for each edge \((i, j)\). Here \(e_1, \dots, e_n\) denotes the standard basis.

INPUT:

• backend – string or None (default); the backend to use; see sage.geometry.polyhedron.constructor.Polyhedron()

EXAMPLES:

The EP of a \(4\)-cycle is a square:

sage: G = graphs.CycleGraph(4)
sage: P = G.edge_polytope(); P                                              # needs sage.geometry.polyhedron
A 2-dimensional polyhedron in ZZ^4 defined as the convex hull of 4 vertices

The EP of a complete graph on \(4\) vertices is cross polytope:

sage: G = graphs.CompleteGraph(4)
sage: P = G.edge_polytope(); P                                              # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 6 vertices
sage: P.is_combinatorially_isomorphic(polytopes.cross_polytope(3))          # needs sage.geometry.polyhedron
True

The EP of a graph is isomorphic to the subdirect sum of its connected components EPs:

sage: n = randint(3, 6)
sage: G1 = graphs.RandomGNP(n, 0.2)                                         # needs networkx
sage: n = randint(3, 6)
sage: G2 = graphs.RandomGNP(n, 0.2)                                         # needs networkx
sage: G = G1.disjoint_union(G2)                                             # needs networkx
sage: P = G.edge_polytope()                                                 # needs networkx sage.geometry.polyhedron
sage: P1 = G1.edge_polytope()                                               # needs networkx sage.geometry.polyhedron
sage: P2 = G2.edge_polytope()                                               # needs networkx sage.geometry.polyhedron
sage: P.is_combinatorially_isomorphic(P1.subdirect_sum(P2))                 # needs networkx sage.geometry.polyhedron
True

All trees on \(n\) vertices have isomorphic EPs:

sage: n = randint(4, 10)
sage: G1 = graphs.RandomTree(n)
sage: G2 = graphs.RandomTree(n)
sage: P1 = G1.edge_polytope()                                               # needs sage.geometry.polyhedron
sage: P2 = G2.edge_polytope()                                               # needs sage.geometry.polyhedron
sage: P1.is_combinatorially_isomorphic(P2)                                  # needs sage.geometry.polyhedron
True

However, there are still many different EPs:

sage: len(list(graphs(5)))
34
sage: polys = []
sage: for G in graphs(5):                                                   # needs sage.geometry.polyhedron
....:     P = G.edge_polytope()
....:     for P1 in polys:
....:         if P.is_combinatorially_isomorphic(P1):
....:             break
....:     else:
....:         polys.append(P)
sage: len(polys)                                                            # needs sage.geometry.polyhedron
19

edges(vertices=None, labels=True, sort=False, key=None, ignore_direction=False, sort_vertices=True)

Return a EdgesView 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.

The returned EdgesView is over the edges incident with any vertex given in the parameter vertices (all edges if None). If self is directed, iterates over outgoing edges only, unless parameter ignore_direction is True in which case it searches across edges in either direction.

INPUT:

• vertices – object (default: None); a vertex, a list of vertices or None

• labels – boolean (default: True); if False, each edge is simply a pair (u, v) of vertices

• sort – boolean (default: False); whether to sort edges according the ordering specified with parameter key. If False (default), edges are not sorted. This is the fastest and less memory consuming method for iterating over edges.

• key – a function (default: None); a function that takes an edge (a pair or a triple, according to the labels keyword) as its one argument and returns a value that can be used for comparisons in the sorting algorithm

• ignore_direction – boolean (default: False); only applies to

  directed graphs. If True, searches across edges in either direction.

• sort_vertices – boolean (default: True); only applies to undirected graphs. If True, sort the ends of the edges. Not sorting the ends is faster.

OUTPUT: A EdgesView.

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(sort=True)
[(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(sort=True, 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(sort=True)
[(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(sort=True, 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(sort=True, 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(sort=False):
....:   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(sort=True, key=lambda x: x[2])
[(0, 1, 'F'), (1, 2, 'L'), (2, 3, 'R'), (0, 4, 'U'), (3, 4, 'X')]

We can restrict considered edges to those incident to a given set:

sage: for i in graphs.PetersenGraph().edges(sort=True, vertices=[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.edges(sort=True, vertices=[0]):
....:     print(i)
(0, 1, None)
(0, 2, None)

Ignoring the direction of edges:

sage: D = DiGraph({1: [0], 2: [0]})
sage: D.edges(sort=True, vertices=0)
[]
sage: D.edges(sort=True, vertices=0, ignore_direction=True)
[(1, 0, None), (2, 0, None)]
sage: D.edges(sort=True, vertices=[0], ignore_direction=True)
[(1, 0, None), (2, 0, None)]

Not sorting the ends of the edges:

sage: G = Graph()
sage: G = Graph()
sage: G.add_edges([[1,2], [2,3], [0,3]])
sage: list(G.edge_iterator(sort_vertices=False))
[(3, 0, None), (2, 1, None), (3, 2, None)]

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. If vertices is None, 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 or None

• labels – boolean (default: True); if False, each edge is

  a tuple \((u,v)\) of vertices

• sort – boolean (default: False); if True 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)

Return the right eigenspaces of the adjacency matrix of the graph.

INPUT:

• laplacian – boolean (default: False); if True, use the

  Laplacian matrix (see kirchhoff_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 use eigenvectors().

EXAMPLES:

sage: P = graphs.PetersenGraph()
sage: P.eigenspaces()                                                       # needs sage.modules sage.rings.number_field
[
(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)                                         # needs sage.modules sage.rings.number_field
[
(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()                                                       # needs sage.modules sage.rings.number_field
[
(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 3-cycle, we have:

sage: T = DiGraph({0: [1], 1: [2], 2: [0]})
sage: T.eigenspaces()                                                       # needs sage.modules sage.rings.number_field
[
(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)

Return the right eigenvectors of the adjacency matrix of the graph.

INPUT:

• laplacian – boolean (default: False); if True, use the Laplacian matrix (see kirchhoff_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()                                                      # needs sage.modules sage.rings.number_field
[(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)                                        # needs sage.modules sage.rings.number_field
[(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()                                                      # needs sage.modules sage.rings.number_field
[(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 3-cycle, we have:

sage: T = DiGraph({0:[1], 1:[2], 2:[0]})
sage: T.eigenvectors()                                                      # needs sage.modules sage.rings.number_field
[(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.

If no Eulerian circuit is found, the method returns False.

This is implemented using Hierholzer’s algorithm.

INPUT:

• return_vertices – boolean (default: False); optionally

  provide a list of vertices for the path

• labels – boolean (default: True); whether to return edges

  with labels (3-tuples)

• path – boolean (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()

Return 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 out-degree and the in-degree of a vertex.

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

ALGORITHM:

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

This algorithm has 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 (default: None); select the output format explicitly. If set to None (default), the format is set to be the file extension of filename. 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:

  adjlist	http://networkx.lanl.gov/reference/generated/networkx.readwrite.adjlist.write_adjlist.html
  dot	https://networkx.github.io/documentation/latest/reference/generated/networkx.drawing.nx_pydot.write_dot.html
  edgelist	http://networkx.lanl.gov/reference/generated/networkx.readwrite.edgelist.write_edgelist.html
  gexf	http://networkx.lanl.gov/reference/generated/networkx.readwrite.gexf.write_gexf.html
  gml	http://networkx.lanl.gov/reference/generated/networkx.readwrite.gml.write_gml.html
  graphml	http://networkx.lanl.gov/reference/generated/networkx.readwrite.graphml.write_graphml.html
  multiline_adjlist	http://networkx.lanl.gov/reference/generated/networkx.readwrite.multiline_adjlist.write_multiline_adjlist.html
  pajek	http://networkx.lanl.gov/reference/generated/networkx.readwrite.pajek.write_pajek.html
  yaml	http://networkx.lanl.gov/reference/generated/networkx.readwrite.nx_yaml.write_yaml.html

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)                                            # needs networkx
sage: import networkx                                                       # needs networkx
sage: G_networkx = networkx.read_pajek(filename)                            # needs networkx
sage: Graph(G_networkx).is_isomorphic(g)                                    # needs networkx
True
sage: filename = tmp_filename(ext=".edgelist")
sage: g.export_to_file(filename, data=False)                                # needs networkx
sage: h = Graph(networkx.read_edgelist(filename))                           # needs networkx
sage: g.is_isomorphic(h)                                                    # needs networkx
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.

If no embedding is provided or stored as self._embedding, this method will compute the set of faces from the embedding returned by is_planar() (if the graph is, of course, planar).

Warning

This method is not well defined when the graph is not connected. Indeed, the result may contain several faces corresponding to the external face.

INPUT:

• embedding – dictionary (default: None); a combinatorial embedding dictionary. Format: {v1: [v2,v3], v2: [v1], v3: [v1]} (clockwise ordering of neighbors at each vertex). If set to None (default) the method will use the embedding stored as self._embedding. If none is stored, the method will compute the set of faces from the embedding returned by is_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.

See also

• set_embedding()

• get_embedding()

• is_planar()

• planar_dual()

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)],
 [(0, 2), (2, 3), (3, 0)],
 [(0, 3), (3, 1), (1, 0)],
 [(1, 3), (3, 2), (2, 1)]]

With no embedding provided:

sage: graphs.TetrahedralGraph().faces()
[[(0, 1), (1, 2), (2, 0)],
 [(0, 2), (2, 3), (3, 0)],
 [(0, 3), (3, 1), (1, 0)],
 [(1, 3), (3, 2), (2, 1)]]

With no embedding provided (non-planar 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, solver=False, verbose=None, constraint_generation=0, integrality_tolerance=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 \(G-S\) is acyclic. For more information, see the Wikipedia article Feedback_vertex_set.

INPUT:

• value_only – boolean (default: False); whether to return only the minimum cardinal of a minimum vertex set, or the Set of vertices of a minimal feedback vertex set

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• constraint_generation – boolean (default: True); whether to use constraint generation when solving the Mixed Integer Linear Program

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

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_u-d_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,n-1]\) 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: # needs sage.numerical.mip
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: # needs sage.numerical.mip
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 = next(cycle.edge_iterator(labels=None))
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                     # needs sage.numerical.mip
True

flow(x, y, value_only, integer=True, use_edge_labels=False, vertex_bound=True, algorithm=False, solver=None, verbose=None, integrality_tolerance=0)

Return a maximum flow in the graph from x to y.

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

Observe that the integrality of the flow variables is automatic for all available solvers when all capacities are integers.

INPUT:

• x – source vertex

• y – sink vertex

• value_only – boolean (default: True); whether to return only the value of a maximal flow, or to also return 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)

• integer – boolean (default: True); whether to compute an optimal solution under the constraint that the flow going through an edge has to be an integer, or without this constraint

• use_edge_labels – boolean (default: False); whether to compute a maximum flow where each edge has a capacity defined by its label (if an edge has no label, capacity \(1\) is assumed), or to use default edge capacity of \(1\)

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

• algorithm – string (default: None); the algorithm to use among:

  • "FF", a Python implementation of the Ford-Fulkerson algorithm (only available when vertex_bound = False)

  • "LP", the flow problem is solved using Linear Programming

  • "igraph", the igraph implementation of the Goldberg-Tarjan algorithm is used (only available when igraph is installed and vertex_bound = False)

  When algorithm = None (default), we use LP if vertex_bound = True, otherwise, we use igraph if it is available, FF if it is not available.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

  Only useful when algorithm "LP" is used to solve the flow problem.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

  Only useful when algorithm "LP" is used to solve the flow problem.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

  Only useful when algorithm == "LP" and integer == True.

Note

Even though the three different implementations are meant to return the same Flow values, they cannot 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 the ButterflyGraph 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 \(s-t\) 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: flow_graph.size()
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: flow_graph.size()
4

genus(set_embedding=True, on_embedding=None, minimal=True, maximal=False, circular=None, ordered=True)

Return 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 non-planarity; 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 (default: True); whether or not to store an embedding attribute of the computed (minimal) genus of the graph

• on_embedding – two kinds of input are allowed (default:

  None):

  • 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 of on_embedding takes precedence over a stored _embedding attribute if minimal is set to False.

  • The value True, in order to indicate that the embedding stored as _embedding should be used (see examples).

• minimal – boolean (default: True); 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 (default: False); 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 (default: None); if circular 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.

• ordered – boolean (default: True); 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)
Traceback (most recent call last):
...
ValueError: on_embedding is not a valid option when circular is defined
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 non-simple 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: cannot work with embeddings of non-simple 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: cannot 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: G = graphs.RandomBlockGraph(10, 5)
sage: G.genus()
10

get_embedding()

Return the stored embedding or None.

If the stored embedding is no longer valid (because of vertex/edge additions) then the stored embedding is discarded and None is returned. In case some vertex/edge has been deleted, the stored embedding is updated accordingly.

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

Note that the embeddings gets properly modified on vertex or edge deletion:

sage: G.delete_edge(0, 1)
sage: G.delete_vertex(3)
sage: G.get_embedding()
{0: [4, 5],
 1: [2, 6],
 2: [1, 7],
 4: [0, 9],
 5: [0, 7, 8],
 6: [1, 9, 8],
 7: [2, 5, 9],
 8: [6, 5],
 9: [4, 6, 7]}

But not under edge addition:

sage: G.add_edge(0, 7)
sage: G.get_embedding() is None
True

get_pos(dim=2)

Return the position dictionary.

The position dictionary specifies the coordinates of each vertex.

INPUT:

• dim – integer (default: 2); whether to return the position dictionary in the plane (dim == 2) or in the 3-dimensional space

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)                                             # needs sage.plot
sage: G.get_pos()                                                           # needs sage.plot
{}

Some of the named graphs come with a pre-specified positioning:

sage: G = graphs.PetersenGraph()
sage: G.get_pos()
{0: (0.0, 1.0),
 ...
 9: (0.475..., 0.154...)}

Note that the position dictionary is modified on vertex removal:

sage: G.delete_vertex(0)
sage: G.get_pos()
{1: (-0.951..., 0.309...),
...
 9: (0.475..., 0.154...)}

But is deleted on vertex addition:

sage: G.add_vertex(0)
sage: G.get_pos() is None
True

get_vertex(vertex)

Retrieve the object associated with a given vertex.

If no associated object is found, None is returned.

INPUT:

• vertex – the given vertex

EXAMPLES:

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

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: Moebius-Kantor Graph: Graph on 16 vertices}

girth(certificate=False)

Return the girth of the graph.

The girth is the length of the shortest cycle in the graph (directed cycle if the graph is directed). Graphs without (directed) cycles have infinite girth.

INPUT:

• certificate – boolean (default: False); whether to return (g, c), where g is the girth and c is a list of vertices of a (directed) cycle of length g in the graph, thus providing a certificate that the girth is at most g, or None if g infinite

EXAMPLES:

sage: graphs.TetrahedralGraph().girth()
3
sage: graphs.CubeGraph(3).girth()
4
sage: graphs.PetersenGraph().girth(certificate=True)  # random
(5, [4, 3, 2, 1, 0])
sage: graphs.HeawoodGraph().girth()
6
sage: next(graphs.trees(9)).girth()
+Infinity

See also

• odd_girth() – return the odd girth of the graph.

graphics_array_defaults = {'graph_border': True, 'layout': 'circular', 'vertex_labels': False, 'vertex_size': 50}

graphplot(**options)

Return a GraphPlot object.

See GraphPlot for more details.

INPUT:

• **options – parameters for the GraphPlot constructor

EXAMPLES:

Creating a GraphPlot object uses the same options as 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,               # needs sage.plot
....:                  edge_style='dashed')
sage: GP.plot()                                                             # needs sage.plot
Graphics object consisting of 22 graphics primitives

We can modify the GraphPlot object. Notice that the changes are cumulative:

sage: # needs sage.plot
sage: GP.set_edges(edge_style='solid')
sage: GP.plot()
Graphics object consisting of 22 graphics primitives
sage: GP.set_vertices(talk=True)
sage: GP.plot()
Graphics object consisting of 22 graphics primitives

graphviz_string(labels='string', vertex_labels=True, edge_labels=False, edge_color=None, edge_colors=None, edge_options=(), color_by_label=False, rankdir='down', 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 (default: "string"); either "string" or "latex". If labels is "string", latex commands 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 3-tuple of floating point (to be interpreted as RGB tuple). In this case the 3-tuple is converted in hexadecimal code.

• edge_colors – dictionary (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 option edge_color for a description of valid color formats.

• color_by_label – a boolean or dictionary or function (default: False); 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 with edge_color and edge_colors. See the option edge_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 – a list of lists of vertices (default: []); 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 post-processing 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: # needs sage.symbolic
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",               # random
....:                         edge_labels=True))
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",               # random        # needs sage.symbolic
....:                         color_by_label=True))
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",               # random        # needs sage.symbolic
....:                         color_by_label={f: "red", g: "blue"}))
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;
}

Edge-specific 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"

• "dot" (a string containing a sequence of options in dot format)

• "label" (a string)

• "label_style" ("string" or "latex")

• "edge_string" ("--" or "->")

• "dir" ("forward", "back", "both" or "none")

• "backward" (boolean), instead of defining the edge in the graphviz string as u -> v it draws it as v -> u [dir=back] and instead of u -> v [dir=back] it draws it as v -> u, this changes the way it is drawn by Graphviz’s dot program: vertex v will be above vertex u instead of below.

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 {"dir":"back"} if u == 1 else {}
sage: print(G.graphviz_string(edge_options=edge_options))   # random        # needs sage.symbolic
digraph {
  node_0  [label="-1"];
  node_1  [label="-1/2"];
  node_2  [label="1/2"];
  node_3  [label="-2"];
  node_4  [label="1/4"];
  node_5  [label="-4"];
  node_6  [label="1/3"];
  node_7  [label="2/3"];
  node_8  [label="4/5"];
  node_9  [label="1"];
  node_10  [label="2"];

  node_2 -> node_3;
  node_2 -> node_7;
  node_4 -> node_5;
  node_4 -> node_8;
  node_9 -> node_0 [dir=back];
  node_9 -> node_2 [dir=back];
  node_10 -> node_1;
  node_10 -> node_6;
}

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["dir"]         = "back"
....:     return options
sage: print(G.graphviz_string(edge_options=edge_options))   # random        # needs sage.symbolic
digraph {
  node_0  [label="-1"];
  node_1  [label="-1/2"];
  node_2  [label="1/2"];
  node_3  [label="-2"];
  node_4  [label="1/4"];
  node_5  [label="-4"];
  node_6  [label="1/3"];
  node_7  [label="2/3"];
  node_8  [label="4/5"];
  node_9  [label="1"];
  node_10  [label="2"];

  node_2 -> node_3 [label="coucou", color = "red"];
  node_2 -> node_7 [x=1,y=2, color = "blue"];
  node_4 -> node_5 [color = "red"];
  node_4 -> node_8 [color = "blue"];
  node_9 -> node_0 [label=" ", texlbl="$x \ {\mapsto}\ -\frac{1}{x}$", color = "red"];
  node_9 -> node_2 [color = "blue", dir=back];
  node_10 -> node_1 [color = "red"];
  node_10 -> node_6 [color = "blue"];
}

We test the possible values of the 'dir' edge option:

sage: edges = [(0,1,'a'), (1,2,'b'), (2,3,'c'), (3,4,'d')]
sage: G = DiGraph(edges)
sage: def edge_options(data):
....:     u,v,label = data
....:     if label == 'a': return {'dir':'forward'}
....:     if label == 'b': return {'dir':'back'}
....:     if label == 'c': return {'dir':'none'}
....:     if label == 'd': return {'dir':'both'}
sage: print(G.graphviz_string(edge_options=edge_options))
digraph {
  node_0  [label="0"];
  node_1  [label="1"];
  node_2  [label="2"];
  node_3  [label="3"];
  node_4  [label="4"];

  node_0 -> node_1;
  node_1 -> node_2 [dir=back];
  node_2 -> node_3 [dir=none];
  node_3 -> node_4 [dir=both];
}

We test the same graph and 'dir' edge options but with backward=True, which reverses the natural direction each edge wants to be pointing for the layout:

sage: def edge_options(data):
....:     u,v,label = data
....:     if label == 'a': return {'dir':'forward', 'backward':True}
....:     if label == 'b': return {'dir':'back', 'backward':True}
....:     if label == 'c': return {'dir':'none', 'backward':True}
....:     if label == 'd': return {'dir':'both', 'backward':True}
sage: print(G.graphviz_string(edge_options=edge_options))
digraph {
  node_0  [label="0"];
  node_1  [label="1"];
  node_2  [label="2"];
  node_3  [label="3"];
  node_4  [label="4"];

  node_1 -> node_0 [dir=back];
  node_2 -> node_1;
  node_3 -> node_2 [dir=none];
  node_4 -> node_3 [dir=both];
}

graphviz_to_file_named(filename, **options)

Write a representation in the dot language 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 in

• **options – options for the graphviz string

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: import tempfile
sage: with tempfile.NamedTemporaryFile(mode="a+t") as f:
....:     G.graphviz_to_file_named(f.name, edge_labels=True)
....:     print(f.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"];
}

greedy_dominating_set(G, k=1, vertices=None, ordering=None, return_sets=False, closest=False)

Return a greedy distance-\(k\) dominating set of the graph.

A distance-\(k\) 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 is at distance at most \(k\) from a vertex in \(S\). See the Wikipedia article Dominating_set.

When \(G\) is directed, vertex \(u\) can be a dominator of vertex \(v\) if there is a directed path of length at most \(k\) from \(u\) to \(v\).

This method implements a greedy heuristic to find a minimal dominatic set.

INPUT:

• G – a Graph

• k – integer (default: 1); the domination distance to consider

• vertices – iterable container of vertices (default: None); when specified, return a dominating set of the specified vertices only

• ordering – string (default: None); specify the order in which to consider the vertices

  • None – if vertices is None, then consider the vertices in the order given by list(G). Otherwise, consider the vertices in the order of iteration of vertices.

  • "degree_min" – consider the vertices by increasing degree

  • "degree_max" – consider the vertices by decreasing degree

• return_sets – boolean (default: False); whether to return the vertices of the dominating set only (default), or a dictionary mapping each vertex of the dominating set to the set of vertices it dominates.

• closest – boolean (default: False); whether to attach a vertex to its closest dominator or not. This parameter is use only when return_sets is True.

EXAMPLES:

Dominating sets of a path:

sage: from sage.graphs.domination import greedy_dominating_set
sage: G = graphs.PathGraph(5)
sage: sorted(greedy_dominating_set(G, ordering=None))
[0, 2, 4]
sage: sorted(greedy_dominating_set(G, ordering="degree_min"))
[0, 2, 4]
sage: sorted(greedy_dominating_set(G, ordering="degree_max"))
[1, 3]
sage: sorted(greedy_dominating_set(G, k=2, ordering=None))
[0, 3]
sage: sorted(greedy_dominating_set(G, k=2, ordering="degree_min"))
[0, 4]
sage: sorted(greedy_dominating_set(G, k=2, ordering="degree_max"))
[1, 4]
sage: greedy_dominating_set(G, k=3, ordering="degree_min", return_sets=True, closest=False)
{0: {0, 1, 2, 3}, 4: {4}}
sage: greedy_dominating_set(G, k=3, ordering="degree_min", return_sets=True, closest=True)
{0: {0, 2, 3}, 4: {1, 4}}

Asking for a dominating set of a subset of vertices:

sage: from sage.graphs.domination import greedy_dominating_set
sage: from sage.graphs.domination import is_dominating
sage: G = graphs.PetersenGraph()
sage: vertices = {0, 1, 2, 3, 4, 5}
sage: dom = greedy_dominating_set(G, vertices=vertices, return_sets=True)
sage: sorted(dom)
[0, 2]
sage: is_dominating(G, dom, focus=vertices)
True
sage: is_dominating(G, dom)
False
sage: dominated = [u for v in dom for u in dom[v]]
sage: sorted(dominated) == sorted(vertices)
True

Influence of the ordering of the vertices on the result:

sage: from sage.graphs.domination import greedy_dominating_set
sage: G = graphs.StarGraph(4)
sage: greedy_dominating_set(G, vertices=[0, 1, 2, 3, 4])
[0]
sage: sorted(greedy_dominating_set(G, vertices=[1, 2, 3, 4, 0]))
[1, 2, 3, 4]

Dominating set of a directed graph:

sage: from sage.graphs.domination import greedy_dominating_set
sage: D = digraphs.Path(3)
sage: sorted(greedy_dominating_set(D, vertices=[0, 1, 2]))
[0, 2]

hamiltonian_cycle(algorithm, solver='tsp', constraint_generation=None, verbose=None, verbose_constraints=0, integrality_tolerance=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 NP-Complete, this algorithm could run for some time depending on the instance.

ALGORITHM:

See traveling_salesman_problem() for ‘tsp’ algorithm and find_hamiltonian() from sage.graphs.generic_graph_pyx for ‘backtrack’ algorithm.

INPUT:

• algorithm – string (default: 'tsp'); one of ‘tsp’ or ‘backtrack’

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• constraint_generation – boolean (default: None); 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 – boolean (default: False); whether to display which constraints are being generated

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

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 using is_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()                                                 # needs sage.numerical.mip
TSP from Heawood graph: Graph on 14 vertices

The Petersen Graph, though, is not

sage: g = graphs.PetersenGraph()
sage: g.hamiltonian_cycle()                                                 # needs sage.numerical.mip
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, [...])

And now in the Petersen graph

sage: G=graphs.PetersenGraph()
sage: B, P = G.hamiltonian_cycle(algorithm='backtrack')
sage: B
False
sage: len(P)
10
sage: G.has_edge(P[0], P[-1])
False

Finally, we test the algorithm in a cube graph, which is Hamiltonian

sage: G=graphs.CubeGraph(3)
sage: G.hamiltonian_cycle(algorithm='backtrack')
(True, [...])

hamiltonian_path(s, t=None, use_edge_labels=None, maximize=False, algorithm=False, solver='MILP', verbose=None, integrality_tolerance=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 NP-Complete, 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 (if maximize == True).

See also

• longest_path()

• hamiltonian_cycle()

INPUT:

• s – vertex (default: None); if specified, then forces the source of the path (the method then returns a Hamiltonian path starting at s)

• t – vertex (default: None); if specified, then forces the destination of the path (the method then returns a Hamiltonian path ending at t)

• use_edge_labels – boolean (default: False); whether to compute a weighted hamiltonian path where the weight of an edge is defined by its label (a label set to None or {} being considered as a weight of \(1\)), or a non-weighted hamiltonian path

• maximize – boolean (default: False); whether to compute a minimum (default) or a maximum (when maximize == True) weight hamiltonian path. This parameter is considered only if use_edge_labels == True.

• algorithm – string (default: "MILP"); the algorithm the use among "MILP" and "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 – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

A subgraph of self corresponding to a (directed if self is directed) hamiltonian path. If no hamiltonian path is found, return None. If use_edge_labels == True, a pair weight, 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: # needs sage.numerical.mip
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)

Check whether (u, v) is an edge of the (di)graph.

INPUT: The following forms are accepted:

• 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(sort=True)
[]

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(sort=True)
[]

has_multiple_edges(to_undirected=False)

Return 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
Multi-graph 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(sort=True)
[(0, 1, None)]

sage: D = DiGraph(multiedges=True, sparse=True); D
Multi-digraph 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(sort=True)
[(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)

Check if vertex is one of the vertices of this graph.

INPUT:

• vertex – the name of a vertex (see add_vertex())

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_list=None, vertex_attrs={}, edge_attrs={})

Return an igraph graph from the Sage 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_list – list (default: None); defines a mapping from the vertices of the graph to consecutive integers in (0, \ldots, n-1)`. Otherwise, the result of :meth:`vertices` will be used instead. Because :meth:`vertices` only works if the vertices can be sorted, using ``vertex_list is useful when working with possibly non-sortable objects in Python 3.

• vertex_attrs – dictionary (default: {}); 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 \(i\)-th vertex in the list vertex_list if it is given or in vertices() when vertex_list == None (see http://igraph.org/python/doc/igraph.Graph-class.html#__init__ for more information)

• edge_attrs – dictionary (default: {}); 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 \(i\)-th edge in the list outputted by edge_iterator() (see http://igraph.org/python/doc/igraph.Graph-class.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 igraph-compatible (see example below).

EXAMPLES:

Standard conversion:

sage: G = graphs.TetrahedralGraph()
sage: H = G.igraph_graph()          # optional - python_igraph
sage: H.summary()                   # optional - python_igraph
'IGRAPH U--- 4 6 -- '
sage: G = digraphs.Path(3)
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')])
sage: E = list(G.edge_iterator())
sage: H = G.igraph_graph(edge_attrs={'label': [e[2] for e in E]}) # 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})])
sage: E = list(G.edge_iterator())
sage: H = G.igraph_graph(edge_attrs={'weight': [e[2]['weight'] for e in E]}) # 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])
sage: H = G.igraph_graph(vertex_attrs={'name': G.vertices(sort=True)}) # optional - python_igraph
sage: H.vs()['name']                                          # optional - python_igraph
[(0, 0), (0, 1), (1, 0), (1, 1)]

Providing a mapping from vertices to consecutive integers:

sage: G = graphs.GridGraph([2, 2])
sage: V = list(G)
sage: H = G.igraph_graph(vertex_list=V, vertex_attrs={'name': V}) # optional - python_igraph
sage: H.vs()['name'] == V                                         # optional - python_igraph
True

Sometimes, Sage integer/floats are not compatible with igraph:

sage: G = Graph([(0, 1, 2)])
sage: E = list(G.edge_iterator())
sage: H = G.igraph_graph(edge_attrs={'capacity': [e[2] for e in E]}) # 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 E]}) # optional - python_igraph
sage: H.maxflow_value(0, 1, 'capacity')                                     # optional - python_igraph
2.0

incidence_matrix(oriented, sparse=None, vertices=True, edges=None, base_ring=None, **kwds)

Return the incidence matrix of the (di)graph.

Each row is a vertex, and each column is an edge. The vertices are ordered as obtained by the method vertices(), except when parameter vertices is given (see below), and the edges as obtained by the method edge_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 – boolean (default: None); when set to True, the matrix will be oriented (i.e. with entries in \(-1\), \(0\), \(1\)) and if set to False 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 option directed=True, a somewhat random direction is chosen for each edge.

• sparse – boolean (default: True); whether to use a sparse or a dense matrix

• vertices – list (default: None); when specified, the \(i\)-th row of the matrix corresponds to the \(i\)-th vertex in the ordering of vertices, otherwise, the \(i\)-th row of the matrix corresponds to the \(i\)-th vertex in the ordering given by method vertices().

• edges – list (default: None); when specified, the \(i\)-th column of the matrix corresponds to the \(i\)-th edge in the ordering of edges, otherwise, the \(i\)-th column of the matrix corresponds to the \(i\)-th edge in the ordering given by method edge_iterator().

• base_ring – a ring (default: ZZ); the base ring of the matrix space to use.

• **kwds – other keywords to pass to matrix().

EXAMPLES:

sage: G = graphs.PetersenGraph()
sage: G.incidence_matrix()                                                  # needs sage.modules
[1 1 1 0 0 0 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 1 0 1 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 1 1 0 0 0 0 0 0]
[0 1 0 0 0 0 0 1 0 1 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0 1 1 0 0 0]
[0 0 0 0 1 0 0 0 0 0 0 0 1 1 0]
[0 0 0 0 0 0 1 0 0 0 1 0 0 0 1]
[0 0 0 0 0 0 0 0 1 0 0 1 1 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 1 1]
sage: G.incidence_matrix(oriented=True)                                     # needs sage.modules
[-1 -1 -1  0  0  0  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  1  0 -1 -1  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  1  0 -1 -1  0  0  0  0  0  0]
[ 0  1  0  0  0  0  0  1  0 -1  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0 -1 -1  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0 -1 -1  0]
[ 0  0  0  0  0  0  1  0  0  0  1  0  0  0 -1]
[ 0  0  0  0  0  0  0  0  1  0  0  1  1  0  0]
[ 0  0  0  0  0  0  0  0  0  1  0  0  0  1  1]

sage: G = digraphs.Circulant(4, [1, 3])
sage: G.incidence_matrix()                                                  # needs sage.modules
[-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()                            # needs sage.modules
[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)                                    # needs sage.modules
[2 1 1]
[0 1 1]

A well known result states that the product of the (oriented) incidence matrix with its transpose of a (non-oriented graph) is in fact the Kirchhoff matrix:

sage: G = graphs.PetersenGraph()
sage: m = G.incidence_matrix(oriented=True)                                 # needs sage.modules
sage: m * m.transpose() == G.kirchhoff_matrix()                             # needs sage.modules
True

sage: K = graphs.CompleteGraph(3)
sage: m = K.incidence_matrix(oriented=True)                                 # needs sage.modules
sage: m * m.transpose() == K.kirchhoff_matrix()                             # needs sage.modules
True

sage: H = Graph([(0, 0), (0, 1), (0, 1)], loops=True, multiedges=True)
sage: m = H.incidence_matrix(oriented=True)                                 # needs sage.modules
sage: m * m.transpose() == H.kirchhoff_matrix()                             # needs sage.modules
True

A different ordering of the vertices:

sage: P5 = graphs.PathGraph(5)
sage: P5.incidence_matrix()                                                 # needs sage.modules
[1 0 0 0]
[1 1 0 0]
[0 1 1 0]
[0 0 1 1]
[0 0 0 1]
sage: P5.incidence_matrix(vertices=[2, 4, 1, 3, 0])                         # needs sage.modules
[0 1 1 0]
[0 0 0 1]
[1 1 0 0]
[0 0 1 1]
[1 0 0 0]

A different ordering of the edges:

sage: E = list(P5.edge_iterator(labels=False))
sage: P5.incidence_matrix(edges=E[::-1])                                    # needs sage.modules
[0 0 0 1]
[0 0 1 1]
[0 1 1 0]
[1 1 0 0]
[1 0 0 0]
sage: P5.incidence_matrix(vertices=[2, 4, 1, 3, 0], edges=E[::-1])          # needs sage.modules
[0 1 1 0]
[1 0 0 0]
[0 0 1 1]
[1 1 0 0]
[0 0 0 1]

A different base ring:

sage: P5.incidence_matrix(base_ring=RDF)                                    # needs sage.modules
[1.0 0.0 0.0 0.0]
[1.0 1.0 0.0 0.0]
[0.0 1.0 1.0 0.0]
[0.0 0.0 1.0 1.0]
[0.0 0.0 0.0 1.0]

Creating an immutable matrix:

sage: m = P5.incidence_matrix(immutable=True); m                            # needs sage.modules
[1 0 0 0]
[1 1 0 0]
[0 1 1 0]
[0 0 1 1]
[0 0 0 1]
sage: m[1,2] = 1                                                            # needs sage.modules
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead
(i.e., use copy(M) to change a copy of M).

is_bipartite(certificate=False)

Check whether the graph is bipartite.

Traverse the graph \(G\) with breadth-first-search and color nodes.

INPUT:

• certificate – boolean (default: False); whether to return a certificate. If set to True, the certificate returned is a proper 2-coloring 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(10, 10, 0.7).is_bipartite()                    # needs numpy
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 be None.

The empty graph is defined to be not a Cayley graph.

Note

For this routine to work on all graphs, the optional package gap_packages needs to be installed: to do so, it is enough to run sage -i gap_packages.

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 vertex-transitive 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()                                                         # needs sage.groups
False

A Cayley digraph is a Cayley graph:

sage: C7 = groups.permutation.Cyclic(7)                                     # needs sage.groups
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)                                     # needs sage.groups
sage: d.is_cayley()                                                         # needs sage.groups
True

Graphs with loops and multiedges will have identity and repeated elements, respectively, among the generators:

sage: # needs sage.rings.finite_rings
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)                                   # needs sage.groups
sage: S  # random                                                           # needs sage.groups
[(),
 (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')

Check 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) [FG1965].

(It can be seen that if \(G\) contains an induced hole, then it cannot have a perfe