8.1.5 Visualization

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

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

Or you can view it in three dimensions via jmol with show3d().

sage: G.show3d()

Module-level Functions

graph_isom_equivalent_non_edge_labeled_graph( g, partition)

Helper function for canonical labeling of edge labeled (di)graphs.

Translates to a bipartite incidence-structure type graph appropriate for computing canonical labels of edge labeled graphs. Note that this is actually computationally equivalent to implementing a change on an inner loop of the main algorithm- namely making the refinement procedure sort for each label.

If the graph is a multigraph, it is translated to a non-multigraph, where each edge is labeled with a dictionary describing how many edges of each label were originally there. Then in either case we are working on a graph without multiple edges. At this point, we create another (bipartite) graph, whose left vertices are the original vertices of the graph, and whose right vertices represent the edges. We partition the left vertices as they were originally, and the right vertices by common labels: only automorphisms taking edges to like-labeled edges are allowed, and this additional partition information enforces this on the bipartite graph.

sage: G = Graph(multiedges=True, implementation='networkx')
sage: G.add_edges([(0,1,i) for i in range(10)])
sage: G.add_edge(1,2,'string')
sage: G.add_edge(2,3)
sage: from sage.graphs.graph import graph_isom_equivalent_non_edge_labeled_graph
sage: graph_isom_equivalent_non_edge_labeled_graph(G, [G.vertices()])
(Graph on 7 vertices,
 [[('o', 0), ('o', 1), ('o', 2), ('o', 3)], [('x', 0)], [('x', 1)], [('x',
2)]])

graph_isom_equivalent_non_multi_graph( g, partition)

Helper function for canonical labeling of multi-(di)graphs.

The idea for this function is that the main algorithm for computing isomorphism of graphs does not allow multiple edges. Instead of making some very difficult changes to that, we can simply modify the multigraph into a non-multi graph that carries essentially the same information. For each pair of vertices $\{u,v\}$ , if there is at most one edge between and , we do nothing, but if there are more than one, we split each edge into two, introducing a new vertex. These vertices really represent edges, so we keep them in their own part of a partition - to distinguish them from genuine vertices. Then the canonical label and automorphism group is computed, and in the end, we strip off the parts of the generators that describe how these new vertices move, and we have the automorphism group of the original multi-graph. Similarly, by putting the additional vertices in their own cell of the partition, we guarantee that the relabeling leading to a canonical label moves genuine vertices amongst themselves, and hence the canonical label is still well-defined, when we forget about the additional vertices.

sage: from sage.graphs.graph import graph_isom_equivalent_non_multi_graph
sage: G = Graph(multiedges=True)
sage: G.add_edge((0,1,1))
sage: G.add_edge((0,1,2))
sage: G.add_edge((0,1,3))
sage: graph_isom_equivalent_non_multi_graph(G, [[0,1]])
(Graph on 5 vertices, [[('o', 0), ('o', 1)], [('x', 0), ('x', 1), ('x',
2)]])

tachyon_vertex_plot( g, [bgcolor=(1, 1, 1)], [vertex_colors=None], [vertex_size=0.06], [pos3d=None], [iterations=50])

Class: DiGraph

class DiGraph

Directed graph.

Input:

data: - can be any of the following: 1. A NetworkX digraph 2. A dictionary of dictionaries 3. A dictionary of lists 4. A numpy matrix or ndarray 5. A Sage adjacency matrix or incidence matrix 6. pygraphviz agraph 7. scipy sparse matrix

pos - a positioning dictionary: for example, the spring layout from NetworkX for the 5-cycle is 0: [-0.91679746, 0.88169588], 1: [ 0.47294849, 1.125 ], 2: [ 1.125 ,-0.12867615], 3: [ 0.12743933,-1.125 ], 4: [-1.125 ,-0.50118505] name - (must be an explicitly named parameter, i.e., name="complete") gives the graph a name loops - boolean, whether to allow loops (ignored if data is an instance of the DiGraph class) multiedges - boolean, whether to allow multiple edges (ignored if data is an instance of the DiGraph class) weighted - whether digraph thinks of itself as weighted or not. See self.weighted() format - if None, DiGraph tries to guess- can be several values, including: 'adjacency_matrix' - a square Sage matrix M, with M[i,j] equal to the number of edges {i,j} 'incidence_matrix' - a Sage matrix, with one column C for each edge, where if C represents {i, j}, C[i] is -1 and C[j] is 1 'weighted_adjacency_matrix' - a square Sage matrix M, with M[i,j] equal to the weight of the single edge {i,j}. Given this format, weighted is ignored (assumed True). boundary - a list of boundary vertices, if none, digraph is considered as a 'digraph without boundary' implementation - what to use as a backend for the graph. Currently, the options are either 'networkx' or 'c_graph' sparse - only for implementation == 'c_graph'. Whether to use sparse or dense graphs as backend. Note that currently dense graphs do not have edge labels, nor can they be multigraphs vertex_labels - only for implementation == 'c_graph'. Whether to allow any object as a vertex (slower), or only the integers 0, ..., n-1, where n is the number of vertices.

1. A NetworkX XDiGraph:

sage: import networkx
sage: g = networkx.XDiGraph({0:[1,2,3], 2:[4]})
sage: DiGraph(g)
Digraph on 5 vertices

In this single case, we do not make a copy of g, but just wrap the actual NetworkX passed. We do this for performance reasons.

sage: import networkx
sage: g = networkx.XDiGraph({0:[1,2,3], 2:[4]})
sage: G = DiGraph(g, implementation='networkx')
sage: H = DiGraph(g, implementation='networkx')
sage: G._backend._nxg is H._backend._nxg
True

2. A NetworkX digraph:

sage: import networkx
sage: g = networkx.DiGraph({0:[1,2,3], 2:[4]})
sage: DiGraph(g)
Digraph on 5 vertices

Note that in this case, we copy the networkX structure.

sage: import networkx
sage: g = networkx.DiGraph({0:[1,2,3], 2:[4]})
sage: G = DiGraph(g, implementation='networkx')
sage: H = DiGraph(g, implementation='networkx')
sage: G._backend._nxg is H._backend._nxg
False

3. A dictionary of dictionaries:

sage: g = DiGraph({0:{1:'x',2:'z',3:'a'}, 2:{5:'out'}}, implementation='networkx'); g
Digraph on 5 vertices

The labels ('x', 'z', 'a', 'out') are labels for edges. For example, 'out' is the label for the edge from 2 to 5. Labels can be used as weights, if all the labels share some common parent.

4. A dictionary of lists:

sage: g = DiGraph({0:[1,2,3], 2:[4]}); g
Digraph on 5 vertices

5. A list of vertices and a function describing adjacencies. Note that the list of vertices and the function must be enclosed in a list (i.e., [list of vertices, function]).

We construct a graph on the integers 1 through 12 such that there is a directed edge from i to j if and only if i divides j.

sage: g=DiGraph([[1..12],lambda i,j: i!=j and i.divides(j)], implementation='networkx')
sage: g.vertices()
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
sage: g.adjacency_matrix()
[0 1 1 1 1 1 1 1 1 1 1 1]
[0 0 0 1 0 1 0 1 0 1 0 1]
[0 0 0 0 0 1 0 0 1 0 0 1]
[0 0 0 0 0 0 0 1 0 0 0 1]
[0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]

6. A numpy matrix or ndarray:

sage: import numpy
sage: A = numpy.array([[0,1,0],[1,0,0],[1,1,0]])
sage: DiGraph(A, implementation='networkx')
Digraph on 3 vertices

7. A Sage matrix: Note: If format is not specified, then Sage assumes a square matrix is an adjacency matrix, and a nonsquare matrix is an incidence matrix.

A. an adjacency matrix:

sage: M = Matrix([[0, 1, 1, 1, 0],[0, 0, 0, 0, 0],[0, 0, 0, 0, 1],[0, 0, 0, 0, 0],[0, 0, 0, 0, 0]]); M
[0 1 1 1 0]
[0 0 0 0 0]
[0 0 0 0 1]
[0 0 0 0 0]
[0 0 0 0 0]
sage: DiGraph(M)
Digraph on 5 vertices

B. an incidence matrix:

sage: M = Matrix(6, [-1,0,0,0,1, 1,-1,0,0,0, 0,1,-1,0,0, 0,0,1,-1,0, 0,0,0,1,-1, 0,0,0,0,0]); M
[-1  0  0  0  1]
[ 1 -1  0  0  0]
[ 0  1 -1  0  0]
[ 0  0  1 -1  0]
[ 0  0  0  1 -1]
[ 0  0  0  0  0]
sage: DiGraph(M)
Digraph on 6 vertices

8. A c_graph implemented DiGraph can be constructed from a networkx implemented DiGraph if its vertex set is equal to range(n):

sage: D = DiGraph({0:[1],1:[2],2:[0]}, implementation="networkx")
sage: E = DiGraph(D,implementation="c_graph")
sage: D == E
True

DiGraph( self, [data=None], [pos=None], [loops=False], [format=None], [boundary=[]], [weighted=False], [implementation=networkx], [sparse=True], [vertex_labels=True])

Functions: dig6_string, $\,$ graphviz_string, $\,$ in_degree, $\,$ in_degree_iterator, $\,$ incoming_edge_iterator, $\,$ incoming_edges, $\,$ is_directed, $\,$ is_directed_acyclic, $\,$ out_degree, $\,$ out_degree_iterator, $\,$ outgoing_edge_iterator, $\,$ outgoing_edges, $\,$ predecessor_iterator, $\,$ predecessors, $\,$ reverse, $\,$ successor_iterator, $\,$ successors, $\,$ to_directed, $\,$ to_undirected, $\,$ topological_sort, $\,$ topological_sort_generator

dig6_string( self)

Returns the dig6 representation of the digraph as an ASCII string. Valid for single (no multiple edges) digraphs on 0 to 262143 vertices.

TODO

graphviz_string( self)

Returns a representation in the DOT language, ready to render in graphviz.

REFERENCES: http://www.graphviz.org/doc/info/lang.html

sage: G = DiGraph({0:{1:None,2:None}, 1:{2:None}, 2:{3:'foo'}, 3:{}}, implementation='networkx')
sage: s = G.graphviz_string(); s 
'digraph {\n"0";"1";"2";"3";\n"0"->"1";"0"->"2";"1"->"2";"2"->"3"[label="fo
o"];\n}'

in_degree( self, [vertices=None], [labels=False])

Same as degree, but for in degree.

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: D.in_degree(vertices = [0,1,2], labels=True)
{0: 2, 1: 2, 2: 2}
sage: D.in_degree()
[2, 2, 2, 2, 1, 1]
sage: G = graphs.PetersenGraph().to_directed()
sage: G.in_degree(0)
3

in_degree_iterator( self, [vertices=None], [labels=False])

Same as degree_iterator, but for in degree.

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

incoming_edge_iterator( self, [vertices=None], [labels=True])

Return an iterator over all arriving edges from vertices, or over all edges if vertices is None.

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: for a in D.incoming_edge_iterator([0]):
...    print a
(1, 0, None)
(4, 0, None)

incoming_edges( self, [vertices=None], [labels=True])

Returns a list of edges arriving at vertices.

Input:

labels: - if False, each edge is a tuple (u,v) of vertices.

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: D.incoming_edges([0])
[(1, 0, None), (4, 0, None)]

is_directed( self): Since digraph is directed, returns True.

is_directed_acyclic( self)

Returns whether the digraph is acyclic or not.

A directed graph is acyclic if for any vertex v, there is no directed path that starts and ends at v. Every directed acyclic graph (dag) corresponds to a partial ordering of its vertices, however multiple dags may lead to the same partial ordering.

sage: D = DiGraph({ 0:[1,2,3], 4:[2,5], 1:[8], 2:[7], 3:[7], 5:[6,7], 7:[8], 6:[9], 8:[10], 9:[10] })
sage: D.plot(layout='circular').show()
sage: D.is_directed_acyclic()
True

sage: D.add_edge(9,7)
sage: D.is_directed_acyclic()
True

sage: D.add_edge(7,4)
sage: D.is_directed_acyclic()
False

out_degree( self, [vertices=None], [labels=False])

Same as degree, but for out degree.

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: D.out_degree(vertices = [0,1,2], labels=True)
{0: 3, 1: 2, 2: 1}
sage: D.out_degree()
[3, 2, 1, 1, 2, 1]

out_degree_iterator( self, [vertices=None], [labels=False])

Same as degree_iterator, but for out degree.

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

outgoing_edge_iterator( self, [vertices=None], [labels=True])

Return an iterator over all departing edges from vertices, or over all edges if vertices is None.

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: for a in D.outgoing_edge_iterator([0]):
...    print a
(0, 1, None)
(0, 2, None)
(0, 3, None)

outgoing_edges( self, [vertices=None], [labels=True])

Returns a list of edges departing from vertices.

Input:

labels: - if False, each edge is a tuple (u,v) of vertices.

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: D.outgoing_edges([0])
[(0, 1, None), (0, 2, None), (0, 3, None)]

predecessor_iterator( self, vertex)

Returns an iterator over predecessor vertices of vertex.

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: for a in D.predecessor_iterator(0):
...    print a
1
4

predecessors( self, vertex)

Returns a list of predecessor vertices of vertex.

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: D.predecessors(0)
[1, 4]

reverse( self)

Returns a copy of digraph with edges reversed in direction.

sage: D = DiGraph({ 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] })
sage: D.reverse()
Reverse of (): Digraph on 6 vertices

successor_iterator( self, vertex)

Returns an iterator over successor vertices of vertex.

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: for a in D.successor_iterator(0):
...    print a
1
2
3

successors( self, vertex)

Returns a list of successor vertices of vertex.

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: D.successors(0)
[1, 2, 3]

to_directed( self)

Since the graph is already directed, simply returns a copy of itself.

sage: DiGraph({0:[1,2,3],4:[5,1]}).to_directed()
Digraph on 6 vertices

to_undirected( self, [implementation=networkx])

Returns an undirected version of the graph. Every directed edge becomes an edge.

sage: D = DiGraph({0:[1,2],1:[0]})
sage: G = D.to_undirected()
sage: D.edges(labels=False)
[(0, 1), (0, 2), (1, 0)]
sage: G.edges(labels=False)
[(0, 1), (0, 2)]

topological_sort( self)

Returns a topological sort of the digraph if it is acyclic, and raises a TypeError if the digraph contains a directed cycle.

A topological sort is an ordering of the vertices of the digraph such that each vertex comes before all of its successors. That is, if u comes before v in the sort, then there may be a directed path from u to v, but there will be no directed path from v to u.

sage: D = DiGraph({ 0:[1,2,3], 4:[2,5], 1:[8], 2:[7], 3:[7], 5:[6,7], 7:[8], 6:[9], 8:[10], 9:[10] })
sage: D.plot(layout='circular').show()
sage: D.topological_sort()
[4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10]

sage: D.add_edge(9,7)
sage: D.topological_sort()
[4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10]

sage: D.add_edge(7,4)
sage: D.topological_sort()
Traceback (most recent call last):
...
TypeError: Digraph is not acyclic-- there is no topological sort.

NOTE: There is a recursive version of this in NetworkX, but it has problems:

sage: import networkx
sage: D = DiGraph({ 0:[1,2,3], 4:[2,5], 1:[8], 2:[7], 3:[7], 5:[6,7], 7:[8], 6:[9], 8:[10], 9:[10] })
sage: N = D.networkx_graph()
sage: networkx.topological_sort(N)
[4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10]
sage: networkx.topological_sort_recursive(N) is None
True

topological_sort_generator( self)

Returns a list of all topological sorts of the digraph if it is acyclic, and raises a TypeError if the digraph contains a directed cycle.

Author Log:

Michael W. Hansen
original implementation Robert L. Miller
wrapping, documentation

REFERENCE: [1] Pruesse, Gara and Ruskey, Frank. Generating Linear Extensions Fast. SIAM J. Comput., Vol. 23 (1994), no. 2, pp. 373-386.

sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] })
sage: D.plot(layout='circular').show()
sage: D.topological_sort_generator()
[[0, 1, 2, 3, 4], [0, 1, 2, 4, 3], [0, 2, 1, 3, 4], [0, 2, 1, 4, 3], [0, 2,
4, 1, 3]]

sage: for sort in D.topological_sort_generator():
...       for edge in D.edge_iterator():
...           u,v,l = edge
...           if sort.index(u) > sort.index(v):
...               print "This should never happen."

Special Functions: __init__

Class: GenericGraph

class GenericGraph: Base class for graphs and digraphs.

Functions: add_cycle, $\,$ add_edge, $\,$ add_edges, $\,$ add_path, $\,$ add_vertex, $\,$ add_vertices, $\,$ adjacency_matrix, $\,$ all_paths, $\,$ am, $\,$ antisymmetric, $\,$ automorphism_group, $\,$ blocks_and_cut_vertices, $\,$ breadth_first_search, $\,$ canonical_label, $\,$ cartesian_product, $\,$ categorical_product, $\,$ center, $\,$ characteristic_polynomial, $\,$ check_embedding_validity, $\,$ clear, $\,$ cluster_transitivity, $\,$ cluster_triangles, $\,$ clustering_average, $\,$ clustering_coeff, $\,$ coarsest_equitable_refinement, $\,$ complement, $\,$ connected_component_containing_vertex, $\,$ connected_components, $\,$ connected_components_number, $\,$ connected_components_subgraphs, $\,$ copy, $\,$ cores, $\,$ degree, $\,$ degree_histogram, $\,$ degree_iterator, $\,$ degree_to_cell, $\,$ delete_edge, $\,$ delete_edges, $\,$ delete_multiedge, $\,$ delete_vertex, $\,$ delete_vertices, $\,$ density, $\,$ depth_first_search, $\,$ diameter, $\,$ disjoint_union, $\,$ disjunctive_product, $\,$ distance, $\,$ eccentricity, $\,$ edge_boundary, $\,$ edge_iterator, $\,$ edge_label, $\,$ edge_labels, $\,$ edges, $\,$ edges_incident, $\,$ eigenspaces, $\,$ genus, $\,$ get_boundary, $\,$ get_embedding, $\,$ get_pos, $\,$ get_vertex, $\,$ get_vertices, $\,$ girth, $\,$ graphviz_string, $\,$ graphviz_to_file_named, $\,$ has_edge, $\,$ has_vertex, $\,$ incidence_matrix, $\,$ interior_paths, $\,$ is_circular_planar, $\,$ is_clique, $\,$ is_connected, $\,$ is_drawn_free_of_edge_crossings, $\,$ is_equitable, $\,$ is_eulerian, $\,$ is_forest, $\,$ is_independent_set, $\,$ is_isomorphic, $\,$ is_planar, $\,$ is_subgraph, $\,$ is_tree, $\,$ is_vertex_transitive, $\,$ kirchhoff_matrix, $\,$ laplacian_matrix, $\,$ lexicographic_product, $\,$ line_graph, $\,$ loop_edges, $\,$ loop_vertices, $\,$ loops, $\,$ multiple_edges, $\,$ name, $\,$ neighbor_iterator, $\,$ neighbors, $\,$ networkx_graph, $\,$ num_edges, $\,$ num_verts, $\,$ number_of_loops, $\,$ order, $\,$ periphery, $\,$ plot, $\,$ plot3d, $\,$ radius, $\,$ random_subgraph, $\,$ relabel, $\,$ remove_loops, $\,$ remove_multiple_edges, $\,$ set_boundary, $\,$ set_edge_label, $\,$ set_embedding, $\,$ set_planar_positions, $\,$ set_pos, $\,$ set_vertex, $\,$ set_vertices, $\,$ shortest_path, $\,$ shortest_path_all_pairs, $\,$ shortest_path_length, $\,$ shortest_path_lengths, $\,$ shortest_paths, $\,$ show, $\,$ show3d, $\,$ size, $\,$ spectrum, $\,$ strong_product, $\,$ subgraph, $\,$ tensor_product, $\,$ to_simple, $\,$ trace_faces, $\,$ transitive_closure, $\,$ transitive_reduction, $\,$ union, $\,$ vertex_boundary, $\,$ vertex_iterator, $\,$ vertices, $\,$ weighted, $\,$ weighted_adjacency_matrix

add_cycle( self, vertices)

Adds a cycle to the graph with the given vertices. If the vertices are already present, only the edges are added.

For digraphs, adds the directed cycle, whose orientation is determined by the list. Adds edges (vertices[u], vertices[u+1]) and (vertices[-1], vertices[0]).

Input:

vertices: - a list of indices for the vertices of the cycle to be added.

sage: G = Graph(implementation='networkx')
sage: G.add_vertices(range(10)); G
Graph on 10 vertices
sage: show(G)
sage: G.add_cycle(range(20)[10:20])
sage: show(G)
sage: G.add_cycle(range(10))
sage: show(G)

sage: D = DiGraph(implementation='networkx')
sage: D.add_cycle(range(4))
sage: D.edges()
[(0, 1, None), (1, 2, None), (2, 3, None), (3, 0, None)]

add_edge( self, u, [v=None], [label=None])

Adds an edge from u and v.

Input: The following forms are all accepted:

G.add_edge( 1, 2 ) G.add_edge( (1, 2) ) G.add_edges( [ (1, 2) ] ) G.add_edge( 1, 2, 'label' ) G.add_edge( (1, 2, 'label') ) G.add_edges( [ (1, 2, 'label') ] )

WARNING: The following intuitive input results in nonintuitive output:

sage: G = Graph(implementation='networkx')
sage: G.add_edge((1,2), 'label')
sage: G.networkx_graph().adj           # random output order
{'label': {(1, 2): None}, (1, 2): {'label': None}}

Use one of these instead:

sage: G = Graph(implementation='networkx')
sage: G.add_edge((1,2), label="label")
sage: G.networkx_graph().adj           # random output order
{1: {2: 'label'}, 2: {1: 'label'}}

sage: G = Graph(implementation='networkx')
sage: G.add_edge(1,2,'label')
sage: G.networkx_graph().adj           # random output order
{1: {2: 'label'}, 2: {1: 'label'}}

add_edges( self, edges)

Add edges from an iterable container.

sage: G = graphs.DodecahedralGraph()
sage: H = Graph(implementation='networkx')
sage: H.add_edges( G.edge_iterator() ); H
Graph on 20 vertices
sage: G = graphs.DodecahedralGraph().to_directed()
sage: H = DiGraph(implementation='networkx')
sage: H.add_edges( G.edge_iterator() ); H
Digraph on 20 vertices

add_path( self, vertices)

Adds 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 path vertices[0], ..., vertices[-1].

Input:

vertices: - a list of indices for the vertices of the cycle to be added.

sage: G = Graph(implementation='networkx')
sage: G.add_vertices(range(10)); G
Graph on 10 vertices
sage: show(G)
sage: G.add_path(range(20)[10:20])
sage: show(G)
sage: G.add_path(range(10))
sage: show(G)

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

add_vertex( self, [name=None])

Creates an isolated vertex. If the vertex already exists, then nothing is done.

Input:

n: - Name of the new vertex. If no name is specified, then the vertex will be represented by the least integer not already representing a vertex. Name must be an immutable object.

As it is implemented now, if a graph has a large number of vertices with numeric labels, then G.add_vertex() could potentially be slow.

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

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

add_vertices( self, vertices)

Add vertices to the (di)graph from an iterable container of vertices. Vertices that already exist in the graph will not be added again.

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, sparse=True)
sage: G.add_vertices([10,11,12])
sage: G.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
sage: G.add_vertices(graphs.CycleGraph(25).vertices())
sage: G.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24]

adjacency_matrix( self, [sparse=None], [boundary_first=False])

Returns the adjacency matrix of the (di)graph. Each vertex is represented by its position in the list returned by the vertices() function.

The matrix returned is over the integers. If a different ring is desired, use either the change_ring function or the matrix function.

Input:

sparse: - whether to represent with a sparse matrix
boundary_first: - whether to represent the boundary vertices in the upper left block

sage: G = graphs.CubeGraph(4)
sage: G.adjacency_matrix()
[0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0]
[1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0]
[1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0]
[0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0]
[1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0]
[0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0]
[0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0]
[0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1]
[1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0]
[0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0]
[0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0]
[0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1]
[0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0]
[0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1]
[0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1]
[0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]

sage: matrix(GF(2),G) # matrix over GF(2)
[0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0]
[1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0]
[1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0]
[0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0]
[1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0]
[0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0]
[0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0]
[0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1]
[1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0]
[0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0]
[0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0]
[0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1]
[0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0]
[0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1]
[0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1]
[0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: D.adjacency_matrix()
[0 1 1 1 0 0]
[1 0 1 0 0 0]
[0 0 0 1 0 0]
[0 0 0 0 1 0]
[1 0 0 0 0 1]
[0 1 0 0 0 0]

TESTS:

sage: graphs.CubeGraph(8).adjacency_matrix().parent()
Full MatrixSpace of 256 by 256 dense matrices over Integer Ring
sage: graphs.CubeGraph(9).adjacency_matrix().parent()
Full MatrixSpace of 512 by 512 sparse matrices over Integer Ring

all_paths( self, start, end)

Returns a list of all paths (also lists) between a pair of vertices (start, end) in the (di)graph.

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

am( self, [sparse=None], [boundary_first=False])

Returns the adjacency matrix of the (di)graph. Each vertex is represented by its position in the list returned by the vertices() function.

The matrix returned is over the integers. If a different ring is desired, use either the change_ring function or the matrix function.

Input:

sparse: - whether to represent with a sparse matrix
boundary_first: - whether to represent the boundary vertices in the upper left block

sage: G = graphs.CubeGraph(4)
sage: G.adjacency_matrix()
[0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0]
[1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0]
[1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0]
[0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0]
[1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0]
[0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0]
[0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0]
[0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1]
[1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0]
[0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0]
[0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0]
[0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1]
[0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0]
[0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1]
[0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1]
[0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]

sage: matrix(GF(2),G) # matrix over GF(2)
[0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0]
[1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0]
[1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0]
[0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0]
[1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0]
[0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0]
[0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0]
[0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1]
[1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0]
[0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0]
[0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0]
[0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1]
[0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0]
[0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1]
[0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1]
[0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: D.adjacency_matrix()
[0 1 1 1 0 0]
[1 0 1 0 0 0]
[0 0 0 1 0 0]
[0 0 0 0 1 0]
[1 0 0 0 0 1]
[0 1 0 0 0 0]

TESTS:

sage: graphs.CubeGraph(8).adjacency_matrix().parent()
Full MatrixSpace of 256 by 256 dense matrices over Integer Ring
sage: graphs.CubeGraph(9).adjacency_matrix().parent()
Full MatrixSpace of 512 by 512 sparse matrices over Integer Ring

antisymmetric( self)

Returns True if the relation given by the graph is antisymmetric and False otherwise.

A graph represents an antisymmetric relation if there being a path from a vertex x to a vertex y implies that there is not a path from y to x unless x=y.

A directed acyclic graph is antisymmetric. An undirected graph is never antisymmetric unless it is just a union of isolated vertices.

sage: graphs.RandomGNP(20,0.5).antisymmetric()
False
sage: digraphs.RandomDirectedGNR(20,0.5).antisymmetric()
True

automorphism_group( self, [partition=None], [translation=False], [verbosity=0], [edge_labels=False], [order=False], [return_group=True], [orbits=False])

Returns the largest subgroup of the automorphism group of the (di)graph whose orbit partition is finer than the partition given. If no partition is given, the unit partition is used and the entire automorphism group is given.

Input:

translation: - if True, then output includes a a dictionary translating from keys == vertices to entries == elements of 1,2,...,n (since permutation groups can currently only act on positive integers).
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

Output: The order of the output is group, translation, order, orbits. However, there are options to turn each of these on or off.

Graphs:

sage: graphs_query = GraphDatabase()
sage: L = graphs_query.get_list(num_vertices=4)
sage: graphs_list.show_graphs(L)
sage: for g in L:
...    G = g.automorphism_group()
...    G.order(), G.gens()
(24, ((2,3), (1,2), (1,4)))
(4, ((2,3), (1,4)))
(2, ((1,2),))
(8, ((1,2), (1,4)(2,3)))
(6, ((1,2), (1,4)))
(6, ((2,3), (1,2)))
(2, ((1,4)(2,3),))
(2, ((1,2),))
(8, ((2,3), (1,4), (1,3)(2,4)))
(4, ((2,3), (1,4)))
(24, ((2,3), (1,2), (1,4)))

sage: C = graphs.CubeGraph(4)
sage: G = C.automorphism_group()
sage: M = G.character_table()
sage: M.determinant()
-712483534798848
sage: G.order()
384

sage: D = graphs.DodecahedralGraph()
sage: G = D.automorphism_group()
sage: A5 = AlternatingGroup(5)
sage: Z2 = CyclicPermutationGroup(2)
sage: H = A5.direct_product(Z2)[0] #see documentation for direct_product to explain the [0]
sage: G.is_isomorphic(H)
True

Multigraphs:

sage: G = Graph(multiedges=True, implementation='networkx')
sage: G.add_edge(('a', 'b'))
sage: G.add_edge(('a', 'b'))
sage: G.add_edge(('a', 'b'))
sage: G.automorphism_group()
Permutation Group with generators [(1,2)]

Digraphs:

sage: D = DiGraph( { 0:[1], 1:[2], 2:[3], 3:[4], 4:[0] } )
sage: D.automorphism_group()
Permutation Group with generators [(1,2,3,4,5)]

Edge labeled graphs:

sage: G = Graph(implementation='networkx')
sage: G.add_edges( [(0,1,'a'),(1,2,'b'),(2,3,'c'),(3,4,'b'),(4,0,'a')] )
sage: G.automorphism_group(edge_labels=True)
Permutation Group with generators [(1,4)(2,3)]

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

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

Or, just the orbits (recall the Petersen graph is transitive!)

sage: G = graphs.PetersenGraph()
sage: G.automorphism_group(return_group=False, orbits=True)
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]

blocks_and_cut_vertices( self)

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

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.

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

ALGORITHM: 8.3.8 in [1]. Notice the typo - the stack must also be considered as one of the blocks at termination.

REFERENCE: [1] D. Jungnickel, Graphs, Networks and Algorithms, Springer, 2005.

breadth_first_search( self, u, [ignore_direction=False])

Returns an iterator over vertices in a breadth-first ordering.

Input:

u: - vertex at which to start search
ignore_direction: - (default False) only applies to directed graphs. If True, searches across edges in either direction.

sage: G = Graph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} } )
sage: list(G.breadth_first_search(0))
[0, 1, 4, 2, 3]
sage: list(G.depth_first_search(0))
[0, 4, 3, 2, 1]

sage: D = DiGraph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} } )
sage: list(D.breadth_first_search(0))
[0, 1, 2, 3, 4]
sage: list(D.depth_first_search(0))
[0, 1, 2, 3, 4]

sage: D = DiGraph({1:[0], 2:[0]})
sage: list(D.breadth_first_search(0))
[0]
sage: list(D.breadth_first_search(0, ignore_direction=True))
[0, 1, 2]

canonical_label( self, [partition=None], [certify=False], [verbosity=0], [edge_labels=False])

Returns the canonical label with respect to the partition. If no partition is given, uses the unit partition.

Input:

partition: - if given, the canonical label with respect to this partition will be computed. The default is the unit partition.
certify: - if True, a dictionary mapping from the (di)graph to its canonical label will be given.
verbosity: - gets passed to nice: prints helpful output.
edge_labels: - default False, otherwise allows only permutations respecting edge labels.

sage: D = graphs.DodecahedralGraph()
sage: E = D.canonical_label(); E
Dodecahedron: Graph on 20 vertices
sage: D.canonical_label(certify=True)
(Dodecahedron: Graph on 20 vertices, {0: 0, 1: 19, 2: 16, 3: 15, 4: 9, 5:
1, 6: 10, 7: 8, 8: 14, 9: 12, 10: 17, 11: 11, 12: 5, 13: 6, 14: 2, 15: 4,
16: 3, 17: 7, 18: 13, 19: 18})
sage: D.is_isomorphic(E)
True

Multigraphs:

sage: G = Graph(multiedges=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

Digraphs:

sage: P = graphs.PetersenGraph()
sage: DP = P.to_directed()
sage: DP.canonical_label().adjacency_matrix()
[0 0 0 0 0 0 0 1 1 1]
[0 0 0 0 1 0 1 0 0 1]
[0 0 0 1 0 0 1 0 1 0]
[0 0 1 0 0 1 0 0 0 1]
[0 1 0 0 0 1 0 0 1 0]
[0 0 0 1 1 0 0 1 0 0]
[0 1 1 0 0 0 0 1 0 0]
[1 0 0 0 0 1 1 0 0 0]
[1 0 1 0 1 0 0 0 0 0]
[1 1 0 1 0 0 0 0 0 0]

Edge labeled graphs:

sage: G = Graph(implementation='networkx')
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

cartesian_product( self, other)

Returns the Cartesian product of self and other.

The Cartesian product of G and H is the graph L with vertex set V(L) equal to the Cartesian product of the vertices V(G) and V(H), and ((u,v), (w,x)) is an edge iff either - (u, w) is an edge of self and v = x, or - (v, x) is an edge of other and u = w.

sage: Z = graphs.CompleteGraph(2)
sage: C = graphs.CycleGraph(5)
sage: P = C.cartesian_product(Z); P
Graph on 10 vertices
sage: P.plot().show()

sage: D = graphs.DodecahedralGraph()
sage: P = graphs.PetersenGraph()
sage: C = D.cartesian_product(P); C    
Graph on 200 vertices
sage: C.plot().show()

categorical_product( self, other)

Returns the tensor product, also called the categorical 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.

sage: Z = graphs.CompleteGraph(2)
sage: C = graphs.CycleGraph(5)
sage: T = C.tensor_product(Z); T
Graph on 10 vertices
sage: T.plot().show()

sage: D = graphs.DodecahedralGraph()
sage: P = graphs.PetersenGraph()
sage: T = D.tensor_product(P); T
Graph on 200 vertices
sage: T.plot().show()

center( self)

Returns the set of vertices in the center, i.e. whose eccentricity is equal to the radius of the (di)graph.

In other words, the center is the set of vertices achieving the minimum eccentricity.

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

characteristic_polynomial( self, [var=x], [laplacian=False])

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

Input:

laplacian: - if True, use the Laplacian matrix instead (see self.kirchhoff_matrix())

sage: P = graphs.PetersenGraph()
sage: P.characteristic_polynomial()
x^10 - 15*x^8 + 75*x^6 - 24*x^5 - 165*x^4 + 120*x^3 + 120*x^2 - 160*x + 48
sage: P.characteristic_polynomial(laplacian=True)
x^10 - 30*x^9 + 390*x^8 - 2880*x^7 + 13305*x^6 - 39882*x^5 + 77640*x^4 -
94800*x^3 + 66000*x^2 - 20000*x

check_embedding_validity( self, [embedding=None])

Checks whether an _embedding attribute is defined on self and if so, checks for accuracy. Returns True if everything is okay, False otherwise.

If embedding=None will test the attribute _embedding.

sage: d = {0: [1, 5, 4], 1: [0, 2, 6], 2: [1, 3, 7], 3: [8, 2, 4], 4: [0, 9, 3], 5: [0, 8, 7], 6: [8, 1, 9], 7: [9, 2, 5], 8: [3, 5, 6], 9: [4, 6, 7]}
sage: G = graphs.PetersenGraph()
sage: G.check_embedding_validity(d)
True

clear( self)

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

sage: G=graphs.CycleGraph(4); G.set_vertices({0:'vertex0'})
sage: G.order(); G.size()
4
4
sage: len(G._pos)
4
sage: G.name()
'Cycle graph'
sage: G.get_vertex(0)
'vertex0'
sage: H = G.copy(implementation='c_graph', sparse=True)
sage: H.clear()
sage: H.order(); H.size()
0
0
sage: len(H._pos)
0
sage: H.name()
''
sage: H.get_vertex(0)
sage: H = G.copy(implementation='networkx')
sage: H.clear()
sage: H.order(); H.size()
0
0
sage: len(H._pos)
0
sage: H.name()
''
sage: H.get_vertex(0)

cluster_transitivity( self)

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

The clustering coefficient of a graph is the fraction of possible triangles that are triangles, c_i = triangles_i / (k_i*(k_i-1)/2) where k_i is the degree of vertex i, [1]. A coefficient for the whole graph is the average of the c_i. Transitivity is the fraction of all possible triangles which are triangles, T = 3*triangles/triads, [1].

REFERENCE: [1] Aric Hagberg, Dan Schult and Pieter Swart. NetworkX documentation. [Online] Available: https://networkx.lanl.gov/reference/networkx/

sage: (graphs.FruchtGraph()).cluster_transitivity()
0.25

cluster_triangles( self, [nbunch=None], [with_labels=False])

Returns the number of triangles for nbunch of vertices as an ordered list.

Input:

: - nbunch - The vertices to inspect. If nbunch=None, returns data for all vertices in the graph
: - with_labels - (boolean) default False returns list as above True returns dict keyed by vertex labels.

REFERENCE: [1] Aric Hagberg, Dan Schult and Pieter Swart. NetworkX documentation. [Online] Available: https://networkx.lanl.gov/reference/networkx/

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

clustering_average( self)

Returns the average clustering coefficient.

REFERENCE: [1] Aric Hagberg, Dan Schult and Pieter Swart. NetworkX documentation. [Online] Available: https://networkx.lanl.gov/reference/networkx/

sage: (graphs.FruchtGraph()).clustering_average()
0.25

clustering_coeff( self, [nbunch=None], [with_labels=False], [weights=False])

Returns the clustering coefficient for each vertex in nbunch as an ordered list.

Input:

: - nbunch - the vertices to inspect (default None returns data on all vertices in graph)
: - with_labels - (boolean) default False returns list as above True returns dict keyed by vertex labels.
: - weights - default is False. If both with_labels and weights are True, then returns a clustering coefficient dict and a dict of weights based on degree. Weights are the fraction of connected triples in the graph that include the keyed vertex.

REFERENCE: [1] Aric Hagberg, Dan Schult and Pieter Swart. NetworkX documentation. [Online] Available: https://networkx.lanl.gov/reference/networkx/

sage: (graphs.FruchtGraph()).clustering_coeff()
[0.33333333333333331, 0.33333333333333331, 0.0, 0.33333333333333331,
0.33333333333333331, 0.33333333333333331, 0.33333333333333331,
0.33333333333333331, 0.0, 0.33333333333333331, 0.33333333333333331, 0.0]
sage: (graphs.FruchtGraph()).clustering_coeff(with_labels=True)
{0: 0.33333333333333331, 1: 0.33333333333333331, 2: 0.0, 3:
0.33333333333333331, 4: 0.33333333333333331, 5: 0.33333333333333331, 6:
0.33333333333333331, 7: 0.33333333333333331, 8: 0.0, 9:
0.33333333333333331, 10: 0.33333333333333331, 11: 0.0}
sage: (graphs.FruchtGraph()).clustering_coeff(with_labels=True,weights=True)
({0: 0.33333333333333331, 1: 0.33333333333333331, 2: 0.0, 3:
0.33333333333333331, 4: 0.33333333333333331, 5: 0.33333333333333331, 6:
0.33333333333333331, 7: 0.33333333333333331, 8: 0.0, 9:
0.33333333333333331, 10: 0.33333333333333331, 11: 0.0}, {0:
0.083333333333333329, 1: 0.083333333333333329, 2: 0.083333333333333329, 3:
0.083333333333333329, 4: 0.083333333333333329, 5: 0.083333333333333329, 6:
0.083333333333333329, 7: 0.083333333333333329, 8: 0.083333333333333329, 9:
0.083333333333333329, 10: 0.083333333333333329, 11: 0.083333333333333329})
sage: (graphs.FruchtGraph()).clustering_coeff(nbunch=[0,1,2])
[0.33333333333333331, 0.33333333333333331, 0.0]
sage: (graphs.FruchtGraph()).clustering_coeff(nbunch=[0,1,2],with_labels=True,weights=True)
({0: 0.33333333333333331, 1: 0.33333333333333331, 2: 0.0}, {0:
0.083333333333333329, 1: 0.083333333333333329, 2: 0.083333333333333329})

coarsest_equitable_refinement( self, partition, [sparse=False])

Returns the coarsest partition which is finer than the input partition, and equitable with respect to self.

A partition is equitable with respect to a graph if for every pair of cells C1, C2 of the partition, the number of edges from a vertex of C1 to C2 is the same, over all vertices in C1.

A partition P1 is finer than P2 (P2 is coarser than P1) if every cell of P1 is a subset of a cell of P2.

Input:

partition: - a list of lists
sparse: - (default False) whether to use sparse or dense representation- for small graphs, use dense for speed

sage: G = graphs.PetersenGraph()
sage: G.coarsest_equitable_refinement([[0],range(1,10)])
[[0], [2, 3, 6, 7, 8, 9], [1, 4, 5]]
sage: G = graphs.CubeGraph(3)
sage: verts = G.vertices()
sage: Pi = [verts[:1], verts[1:]]
sage: Pi
[['000'], ['001', '010', '011', '100', '101', '110', '111']]
sage: G.coarsest_equitable_refinement(Pi)
[['000'], ['011', '101', '110'], ['111'], ['001', '010', '100']]

Note that given an equitable partition, this function returns that partition:

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

sage: ss = (graphs.WheelGraph(6)).line_graph(labels=False)
sage: prt = [[(0, 1)], [(0, 2), (0, 3), (0, 4), (1, 2), (1, 4)], [(2, 3), (3, 4)]]
sage: ss.coarsest_equitable_refinement(prt)
Traceback (most recent call last):
...
TypeError: Partition ([[(0, 1)], [(0, 2), (0, 3), (0, 4), (1, 2), (1, 4)],
[(2, 3), (3, 4)]]) is not valid for this graph: vertices are incorrect.

sage: ss = (graphs.WheelGraph(5)).line_graph(labels=False)
sage: ss.coarsest_equitable_refinement(prt)
[[(0, 1)], [(1, 2), (1, 4)], [(0, 3)], [(0, 2), (0, 4)], [(2, 3), (3, 4)]]

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

complement( self)

Returns the complement of the (di)graph.

The complement of a graph has the same vertices, but exactly those edges that are not in the original graph. This is not well defined for graphs with multiple edges.

sage: P = graphs.PetersenGraph()
sage: P.plot().show()
sage: PC = P.complement()
sage: PC.plot().show()

sage: graphs.TetrahedralGraph().complement().size()
0
sage: graphs.CycleGraph(4).complement().edges()
[(0, 2, None), (1, 3, None)]
sage: graphs.CycleGraph(4).complement()
complement(Cycle graph): Graph on 4 vertices
sage: Graph(multiedges=True).complement()
Traceback (most recent call last):
...
TypeError: Complement not well defined for (di)graphs with multiple edges.

connected_component_containing_vertex( self, vertex)

Returns a list of the vertices connected to vertex.

sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } )
sage: G.connected_component_containing_vertex(0)
[0, 1, 2, 3]
sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } )
sage: D.connected_component_containing_vertex(0)
[0, 1, 2, 3]

connected_components( self)

Returns a list of lists of vertices, each list representing a connected component. The list is ordered from largest to smallest component.

sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } )
sage: G.connected_components()
[[0, 1, 2, 3], [4, 5, 6]]
sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } )
sage: D.connected_components()
[[0, 1, 2, 3], [4, 5, 6]]

connected_components_number( self)

Returns the number of connected components.

sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } )
sage: G.connected_components_number()
2
sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } )
sage: D.connected_components_number()
2

connected_components_subgraphs( self)

Returns a list of connected components as graph objects.

sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } )
sage: L = G.connected_components_subgraphs()
sage: graphs_list.show_graphs(L)
sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } )
sage: L = D.connected_components_subgraphs()
sage: graphs_list.show_graphs(L)

copy( self, [implementation=networkx], [sparse=True])

Creates a copy of the graph.

sage: g=Graph({0:[0,1,1,2]},loops=True,multiedges=True,implementation='networkx')
sage: g==g.copy()
True
sage: g=DiGraph({0:[0,1,1,2],1:[0,1]},loops=True,multiedges=True,implementation='networkx')
sage: g==g.copy()
True

Note that vertex associations are also kept:

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

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

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

TESTS: We make copies of the _pos and _boundary attributes.

sage: g = graphs.PathGraph(3)
sage: h = g.copy()
sage: h._pos is g._pos
False
sage: h._boundary is g._boundary
False

cores( self, [with_labels=False])

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

'K-cores in graph theory were introduced by Seidman in 1983 and by Bollobas in 1984 as a method of (destructively) simplifying graph topology to aid in analysis and visualization. They have been more recently defined as the following by Batagelj et al: given a graph G with vertices set V and edges set E, the k-core is computed by pruning all the vertices (with their respective edges) with degree less than k. That means that if a vertex u has degree d_u, and it has n neighbors with degree less than k, then the degree of u becomes d_u - n, and it will be also pruned if k > d_u - n. This operation can be useful to filter or to study some properties of the graphs. For instance, when you compute the 2-core of graph G, you are cutting all the vertices which are in a tree part of graph. (A tree is a graph with no loops),' [1].

Input:

: - with_labels - default False returns list as described above. True returns dict keyed by vertex labels.

REFERENCE: [1] K-core. Wikipedia. (2007). [Online] Available: http://en.wikipedia.org/wiki/K-core [2] Boris Pittel, Joel Spencer and Nicholas Wormald. Sudden Emergence of a Giant k-Core in a Random Graph. (1996). J. Combinatorial Theory. Ser B 67. pages 111-151. [Online] Available: http://cs.nyu.edu/cs/faculty/spencer/papers/k-core.pdf

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

degree( self, [vertices=None], [labels=False])

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

Input:

vertices: - If vertices is a single vertex, returns the number of neighbors of vertex. If vertices is an iterable container of vertices, returns a list of degrees. If vertices is None, same as listing all vertices.
labels: - see OUTPUT

Output: Single vertex- an integer. Multiple vertices- a list of integers. If labels is True, then returns a dictionary mapping each vertex to its degree.

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

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

sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: D.degree(vertices = [0,1,2], labels=True)
{0: 5, 1: 4, 2: 3}
sage: D.degree()
[5, 4, 3, 3, 3, 2]

degree_histogram( self)

Returns a list, whose ith entry is the frequency of degree i.

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

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

degree_iterator( self, [vertices=None], [labels=False])

Returns an iterator over the degrees of the (di)graph. In the case of a digraph, the degree is defined as the sum of the in-degree and the out-degree, i.e. the total number of edges incident to a given vertex.

Input: labels=False: returns an iterator over degrees. labels=True: returns an iterator over tuples (vertex, degree).

vertices: - if specified, restrict to this subset.

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

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

degree_to_cell( self, vertex, cell)

Returns the number of edges from vertex to an edge in cell. In the case of a digraph, returns a tuple (in_degree, out_degree).

sage: G = graphs.CubeGraph(3)
sage: cell = G.vertices()[:3]
sage: G.degree_to_cell('011', cell)
2
sage: G.degree_to_cell('111', cell)
0

sage: D = DiGraph({ 0:[1,2,3], 1:[3,4], 3:[4,5]})
sage: cell = [0,1,2]
sage: D.degree_to_cell(5, cell)
(0, 0)
sage: D.degree_to_cell(3, cell)
(2, 0)
sage: D.degree_to_cell(0, cell)
(0, 2)

delete_edge( self, u, [v=None], [label=None])

Delete the edge from u to v, returning silently if vertices or edge does not exist.

Input: The following forms are all accepted:

G.delete_edge( 1, 2 ) G.delete_edge( (1, 2) ) G.delete_edges( [ (1, 2) ] ) G.delete_edge( 1, 2, 'label' ) G.delete_edge( (1, 2, 'label') ) G.delete_edges( [ (1, 2, 'label') ] )

sage: G = graphs.CompleteGraph(19)
sage: G.size()
171
sage: G.delete_edge( 1, 2 )
sage: G.delete_edge( (3, 4) )
sage: G.delete_edges( [ (5, 6), (7, 8) ] )
sage: G.delete_edge( 9, 10, 'label' )
sage: G.delete_edge( (11, 12, 'label') )
sage: G.delete_edges( [ (13, 14, 'label') ] )
sage: G.size()
164
sage: G.has_edge( (11, 12) )
False

Note that even though the edge (11, 12) has no label, it still gets deleted: NetworkX does not pay attention to labels here.

sage: D = graphs.CompleteGraph(19).to_directed()
sage: D.size()
342
sage: D.delete_edge( 1, 2 )
sage: D.delete_edge( (3, 4) )
sage: D.delete_edges( [ (5, 6), (7, 8) ] )
sage: D.delete_edge( 9, 10, 'label' )
sage: D.delete_edge( (11, 12, 'label') )
sage: D.delete_edges( [ (13, 14, 'label') ] )
sage: D.size()
335
sage: D.has_edge( (11, 12) )
False

delete_edges( self, edges)

Delete edges from an iterable container.

sage: K12 = graphs.CompleteGraph(12)
sage: K4 = graphs.CompleteGraph(4)
sage: K12.size()
66
sage: K12.delete_edges(K4.edge_iterator())
sage: K12.size()
60

sage: K12 = graphs.CompleteGraph(12).to_directed()
sage: K4 = graphs.CompleteGraph(4).to_directed()
sage: K12.size()
132
sage: K12.delete_edges(K4.edge_iterator())
sage: K12.size()
120

delete_multiedge( self, u, v)

Deletes all edges from u and v.

sage: G = Graph(multiedges=True, implementation='networkx')
sage: G.add_edges([(0,1), (0,1), (0,1), (1,2), (2,3)])
sage: G.edges()
[(0, 1, None), (0, 1, None), (0, 1, None), (1, 2, None), (2, 3, None)]
sage: G.delete_multiedge( 0, 1 )
sage: G.edges()
[(1, 2, None), (2, 3, None)]

sage: D = DiGraph(multiedges=True)
sage: D.add_edges([(0,1,1), (0,1,2), (0,1,3), (1,0), (1,2), (2,3)])
sage: D.edges()
[(0, 1, 1), (0, 1, 2), (0, 1, 3), (1, 0, None), (1, 2, None), (2, 3, None)]
sage: D.delete_multiedge( 0, 1 )
sage: D.edges()
[(1, 0, None), (1, 2, None), (2, 3, None)]

delete_vertex( self, vertex, [in_order=False])

Deletes vertex, removing all incident edges. Deleting a non-existant vertex will raise an exception.

Input:

in_order: - (default False) If True, this deletes the ith vertex in the sorted list of vertices, i.e. G.vertices()[i]

sage: G = Graph(graphs.WheelGraph(9), sparse=True)
sage: G.delete_vertex(0); G.show()

sage: D = DiGraph({0:[1,2,3,4,5],1:[2],2:[3],3:[4],4:[5],5:[1]}, implementation='networkx')
sage: D.delete_vertex(0); D
Digraph on 5 vertices
sage: D.vertices()
[1, 2, 3, 4, 5]
sage: D.delete_vertex(0)
Traceback (most recent call last):
...
NetworkXError: node 0 not in graph

sage: G = graphs.CompleteGraph(4).line_graph(labels=False)
sage: G.vertices()
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
sage: G.delete_vertex(0, in_order=True)
sage: G.vertices()
[(0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

delete_vertices( self, vertices)

Remove vertices from the (di)graph taken from an iterable container of vertices. Deleting a non-existant vertex will raise an exception.

sage: D = DiGraph({0:[1,2,3,4,5],1:[2],2:[3],3:[4],4:[5],5:[1]}, implementation='networkx')
sage: D.delete_vertices([1,2,3,4,5]); D
Digraph on 1 vertex
sage: D.vertices()
[0]
sage: D.delete_vertices([1])
Traceback (most recent call last):
...
NetworkXError: node 1 not in graph

density( self)

Returns the density (number of edges divided by number of possible edges).

In the case of a multigraph, raises an error, since there is an infinite number of possible edges.

sage: d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7, 8], 6: [8,9], 7: [9]}
sage: G = Graph(d); G.density()
1/3
sage: G = Graph({0:[1,2], 1:[0] }); G.density()
2/3
sage: G = DiGraph({0:[1,2], 1:[0] }); G.density()
1/2

Note that there are more possible edges on a looped graph:

sage: G.loops(True)
sage: G.density()
1/3

depth_first_search( self, u, [ignore_direction=False])

Returns an iterator over vertices in a depth-first ordering.

Input:

u: - vertex at which to start search
ignore_direction: - (default False) only applies to directed graphs. If True, searches across edges in either direction.

sage: G = Graph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} } )
sage: list(G.breadth_first_search(0))
[0, 1, 4, 2, 3]
sage: list(G.depth_first_search(0))
[0, 4, 3, 2, 1]

sage: D = DiGraph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} } )
sage: list(D.breadth_first_search(0))
[0, 1, 2, 3, 4]
sage: list(D.depth_first_search(0))
[0, 1, 2, 3, 4]

sage: D = DiGraph({1:[0], 2:[0]})
sage: list(D.depth_first_search(0))
[0]
sage: list(D.depth_first_search(0, ignore_direction=True))
[0, 2, 1]

diameter( self)

Returns the largest distance between any two vertices. Returns Infinity if the (di)graph is not connected.

sage: G = graphs.PetersenGraph()
sage: G.diameter()
2
sage: G = Graph( { 0 : [], 1 : [], 2 : [1] } )
sage: G.diameter()
+Infinity

Although max( ) is usually defined as -Infinity, since the diameter will never be negative, we define it to be zero:

sage: G = graphs.EmptyGraph()
sage: G.diameter()
0

disjoint_union( self, other, [verbose_relabel=True])

Returns the disjoint union of self and other.

If the graphs have common vertices, the vertices will be renamed to form disjoint sets.

Input:

verbose_relabel: - (defaults to True) If True and the graphs have common vertices, then each vertex v in the first graph will be changed to '0,v' and each vertex u in the second graph will be changed to '1,u'. If False, the vertices of the first graph and the second graph will be relabeled with consecutive integers.

sage: G = graphs.CycleGraph(3)
sage: H = graphs.CycleGraph(4)
sage: J = G.disjoint_union(H); J
Cycle graph disjoint_union Cycle graph: Graph on 7 vertices
sage: J.vertices()
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (1, 3)]
sage: J = G.disjoint_union(H, verbose_relabel=False); J
Cycle graph disjoint_union Cycle graph: Graph on 7 vertices
sage: J.vertices()
[0, 1, 2, 3, 4, 5, 6]

If the vertices are already disjoint and verbose_relabel is True, then the vertices are not relabeled.

sage: G=Graph({'a': ['b']}, implementation='networkx')
sage: G.name("Custom path")
sage: G.name()
'Custom path'
sage: H=graphs.CycleGraph(3)
sage: J=G.disjoint_union(H); J
Custom path disjoint_union Cycle graph: Graph on 5 vertices
sage: J.vertices()
[0, 1, 2, 'a', 'b']

disjunctive_product( self, other)

Returns the disjunctive product of self and other.

The disjunctive product of G and H is the graph L with vertex set V(L) 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, or - (v, x) is an edge of other.

sage: Z = graphs.CompleteGraph(2)
sage: D = Z.disjunctive_product(Z); D
Graph on 4 vertices
sage: D.plot().show()

sage: C = graphs.CycleGraph(5)
sage: D = C.disjunctive_product(Z); D
Graph on 10 vertices
sage: D.plot().show()

distance( self, u, v)

Returns the (directed) distance from u to v in the (di)graph, i.e. the length of the shortest path from u to v.

sage: G = graphs.CycleGraph(9)
sage: G.distance(0,1)
1
sage: G.distance(0,4)
4
sage: G.distance(0,5)
4
sage: G = Graph( {0:[], 1:[]} )
sage: G.distance(0,1)
+Infinity

eccentricity( self, [v=None], [dist_dict=None], [with_labels=False])

Return the eccentricity of vertex (or vertices) v.

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

Input:

v: - either a single vertex or a list of vertices. If it is not specified, then it is taken to be all vertices.
dist_dict: - optional, a dict of dicts of distance.
with_labels: - Whether to return a list or a dict.

sage: G = graphs.KrackhardtKiteGraph()
sage: G.eccentricity()
[4, 4, 4, 4, 4, 3, 3, 2, 3, 4]
sage: G.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: G.eccentricity(7)
2
sage: G.eccentricity([7,8,9])
[3, 4, 2]
sage: G.eccentricity([7,8,9], with_labels=True) == {8: 3, 9: 4, 7: 2}
True
sage: G = Graph( { 0 : [], 1 : [], 2 : [1] } )
sage: G.eccentricity()
[+Infinity, +Infinity, +Infinity]
sage: G = Graph({0:[]})
sage: G.eccentricity(with_labels=True)
{0: 0}
sage: G = Graph({0:[], 1:[]})
sage: G.eccentricity(with_labels=True)
{0: +Infinity, 1: +Infinity}

edge_boundary( self, vertices1, [vertices2=None], [labels=True])

Returns a list of edges (u,v,l) with u in vertices1 and v in vertices2. If vertices2 is None, then it is set to the complement of vertices1.

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

Input:

labels: - if False, each edge is a tuple (u,v) of vertices.

sage: K = graphs.CompleteBipartiteGraph(9,3)
sage: len(K.edge_boundary( [0,1,2,3,4,5,6,7,8], [9,10,11] ))
27
sage: K.size()
27

Note that the edge boundary preserves direction:

sage: K = graphs.CompleteBipartiteGraph(9,3).to_directed()
sage: len(K.edge_boundary( [0,1,2,3,4,5,6,7,8], [9,10,11] ))
27
sage: K.size()
54

sage: D = DiGraph({0:[1,2], 3:[0]})
sage: D.edge_boundary([0])
[(0, 1, None), (0, 2, None)]
sage: D.edge_boundary([0], labels=False)
[(0, 1), (0, 2)]

edge_iterator( self, [vertices=None], [labels=True], [ignore_direction=False])

Returns an iterator over the edges incident with any vertex given. If the graph is directed, iterates over edges going out only. If vertices is None, then returns an iterator over all edges. If self is directed, returns outgoing edges only.

Input:

labels: - if False, each edge is a tuple (u,v) of vertices.
ignore_direction: - (default False) only applies to directed graphs. If True, searches across edges in either direction.

sage: for i in graphs.PetersenGraph().edge_iterator([0]):
...    print i
(0, 1, None)
(0, 4, None)
(0, 5, None)
sage: D = DiGraph( { 0 : [1,2], 1: [0] } )
sage: for i in D.edge_iterator([0]):
...    print i
(0, 1, None)
(0, 2, None)

sage: G = graphs.TetrahedralGraph()
sage: list(G.edge_iterator(labels=False))
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

sage: D = DiGraph({1:[0], 2:[0]})
sage: list(D.edge_iterator(0))
[]
sage: list(D.edge_iterator(0, ignore_direction=True))
[(1, 0, None), (2, 0, None)]

edge_label( self, u, [v=None])

Returns the label of an edge. Note that if the graph allows multiple edges, then a list of labels on the edge is returned.

sage: G = Graph({0 : {1 : 'edgelabel'}}, implementation='networkx')
sage: G.edges(labels=False)
[(0, 1)]
sage: G.edge_label( 0, 1 )
'edgelabel'
sage: D = DiGraph({0 : {1 : 'edgelabel'}}, implementation='networkx')
sage: D.edges(labels=False)
[(0, 1)]
sage: D.edge_label( 0, 1 )
'edgelabel'

sage: G = Graph(multiedges=True)
sage: [G.add_edge(0,1,i) for i in range(1,6)]
[None, None, None, None, None]
sage: sorted(G.edge_label(0,1))
[1, 2, 3, 4, 5]

edge_labels( self)

Returns a list of edge labels.

sage: G = Graph({0:{1:'x',2:'z',3:'a'}, 2:{5:'out'}}, implementation='networkx')
sage: G.edge_labels()
['x', 'z', 'a', 'out']
sage: G = DiGraph({0:{1:'x',2:'z',3:'a'}, 2:{5:'out'}}, implementation='networkx')
sage: G.edge_labels()
['x', 'z', 'a', 'out']

edges( self, [labels=True], [sort=True])

Return a list of edges. Each edge is a triple (u,v,l) where u and v are vertices and l is a label.

Input:

labels: - (bool; default: True) if False, each edge is a tuple (u,v) of vertices.
sort: - (bool; default: True) if True, ensure that the list of edges is sorted.

Output: A list of tuples. It is safe to change the returned list.

sage: graphs.DodecahedralGraph().edges()
[(0, 1, None), (0, 10, None), (0, 19, None), (1, 2, None), (1, 8, None),
(2, 3, None), (2, 6, None), (3, 4, None), (3, 19, None), (4, 5, None), (4,
17, None), (5, 6, None), (5, 15, None), (6, 7, None), (7, 8, None), (7, 14,
None), (8, 9, None), (9, 10, None), (9, 13, None), (10, 11, None), (11, 12,
None), (11, 18, None), (12, 13, None), (12, 16, None), (13, 14, None), (14,
15, None), (15, 16, None), (16, 17, None), (17, 18, None), (18, 19, None)]

sage: graphs.DodecahedralGraph().edges(labels=False)
[(0, 1), (0, 10), (0, 19), (1, 2), (1, 8), (2, 3), (2, 6), (3, 4), (3, 19),
(4, 5), (4, 17), (5, 6), (5, 15), (6, 7), (7, 8), (7, 14), (8, 9), (9, 10),
(9, 13), (10, 11), (11, 12), (11, 18), (12, 13), (12, 16), (13, 14), (14,
15), (15, 16), (16, 17), (17, 18), (18, 19)]

sage: D = graphs.DodecahedralGraph().to_directed()
sage: D.edges()
[(0, 1, None), (0, 10, None), (0, 19, None), (1, 0, None), (1, 2, None),
(1, 8, None), (2, 1, None), (2, 3, None), (2, 6, None), (3, 2, None), (3,
4, None), (3, 19, None), (4, 3, None), (4, 5, None), (4, 17, None), (5, 4,
None), (5, 6, None), (5, 15, None), (6, 2, None), (6, 5, None), (6, 7,
None), (7, 6, None), (7, 8, None), (7, 14, None), (8, 1, None), (8, 7,
None), (8, 9, None), (9, 8, None), (9, 10, None), (9, 13, None), (10, 0,
None), (10, 9, None), (10, 11, None), (11, 10, None), (11, 12, None), (11,
18, None), (12, 11, None), (12, 13, None), (12, 16, None), (13, 9, None),
(13, 12, None), (13, 14, None), (14, 7, None), (14, 13, None), (14, 15,
None), (15, 5, None), (15, 14, None), (15, 16, None), (16, 12, None), (16,
15, None), (16, 17, None), (17, 4, None), (17, 16, None), (17, 18, None),
(18, 11, None), (18, 17, None), (18, 19, None), (19, 0, None), (19, 3,
None), (19, 18, None)]
sage: D.edges(labels = False)
[(0, 1), (0, 10), (0, 19), (1, 0), (1, 2), (1, 8), (2, 1), (2, 3), (2, 6),
(3, 2), (3, 4), (3, 19), (4, 3), (4, 5), (4, 17), (5, 4), (5, 6), (5, 15),
(6, 2), (6, 5), (6, 7), (7, 6), (7, 8), (7, 14), (8, 1), (8, 7), (8, 9),
(9, 8), (9, 10), (9, 13), (10, 0), (10, 9), (10, 11), (11, 10), (11, 12),
(11, 18), (12, 11), (12, 13), (12, 16), (13, 9), (13, 12), (13, 14), (14,
7), (14, 13), (14, 15), (15, 5), (15, 14), (15, 16), (16, 12), (16, 15),
(16, 17), (17, 4), (17, 16), (17, 18), (18, 11), (18, 17), (18, 19), (19,
0), (19, 3), (19, 18)]

edges_incident( self, [vertices=None], [labels=True])

Returns a list of edges incident with any vertex given. If vertices is None, returns a list of all edges in graph. For digraphs, only lists outward edges.

Input:

label: - if False, each edge is a tuple (u,v) of vertices.

sage: graphs.PetersenGraph().edges_incident([0,9], labels=False)
[(0, 1), (0, 4), (0, 5), (9, 4), (9, 6), (9, 7)]
sage: D = DiGraph({0:[1]})
sage: D.edges_incident([0])
[(0, 1, None)]
sage: D.edges_incident([1])
[]

eigenspaces( self, [laplacian=False])

Returns the eigenspaces of the adjacency matrix of the graph.

Input:

laplacian: - if True, use the Laplacian matrix instead (see self.kirchhoff_matrix())

sage: C = graphs.CycleGraph(5)
sage: E = C.eigenspaces()
sage: E[0][0]
-1.618...
sage: E[1][0]  # eigenspace computation is somewhat random
Vector space of degree 5 and dimension 1 over Real Double Field
User basis matrix:
[ 0.632... -0.632... -0.447... -0.013... 0.073...]

sage: D = C.to_directed()
sage: F = D.eigenspaces()
sage: abs(E[0][0] - F[0][0]) < 0.00001
True

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

Returns the minimal genus of the graph. The genus of a compact surface is the number of handles it has. The genus of a graph is the minimal genus of the surface it can be embedded into.

Note - This function uses Euler's formula and thus it is necessary to consider only connected graphs.

Input:

set_embedding (boolean): - whether or not to store an embedding attribute of the computed (minimal) genus of the graph. (Default is True).
on_embedding (dict): - a combinatorial embedding to compute the genus of the graph on. Note that this must be a valid embedding for the graph. The dictionary structure is given by: vertex1: [neighbor1, neighbor2, neighbor3], vertex2: [neighbor] where there is a key for each vertex in the graph and a (clockwise) ordered list of each vertex's neighbors as values. on_embedding takes precedence over a stored _embedding attribute if minimal is set to False. Note that as a shortcut, the user can enter on_embedding=True to compute the genus on the current _embedding attribute. (see eg's.)
minimal (boolean): - whether or not to compute the minimal genus of the graph (i.e., testing all embeddings). If minimal is False, then either maximal must be True or on_embedding must not be None. If on_embedding is not None, it will take priority over minimal. Similarly, if maximal is True, it will take priority over minimal.
maximal (boolean): - whether or not to compute the maximal genus of the graph (i.e., testin all embeddings). If maximal is False, then either minimal must be True or on_embedding must not be None. If on_embedding is not None, it will take priority over maximal. However, maximal takes priority over the default minimal.
circular (boolean): - whether or not to compute the genus preserving a planar embedding of the boundary. (Default is False). If circular is True, on_embedding is not a valid option.
ordered (boolean): - if circular is True, then whether or not the boundary order may be permuted. (Default is True, which means the boundary order is preserved.)

sage: g = graphs.PetersenGraph()
sage: g.genus() # tests for minimal genus by default
1
sage: g.genus(on_embedding=True, maximal=True) # on_embedding overrides minimal and maximal arguments
1
sage: g.genus(maximal=True) # setting maximal to True overrides default minimal=True
3
sage: g.genus(on_embedding=g.get_embedding()) # can also send a valid combinatorial embedding dict
3
sage: (graphs.CubeGraph(3)).genus()
0
sage: K23 = graphs.CompleteBipartiteGraph(2,3)
sage: K23.genus()
0
sage: K33 = graphs.CompleteBipartiteGraph(3,3)
sage: K33.genus()
1