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.
`all_paths_iterator()`	Return an iterator over the paths of `self`.
`all_simple_paths()`	Return a list of all the simple paths of `self` starting with one of the given vertices.
`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_geodetic()`	Check whether the input (di)graph is geodetic.
`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_cycle()`	Return the longest (induced) cycle of `self`.
`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.
`maximum_leaf_number()`	Return the maximum leaf number 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[source]#

Bases: GenericGraph_pyx

Base class for graphs and digraphs.

__eq__(other)[source]#

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

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

Python

>>> from sage.all import *
>>> G = graphs.EmptyGraph()
>>> H = Graph()
>>> G == H
True
>>> G.to_directed() == H.to_directed()
True
>>> G = graphs.RandomGNP(Integer(8), RealNumber('.9999'))
>>> H = graphs.CompleteGraph(Integer(8))
>>> G == H  # random - most often true
True
>>> G = Graph({Integer(0): [Integer(1), Integer(2), Integer(3), Integer(4), Integer(5), Integer(6), Integer(7)]} )
>>> H = Graph({Integer(1): [Integer(0)], Integer(2): [Integer(0)], Integer(3): [Integer(0)], Integer(4): [Integer(0)], Integer(5): [Integer(0)], Integer(6): [Integer(0)], Integer(7): [Integer(0)]} )
>>> G == H
True
>>> G.allow_loops(True)
>>> G == H
False
>>> G = graphs.RandomGNP(Integer(9), RealNumber('.3')).to_directed()
>>> H = graphs.RandomGNP(Integer(9), RealNumber('.3')).to_directed()
>>> G == H # most often false
False
>>> G = Graph(multiedges=True, sparse=True)
>>> G.add_edge(Integer(0), Integer(1))
>>> H = copy(G)
>>> H.add_edge(Integer(0), Integer(1))
>>> G == H
False

Note that graphs must be considered weighted, or Sage will not pay attention to edge label data in equality testing:

Sage

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

Python

>>> from sage.all import *
>>> foo = Graph(sparse=True)
>>> foo.add_edges([(Integer(0), Integer(1), Integer(1)), (Integer(0), Integer(2), Integer(2))])
>>> bar = Graph(sparse=True)
>>> bar.add_edges([(Integer(0), Integer(1), Integer(2)), (Integer(0), Integer(2), Integer(1))])
>>> foo == bar
True
>>> foo.weighted(True)
>>> foo == bar
False
>>> bar.weighted(True)
>>> foo == bar
False

add_clique(vertices, loops=False)[source]#

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

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

Python

>>> from sage.all import *
>>> G = Graph()
>>> G.add_clique(range(Integer(4)))
>>> G.is_isomorphic(graphs.CompleteGraph(Integer(4)))
True
>>> D = DiGraph()
>>> D.add_clique(range(Integer(4)))
>>> D.is_isomorphic(digraphs.Complete(Integer(4)))
True
>>> D = DiGraph(loops=True)
>>> D.add_clique(range(Integer(4)), loops=True)
>>> D.is_isomorphic(digraphs.Complete(Integer(4), loops=True))
True
>>> D = DiGraph(loops=False)
>>> D.add_clique(range(Integer(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

sage: G = Graph(loops=True)
sage: G.add_clique([1, 1])
sage: G.edges(sort=True)
[(1, 1, None)]

Python

>>> from sage.all import *
>>> G = Graph(loops=True)
>>> G.add_clique([Integer(1), Integer(1)])
>>> G.edges(sort=True)
[(1, 1, None)]

This is equivalent to:

Sage

sage: G = Graph(loops=True)
sage: G.add_clique([1], loops=True)
sage: G.edges(sort=True)
[(1, 1, None)]

Python

>>> from sage.all import *
>>> G = Graph(loops=True)
>>> G.add_clique([Integer(1)], loops=True)
>>> G.edges(sort=True)
[(1, 1, None)]

add_cycle(vertices)[source]#

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

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

Python

>>> from sage.all import *
>>> G = Graph()
>>> G.add_vertices(range(Integer(10))); G
Graph on 10 vertices
>>> show(G)                                                               # needs sage.plot
>>> G.add_cycle(list(range(Integer(10), Integer(20))))
>>> show(G)                                                               # needs sage.plot
>>> G.add_cycle(list(range(Integer(10))))
>>> show(G)                                                               # needs sage.plot

Sage

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

Python

>>> from sage.all import *
>>> D = DiGraph()
>>> D.add_cycle(list(range(Integer(4))))
>>> D.edges(sort=True)
[(0, 1, None), (1, 2, None), (2, 3, None), (3, 0, None)]

add_edge(u, v=None, label=None)[source]#

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

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

Python

>>> from sage.all import *
>>> G = Graph()
>>> G.add_edge((Integer(1), Integer(2)), 'label')
>>> G.edges(sort=False)
[('label', (1, 2), None)]

You must either use the label keyword:

Sage

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

Python

>>> from sage.all import *
>>> G = Graph()
>>> G.add_edge((Integer(1), Integer(2)), label="label")
>>> G.edges(sort=False)
[(1, 2, 'label')]

Or use one of these:

Sage

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

Python

>>> from sage.all import *
>>> G = Graph()
>>> G.add_edge(Integer(1), Integer(2), 'label')
>>> G.edges(sort=False)
[(1, 2, 'label')]
>>> G = Graph()
>>> G.add_edge((Integer(1), Integer(2), 'label'))
>>> G.edges(sort=False)
[(1, 2, 'label')]

Vertex name cannot be None, so:

Sage

sage: G = Graph()
sage: G.add_edge(None, 4)
sage: G.vertices(sort=True)
[0, 4]

Python

>>> from sage.all import *
>>> G = Graph()
>>> G.add_edge(None, Integer(4))
>>> G.vertices(sort=True)
[0, 4]

add_edges(edges, loops=True)[source]#

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

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

Python

>>> from sage.all import *
>>> G = graphs.DodecahedralGraph()
>>> H = Graph()
>>> H.add_edges(G.edge_iterator()); H
Graph on 20 vertices
>>> G = graphs.DodecahedralGraph().to_directed()
>>> H = DiGraph()
>>> H.add_edges(G.edge_iterator()); H
Digraph on 20 vertices
>>> H.add_edges(iter([]))

>>> H = Graph()
>>> H.add_edges([(Integer(0), Integer(1)), (Integer(0), Integer(2), "label")])
>>> H.edges(sort=True)
[(0, 1, None), (0, 2, 'label')]

We demonstrate the loops argument:

Sage

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

Python

>>> from sage.all import *
>>> H = Graph()
>>> H.add_edges([(Integer(0), Integer(0))], loops=False); H.edges(sort=True)
[]
>>> H.add_edges([(Integer(0), Integer(0))], loops=None); H.edges(sort=True)
[]
>>> H.add_edges([(Integer(0), Integer(0))]); H.edges(sort=True)
Traceback (most recent call last):
...
ValueError: cannot add edge from 0 to 0 in graph without loops
>>> H = Graph(loops=True)
>>> H.add_edges([(Integer(0), Integer(0))], loops=False); H.edges(sort=True)
[]
>>> H.add_edges([(Integer(0), Integer(0))], loops=None); H.edges(sort=True)
[(0, 0, None)]
>>> H.add_edges([(Integer(0), Integer(0))]); H.edges(sort=True)
[(0, 0, None)]

add_path(vertices)[source]#

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

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

Python

>>> from sage.all import *
>>> G = Graph()
>>> G.add_vertices(range(Integer(10))); G
Graph on 10 vertices
>>> show(G)                                                               # needs sage.plot
>>> G.add_path(list(range(Integer(10), Integer(20))))
>>> show(G)                                                               # needs sage.plot
>>> G.add_path(list(range(Integer(10))))
>>> show(G)                                                               # needs sage.plot

Sage

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

Python

>>> from sage.all import *
>>> D = DiGraph()
>>> D.add_path(list(range(Integer(4))))
>>> D.edges(sort=True)
[(0, 1, None), (1, 2, None), (2, 3, None)]

add_vertex(name=None)[source]#

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

sage: G = Graph(); G.add_vertex(); G
0
Graph on 1 vertex

Python

>>> from sage.all import *
>>> G = Graph(); G.add_vertex(); G
0
Graph on 1 vertex

Sage

sage: D = DiGraph(); D.add_vertex(); D
0
Digraph on 1 vertex

Python

>>> from sage.all import *
>>> D = DiGraph(); D.add_vertex(); D
0
Digraph on 1 vertex

add_vertices(vertices)[source]#

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

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]

Python

>>> from sage.all import *
>>> d = {Integer(0): [Integer(1),Integer(4),Integer(5)], Integer(1): [Integer(2),Integer(6)], Integer(2): [Integer(3),Integer(7)], Integer(3): [Integer(4),Integer(8)], Integer(4): [Integer(9)], Integer(5): [Integer(7),Integer(8)], Integer(6): [Integer(8),Integer(9)], Integer(7): [Integer(9)]}
>>> G = Graph(d)
>>> G.add_vertices([Integer(10),Integer(11),Integer(12)])
>>> G.vertices(sort=True)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
>>> G.add_vertices(graphs.CycleGraph(Integer(25)).vertex_iterator())
>>> 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

sage: G = Graph()
sage: G.add_vertices([1, 2, 3])
sage: G.add_vertices([4, None, None, 5])
[0, 6]

Python

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

adjacency_matrix(sparse, vertices=None, base_ring=None, **kwds)[source]#

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, None, or True (default: None);
- when a list, the \(i\)-th row and column of the matrix correspond to the \(i\)-th vertex in the ordering of vertices,
- when None, the \(i\)-th row and column of the matrix correspond to the \(i\)-th vertex in the ordering given by GenericGraph.vertices() with sort=True.
- when True, construct an endomorphism of a free module instead of a matrix, where the module’s basis is indexed by the vertices.
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

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]

Python

>>> from sage.all import *
>>> G = graphs.CubeGraph(Integer(4))
>>> 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

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]

Python

>>> from sage.all import *
>>> matrix(GF(Integer(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

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]

Python

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(0), Integer(2)], Integer(2): [Integer(3)],
...              Integer(3): [Integer(4)], Integer(4): [Integer(0), Integer(5)], Integer(5): [Integer(1)]})
>>> 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

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]

Python

>>> from sage.all import *
>>> graphs.PathGraph(Integer(5)).adjacency_matrix(vertices=[Integer(2), Integer(4), Integer(1), Integer(3), Integer(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

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

Python

>>> from sage.all import *
>>> graphs.PathGraph(Integer(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]
>>> type(_)                                                               # needs sage.modules
<class 'sage.matrix.matrix_real_double_dense.Matrix_real_double_dense'>

A different matrix implementation:

Sage

sage: graphs.PathGraph(5).adjacency_matrix(sparse=False,                    # needs numpy 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'>

Python

>>> from sage.all import *
>>> graphs.PathGraph(Integer(5)).adjacency_matrix(sparse=False,                    # needs numpy 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]
>>> type(_)
<class 'sage.matrix.matrix_numpy_integer_dense.Matrix_numpy_integer_dense'>

As an immutable matrix:

Sage

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

Python

>>> from sage.all import *
>>> M = graphs.PathGraph(Integer(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]
>>> M[Integer(2), Integer(2)] = Integer(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).

Creating a module endomorphism:

Sage

sage: # needs sage.modules
sage: D12 = posets.DivisorLattice(12).hasse_diagram()
sage: phi = D12.adjacency_matrix(vertices=True); phi
Generic endomorphism of
 Free module generated by {1, 2, 3, 4, 6, 12} over Integer Ring
sage: print(phi._unicode_art_matrix())
    1  2  3  4  6 12
 1⎛ 0  1  1  0  0  0⎞
 2⎜ 0  0  0  1  1  0⎟
 3⎜ 0  0  0  0  1  0⎟
 4⎜ 0  0  0  0  0  1⎟
 6⎜ 0  0  0  0  0  1⎟
12⎝ 0  0  0  0  0  0⎠

Python

>>> from sage.all import *
>>> # needs sage.modules
>>> D12 = posets.DivisorLattice(Integer(12)).hasse_diagram()
>>> phi = D12.adjacency_matrix(vertices=True); phi
Generic endomorphism of
 Free module generated by {1, 2, 3, 4, 6, 12} over Integer Ring
>>> print(phi._unicode_art_matrix())
    1  2  3  4  6 12
 1⎛ 0  1  1  0  0  0⎞
 2⎜ 0  0  0  1  1  0⎟
 3⎜ 0  0  0  0  1  0⎟
 4⎜ 0  0  0  0  0  1⎟
 6⎜ 0  0  0  0  0  1⎟
12⎝ 0  0  0  0  0  0⎠

all_paths(G, start, end, use_multiedges=False, report_edges=False, labels=False)[source]#

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

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

Python

>>> from sage.all import *
>>> eg1 = Graph({Integer(0):[Integer(1), Integer(2)], Integer(1):[Integer(4)], Integer(2):[Integer(3), Integer(4)], Integer(4):[Integer(5)], Integer(5):[Integer(6)]})
>>> eg1.all_paths(Integer(0), Integer(6))
[[0, 1, 4, 5, 6], [0, 2, 4, 5, 6]]
>>> eg2 = graphs.PetersenGraph()
>>> sorted(eg2.all_paths(Integer(1), Integer(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]]
>>> dg = DiGraph({Integer(0):[Integer(1), Integer(3)], Integer(1):[Integer(3)], Integer(2):[Integer(0), Integer(3)]})
>>> sorted(dg.all_paths(Integer(0), Integer(3)))
[[0, 1, 3], [0, 3]]
>>> ug = dg.to_undirected()
>>> sorted(ug.all_paths(Integer(0), Integer(3)))
[[0, 1, 3], [0, 2, 3], [0, 3]]

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

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

>>> g = Graph([(Integer(0), Integer(1), 'a'), (Integer(0), Integer(1), 'b'), (Integer(1), Integer(2), 'c'), (Integer(1), Integer(2), 'd')], multiedges=True)
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=False)
[[0, 1, 2]]
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=True, report_edges=True)
[[(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)]]
>>> g.all_paths(Integer(0), Integer(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'))]
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=False, report_edges=True, labels=True)
[((0, 1, 'b'), (1, 2, 'd'))]
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=False, report_edges=False, labels=True)
[[0, 1, 2]]
>>> g.all_paths(Integer(0), Integer(2), use_multiedges=True, report_edges=False, labels=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]

all_paths_iterator(starting_vertices=None, ending_vertices=None, simple=False, max_length=None, trivial=False, use_multiedges=False, report_edges=False, labels=False)[source]#

Return an iterator over the paths of self.

The paths are enumerated in increasing length order.

INPUT:

starting_vertices – iterable (default: None); vertices from which the paths must start. If None, then all vertices of the graph can be starting points.
ending_vertices – iterable (default: None); allowed ending vertices of the paths. If None, then all vertices are allowed.
simple – boolean (default: False); if set to True, then only simple paths are considered. Simple paths are paths in which no two arcs share a head or share a tail, i.e. every vertex in the path is entered at most once and exited at most once.
max_length – non negative integer (default: None); the maximum length of the enumerated paths. If set to None, then all lengths are allowed.
trivial – boolean (default: False); if set to True, then the empty paths are also enumerated.
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.

OUTPUT:

iterator

AUTHOR:

Alexandre Blondin Masse

EXAMPLES:

Sage

sage: G = graphs.CompleteGraph(4)
sage: list(G.all_paths_iterator(starting_vertices=[1], ending_vertices=[3], simple=True))
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3]]
sage: list(G.shortest_simple_paths(1, 3))
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 2, 0, 3], [1, 0, 2, 3]]
sage: pi = G.all_paths_iterator(starting_vertices=[1], ending_vertices=[3])
sage: for _ in range(6):
....:     print(next(pi))
[1, 3]
[1, 0, 3]
[1, 2, 3]
[1, 0, 1, 3]
[1, 0, 2, 3]
[1, 2, 0, 3]

sage: g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
sage: pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['d'], report_edges=True, simple=True)
sage: list(pi)
[[('a', 'b'), ('b', 'c'), ('c', 'd')]]

sage: g = DiGraph([(0, 1, 'a'), (0, 1, 'b'), (1, 2,'c'), (1, 2,'d')], multiedges=True)
sage: pi =  g.all_paths_iterator(starting_vertices=[0], use_multiedges=True)
sage: for _ in range(6):
....:     print(next(pi))
[0, 1]
[0, 1]
[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
sage: pi =  g.all_paths_iterator(starting_vertices=[0], use_multiedges=True, report_edges=True, labels=True)
sage: for _ in range(6):
....:     print(next(pi))
[(0, 1, 'b')]
[(0, 1, 'a')]
[(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: list(g.all_paths_iterator(starting_vertices=[0, 1], ending_vertices=[2], use_multiedges=False, report_edges=True, labels=True, simple=True))
[[(1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'd')]]
sage: list(g.all_paths_iterator(starting_vertices=[0, 1], ending_vertices=[2], use_multiedges=False, report_edges=False, labels=True))
[[1, 2], [0, 1, 2]]
sage: list(g.all_paths_iterator(use_multiedges=True, report_edges=False, labels=True, max_length=1))
[[1, 2], [1, 2], [0, 1], [0, 1]]
sage: list(g.all_paths_iterator(use_multiedges=True, report_edges=True, labels=True, max_length=1))
[[(1, 2, 'd')], [(1, 2, 'c')], [(0, 1, 'b')], [(0, 1, 'a')]]

sage: g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
sage: pi = g.all_paths_iterator()
sage: [len(next(pi)) - 1 for _ in range(7)]
[1, 1, 1, 1, 1, 2, 2]

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(4))
>>> list(G.all_paths_iterator(starting_vertices=[Integer(1)], ending_vertices=[Integer(3)], simple=True))
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3]]
>>> list(G.shortest_simple_paths(Integer(1), Integer(3)))
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 2, 0, 3], [1, 0, 2, 3]]
>>> pi = G.all_paths_iterator(starting_vertices=[Integer(1)], ending_vertices=[Integer(3)])
>>> for _ in range(Integer(6)):
...     print(next(pi))
[1, 3]
[1, 0, 3]
[1, 2, 3]
[1, 0, 1, 3]
[1, 0, 2, 3]
[1, 2, 0, 3]

>>> g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
>>> pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['d'], report_edges=True, simple=True)
>>> list(pi)
[[('a', 'b'), ('b', 'c'), ('c', 'd')]]

>>> g = DiGraph([(Integer(0), Integer(1), 'a'), (Integer(0), Integer(1), 'b'), (Integer(1), Integer(2),'c'), (Integer(1), Integer(2),'d')], multiedges=True)
>>> pi =  g.all_paths_iterator(starting_vertices=[Integer(0)], use_multiedges=True)
>>> for _ in range(Integer(6)):
...     print(next(pi))
[0, 1]
[0, 1]
[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
>>> pi =  g.all_paths_iterator(starting_vertices=[Integer(0)], use_multiedges=True, report_edges=True, labels=True)
>>> for _ in range(Integer(6)):
...     print(next(pi))
[(0, 1, 'b')]
[(0, 1, 'a')]
[(0, 1, 'b'), (1, 2, 'd')]
[(0, 1, 'b'), (1, 2, 'c')]
[(0, 1, 'a'), (1, 2, 'd')]
[(0, 1, 'a'), (1, 2, 'c')]
>>> list(g.all_paths_iterator(starting_vertices=[Integer(0), Integer(1)], ending_vertices=[Integer(2)], use_multiedges=False, report_edges=True, labels=True, simple=True))
[[(1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'd')]]
>>> list(g.all_paths_iterator(starting_vertices=[Integer(0), Integer(1)], ending_vertices=[Integer(2)], use_multiedges=False, report_edges=False, labels=True))
[[1, 2], [0, 1, 2]]
>>> list(g.all_paths_iterator(use_multiedges=True, report_edges=False, labels=True, max_length=Integer(1)))
[[1, 2], [1, 2], [0, 1], [0, 1]]
>>> list(g.all_paths_iterator(use_multiedges=True, report_edges=True, labels=True, max_length=Integer(1)))
[[(1, 2, 'd')], [(1, 2, 'c')], [(0, 1, 'b')], [(0, 1, 'a')]]

>>> g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
>>> pi = g.all_paths_iterator()
>>> [len(next(pi)) - Integer(1) for _ in range(Integer(7))]
[1, 1, 1, 1, 1, 2, 2]

It is possible to precise the allowed starting and/or ending vertices:

Sage

sage: pi = g.all_paths_iterator(starting_vertices=['a'])
sage: [len(next(pi)) - 1 for _ in range(5)]
[1, 1, 2, 2, 2]
sage: pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b'])
sage: for _ in range(5):
....:     print(next(pi))
['a', 'b']
['a', 'a', 'b']
['a', 'a', 'a', 'b']
['a', 'a', 'a', 'a', 'b']
['a', 'a', 'a', 'a', 'a', 'b']

Python

>>> from sage.all import *
>>> pi = g.all_paths_iterator(starting_vertices=['a'])
>>> [len(next(pi)) - Integer(1) for _ in range(Integer(5))]
[1, 1, 2, 2, 2]
>>> pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b'])
>>> for _ in range(Integer(5)):
...     print(next(pi))
['a', 'b']
['a', 'a', 'b']
['a', 'a', 'a', 'b']
['a', 'a', 'a', 'a', 'b']
['a', 'a', 'a', 'a', 'a', 'b']

One may prefer to enumerate only simple paths (see all_simple_paths()):

Sage

sage: pi = g.all_paths_iterator(simple=True)
sage: sorted(list(pi), key=lambda x:(len(x), x))
[['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'],
    ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd'],
    ['a', 'b', 'c', 'd']]
sage: pi = g.all_paths_iterator(simple=True)
sage: [len(p) - 1 for p in pi]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 3]

Python

>>> from sage.all import *
>>> pi = g.all_paths_iterator(simple=True)
>>> sorted(list(pi), key=lambda x:(len(x), x))
[['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'],
    ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd'],
    ['a', 'b', 'c', 'd']]
>>> pi = g.all_paths_iterator(simple=True)
>>> [len(p) - Integer(1) for p in pi]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 3]

Or simply bound the length of the enumerated paths:

Sage

sage: pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b', 'c'], max_length=6)
sage: sorted(list(pi), key=lambda x:(len(x), x))
[['a', 'b'], ['a', 'a', 'b'], ['a', 'b', 'c'], ['a', 'a', 'a', 'b'],
    ['a', 'a', 'b', 'c'], ['a', 'a', 'a', 'a', 'b'],
    ['a', 'a', 'a', 'b', 'c'], ['a', 'b', 'c', 'd', 'c'],
    ['a', 'a', 'a', 'a', 'a', 'b'], ['a', 'a', 'a', 'a', 'b', 'c'],
    ['a', 'a', 'b', 'c', 'd', 'c'],
    ['a', 'a', 'a', 'a', 'a', 'a', 'b'],
    ['a', 'a', 'a', 'a', 'a', 'b', 'c'],
    ['a', 'a', 'a', 'b', 'c', 'd', 'c'],
    ['a', 'b', 'c', 'd', 'c', 'd', 'c']]
sage: pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b', 'c'], max_length=6)
sage: [len(p) - 1 for p in pi]
[1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6]

Python

>>> from sage.all import *
>>> pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b', 'c'], max_length=Integer(6))
>>> sorted(list(pi), key=lambda x:(len(x), x))
[['a', 'b'], ['a', 'a', 'b'], ['a', 'b', 'c'], ['a', 'a', 'a', 'b'],
    ['a', 'a', 'b', 'c'], ['a', 'a', 'a', 'a', 'b'],
    ['a', 'a', 'a', 'b', 'c'], ['a', 'b', 'c', 'd', 'c'],
    ['a', 'a', 'a', 'a', 'a', 'b'], ['a', 'a', 'a', 'a', 'b', 'c'],
    ['a', 'a', 'b', 'c', 'd', 'c'],
    ['a', 'a', 'a', 'a', 'a', 'a', 'b'],
    ['a', 'a', 'a', 'a', 'a', 'b', 'c'],
    ['a', 'a', 'a', 'b', 'c', 'd', 'c'],
    ['a', 'b', 'c', 'd', 'c', 'd', 'c']]
>>> pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b', 'c'], max_length=Integer(6))
>>> [len(p) - Integer(1) for p in pi]
[1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6]

By default, empty paths are not enumerated, but it may be parametrized:

Sage

sage: pi = g.all_paths_iterator(simple=True, trivial=True)
sage: sorted(list(pi), key=lambda x:(len(x), x))
[['a'], ['b'], ['c'], ['d'], ['a', 'a'], ['a', 'b'], ['b', 'c'],
    ['c', 'd'], ['d', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'],
    ['c', 'd', 'c'], ['d', 'c', 'd'], ['a', 'b', 'c', 'd']]
sage: pi = g.all_paths_iterator(simple=True, trivial=True)
sage: [len(p) - 1 for p in pi]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3]
sage: pi = g.all_paths_iterator(simple=True, trivial=False)
sage: sorted(list(pi), key=lambda x:(len(x), x))
[['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'],
    ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd'],
    ['a', 'b', 'c', 'd']]
sage: pi = g.all_paths_iterator(simple=True, trivial=False)
sage: [len(p) - 1 for p in pi]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 3]

Python

>>> from sage.all import *
>>> pi = g.all_paths_iterator(simple=True, trivial=True)
>>> sorted(list(pi), key=lambda x:(len(x), x))
[['a'], ['b'], ['c'], ['d'], ['a', 'a'], ['a', 'b'], ['b', 'c'],
    ['c', 'd'], ['d', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'],
    ['c', 'd', 'c'], ['d', 'c', 'd'], ['a', 'b', 'c', 'd']]
>>> pi = g.all_paths_iterator(simple=True, trivial=True)
>>> [len(p) - Integer(1) for p in pi]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3]
>>> pi = g.all_paths_iterator(simple=True, trivial=False)
>>> sorted(list(pi), key=lambda x:(len(x), x))
[['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'],
    ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd'],
    ['a', 'b', 'c', 'd']]
>>> pi = g.all_paths_iterator(simple=True, trivial=False)
>>> [len(p) - Integer(1) for p in pi]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 3]

all_simple_paths(starting_vertices=None, ending_vertices=None, max_length=None, trivial=False, use_multiedges=False, report_edges=False, labels=False)[source]#

Return a list of all the simple paths of self starting with one of the given vertices.

Simple paths are paths in which no two arcs share a head or share a tail, i.e. every vertex in the path is entered at most once and exited at most once.

INPUT:

starting_vertices – list (default: None); vertices from which the paths must start. If None, then all vertices of the graph can be starting points.
ending_vertices – iterable (default: None); allowed ending vertices of the paths. If None, then all vertices are allowed.
max_length – non negative integer (default: None); the maximum length of the enumerated paths. If set to None, then all lengths are allowed.
trivial – boolean (default: False); if set to True, then the empty paths are also enumerated.
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.

OUTPUT:

list

Note

Although the number of simple paths of a finite graph is always finite, computing all its paths may take a very long time.

EXAMPLES:

Sage

sage: G = graphs.CompleteGraph(4)
sage: G.all_simple_paths([1], [3])
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3]]
sage: list(G.shortest_simple_paths(1, 3))
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 2, 0, 3], [1, 0, 2, 3]]
sage: G.all_simple_paths([0, 1], [2, 3])
[[1, 2],
 [1, 3],
 [0, 2],
 [0, 3],
 [0, 1, 2],
 [0, 1, 3],
 [0, 2, 3],
 [0, 3, 2],
 [1, 0, 2],
 [1, 0, 3],
 [1, 2, 3],
 [1, 3, 2],
 [1, 0, 2, 3],
 [1, 0, 3, 2],
 [1, 2, 0, 3],
 [1, 3, 0, 2],
 [0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 3, 1, 2]]

sage: g = DiGraph({0: [0, 1], 1: [2], 2: [3], 3: [2]}, loops=True)
sage: g.all_simple_paths()
[[3, 2],
 [2, 3],
 [1, 2],
 [0, 0],
 [0, 1],
 [0, 1, 2],
 [1, 2, 3],
 [2, 3, 2],
 [3, 2, 3],
 [0, 1, 2, 3]]

sage: g = DiGraph([(0, 1, 'a'), (0, 1, 'b'), (1, 2,'c'), (1, 2,'d')], multiedges=True)
sage: g.all_simple_paths(starting_vertices=[0], ending_vertices=[2], use_multiedges=False)
[[0, 1, 2]]
sage: g.all_simple_paths(starting_vertices=[0], ending_vertices=[2], use_multiedges=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
sage: g.all_simple_paths(starting_vertices=[0], ending_vertices=[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_simple_paths(starting_vertices=[0], ending_vertices=[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_simple_paths(starting_vertices=[0, 1], ending_vertices=[2], use_multiedges=False, report_edges=True, labels=True)
[[(1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'd')]]
sage: g.all_simple_paths(starting_vertices=[0, 1], ending_vertices=[2], use_multiedges=False, report_edges=False, labels=True)
[[1, 2], [0, 1, 2]]
sage: g.all_simple_paths(use_multiedges=True, report_edges=False, labels=True)
[[1, 2], [1, 2], [0, 1], [0, 1], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
sage: g.all_simple_paths(starting_vertices=[0, 1], ending_vertices=[2], use_multiedges=False, report_edges=True, labels=True, trivial=True)
[[(1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'd')]]

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(4))
>>> G.all_simple_paths([Integer(1)], [Integer(3)])
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3]]
>>> list(G.shortest_simple_paths(Integer(1), Integer(3)))
[[1, 3], [1, 0, 3], [1, 2, 3], [1, 2, 0, 3], [1, 0, 2, 3]]
>>> G.all_simple_paths([Integer(0), Integer(1)], [Integer(2), Integer(3)])
[[1, 2],
 [1, 3],
 [0, 2],
 [0, 3],
 [0, 1, 2],
 [0, 1, 3],
 [0, 2, 3],
 [0, 3, 2],
 [1, 0, 2],
 [1, 0, 3],
 [1, 2, 3],
 [1, 3, 2],
 [1, 0, 2, 3],
 [1, 0, 3, 2],
 [1, 2, 0, 3],
 [1, 3, 0, 2],
 [0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 3, 1, 2]]

>>> g = DiGraph({Integer(0): [Integer(0), Integer(1)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(2)]}, loops=True)
>>> g.all_simple_paths()
[[3, 2],
 [2, 3],
 [1, 2],
 [0, 0],
 [0, 1],
 [0, 1, 2],
 [1, 2, 3],
 [2, 3, 2],
 [3, 2, 3],
 [0, 1, 2, 3]]

>>> g = DiGraph([(Integer(0), Integer(1), 'a'), (Integer(0), Integer(1), 'b'), (Integer(1), Integer(2),'c'), (Integer(1), Integer(2),'d')], multiedges=True)
>>> g.all_simple_paths(starting_vertices=[Integer(0)], ending_vertices=[Integer(2)], use_multiedges=False)
[[0, 1, 2]]
>>> g.all_simple_paths(starting_vertices=[Integer(0)], ending_vertices=[Integer(2)], use_multiedges=True)
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
>>> g.all_simple_paths(starting_vertices=[Integer(0)], ending_vertices=[Integer(2)], use_multiedges=True, report_edges=True)
[[(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)], [(0, 1), (1, 2)]]
>>> g.all_simple_paths(starting_vertices=[Integer(0)], ending_vertices=[Integer(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')]]
>>> g.all_simple_paths(starting_vertices=[Integer(0), Integer(1)], ending_vertices=[Integer(2)], use_multiedges=False, report_edges=True, labels=True)
[[(1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'd')]]
>>> g.all_simple_paths(starting_vertices=[Integer(0), Integer(1)], ending_vertices=[Integer(2)], use_multiedges=False, report_edges=False, labels=True)
[[1, 2], [0, 1, 2]]
>>> g.all_simple_paths(use_multiedges=True, report_edges=False, labels=True)
[[1, 2], [1, 2], [0, 1], [0, 1], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
>>> g.all_simple_paths(starting_vertices=[Integer(0), Integer(1)], ending_vertices=[Integer(2)], use_multiedges=False, report_edges=True, labels=True, trivial=True)
[[(1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'd')]]

One may compute all paths having specific starting and/or ending vertices:

Sage

sage: g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
sage: g.all_simple_paths(starting_vertices=['a'])
[['a', 'a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'd']]
sage: g.all_simple_paths(starting_vertices=['a'], ending_vertices=['c'])
[['a', 'b', 'c']]
sage: g.all_simple_paths(starting_vertices=['a'], ending_vertices=['b', 'c'])
[['a', 'b'], ['a', 'b', 'c']]

Python

>>> from sage.all import *
>>> g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
>>> g.all_simple_paths(starting_vertices=['a'])
[['a', 'a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'd']]
>>> g.all_simple_paths(starting_vertices=['a'], ending_vertices=['c'])
[['a', 'b', 'c']]
>>> g.all_simple_paths(starting_vertices=['a'], ending_vertices=['b', 'c'])
[['a', 'b'], ['a', 'b', 'c']]

It is also possible to bound the length of the paths:

Sage

sage: g = DiGraph({0: [0, 1], 1: [2], 2: [3], 3: [2]}, loops=True)
sage: g.all_simple_paths(max_length=2)
[[3, 2],
 [2, 3],
 [1, 2],
 [0, 0],
 [0, 1],
 [0, 1, 2],
 [1, 2, 3],
 [2, 3, 2],
 [3, 2, 3]]

Python

>>> from sage.all import *
>>> g = DiGraph({Integer(0): [Integer(0), Integer(1)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(2)]}, loops=True)
>>> g.all_simple_paths(max_length=Integer(2))
[[3, 2],
 [2, 3],
 [1, 2],
 [0, 0],
 [0, 1],
 [0, 1, 2],
 [1, 2, 3],
 [2, 3, 2],
 [3, 2, 3]]

By default, empty paths are not enumerated, but this can be parametrized:

Sage

sage: g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
sage: g.all_simple_paths(starting_vertices=['a'], trivial=True)
[['a'], ['a', 'a'], ['a', 'b'], ['a', 'b', 'c'],
 ['a', 'b', 'c', 'd']]
sage: g.all_simple_paths(starting_vertices=['a'], trivial=False)
[['a', 'a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'd']]

Python

>>> from sage.all import *
>>> g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
>>> g.all_simple_paths(starting_vertices=['a'], trivial=True)
[['a'], ['a', 'a'], ['a', 'b'], ['a', 'b', 'c'],
 ['a', 'b', 'c', 'd']]
>>> g.all_simple_paths(starting_vertices=['a'], trivial=False)
[['a', 'a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'd']]

allow_loops(new, check=True)[source]#

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

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

Python

>>> from sage.all import *
>>> G = Graph(loops=True); G
Looped graph on 0 vertices
>>> G.has_loops()
False
>>> G.allows_loops()
True
>>> G.add_edge((Integer(0), Integer(0)))
>>> G.has_loops()
True
>>> G.loops()
[(0, 0, None)]
>>> G.allow_loops(False); G
Graph on 1 vertex
>>> G.has_loops()
False
>>> G.edges(sort=True)
[]

>>> D = DiGraph(loops=True); D
Looped digraph on 0 vertices
>>> D.has_loops()
False
>>> D.allows_loops()
True
>>> D.add_edge((Integer(0), Integer(0)))
>>> D.has_loops()
True
>>> D.loops()
[(0, 0, None)]
>>> D.allow_loops(False); D
Digraph on 1 vertex
>>> D.has_loops()
False
>>> D.edges(sort=True)
[]

allow_multiple_edges(new, check=True, keep_label='any')[source]#

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.

EXAMPLES:

The standard behavior with undirected graphs:

Sage

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

Python

>>> from sage.all import *
>>> G = Graph(multiedges=True, sparse=True); G
Multi-graph on 0 vertices
>>> G.has_multiple_edges()
False
>>> G.allows_multiple_edges()
True
>>> G.add_edges([(Integer(0), Integer(1), Integer(1)), (Integer(0), Integer(1), Integer(2)), (Integer(0), Integer(1), Integer(3))])
>>> G.has_multiple_edges()
True
>>> G.multiple_edges(sort=True)
[(0, 1, 1), (0, 1, 2), (0, 1, 3)]
>>> G.allow_multiple_edges(False); G
Graph on 2 vertices
>>> G.has_multiple_edges()
False
>>> G.edges(sort=True)
[(0, 1, 3)]

If we ask for the minimum label:

Sage

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

Python

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1), Integer(1)), (Integer(0), Integer(1), Integer(2)), (Integer(0), Integer(1), Integer(3))], multiedges=True, sparse=True)
>>> G.allow_multiple_edges(False, keep_label='min')
>>> G.edges(sort=True)
[(0, 1, 1)]

If we ask for the maximum label:

Sage

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

Python

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1), Integer(1)), (Integer(0), Integer(1), Integer(2)), (Integer(0), Integer(1), Integer(3))], multiedges=True, sparse=True)
>>> G.allow_multiple_edges(False, keep_label='max')
>>> G.edges(sort=True)
[(0, 1, 3)]

The standard behavior with digraphs:

Sage

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

Python

>>> from sage.all import *
>>> D = DiGraph(multiedges=True, sparse=True); D
Multi-digraph on 0 vertices
>>> D.has_multiple_edges()
False
>>> D.allows_multiple_edges()
True
>>> D.add_edges([(Integer(0), Integer(1))] * Integer(3))
>>> D.has_multiple_edges()
True
>>> D.multiple_edges()
[(0, 1, None), (0, 1, None), (0, 1, None)]
>>> D.allow_multiple_edges(False); D
Digraph on 2 vertices
>>> D.has_multiple_edges()
False
>>> D.edges(sort=True)
[(0, 1, None)]

allows_loops()[source]#

Return whether loops are permitted in the (di)graph

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> G = Graph(loops=True); G
Looped graph on 0 vertices
>>> G.has_loops()
False
>>> G.allows_loops()
True
>>> G.add_edge((Integer(0), Integer(0)))
>>> G.has_loops()
True
>>> G.loops()
[(0, 0, None)]
>>> G.allow_loops(False); G
Graph on 1 vertex
>>> G.has_loops()
False
>>> G.edges(sort=True)
[]

>>> D = DiGraph(loops=True); D
Looped digraph on 0 vertices
>>> D.has_loops()
False
>>> D.allows_loops()
True
>>> D.add_edge((Integer(0), Integer(0)))
>>> D.has_loops()
True
>>> D.loops()
[(0, 0, None)]
>>> D.allow_loops(False); D
Digraph on 1 vertex
>>> D.has_loops()
False
>>> D.edges(sort=True)
[]

allows_multiple_edges()[source]#

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

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> G = Graph(multiedges=True, sparse=True); G
Multi-graph on 0 vertices
>>> G.has_multiple_edges()
False
>>> G.allows_multiple_edges()
True
>>> G.add_edges([(Integer(0), Integer(1))] * Integer(3))
>>> G.has_multiple_edges()
True
>>> G.multiple_edges()
[(0, 1, None), (0, 1, None), (0, 1, None)]
>>> G.allow_multiple_edges(False); G
Graph on 2 vertices
>>> G.has_multiple_edges()
False
>>> G.edges(sort=True)
[(0, 1, None)]

>>> D = DiGraph(multiedges=True, sparse=True); D
Multi-digraph on 0 vertices
>>> D.has_multiple_edges()
False
>>> D.allows_multiple_edges()
True
>>> D.add_edges([(Integer(0), Integer(1))] * Integer(3))
>>> D.has_multiple_edges()
True
>>> D.multiple_edges()
[(0, 1, None), (0, 1, None), (0, 1, None)]
>>> D.allow_multiple_edges(False); D
Digraph on 2 vertices
>>> D.has_multiple_edges()
False
>>> D.edges(sort=True)
[(0, 1, None)]

am(sparse, vertices=None, base_ring=None, **kwds)[source]#

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, None, or True (default: None);
- when a list, the \(i\)-th row and column of the matrix correspond to the \(i\)-th vertex in the ordering of vertices,
- when None, the \(i\)-th row and column of the matrix correspond to the \(i\)-th vertex in the ordering given by GenericGraph.vertices() with sort=True.
- when True, construct an endomorphism of a free module instead of a matrix, where the module’s basis is indexed by the vertices.
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

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]

Python

>>> from sage.all import *
>>> G = graphs.CubeGraph(Integer(4))
>>> 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

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]

Python

>>> from sage.all import *
>>> matrix(GF(Integer(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

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]

Python

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(0), Integer(2)], Integer(2): [Integer(3)],
...              Integer(3): [Integer(4)], Integer(4): [Integer(0), Integer(5)], Integer(5): [Integer(1)]})
>>> 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

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]

Python

>>> from sage.all import *
>>> graphs.PathGraph(Integer(5)).adjacency_matrix(vertices=[Integer(2), Integer(4), Integer(1), Integer(3), Integer(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

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

Python

>>> from sage.all import *
>>> graphs.PathGraph(Integer(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]
>>> type(_)                                                               # needs sage.modules
<class 'sage.matrix.matrix_real_double_dense.Matrix_real_double_dense'>

A different matrix implementation:

Sage

sage: graphs.PathGraph(5).adjacency_matrix(sparse=False,                    # needs numpy 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'>

Python

>>> from sage.all import *
>>> graphs.PathGraph(Integer(5)).adjacency_matrix(sparse=False,                    # needs numpy 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]
>>> type(_)
<class 'sage.matrix.matrix_numpy_integer_dense.Matrix_numpy_integer_dense'>

As an immutable matrix:

Sage

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

Python

>>> from sage.all import *
>>> M = graphs.PathGraph(Integer(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]
>>> M[Integer(2), Integer(2)] = Integer(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).

Creating a module endomorphism:

Sage

sage: # needs sage.modules
sage: D12 = posets.DivisorLattice(12).hasse_diagram()
sage: phi = D12.adjacency_matrix(vertices=True); phi
Generic endomorphism of
 Free module generated by {1, 2, 3, 4, 6, 12} over Integer Ring
sage: print(phi._unicode_art_matrix())
    1  2  3  4  6 12
 1⎛ 0  1  1  0  0  0⎞
 2⎜ 0  0  0  1  1  0⎟
 3⎜ 0  0  0  0  1  0⎟
 4⎜ 0  0  0  0  0  1⎟
 6⎜ 0  0  0  0  0  1⎟
12⎝ 0  0  0  0  0  0⎠

Python

>>> from sage.all import *
>>> # needs sage.modules
>>> D12 = posets.DivisorLattice(Integer(12)).hasse_diagram()
>>> phi = D12.adjacency_matrix(vertices=True); phi
Generic endomorphism of
 Free module generated by {1, 2, 3, 4, 6, 12} over Integer Ring
>>> print(phi._unicode_art_matrix())
    1  2  3  4  6 12
 1⎛ 0  1  1  0  0  0⎞
 2⎜ 0  0  0  1  1  0⎟
 3⎜ 0  0  0  0  1  0⎟
 4⎜ 0  0  0  0  0  1⎟
 6⎜ 0  0  0  0  0  1⎟
12⎝ 0  0  0  0  0  0⎠

antisymmetric()[source]#

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

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

Python

>>> from sage.all import *
>>> G = digraphs.RandomDirectedGNR(Integer(20), RealNumber('0.5'))                               # needs networkx
>>> G.antisymmetric()                                                     # needs networkx
True

Loops are allowed:

Sage

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

Python

>>> from sage.all import *
>>> G.allow_loops(True)                                                   # needs networkx
>>> G.add_edge(Integer(0), Integer(0))                                                      # needs networkx
>>> G.antisymmetric()                                                     # needs networkx
True

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

Sage

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

Python

>>> from sage.all import *
>>> graphs.RandomGNP(Integer(20), RealNumber('0.5')).antisymmetric()                             # needs networkx
False
>>> Graph(Integer(3)).antisymmetric()
True
>>> Graph([(i, i) for i in range(Integer(3))], loops=True).antisymmetric()
True
>>> DiGraph([(i, i) for i in range(Integer(3))], loops=True).antisymmetric()
True

automorphism_group(partition=None, verbosity=0, edge_labels=False, order=False, return_group=True, orbits=False, algorithm=None)[source]#

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

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

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> graphs_query = GraphQuery(display_cols=['graph6'],num_vertices=Integer(4))
>>> L = graphs_query.get_graphs_list()
>>> graphs_list.show_graphs(L)                                            # needs sage.plot
>>> 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)))
>>> C = graphs.CubeGraph(Integer(4))
>>> G = C.automorphism_group()
>>> M = G.character_table() # random order of rows, thus abs() below
>>> QQ(M.determinant()).abs()
712483534798848
>>> G.order()
384

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> D = graphs.DodecahedralGraph()
>>> G = D.automorphism_group()
>>> A5 = AlternatingGroup(Integer(5))
>>> Z2 = CyclicPermutationGroup(Integer(2))
>>> H = A5.direct_product(Z2)[Integer(0)] #see documentation for direct_product to explain the [0]
>>> G.is_isomorphic(H)
True

Multigraphs:

Sage

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

Python

>>> from sage.all import *
>>> G = Graph(multiedges=True,sparse=True)
>>> G.add_edge(('a', 'b'))
>>> G.add_edge(('a', 'b'))
>>> G.add_edge(('a', 'b'))
>>> G.automorphism_group()                                                # needs sage.groups
Permutation Group with generators [('a','b')]

Digraphs:

Sage

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

Python

>>> from sage.all import *
>>> D = DiGraph( { Integer(0):[Integer(1)], Integer(1):[Integer(2)], Integer(2):[Integer(3)], Integer(3):[Integer(4)], Integer(4):[Integer(0)] } )
>>> D.automorphism_group()                                                # needs sage.groups
Permutation Group with generators [(0,1,2,3,4)]

Edge labeled graphs:

Sage

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

Python

>>> from sage.all import *
>>> G = Graph(sparse=True)
>>> G.add_edges( [(Integer(0),Integer(1),'a'),(Integer(1),Integer(2),'b'),(Integer(2),Integer(3),'c'),(Integer(3),Integer(4),'b'),(Integer(4),Integer(0),'a')] )
>>> G.automorphism_group(edge_labels=True)                                # needs sage.groups
Permutation Group with generators [(1,4)(2,3)]

>>> G.automorphism_group(edge_labels=True, algorithm="bliss")  # optional - bliss
Permutation Group with generators [(1,4)(2,3)]

>>> G.automorphism_group(edge_labels=True, algorithm="sage")              # needs sage.groups
Permutation Group with generators [(1,4)(2,3)]

Sage

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

Python

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

>>> # needs sage.groups
>>> foo = Graph(sparse=True)
>>> bar = Graph(sparse=True)
>>> foo.add_edges([(Integer(0),Integer(1),Integer(1)),(Integer(1),Integer(2),Integer(2)), (Integer(2),Integer(3),Integer(3))])
>>> bar.add_edges([(Integer(0),Integer(1),Integer(1)),(Integer(1),Integer(2),Integer(2)), (Integer(2),Integer(3),Integer(3))])
>>> foo.automorphism_group(edge_labels=True)
Permutation Group with generators [()]
>>> foo.automorphism_group()
Permutation Group with generators [(0,3)(1,2)]
>>> bar.automorphism_group(edge_labels=True)
Permutation Group with generators [()]

You can also ask for just the order of the group:

Sage

sage: G = graphs.PetersenGraph()
sage: G.automorphism_group(return_group=False, order=True)                  # needs sage.groups
120

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> 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

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

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> G = graphs.PetersenGraph()
>>> G.automorphism_group(return_group=False, orbits=True, algorithm='sage')
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]
>>> orb = G.automorphism_group(partition=[[Integer(0)],list(range(Integer(1),Integer(10)))],
...                            return_group=False, orbits=True, algorithm='sage')
>>> sorted([sorted(o) for o in orb], key=len)
[[0], [1, 4, 5], [2, 3, 6, 7, 8, 9]]
>>> C = graphs.CubeGraph(Integer(3))
>>> orb = C.automorphism_group(orbits=True, return_group=False, algorithm='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

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

Python

>>> from sage.all import *
>>> # optional - bliss
>>> G = graphs.HallJankoGraph()
>>> A1 = G.automorphism_group()                                           # needs sage.groups
>>> A2 = G.automorphism_group(algorithm='bliss')
>>> A1.is_isomorphic(A2)                                                  # needs sage.groups
True

average_degree()[source]#

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

sage: g = graphs.CompleteGraph(5)
sage: g.average_degree() == 4
True

Python

>>> from sage.all import *
>>> g = graphs.CompleteGraph(Integer(5))
>>> g.average_degree() == Integer(4)
True

The average degree of a tree is always strictly less than \(2\):

Sage

sage: tree = graphs.RandomTree(20)
sage: tree.average_degree() < 2
True

Python

>>> from sage.all import *
>>> tree = graphs.RandomTree(Integer(20))
>>> tree.average_degree() < Integer(2)
True

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

Sage

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

Python

>>> from sage.all import *
>>> g = graphs.RandomGNP(Integer(20), RealNumber('.4'))
>>> g.average_degree() == Integer(2) * g.size() / g.order()
True

average_distance(by_weight=False, algorithm=None, weight_function=None, check_weight=True)[source]#

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

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

Python

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

Average distance of a circuit:

Sage

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

Python

>>> from sage.all import *
>>> g = digraphs.Circuit(Integer(6))
>>> g.average_distance()
3

blocks_and_cut_vertices(G, algorithm='Tarjan_Boost', sort=False, key=None)[source]#

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

EXAMPLES:

We construct a trivial example of a graph with one cut vertex:

Sage

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

Python

>>> from sage.all import *
>>> from sage.graphs.connectivity import blocks_and_cut_vertices
>>> rings = graphs.CycleGraph(Integer(10))
>>> rings.merge_vertices([Integer(0), Integer(5)])
>>> blocks_and_cut_vertices(rings)
([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0])
>>> rings.blocks_and_cut_vertices()
([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0])
>>> B, C = blocks_and_cut_vertices(rings, algorithm="Tarjan_Sage", sort=True)
>>> B, C
([[0, 1, 2, 3, 4], [0, 6, 7, 8, 9]], [0])
>>> B2, C2 = blocks_and_cut_vertices(rings, algorithm="Tarjan_Sage", sort=False)
>>> 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

sage: blocks_and_cut_vertices(graphs.PetersenGraph())
([[0, 1, 4, 5, 2, 6, 3, 7, 8, 9]], [])

Python

>>> from sage.all import *
>>> blocks_and_cut_vertices(graphs.PetersenGraph())
([[0, 1, 4, 5, 2, 6, 3, 7, 8, 9]], [])

Decomposing paths to pairs:

Sage

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

Python

>>> from sage.all import *
>>> g = graphs.PathGraph(Integer(4)) + graphs.PathGraph(Integer(5))
>>> 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

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

Python

>>> from sage.all import *
>>> g = Graph({Integer(1): {Integer(2): Integer(28), Integer(3): Integer(10)}, Integer(2): {Integer(1): Integer(10), Integer(3): Integer(16)}, Integer(4): {}, Integer(5): {Integer(6): Integer(3), Integer(7): Integer(10), Integer(8): Integer(4)}})
>>> blocks_and_cut_vertices(g)
([[1, 2, 3], [5, 6], [5, 7], [5, 8], [4]], [5])

A directed graph with Boost’s algorithm (Issue #25994):

Sage

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

Python

>>> from sage.all import *
>>> rings = graphs.CycleGraph(Integer(10))
>>> rings.merge_vertices([Integer(0), Integer(5)])
>>> rings = rings.to_directed()
>>> blocks_and_cut_vertices(rings, algorithm="Tarjan_Boost")
([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0])

blocks_and_cuts_tree(G)[source]#

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

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

Python

>>> from sage.all import *
>>> from sage.graphs.connectivity import blocks_and_cuts_tree
>>> T = blocks_and_cuts_tree(graphs.KrackhardtKiteGraph()); T
Graph on 5 vertices
>>> T.is_isomorphic(graphs.PathGraph(Integer(5)))
True
>>> from sage.graphs.connectivity import blocks_and_cuts_tree
>>> T = graphs.KrackhardtKiteGraph().blocks_and_cuts_tree(); T
Graph on 5 vertices

The distance between two leaves is even:

Sage

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

Python

>>> from sage.all import *
>>> T = blocks_and_cuts_tree(graphs.RandomTree(Integer(40)))
>>> T.is_tree()
True
>>> leaves = [v for v in T if T.degree(v) == Integer(1)]
>>> all(T.distance(u,v) % Integer(2) == Integer(0) for u in leaves for v in leaves)
True

The tree of a biconnected graph has a single vertex, of type \(B\):

Sage

sage: T = blocks_and_cuts_tree(graphs.PetersenGraph())
sage: T.vertices(sort=True)
[('B', (0, 1, 4, 5, 2, 6, 3, 7, 8, 9))]

Python

>>> from sage.all import *
>>> T = blocks_and_cuts_tree(graphs.PetersenGraph())
>>> 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)[source]#

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

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]

Python

>>> from sage.all import *
>>> G = Graph({Integer(0): [Integer(1)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0)]})
>>> list(G.breadth_first_search(Integer(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

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]

Python

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(4), Integer(5)], Integer(2): [Integer(5)], Integer(3): [Integer(6)], Integer(5): [Integer(7)], Integer(6): [Integer(7)], Integer(7): [Integer(0)]})
>>> list(D.breadth_first_search(Integer(0)))
[0, 1, 2, 3, 4, 5, 6, 7]
>>> list(D.breadth_first_search(Integer(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

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]

Python

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(4), Integer(5)], Integer(2): [Integer(5)], Integer(3): [Integer(6)], Integer(5): [Integer(7)], Integer(6): [Integer(7)], Integer(7): [Integer(0)]})
>>> list(D.breadth_first_search(Integer(0), distance=Integer(0)))
[0]
>>> list(D.breadth_first_search(Integer(0), distance=Integer(1)))
[0, 1, 2, 3]

Multiple starting vertices can be specified in a list:

Sage

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]

Python

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(4), Integer(5)], Integer(2): [Integer(5)], Integer(3): [Integer(6)], Integer(5): [Integer(7)], Integer(6): [Integer(7)], Integer(7): [Integer(0)]})
>>> list(D.breadth_first_search([Integer(0)]))
[0, 1, 2, 3, 4, 5, 6, 7]
>>> list(D.breadth_first_search([Integer(0), Integer(6)]))
[0, 6, 1, 2, 3, 7, 4, 5]
>>> list(D.breadth_first_search([Integer(0), Integer(6)], distance=Integer(0)))
[0, 6]
>>> list(D.breadth_first_search([Integer(0), Integer(6)], distance=Integer(1)))
[0, 6, 1, 2, 3, 7]
>>> list(D.breadth_first_search(Integer(6), ignore_direction=True, distance=Integer(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

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]

Python

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(4), Integer(5)], Integer(2): [Integer(5)], Integer(3): [Integer(6)], Integer(5): [Integer(7)], Integer(6): [Integer(7)], Integer(7): [Integer(0)]})
>>> list(D.breadth_first_search(Integer(5), neighbors=D.neighbors_in, distance=Integer(2)))
[5, 1, 2, 0]
>>> list(D.breadth_first_search(Integer(5), neighbors=D.neighbors_out, distance=Integer(2)))
[5, 7, 0]
>>> list(D.breadth_first_search(Integer(5) ,neighbors=D.neighbors, distance=Integer(2)))
[5, 1, 2, 7, 0, 4, 6]

It is possible (Issue #16470) using the keyword report_distance to get pairs (vertex, distance) encoding the distance from the starting vertices:

Sage

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

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> list(G.breadth_first_search(Integer(0), report_distance=True))
[(0, 0), (1, 1), (4, 1), (5, 1), (2, 2), (6, 2), (3, 2), (9, 2),
(7, 2), (8, 2)]
>>> list(G.breadth_first_search(Integer(0), report_distance=False))
[0, 1, 4, 5, 2, 6, 3, 9, 7, 8]

>>> D = DiGraph({Integer(0): [Integer(1), Integer(3)], Integer(1): [Integer(0), Integer(2)], Integer(2): [Integer(0), Integer(3)], Integer(3): [Integer(4)]})
>>> D.show()                                                              # needs sage.plot
>>> list(D.breadth_first_search(Integer(4), neighbors=D.neighbor_in_iterator,
...                             report_distance=True))
[(4, 0), (3, 1), (0, 2), (2, 2), (1, 3)]

>>> C = graphs.CycleGraph(Integer(4))
>>> list(C.breadth_first_search([Integer(0), Integer(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

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

Python

>>> from sage.all import *
>>> D = DiGraph({Integer(1):[Integer(2),Integer(3)],Integer(2):[Integer(4)],Integer(3):[Integer(4)],Integer(4):[Integer(1)],Integer(5):[Integer(2),Integer(6)]})
>>> list(D.breadth_first_search(Integer(1), edges=True))
[(1, 2), (1, 3), (2, 4)]

canonical_label(partition=None, certificate=False, edge_labels=False, algorithm=None, return_graph=True)[source]#

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

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

Python

>>> from sage.all import *
>>> g1 = graphs.GridGraph([Integer(2),Integer(3)])
>>> g2 = Graph({Integer(1): [Integer(2), Integer(4)], Integer(3): [Integer(2), Integer(6)], Integer(5): [Integer(4), Integer(2), Integer(6)]})
>>> g1 == g2
False
>>> g1.is_isomorphic(g2)
True
>>> g1.canonical_label() == g2.canonical_label()
True

We can get the relabeling used for canonization:

Sage

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}

Python

>>> from sage.all import *
>>> g, c = g1.canonical_label(algorithm='sage', certificate=True)
>>> g
Grid Graph for [2, 3]: Graph on 6 vertices
>>> 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

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]

Python

>>> from sage.all import *
>>> G = Graph(multiedges=True,sparse=True)
>>> G.add_edge((Integer(0),Integer(1)))
>>> G.add_edge((Integer(0),Integer(1)))
>>> G.add_edge((Integer(0),Integer(1)))
>>> G.canonical_label()
Multi-graph on 2 vertices
>>> Graph('A?').canonical_label()
Graph on 2 vertices

>>> P = graphs.PetersenGraph()
>>> DP = P.to_directed()
>>> 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

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

Python

>>> from sage.all import *
>>> G = Graph(sparse=True)
>>> G.add_edges( [(Integer(0),Integer(1),'a'),(Integer(1),Integer(2),'b'),(Integer(2),Integer(3),'c'),(Integer(3),Integer(4),'b'),(Integer(4),Integer(0),'a')] )
>>> G.canonical_label(edge_labels=True)
Graph on 5 vertices
>>> 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})

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

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

Python

>>> from sage.all import *
>>> g = Graph({'a': ['b'], 'c': ['d']})
>>> g_sage = g.canonical_label(algorithm='sage')
>>> g_bliss = g.canonical_label(algorithm='bliss')                # optional - bliss
>>> g_sage.edges(sort=True, labels=False)
[(0, 3), (1, 2)]
>>> g_bliss.edges(sort=True, labels=False)                        # optional - bliss
[(0, 1), (2, 3)]

cartesian_product(other)[source]#

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)[source]#

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

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                             # needs sage.plot
Graphics object consisting of 21 graphics primitives

Python

>>> from sage.all import *
>>> Z = graphs.CompleteGraph(Integer(2))
>>> C = graphs.CycleGraph(Integer(5))
>>> T = C.tensor_product(Z); T
Graph on 10 vertices
>>> T.size()
10
>>> T.plot()                      # long time                             # needs sage.plot
Graphics object consisting of 21 graphics primitives

Sage

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                             # needs sage.plot
Graphics object consisting of 1101 graphics primitives

Python

>>> from sage.all import *
>>> D = graphs.DodecahedralGraph()
>>> P = graphs.PetersenGraph()
>>> T = D.tensor_product(P); T
Graph on 200 vertices
>>> T.size()
900
>>> T.plot()                      # long time                             # needs sage.plot
Graphics object consisting of 1101 graphics primitives

centrality_betweenness(k=None, normalized=True, weight=None, endpoints=False, seed=None, exact=False, algorithm=None)[source]#

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

EXAMPLES:

Sage

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}

Python

>>> from sage.all import *
>>> g = graphs.ChvatalGraph()
>>> 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}
>>> 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}
>>> D = DiGraph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(2)], Integer(3):[Integer(0),Integer(1)]})
>>> D.show(figsize=[Integer(2),Integer(2)])                                                 # needs sage.plot
>>> D = D.to_undirected()
>>> D.show(figsize=[Integer(2),Integer(2)])                                                 # needs sage.plot
>>> 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)[source]#

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

EXAMPLES:

Standard examples:

Sage

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}

Python

>>> from sage.all import *
>>> (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...}
>>> D = DiGraph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(2)], Integer(3):[Integer(0),Integer(1)]})
>>> D.show(figsize=[Integer(2),Integer(2)])                                                 # needs sage.plot
>>> D.centrality_closeness(vert=[Integer(0),Integer(1)])
{0: 1.0, 1: 0.3333333333333333}
>>> D = D.to_undirected()
>>> D.show(figsize=[Integer(2),Integer(2)])                                                 # needs sage.plot
>>> 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

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

Python

>>> from sage.all import *
>>> g = graphs.PathGraph(Integer(5))
>>> g.centrality_closeness(Integer(0))
0.4
>>> dist = g.shortest_path_lengths(Integer(0)).values()
>>> float(len(dist)-Integer(1)) / sum(dist)
0.4
>>> d = g.to_directed()
>>> d.centrality_closeness(Integer(0))
0.4
>>> dist = d.shortest_path_lengths(Integer(0)).values()
>>> float(len(dist)-Integer(1)) / sum(dist)
0.4

If a vertex has (out)degree 0, its closeness centrality is not defined:

Sage

sage: g = Graph(5)
sage: g.centrality_closeness()
{}
sage: print(g.centrality_closeness(0))
None

Python

>>> from sage.all import *
>>> g = Graph(Integer(5))
>>> g.centrality_closeness()
{}
>>> print(g.centrality_closeness(Integer(0)))
None

Weighted graphs:

Sage

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

Python

>>> from sage.all import *
>>> D = graphs.GridGraph([Integer(2),Integer(2)])
>>> weight_function = lambda e:Integer(10)
>>> D.centrality_closeness([(Integer(0),Integer(0)),(Integer(0),Integer(1))])                          # tol abs 1e-12
{(0, 0): 0.75, (0, 1): 0.75}
>>> D.centrality_closeness((Integer(0),Integer(0)), weight_function=weight_function) # tol abs 1e-12
0.075

characteristic_polynomial(var='x', laplacian=False)[source]#

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

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

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> 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
>>> 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
>>> 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)[source]#

Return the characteristic polynomial of the adjacency matrix of the (di)graph.

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

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

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> 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
>>> 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
>>> 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()[source]#

Empties the graph of vertices and edges and removes name, associated objects, and position information.

EXAMPLES:

Sage

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)

Python

>>> from sage.all import *
>>> G = graphs.CycleGraph(Integer(4))
>>> G.set_vertices({Integer(0):'vertex0'})
>>> print(G.order(), G.size())
4 4
>>> G.name()
'Cycle graph'
>>> G.get_vertex(Integer(0))
'vertex0'
>>> H = G.copy(sparse=True)
>>> H.clear()
>>> print(H.order(), H.size())
0 0
>>> H.name()
''
>>> H.get_vertex(Integer(0))
>>> H = G.copy(sparse=False)
>>> H.clear()
>>> print(H.order(), H.size())
0 0
>>> H.name()
''
>>> H.get_vertex(Integer(0))

cluster_transitivity()[source]#

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

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

Python

>>> from sage.all import *
>>> graphs.FruchtGraph().cluster_transitivity()                           # needs networkx
0.25

cluster_triangles(nbunch=None, implementation=None)[source]#

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

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

Python

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

Sage

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

Python

>>> from sage.all import *
>>> G = graphs.RandomGNP(Integer(20), RealNumber('.3'))
>>> d1 = G.cluster_triangles(implementation="networkx")                   # needs networkx
>>> d2 = G.cluster_triangles(implementation="dense_copy")
>>> d3 = G.cluster_triangles(implementation="sparse_copy")
>>> d1 == d2 and d1 == d3                                                 # needs networkx
True

clustering_average(implementation=None)[source]#

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

sage: (graphs.FruchtGraph()).clustering_average()
1/4
sage: (graphs.FruchtGraph()).clustering_average(implementation='networkx')  # needs networkx
0.25

Python

>>> from sage.all import *
>>> (graphs.FruchtGraph()).clustering_average()
1/4
>>> (graphs.FruchtGraph()).clustering_average(implementation='networkx')  # needs networkx
0.25

clustering_coeff(nodes=None, weight=False, implementation=None)[source]#

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

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}

Python

>>> from sage.all import *
>>> 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}

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

>>> (graphs.FruchtGraph()).clustering_coeff(nodes=[Integer(0),Integer(1),Integer(2)])
{0: 0.3333333333333333, 1: 0.3333333333333333, 2: 0.0}

>>> (graphs.FruchtGraph()).clustering_coeff(nodes=[Integer(0),Integer(1),Integer(2)],                # needs networkx
...                                         weight=True)
{0: 0.3333333333333333, 1: 0.3333333333333333, 2: 0}

>>> (graphs.GridGraph([Integer(5),Integer(5)])).clustering_coeff(nodes=[(Integer(0),Integer(0)),(Integer(0),Integer(1)),(Integer(2),Integer(2))])
{(0, 0): 0.0, (0, 1): 0.0, (2, 2): 0.0}

coarsest_equitable_refinement(partition, sparse=True)[source]#

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

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

Python

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> G.coarsest_equitable_refinement([[Integer(0)],list(range(Integer(1),Integer(10)))])
[[0], [2, 3, 6, 7, 8, 9], [1, 4, 5]]
>>> G = graphs.CubeGraph(Integer(3))
>>> verts = G.vertices(sort=True)
>>> Pi = [verts[:Integer(1)], verts[Integer(1):]]
>>> Pi
[['000'], ['001', '010', '011', '100', '101', '110', '111']]
>>> [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

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

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> prt = [[Integer(0)], [Integer(1), Integer(4), Integer(5)], [Integer(2), Integer(3), Integer(6), Integer(7), Integer(8), Integer(9)]]
>>> P.coarsest_equitable_refinement(prt)
[[0], [1, 4, 5], [2, 3, 6, 7, 8, 9]]

Sage

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

Python

>>> from sage.all import *
>>> ss = (graphs.WheelGraph(Integer(6))).line_graph(labels=False)
>>> prt = [[(Integer(0), Integer(1))], [(Integer(0), Integer(2)), (Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(1), Integer(2)), (Integer(1), Integer(4))], [(Integer(2), Integer(3)), (Integer(3), Integer(4))]]
>>> 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

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

Python

>>> from sage.all import *
>>> ss = (graphs.WheelGraph(Integer(5))).line_graph(labels=False)
>>> 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()[source]#

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

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

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> P.plot()                      # long time                             # needs sage.plot
Graphics object consisting of 26 graphics primitives
>>> PC = P.complement()
>>> PC.plot()                     # long time                             # needs sage.plot
Graphics object consisting of 41 graphics primitives

Sage

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

Python

>>> from sage.all import *
>>> graphs.TetrahedralGraph().complement().size()
0
>>> graphs.CycleGraph(Integer(4)).complement().edges(sort=True)
[(0, 2, None), (1, 3, None)]
>>> graphs.CycleGraph(Integer(4)).complement()
complement(Cycle graph): Graph on 4 vertices
>>> G = Graph(multiedges=True, sparse=True)
>>> G.add_edges([(Integer(0), Integer(1))] * Integer(3))
>>> 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)[source]#

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

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]

Python

>>> from sage.all import *
>>> from sage.graphs.connectivity import connected_component_containing_vertex
>>> G = Graph({Integer(0): [Integer(1), Integer(3)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(4): [Integer(5), Integer(6)], Integer(5): [Integer(6)]})
>>> connected_component_containing_vertex(G, Integer(0), sort=True)
[0, 1, 2, 3]
>>> G.connected_component_containing_vertex(Integer(0), sort=True)
[0, 1, 2, 3]
>>> D = DiGraph({Integer(0): [Integer(1), Integer(3)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(4): [Integer(5), Integer(6)], Integer(5): [Integer(6)]})
>>> connected_component_containing_vertex(D, Integer(0), sort=True)
[0, 1, 2, 3]
>>> connected_component_containing_vertex(D, Integer(0), sort=True, key=lambda x: -x)
[3, 2, 1, 0]

connected_components(G, sort=None, key=None)[source]#

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

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

Python

>>> from sage.all import *
>>> from sage.graphs.connectivity import connected_components
>>> G = Graph({Integer(0): [Integer(1), Integer(3)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(4): [Integer(5), Integer(6)], Integer(5): [Integer(6)]})
>>> connected_components(G, sort=True)
[[0, 1, 2, 3], [4, 5, 6]]
>>> G.connected_components(sort=True)
[[0, 1, 2, 3], [4, 5, 6]]
>>> D = DiGraph({Integer(0): [Integer(1), Integer(3)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(4): [Integer(5), Integer(6)], Integer(5): [Integer(6)]})
>>> connected_components(D, sort=True)
[[0, 1, 2, 3], [4, 5, 6]]
>>> connected_components(D, sort=True, key=lambda x: -x)
[[3, 2, 1, 0], [6, 5, 4]]

connected_components_number(G)[source]#

Return the number of connected components.

INPUT:

G – the input graph

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> from sage.graphs.connectivity import connected_components_number
>>> G = Graph({Integer(0): [Integer(1), Integer(3)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(4): [Integer(5), Integer(6)], Integer(5): [Integer(6)]})
>>> connected_components_number(G)
2
>>> G.connected_components_number()
2
>>> D = DiGraph({Integer(0): [Integer(1), Integer(3)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(4): [Integer(5), Integer(6)], Integer(5): [Integer(6)]})
>>> connected_components_number(D)
2

connected_components_sizes(G)[source]#

Return the sizes of the connected components as a list.

The list is sorted from largest to lower values.

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> from sage.graphs.connectivity import connected_components_sizes
>>> for x in graphs(Integer(3)):
...     print(connected_components_sizes(x))
[1, 1, 1]
[2, 1]
[3]
[3]
>>> for x in graphs(Integer(3)):
...     print(x.connected_components_sizes())
[1, 1, 1]
[2, 1]
[3]
[3]

connected_components_subgraphs(G)[source]#

Return a list of connected components as graph objects.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> from sage.graphs.connectivity import connected_components_subgraphs
>>> G = Graph({Integer(0): [Integer(1), Integer(3)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(4): [Integer(5), Integer(6)], Integer(5): [Integer(6)]})
>>> L = connected_components_subgraphs(G)
>>> graphs_list.show_graphs(L)                                                # needs sage.plot
>>> D = DiGraph({Integer(0): [Integer(1), Integer(3)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(4): [Integer(5), Integer(6)], Integer(5): [Integer(6)]})
>>> L = connected_components_subgraphs(D)
>>> graphs_list.show_graphs(L)                                                # needs sage.plot
>>> L = D.connected_components_subgraphs()
>>> 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)[source]#

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

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

Python

>>> from sage.all import *
>>> G = DiGraph([(Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(3), Integer(4)), (Integer(4), Integer(2))])
>>> 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]
>>> 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]]
>>> list(G.connected_subgraph_iterator(k=Integer(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]
>>> list(G.connected_subgraph_iterator(k=Integer(3), vertices_only=True, exactly_k=True))
[[1, 2, 3], [1, 2, 4], [2, 3, 4]]
>>> list(G.connected_subgraph_iterator(k=Integer(2), vertices_only=True))
[[1], [1, 2], [2], [2, 3], [2, 4], [3], [3, 4], [4]]

>>> G = DiGraph([(Integer(1), Integer(2)), (Integer(2), Integer(1))])
>>> list(G.connected_subgraph_iterator())
[Subgraph of (): Digraph on 1 vertex,
 Subgraph of (): Digraph on 2 vertices,
 Subgraph of (): Digraph on 1 vertex]
>>> list(G.connected_subgraph_iterator(vertices_only=True))
[[1], [1, 2], [2]]

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

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

contract_edge(u, v=None, label=None)[source]#

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

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

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(4))
>>> G.contract_edge((Integer(0), Integer(1))); G.edges(sort=True)
[(0, 2, None), (0, 3, None), (2, 3, None)]
>>> G = graphs.CompleteGraph(Integer(4))
>>> G.allow_loops(True); G.allow_multiple_edges(True)
>>> G.contract_edge((Integer(0), Integer(1))); G.edges(sort=True)
[(0, 2, None), (0, 2, None), (0, 3, None), (0, 3, None), (2, 3, None)]
>>> G.contract_edge((Integer(0), Integer(2))); G.edges(sort=True)
[(0, 0, None), (0, 3, None), (0, 3, None), (0, 3, None)]

Sage

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

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(4)).to_directed()
>>> G.allow_loops(True)
>>> G.contract_edge(Integer(0), Integer(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)[source]#

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

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

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(4))
>>> G.allow_loops(True); G.allow_multiple_edges(True)
>>> G.contract_edges([(Integer(0), Integer(1)), (Integer(1), Integer(2)), (Integer(0), Integer(2))]); G.edges(sort=True)
[(0, 3, None), (0, 3, None), (0, 3, None)]
>>> G.contract_edges([(Integer(1), Integer(3)), (Integer(2), Integer(3))]); G.edges(sort=True)
[(0, 3, None), (0, 3, None), (0, 3, None)]
>>> G = graphs.CompleteGraph(Integer(4))
>>> G.allow_loops(True); G.allow_multiple_edges(True)
>>> G.contract_edges([(Integer(0), Integer(1)), (Integer(1), Integer(2)), (Integer(0), Integer(2)), (Integer(1), Integer(3)), (Integer(2), Integer(3))]); G.edges(sort=True)
[(0, 0, None)]

Sage

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

Python

>>> from sage.all import *
>>> D = digraphs.Complete(Integer(4))
>>> D.allow_loops(True); D.allow_multiple_edges(True)
>>> D.contract_edges([(Integer(0), Integer(1)), (Integer(1), Integer(0)), (Integer(0), Integer(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)[source]#

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

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

Python

>>> from sage.all import *
>>> g = Graph({Integer(0): [Integer(0), Integer(1), Integer(1), Integer(2)]}, loops=True, multiedges=True, sparse=True)
>>> g == copy(g)
True
>>> g = DiGraph({Integer(0): [Integer(0), Integer(1), Integer(1), Integer(2)], Integer(1): [Integer(0), Integer(1)]}, loops=True, multiedges=True, sparse=True)
>>> g == copy(g)
True

Note that vertex associations are also kept:

Sage

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

Python

>>> from sage.all import *
>>> d = {Integer(0): graphs.DodecahedralGraph(), Integer(1): graphs.FlowerSnark(), Integer(2): graphs.MoebiusKantorGraph(), Integer(3): graphs.PetersenGraph()}
>>> T = graphs.TetrahedralGraph()
>>> T.set_vertices(d)
>>> T2 = copy(T)
>>> T2.get_vertex(Integer(0))
Dodecahedron: Graph on 20 vertices

Notice that the copy is at least as deep as the objects:

Sage

sage: T2.get_vertex(0) is T.get_vertex(0)
False

Python

>>> from sage.all import *
>>> T2.get_vertex(Integer(0)) is T.get_vertex(Integer(0))
False

Examples of the keywords in use:

Sage

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

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(9))
>>> H = G.copy()
>>> H == G; H is G
True
False
>>> G1 = G.copy(sparse=True)
>>> G1 == G
True
>>> G1 is G
False
>>> G2 = copy(G)
>>> G2 is G
False

Argument weighted affects the equality class:

Sage

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]

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(5))
>>> H1 = G.copy(weighted=False)
>>> H2 = G.copy(weighted=True)
>>> [G.weighted(), H1.weighted(), H2.weighted()]
[False, False, True]
>>> [G == H1, G == H2, H1 == H2]
[True, False, False]
>>> G.weighted(True)
>>> [G == H1, G == H2, H1 == H2]
[False, True, False]

crossing_number()[source]#

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

sage: P = graphs.PetersenGraph()
sage: P.crossing_number()
2

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> 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')[source]#

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

sage: g = graphs.PetersenGraph()
sage: g.cycle_basis()                                                       # needs networkx, random (changes in networkx 3.2)
[[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]]

Python

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> g.cycle_basis()                                                       # needs networkx, random (changes in networkx 3.2)
[[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

sage: g.cycle_basis(output='edge')                                          # needs networkx, random (changes in networkx 3.2)
[[(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)]]

Python

>>> from sage.all import *
>>> g.cycle_basis(output='edge')                                          # needs networkx, random (changes in networkx 3.2)
[[(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

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

Python

>>> from sage.all import *
>>> g = graphs.RandomGNP(Integer(30), RealNumber('.4'))                                          # needs networkx
>>> 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

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

Python

>>> from sage.all import *
>>> m = g.size()
>>> edge_space = VectorSpace(FiniteField(Integer(2)), m)                           # needs sage.modules sage.rings.finite_rings
>>> edge_vector = dict(zip(g.edges(labels=False, sort=False),             # needs sage.modules sage.rings.finite_rings
...                        edge_space.basis()))
>>> 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

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

Python

>>> from sage.all import *
>>> vertices_to_edges = lambda x: zip(x, x[Integer(1):] + [x[Integer(0)]])
>>> 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

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

Python

>>> from sage.all import *
>>> basis_as_vectors = [cycle_to_vector(_) for _ in basis]                # needs networkx sage.modules sage.rings.finite_rings
>>> 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

sage: G = Graph([(0, 2, 'a'), (0, 2, 'b'), (0, 1, 'c'), (1, 2, 'd')],
....:           multiedges=True)
sage: G.cycle_basis()
[[2, 0], [2, 0, 1]]
sage: G.cycle_basis(output='edge')
[[(0, 2, 'b'), (2, 0, 'a')], [(1, 2, 'd'), (2, 0, 'a'), (0, 1, 'c')]]
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()
[[4, 1], [3, 2], [4, 1, 2, 3], [6, 4, 5]]

Python

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(2), 'a'), (Integer(0), Integer(2), 'b'), (Integer(0), Integer(1), 'c'), (Integer(1), Integer(2), 'd')],
...           multiedges=True)
>>> G.cycle_basis()
[[2, 0], [2, 0, 1]]
>>> G.cycle_basis(output='edge')
[[(0, 2, 'b'), (2, 0, 'a')], [(1, 2, 'd'), (2, 0, 'a'), (0, 1, 'c')]]
>>> H = Graph([(Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(2), Integer(3)), (Integer(3), Integer(4)), (Integer(1), Integer(4)),
...            (Integer(1), Integer(4)), (Integer(4), Integer(5)), (Integer(5), Integer(6)), (Integer(4), Integer(6)), (Integer(6), Integer(7))], multiedges=True)
>>> H.cycle_basis()
[[4, 1], [3, 2], [4, 1, 2, 3], [6, 4, 5]]

Disconnected graph:

Sage

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', 'Really ?', None),
  ('Really ?', 'Wuuhuu', None),
  ('Wuuhuu', 'Hey', None)],
 [(0, 2, 'a'), (2, 0, 'b')],
 [(0, 1, 'c'), (1, 2, 'd'), (2, 0, 'b')]]

Python

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

Graph that allows multiple edges but does not contain any:

Sage

sage: G = graphs.CycleGraph(3)
sage: G.allow_multiple_edges(True)
sage: G.cycle_basis()
[[2, 0, 1]]

Python

>>> from sage.all import *
>>> G = graphs.CycleGraph(Integer(3))
>>> G.allow_multiple_edges(True)
>>> G.cycle_basis()
[[2, 0, 1]]

Not yet implemented for directed graphs:

Sage

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

Python

>>> from sage.all import *
>>> G = DiGraph([(Integer(0), Integer(2), 'a'), (Integer(0), Integer(1), 'c'), (Integer(1), Integer(2), 'd')])
>>> G.cycle_basis()
Traceback (most recent call last):
...
NotImplementedError: not implemented for directed graphs

degree(vertices=None, labels=False)[source]#

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

sage: P = graphs.PetersenGraph()
sage: P.degree(5)
3

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> P.degree(Integer(5))
3

Sage

sage: K = graphs.CompleteGraph(9)
sage: K.degree()
[8, 8, 8, 8, 8, 8, 8, 8, 8]

Python

>>> from sage.all import *
>>> K = graphs.CompleteGraph(Integer(9))
>>> K.degree()
[8, 8, 8, 8, 8, 8, 8, 8, 8]

Sage

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]

Python

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(0), Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0),Integer(5)], Integer(5): [Integer(1)]})
>>> D.degree(vertices=[Integer(0), Integer(1), Integer(2)], labels=True)
{0: 5, 1: 4, 2: 3}
>>> 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

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]

Python

>>> from sage.all import *
>>> # needs sage.combinat
>>> D = digraphs.DeBruijn(Integer(4), Integer(2))
>>> D.delete_vertex('20')
>>> print(D.degree())
[7, 7, 6, 7, 8, 8, 7, 8, 8, 7, 8, 8, 8, 7, 8]
>>> print(D.degree(vertices=list(D)))
[7, 7, 6, 7, 8, 8, 7, 8, 8, 7, 8, 8, 8, 7, 8]
>>> 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()[source]#

Return a list, whose \(i\)-th entry is the frequency of degree \(i\).

EXAMPLES:

Sage

sage: G = graphs.Grid2dGraph(9, 12)
sage: G.degree_histogram()
[0, 0, 4, 34, 70]

Python

>>> from sage.all import *
>>> G = graphs.Grid2dGraph(Integer(9), Integer(12))
>>> G.degree_histogram()
[0, 0, 4, 34, 70]

Sage

sage: G = graphs.Grid2dGraph(9, 12).to_directed()
sage: G.degree_histogram()
[0, 0, 0, 0, 4, 0, 34, 0, 70]

Python

>>> from sage.all import *
>>> G = graphs.Grid2dGraph(Integer(9), Integer(12)).to_directed()
>>> G.degree_histogram()
[0, 0, 0, 0, 4, 0, 34, 0, 70]

degree_iterator(vertices=None, labels=False)[source]#

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

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)

Python

>>> from sage.all import *
>>> G = graphs.Grid2dGraph(Integer(3), Integer(4))
>>> for i in G.degree_iterator():
...     print(i)
2
3
3
...
3
2
>>> 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

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)

Python

>>> from sage.all import *
>>> D = graphs.Grid2dGraph(Integer(2),Integer(4)).to_directed()
>>> for i in D.degree_iterator():
...     print(i)
4
6
...
6
4
>>> 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

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]

Python

>>> from sage.all import *
>>> V = list(D)
>>> D = digraphs.DeBruijn(Integer(4), Integer(2))                                           # needs sage.combinat
>>> D.delete_vertex('20')                                                 # needs sage.combinat
>>> print(list(D.degree_iterator()))                                      # needs sage.combinat
[7, 7, 6, 7, 8, 8, 7, 8, 8, 7, 8, 8, 8, 7, 8]
>>> 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()[source]#

Return the degree sequence of this (di)graph.

EXAMPLES:

The degree sequence of an undirected graph:

Sage

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]

Python

>>> from sage.all import *
>>> g = Graph({Integer(1): [Integer(2), Integer(5)], Integer(2): [Integer(1), Integer(5), Integer(3), Integer(4)], Integer(3): [Integer(2), Integer(5)], Integer(4): [Integer(3)], Integer(5): [Integer(2), Integer(3)]})
>>> g.degree_sequence()
[4, 3, 3, 2, 2]

The degree sequence of a digraph:

Sage

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]

Python

>>> from sage.all import *
>>> g = DiGraph({Integer(1): [Integer(2), Integer(5), Integer(6)], Integer(2): [Integer(3), Integer(6)], Integer(3): [Integer(4), Integer(6)], Integer(4): [Integer(6)], Integer(5): [Integer(4), Integer(6)]})
>>> g.degree_sequence()
[5, 3, 3, 3, 3, 3]

Degree sequences of some common graphs:

Sage

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]

Python

>>> from sage.all import *
>>> graphs.PetersenGraph().degree_sequence()
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
>>> graphs.HouseGraph().degree_sequence()
[3, 3, 2, 2, 2]
>>> 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)[source]#

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

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

Python

>>> from sage.all import *
>>> G = graphs.CubeGraph(Integer(3))
>>> cell = G.vertices(sort=True)[:Integer(3)]
>>> G.degree_to_cell('011', cell)
2
>>> G.degree_to_cell('111', cell)
0

Sage

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)

Python

>>> from sage.all import *
>>> D = DiGraph({ Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(3),Integer(4)], Integer(3):[Integer(4),Integer(5)]})
>>> cell = [Integer(0),Integer(1),Integer(2