CoCalc Shared FilesDigraphDocsJumpStart.sagews
Author: Raazesh Sainudiin
Views : 4
Description: DigraphDocsJumpStart

# Minimal Syntactic Dives into SageMath DiGraphs

### Raazesh Sainudiin and Joel Dahne

Just went through the digraphs documentation and jot down the commands we will need (and a lot more commands that may be useful for insights and visualizations). -- Raaz

## Syntax that may be useful

g = DiGraph()

g.edges?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.edges(self, labels=True, sort=True, key=None)
Docstring :
Return a list of edges.

Each edge is a triple (u,v,l) where u and v are vertices and l is a
label. If the parameter "labels" is False then a list of couple
(u,v) is returned where u and v are vertices.

INPUT:

* "labels" - default: "True" - if "False", each edge is simply a
pair (u,v) of vertices.

* "sort" - default: "True" - if "True", edges are sorted
according to the default ordering.

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

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

Warning: Since any object may be a vertex, there is no guarantee
that any two vertices will be comparable, and thus no guarantee
how two edges may compare.  With default objects for vertices
(all integers), or when all the vertices are of the same simple
type, then there should not be a problem with how the vertices
will be sorted. However, if you need to guarantee a total order
for the sorting of the edges, use the "key" argument, as
illustrated in the examples below.

EXAMPLES:

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

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

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

The default is to sort the returned list in the default fashion, as
in the above examples. this can be overridden by specifying a key
function. This first example just ignores the labels in the third
component of the triple.

sage: G=graphs.CycleGraph(5)
sage: G.edges(key = lambda x: (x[1],-x[0]))
[(0, 1, None), (1, 2, None), (2, 3, None), (3, 4, None), (0, 4, None)]

We set the labels to characters and then perform a default sort
followed by a sort according to the labels.

sage: G=graphs.CycleGraph(5)
sage: for e in G.edges():
...     G.set_edge_label(e[0], e[1], chr(ord('A')+e[0]+5*e[1]))
sage: G.edges(sort=True)
[(0, 1, 'F'), (0, 4, 'U'), (1, 2, 'L'), (2, 3, 'R'), (3, 4, 'X')]
sage: G.edges(key=lambda x: x[2])
[(0, 1, 'F'), (1, 2, 'L'), (2, 3, 'R'), (0, 4, 'U'), (3, 4, 'X')]

g.edges()

[(0, 1, None), (0, 2, None), (0, 3, None), (1, 0, None), (1, 2, None), (1, 3, None), (2, 0, None), (2, 1, None), (2, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)]


g.add_edges?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Docstring :
Add edges from an iterable container.

All elements of "edges" must follow the same format, i.e. have the
same length.

EXAMPLES:

sage: G = graphs.DodecahedralGraph()
sage: H = Graph()
Graph on 20 vertices
sage: G = graphs.DodecahedralGraph().to_directed()
sage: H = DiGraph()
Digraph on 20 vertices

sage: H = Graph()
sage: H.edges()
[(0, 1, None), (0, 2, None)]

g=graphs.CompleteGraph(4).to_directed()
print g.edges()
g.add_edges([(0,1)]) # Note that adding existing edges to a digraph does nothing to the digraph!
print g.edges()

[(0, 1, None), (0, 2, None), (0, 3, None), (1, 0, None), (1, 2, None), (1, 3, None), (2, 0, None), (2, 1, None), (2, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)] [(0, 1, None), (0, 2, None), (0, 3, None), (1, 0, None), (1, 2, None), (1, 3, None), (2, 0, None), (2, 1, None), (2, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)]
g.delete_edges?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.delete_edges()
Docstring :
Delete edges from an iterable container.

EXAMPLES:

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

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

g=graphs.CompleteGraph(4).to_directed()
print g.edges()
g.delete_edges([(0,10)]) # Note that deleting non-existing edges to a digraph does nothing to the digraph!
print g.edges()

[(0, 1, None), (0, 2, None), (0, 3, None), (1, 0, None), (1, 2, None), (1, 3, None), (2, 0, None), (2, 1, None), (2, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)] [(0, 1, None), (0, 2, None), (0, 3, None), (1, 0, None), (1, 2, None), (1, 3, None), (2, 0, None), (2, 1, None), (2, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)]
g=graphs.CompleteGraph(4).to_directed()
print g.edges()
g.delete_edges([(0,1),(1,3)])
print g.edges()

[(0, 1, None), (0, 2, None), (0, 3, None), (1, 0, None), (1, 2, None), (1, 3, None), (2, 0, None), (2, 1, None), (2, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)] [(0, 2, None), (0, 3, None), (1, 0, None), (1, 2, None), (2, 0, None), (2, 1, None), (2, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)]
print g.edges()
print g.edges()

[(0, 2, None), (0, 3, None), (1, 0, None), (1, 2, None), (1, 3, None), (2, 0, None), (2, 1, None), (2, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)] [(0, 1, None), (0, 2, None), (0, 3, None), (1, 0, None), (1, 2, None), (1, 3, None), (2, 0, None), (2, 1, None), (2, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)]
g.allows_multiple_edges() # we could get multigraphs with G = Graph(multiedges=True,sparse=True); G but let's work with digraphs without multiple edges for now...

False
g.allows_loops() # also let's not allow loops for now

False
g.am? # Returns the adjacency matrix of the (di)graph.

g.connected_component_containing_vertex?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.connected_component_containing_vertex()
Docstring :
Returns a list of the vertices connected to vertex.

EXAMPLES:

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]

g.connected_components?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.connected_components()
Docstring :
Returns the list of connected components.

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

EXAMPLES:

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

g.connected_components_number?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.connected_components_number()
Docstring :
Returns the number of connected components.

EXAMPLES:

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

g.connected_components_sizes?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.connected_components_sizes()
Docstring :
Return the sizes of the connected components as a list.

The list is sorted from largest to lower values.

EXAMPLES:

sage: for x in graphs(3):    print(x.connected_components_sizes())
[1, 1, 1]
[2, 1]
[3]
[3]

g.connected_components_subgraphs?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.connected_components_subgraphs()
Docstring :
Returns a list of connected components as graph objects.

EXAMPLES:

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)

g.copy?
#Warning: Please use this method only if you need to copy but
#  change the underlying implementation or weightedness.  Otherwise
#  simply do "copy(g)" instead of "g.copy()".

g.degree?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.degree(self, vertices=None, labels=False)
Docstring :
Gives the degree (in + out for digraphs) of a vertex or of
vertices.

INPUT:

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

* "labels" - see OUTPUT

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

EXAMPLES:

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

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

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


g.degree()

[6, 6, 6, 6]
print g.in_degree()
print g.out_degree()

[3, 3, 3, 3] [3, 3, 3, 3]
g.degree_histogram()

[0, 0, 0, 0, 0, 0, 4]
g.degree_sequence()

[6, 6, 6, 6]
g.distance? # Returns the (directed) distance from u to v in the (di)graph, i.e. the length of the shortest path from u to v.

g.distance_all_pairs? # Returns the distances between all pairs of vertices.

g.distance_graph?

g.distance_matrix?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.distance_matrix()
Docstring :
Returns the distance matrix of the (strongly) connected (di)graph.

The distance matrix of a (strongly) connected (di)graph is a matrix
whose rows and columns are indexed with the vertices of the (di)
graph. The intersection of a row and column contains the respective
distance between the vertices indexed at these position.

Warning: The ordering of vertices in the matrix has no reason to
correspond to the order of vertices in "vertices()". In
particular, if two integers i,j are vertices of a graph G with
distance matrix "M", then "M[i][i]" is not necessarily the
distance between vertices i and j.

EXAMPLES:

sage: G = graphs.CubeGraph(3)
sage: G.distance_matrix()
[0 1 1 2 1 2 2 3]
[1 0 2 1 2 1 3 2]
[1 2 0 1 2 3 1 2]
[2 1 1 0 3 2 2 1]
[1 2 2 3 0 1 1 2]
[2 1 3 2 1 0 2 1]
[2 3 1 2 1 2 0 1]
[3 2 2 1 2 1 1 0]

The well known result of Graham and Pollak states that the
determinant of the distance matrix of any tree of order n is
(-1)^{n-1}(n-1)2^{n-2}

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

* "distance_all_pairs()" -- computes the distance between any
two vertices.

g.edges()

[(0, 1, None), (0, 2, None), (0, 3, None), (1, 0, None), (1, 2, None), (1, 3, None), (2, 0, None), (2, 1, None), (2, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)]
g.distance_matrix()

[0 1 1 1] [1 0 1 1] [1 1 0 1] [1 1 1 0]
g.distances_distribution?

g.edges_incident?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.edges_incident(self, vertices=None, labels=True, sort=True)
Docstring :
Returns incident edges to some vertices.

If "vertices is a vertex, then it returns the list of edges
incident to that vertex. If vertices" is a list of vertices then
it returns the list of all edges adjacent to those vertices. If
"vertices" is None, returns a list of all edges in graph. For
digraphs, only lists outward edges.

INPUT:

* "vertices" - object (default: None) - a vertex, a list of
vertices or None.

* "labels" - bool (default: True) - if False, each edge is a
tuple (u,v) of vertices.

* "sort" - bool (default: True) - if True the returned list is
sorted.

EXAMPLES:

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

print g.edges()
print g.edges_incident([0])
print g.edges_incident([0,3])

[(0, 1, None), (0, 2, None), (0, 3, None), (1, 0, None), (1, 2, None), (1, 3, None), (2, 0, None), (2, 1, None), (2, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)] [(0, 1, None), (0, 2, None), (0, 3, None)] [(0, 1, None), (0, 2, None), (0, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)]
g.edge_boundary?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.edge_boundary(self, vertices1, vertices2=None, labels=True, sort=True)
Docstring :
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.

EXAMPLES:

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

Note that the edge boundary preserves direction:

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

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

g.edge_disjoint_spanning_trees?

g.edge_labels?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.edge_labels()
Docstring :
Returns a list of edge labels.

EXAMPLES:

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

g.edge_connectivity()

3
g.eigenspaces?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.eigenspaces(self, laplacian=False)
Docstring :
Returns the *right* eigenspaces of the adjacency matrix of the
graph.

INPUT:

* "laplacian" - if True, use the Laplacian matrix (see
"kirchhoff_matrix()")

OUTPUT:

A list of pairs.  Each pair is an eigenvalue of the adjacency
matrix of the graph, followed by the vector space that is the
eigenspace for that eigenvalue, when the eigenvectors are placed on
the right of the matrix.

For some graphs, some of the the eigenspaces are described exactly
by vector spaces over a "NumberField()". For numerical eigenvectors
use "eigenvectors()".

EXAMPLES:

sage: P = graphs.PetersenGraph()
sage: P.eigenspaces()
[
(3, Vector space of degree 10 and dimension 1 over Rational Field
User basis matrix:
[1 1 1 1 1 1 1 1 1 1]),
(-2, Vector space of degree 10 and dimension 4 over Rational Field
User basis matrix:
[ 1  0  0  0 -1 -1 -1  0  1  1]
[ 0  1  0  0 -1  0 -2 -1  1  2]
[ 0  0  1  0 -1  1 -1 -2  0  2]
[ 0  0  0  1 -1  1  0 -1 -1  1]),
(1, Vector space of degree 10 and dimension 5 over Rational Field
User basis matrix:
[ 1  0  0  0  0  1 -1  0  0 -1]
[ 0  1  0  0  0 -1  1 -1  0  0]
[ 0  0  1  0  0  0 -1  1 -1  0]
[ 0  0  0  1  0  0  0 -1  1 -1]
[ 0  0  0  0  1 -1  0  0 -1  1])
]

Eigenspaces for the Laplacian should be identical since the
Petersen graph is regular.  However, since the output also contains
the eigenvalues, the two outputs are slightly different.

sage: P.eigenspaces(laplacian=True)
[
(0, Vector space of degree 10 and dimension 1 over Rational Field
User basis matrix:
[1 1 1 1 1 1 1 1 1 1]),
(5, Vector space of degree 10 and dimension 4 over Rational Field
User basis matrix:
[ 1  0  0  0 -1 -1 -1  0  1  1]
[ 0  1  0  0 -1  0 -2 -1  1  2]
[ 0  0  1  0 -1  1 -1 -2  0  2]
[ 0  0  0  1 -1  1  0 -1 -1  1]),
(2, Vector space of degree 10 and dimension 5 over Rational Field
User basis matrix:
[ 1  0  0  0  0  1 -1  0  0 -1]
[ 0  1  0  0  0 -1  1 -1  0  0]
[ 0  0  1  0  0  0 -1  1 -1  0]
[ 0  0  0  1  0  0  0 -1  1 -1]
[ 0  0  0  0  1 -1  0  0 -1  1])
]

Notice how one eigenspace below is described with a square root of
2.  For the two possible values (positive and negative) there is a
corresponding eigenspace.

sage: C = graphs.CycleGraph(8)
sage: C.eigenspaces()
[
(2, Vector space of degree 8 and dimension 1 over Rational Field
User basis matrix:
[1 1 1 1 1 1 1 1]),
(-2, Vector space of degree 8 and dimension 1 over Rational Field
User basis matrix:
[ 1 -1  1 -1  1 -1  1 -1]),
(0, Vector space of degree 8 and dimension 2 over Rational Field
User basis matrix:
[ 1  0 -1  0  1  0 -1  0]
[ 0  1  0 -1  0  1  0 -1]),
(a3, Vector space of degree 8 and dimension 2 over Number Field in a3 with defining polynomial x^2 - 2
User basis matrix:
[  1   0  -1 -a3  -1   0   1  a3]
[  0   1  a3   1   0  -1 -a3  -1])
]

A digraph may have complex eigenvalues and eigenvectors. For a
3-cycle, we have:

sage: T = DiGraph({0:[1], 1:[2], 2:[0]})
sage: T.eigenspaces()
[
(1, Vector space of degree 3 and dimension 1 over Rational Field
User basis matrix:
[1 1 1]),
(a1, Vector space of degree 3 and dimension 1 over Number Field in a1 with defining polynomial x^2 + x + 1
User basis matrix:
[      1      a1 -a1 - 1])
]

g.eigenvectors?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.eigenvectors(self, laplacian=False)
Docstring :
Returns the *right* eigenvectors of the adjacency matrix of the
graph.

INPUT:

* "laplacian" - if True, use the Laplacian matrix (see
"kirchhoff_matrix()")

OUTPUT:

A list of triples.  Each triple begins with an eigenvalue of the
adjacency matrix of the graph.  This is followed by a list of
eigenvectors for the eigenvalue, when the eigenvectors are placed
on the right side of the matrix. Together, the eigenvectors form a
basis for the eigenspace. The triple concludes with the algebraic
multiplicity of the eigenvalue.

For some graphs, the exact eigenspaces provided by "eigenspaces()"
provide additional insight into the structure of the eigenspaces.

EXAMPLES:

sage: P = graphs.PetersenGraph()
sage: P.eigenvectors()
[(3, [
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
], 1), (-2, [
(1, 0, 0, 0, -1, -1, -1, 0, 1, 1),
(0, 1, 0, 0, -1, 0, -2, -1, 1, 2),
(0, 0, 1, 0, -1, 1, -1, -2, 0, 2),
(0, 0, 0, 1, -1, 1, 0, -1, -1, 1)
], 4), (1, [
(1, 0, 0, 0, 0, 1, -1, 0, 0, -1),
(0, 1, 0, 0, 0, -1, 1, -1, 0, 0),
(0, 0, 1, 0, 0, 0, -1, 1, -1, 0),
(0, 0, 0, 1, 0, 0, 0, -1, 1, -1),
(0, 0, 0, 0, 1, -1, 0, 0, -1, 1)
], 5)]

Eigenspaces for the Laplacian should be identical since the
Petersen graph is regular.  However, since the output also contains
the eigenvalues, the two outputs are slightly different.

sage: P.eigenvectors(laplacian=True)
[(0, [
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
], 1), (5, [
(1, 0, 0, 0, -1, -1, -1, 0, 1, 1),
(0, 1, 0, 0, -1, 0, -2, -1, 1, 2),
(0, 0, 1, 0, -1, 1, -1, -2, 0, 2),
(0, 0, 0, 1, -1, 1, 0, -1, -1, 1)
], 4), (2, [
(1, 0, 0, 0, 0, 1, -1, 0, 0, -1),
(0, 1, 0, 0, 0, -1, 1, -1, 0, 0),
(0, 0, 1, 0, 0, 0, -1, 1, -1, 0),
(0, 0, 0, 1, 0, 0, 0, -1, 1, -1),
(0, 0, 0, 0, 1, -1, 0, 0, -1, 1)
], 5)]

sage: C = graphs.CycleGraph(8)
sage: C.eigenvectors()
[(2, [
(1, 1, 1, 1, 1, 1, 1, 1)
], 1), (-2, [
(1, -1, 1, -1, 1, -1, 1, -1)
], 1), (0, [
(1, 0, -1, 0, 1, 0, -1, 0),
(0, 1, 0, -1, 0, 1, 0, -1)
], 2), (-1.4142135623..., [(1, 0, -1, 1.4142135623..., -1, 0, 1, -1.4142135623...), (0, 1, -1.4142135623..., 1, 0, -1, 1.4142135623..., -1)], 2), (1.4142135623..., [(1, 0, -1, -1.4142135623..., -1, 0, 1, 1.4142135623...), (0, 1, 1.4142135623..., 1, 0, -1, -1.4142135623..., -1)], 2)]

A digraph may have complex eigenvalues.  Previously, the complex
parts of graph eigenvalues were being dropped.  For a 3-cycle, we
have:

sage: T = DiGraph({0:[1], 1:[2], 2:[0]})
sage: T.eigenvectors()
[(1, [
(1, 1, 1)
], 1), (-0.5000000000... - 0.8660254037...*I, [(1, -0.5000000000... - 0.8660254037...*I, -0.5000000000... + 0.8660254037...*I)], 1), (-0.5000000000... + 0.8660254037...*I, [(1, -0.5000000000... + 0.8660254037...*I, -0.5000000000... - 0.8660254037...*I)], 1)]

g.flow?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/misc/decorators.py
Signature : g.flow(self, x, y, value_only=True, integer=False, use_edge_labels=True, vertex_bound=False, algorithm=None, solver=None, verbose=0)
Docstring :
Returns a maximum flow in the graph from "x" to "y" represented by
Wikipedia article on maximum flow.

As an optimization problem, is can be expressed this way :

Maximize : &sum_{ein G.edges()} w_e b_e Such that : &forall
v in G, sum_{(u,v)in G.edges()} b_{(u,v)}<= 1 &forall
xin G, b_x is a binary variable

INPUT:

* "x" -- Source vertex

* "y" -- Sink vertex

* "value_only" -- boolean (default: "True")

* When set to "True", only the value of a maximal flow is
returned.

* When set to "False", is returned a pair whose first element
is the value of the maximum flow, and whose second value is a
flow graph (a copy of the current graph, such that each edge
has the flow using it as a label, the edges without flow being
omitted).

* "integer" -- boolean (default: "True")

* When set to "True", computes an optimal solution under the
constraint that the flow going through an edge has to be an
integer.

* "use_edge_labels" -- boolean (default: "True")

* When set to "True", computes a maximum flow where each edge
has a capacity defined by its label. (If an edge has no label,
1 is assumed.)

* When set to "False", each edge has capacity 1.

* "vertex_bound" -- boolean (default: "False")

* When set to "True", sets the maximum flow leaving a vertex
different from x to 1 (useful for vertex connectivity
parameters).

* "algorithm" -- There are currently three different
implementations of this method:

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

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

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

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

* "solver" -- Specify a Linear Program solver to be used. If set
to "None", the default one is used.  function of
"MixedIntegerLinearProgram". See the documentation of

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

* "verbose" (integer) -- sets the level of verbosity. Set to 0 by
default (quiet).

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

Note: Even though the three different implementations are meant
to return the same Flow values, they can not be expected to
return the same Flow graphs.Besides, the use of Linear
Programming may possibly mean a (slight) numerical noise.

EXAMPLES:

Two basic applications of the flow method for the "PappusGraph" and
the "ButterflyGraph" with parameter 2

sage: g=graphs.PappusGraph()
sage: int(g.flow(1,2))
3

sage: b=digraphs.ButterflyGraph(2)
sage: int(b.flow(('00',1),('00',2)))
1

The flow method can be used to compute a matching in a bipartite
graph by linking a source s to all the vertices of the first set
and linking a sink t to all the vertices of the second set, then
computing a maximum s-t flow

sage: g = DiGraph()
sage: g.add_edges([('s',i) for i in range(4)])
sage: g.add_edges([(i,4+j) for i in range(4) for j in range(4)])
sage: g.add_edges([(4+i,'t') for i in range(4)])
sage: [cardinal, flow_graph] = g.flow('s','t',integer=True,value_only=False)
sage: flow_graph.delete_vertices(['s','t'])
sage: len(flow_graph.edges())
4

The undirected case:

sage: g = Graph()
sage: g.add_edges([('s',i) for i in range(4)])
sage: g.add_edges([(i,4+j) for i in range(4) for j in range(4)])
sage: g.add_edges([(4+i,'t') for i in range(4)])
sage: [cardinal, flow_graph] = g.flow('s','t',integer=True,value_only=False)
sage: flow_graph.delete_vertices(['s','t'])
sage: len(flow_graph.edges())
4

g.flow_polytope?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.flow_polytope(self, edges=None, ends=None)
Docstring :
Return the flow polytope of a digraph.

The flow polytope of a directed graph is the polytope consisting of
all nonnegative flows on the graph with a given set S of sources
and a given set T of sinks.

A *flow* on a directed graph G with a given set S of sources and a
given set T of sinks means an assignment of a nonnegative real to
each edge of G such that the flow is conserved in each vertex
outside of S and T, and there is a unit of flow entering each
vertex in S and a unit of flow leaving each vertex in T. These
flows clearly form a polytope in the space of all assignments of
reals to the edges of G.

The polytope is empty unless the sets S and T are equinumerous.

By default, S is taken to be the set of all sources (i.e., vertices
of indegree 0) of G, and T is taken to be the set of all sinks
(i.e., vertices of outdegree 0) of G. If a different choice of S
and T is desired, it can be specified using the optional "ends"
parameter.

The polytope is returned as a polytope in RR^m, where m is the
number of edges of the digraph "self". The k-th coordinate of a
point in the polytope is the real assigned to the k-th edge of
"self". The order of the edges is the one returned by
"self.edges()". If a different order is desired, it can be
specified using the optional "edges" parameter.

The faces and volume of these polytopes are of interest. Examples
of these polytopes are the Chan-Robbins-Yuen polytope and the
Pitman-Stanley polytope [PitSta].

INPUT:

* "edges" -- (optional, default: "self.edges()") a list or tuple
of all edges of "self" (each only once). This determines which
coordinate of a point in the polytope will correspond to which
edge of "self". It is also possible to specify a list which
contains not all edges of "self"; this results in a polytope
corresponding to the flows which are 0 on all remaining edges.
Notice that the edges entered here must be in the precisely same
format as outputted by "self.edges()"; so, if "self.edges()"
outputs an edge in the form "(1, 3, None)", then "(1, 3)" will
not do!

* "ends" -- (optional, default: "(self.sources(), self.sinks())")
a pair (S, T) of an iterable S and an iterable T.

Note: Flow polytopes can also be built through the
"polytopes.<tab>" object:

sage: polytopes.flow_polytope(digraphs.Path(5))
A 0-dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex

EXAMPLES:

A commutative square:

sage: G = DiGraph({1: [2, 3], 2: [4], 3: [4]})
sage: fl = G.flow_polytope(); fl
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
sage: fl.vertices()
(A vertex at (0, 1, 0, 1), A vertex at (1, 0, 1, 0))

Using a different order for the edges of the graph:

sage: fl = G.flow_polytope(edges=G.edges(key=lambda x: x[0]-x[1])); fl
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
sage: fl.vertices()
(A vertex at (0, 1, 1, 0), A vertex at (1, 0, 0, 1))

A tournament on 4 vertices:

sage: H = digraphs.TransitiveTournament(4)
sage: fl = H.flow_polytope(); fl
A 3-dimensional polyhedron in QQ^6 defined as the convex hull
of 4 vertices
sage: fl.vertices()
(A vertex at (0, 0, 1, 0, 0, 0),
A vertex at (0, 1, 0, 0, 0, 1),
A vertex at (1, 0, 0, 0, 1, 0),
A vertex at (1, 0, 0, 1, 0, 1))

Restricting to a subset of the edges:

sage: fl = H.flow_polytope(edges=[(0, 1, None), (1, 2, None),
....:                             (2, 3, None), (0, 3, None)])
sage: fl
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
sage: fl.vertices()
(A vertex at (0, 0, 0, 1), A vertex at (1, 1, 1, 0))

Using a different choice of sources and sinks:

sage: fl = H.flow_polytope(ends=([1], [3])); fl
A 1-dimensional polyhedron in QQ^6 defined as the convex hull
of 2 vertices
sage: fl.vertices()
(A vertex at (0, 0, 0, 1, 0, 1), A vertex at (0, 0, 0, 0, 1, 0))
sage: fl = H.flow_polytope(ends=([0, 1], [3])); fl
The empty polyhedron in QQ^6
sage: fl = H.flow_polytope(ends=([3], [0])); fl
The empty polyhedron in QQ^6
sage: fl = H.flow_polytope(ends=([0, 1], [2, 3])); fl
A 3-dimensional polyhedron in QQ^6 defined as the convex hull
of 5 vertices
sage: fl.vertices()
(A vertex at (0, 0, 1, 1, 0, 0),
A vertex at (0, 1, 0, 0, 1, 0),
A vertex at (1, 0, 0, 2, 0, 1),
A vertex at (1, 0, 0, 1, 1, 0),
A vertex at (0, 1, 0, 1, 0, 1))
sage: fl = H.flow_polytope(edges=[(0, 1, None), (1, 2, None),
....:                             (2, 3, None), (0, 2, None),
....:                             (1, 3, None)],
....:                      ends=([0, 1], [2, 3])); fl
A 2-dimensional polyhedron in QQ^5 defined as the convex hull
of 4 vertices
sage: fl.vertices()
(A vertex at (0, 0, 0, 1, 1),
A vertex at (1, 2, 1, 0, 0),
A vertex at (1, 1, 0, 0, 1),
A vertex at (0, 1, 1, 1, 0))

A digraph with one source and two sinks:

sage: Y = DiGraph({1: [2], 2: [3, 4]})
sage: Y.flow_polytope()
The empty polyhedron in QQ^3

A digraph with one vertex and no edge:

sage: Z = DiGraph({1: []})
sage: Z.flow_polytope()
A 0-dimensional polyhedron in QQ^0 defined as the convex hull
of 1 vertex

REFERENCES:

[PitSta] Jim Pitman, Richard Stanley, "A polytope related
to empirical distributions, plane trees, parking
functions, and the associahedron",
http://arxiv.org/abs/math/9908029

print g.has_edge((0,1))
print g.has_vertex(0)
g.get_vertices?

True True
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.get_vertices(self, verts=None)
Docstring :
Return a dictionary of the objects associated to each vertex.

INPUT:

* "verts" - iterable container of vertices

EXAMPLES:

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

g.in_degree?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.in_degree(self, vertices=None, labels=False)
Docstring :
Same as degree, but for in degree.

EXAMPLES:

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

g.in_degree_iterator?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.in_degree_iterator(self, vertices=None, labels=False)
Docstring :
Same as degree_iterator, but for in degree.

EXAMPLES:

sage: D = graphs.Grid2dGraph(2,4).to_directed()
sage: for i in D.in_degree_iterator():
....:     print(i)
3
3
2
2
3
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, 3), 2)
((1, 1), 3)
((1, 3), 2)
((1, 0), 2)
((0, 2), 3)

g.in_degree_sequence?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.in_degree_sequence()
Docstring :
Return the indegree sequence.

EXAMPLES:

The indegree sequences of two digraphs:

sage: g = DiGraph({1: [2, 5, 6], 2: [3, 6], 3: [4, 6], 4: [6], 5: [4, 6]})
sage: g.in_degree_sequence()
[5, 2, 1, 1, 1, 0]

sage: V = [2, 3, 5, 7, 8, 9, 10, 11]
sage: E = [[], [8, 10], [11], [8, 11], [9], [], [], [2, 9, 10]]
sage: g = DiGraph(dict(zip(V, E)))
sage: g.in_degree_sequence()
[2, 2, 2, 2, 1, 0, 0, 0]

g.incoming_edge_iterator?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.incoming_edge_iterator(self, vertices, labels=True)
Docstring :
Return an iterator over all arriving edges from vertices.

INPUT:

* "vertices" -- a vertex or a list of vertices

* "labels" (boolean) -- whether to return edges as pairs of
vertices, or as triples containing the labels.

EXAMPLES:

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)

g.incoming_edges?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.incoming_edges(self, vertices, labels=True)
Docstring :
Returns a list of edges arriving at vertices.

INPUT:

* "vertices" -- a vertex or a list of vertices

* "labels" (boolean) -- whether to return edges as pairs of
vertices, or as triples containing the labels.

EXAMPLES:

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

g.is_strongly_connected?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.is_strongly_connected()
Docstring :
Returns whether the current "DiGraph" is strongly connected.

EXAMPLE:

The circuit is obviously strongly connected

sage: g = digraphs.Circuit(5)
sage: g.is_strongly_connected()
True

But a transitive triangle is not:

sage: g = DiGraph({ 0 : [1,2], 1 : [2]})
sage: g.is_strongly_connected()
False

g.laplacian_matrix?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.laplacian_matrix(self, weighted=None, indegree=True, normalized=False, **kwds)
Docstring :
Returns the Kirchhoff matrix (a.k.a. the Laplacian) of the graph.

The Kirchhoff matrix is defined to be D - M, where D is the
diagonal degree matrix (each diagonal entry is the degree of the
corresponding vertex), and M is the adjacency matrix. If
"normalized" is "True", then the returned matrix is
D^{-1/2}(D-M)D^{-1/2}.

( In the special case of DiGraphs, D is defined as the diagonal in-
degree matrix or diagonal out-degree matrix according to the value
of "indegree")

INPUT:

* "weighted" -- Binary variable :

* If "True", the weighted adjacency matrix is used for M,
and the diagonal matrix D takes into account the weight of
edges (replace in the definition "degree" by "sum of the
incident edges" ).

* Else, each edge is assumed to have weight 1.

Default is to take weights into consideration if and only if
the graph is weighted.

* "indegree" -- Binary variable  :

* If "True", each diagonal entry of D is equal to the in-
degree of the corresponding vertex.

* Else, each diagonal entry of D is equal to the out-degree
of the corresponding vertex.

By default, "indegree" is set to "True"

( This variable only matters when the graph is a digraph )

* "normalized" -- Binary variable :

* If "True", the returned matrix is D^{-1/2}(D-M)D^{-1/2}, a
normalized version of the Laplacian matrix. (More
accurately, the normalizing matrix used is equal to D^{-1/2}
only for non-isolated vertices.  If vertex i is isolated,
then diagonal entry i in the matrix is 1, rather than a
division by zero.)

* Else, the matrix D-M is returned

Note that any additional keywords will be passed on to either the

AUTHORS:

* Tom Boothby

* Jason Grout

EXAMPLES:

sage: G = Graph(sparse=True)
sage: M = G.kirchhoff_matrix(weighted=True); M
[ 8 -1 -3 -4]
[-1  3 -2  0]
[-3 -2  5  0]
[-4  0  0  4]
sage: M = G.kirchhoff_matrix(); M
[ 3 -1 -1 -1]
[-1  2 -1  0]
[-1 -1  2  0]
[-1  0  0  1]
sage: M = G.laplacian_matrix(normalized=True); M
[                   1 -1/6*sqrt(3)*sqrt(2) -1/6*sqrt(3)*sqrt(2)         -1/3*sqrt(3)]
[-1/6*sqrt(3)*sqrt(2)                    1                 -1/2                    0]
[-1/6*sqrt(3)*sqrt(2)                 -1/2                    1                    0]
[        -1/3*sqrt(3)                    0                    0                    1]

sage: Graph({0:[],1:[2]}).laplacian_matrix(normalized=True)
[ 0  0  0]
[ 0  1 -1]
[ 0 -1  1]

A weighted directed graph with loops, changing the variable
"indegree"

sage: G = DiGraph({1:{1:2,2:3}, 2:{1:4}}, weighted=True,sparse=True)
sage: G.laplacian_matrix()
[ 4 -3]
[-4  3]

sage: G = DiGraph({1:{1:2,2:3}, 2:{1:4}}, weighted=True,sparse=True)
sage: G.laplacian_matrix(indegree=False)
[ 3 -3]
[-4  4]

g.layout?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.layout(self, layout=None, pos=None, dim=2, save_pos=False, **kwds)
Docstring :
Returns a layout for the vertices of this graph.

INPUT:

* layout -- one of "acyclic", "circular", "ranked",
"graphviz", "planar", "spring", or "tree"

* pos -- a dictionary of positions or None (the default)

* save_pos -- a boolean

* layout options -- (see below)

If "layout=algorithm" is specified, this algorithm is used to
compute the positions.

Otherwise, if "pos" is specified, use the given positions.

Otherwise, try to fetch previously computed and saved positions.

Otherwise use the default layout (usually the spring layout)

If "save_pos = True", the layout is saved for later use.

EXAMPLES:

sage: g = digraphs.ButterflyGraph(1)
sage: g.layout()
{('0', 0): [2.22..., 0.832...],
('0', 1): [0.833..., 0.543...],
('1', 0): [1.12..., -0.830...],
('1', 1): [2.50..., -0.545...]}

sage: g.layout(layout="acyclic_dummy", save_pos=True)
{('0', 0): [0.3..., 0],
('0', 1): [0.3..., 1],
('1', 0): [0.6..., 0],
('1', 1): [0.6..., 1]}

sage: g.layout(dim = 3)
{('0', 0): [2.02..., 0.528..., 0.343...],
('0', 1): [1.61..., 0.260..., -0.927...],
('1', 0): [0.674..., -0.528..., -0.343...],
('1', 1): [1.07..., -0.260..., 0.927...]}

Here is the list of all the available layout options:

sage: from sage.graphs.graph_plot import layout_options
sage: for key, value in list(sorted(layout_options.iteritems())):
....:     print("option {} : {}".format(key, value))
option by_component : Whether to do the spring layout by connected component -- a boolean.
option dim : The dimension of the layout -- 2 or 3.
option heights : A dictionary mapping heights to the list of vertices at this height.
option iterations : The number of times to execute the spring layout algorithm.
option layout : A layout algorithm -- one of : "acyclic", "circular" (plots the graph with vertices evenly distributed on a circle), "ranked", "graphviz", "planar", "spring" (traditional spring layout, using the graph's current positions as initial positions), or "tree" (the tree will be plotted in levels, depending on minimum distance for the root).
option prog : Which graphviz layout program to use -- one of "circo", "dot", "fdp", "neato", or "twopi".
option save_pos : Whether or not to save the computed position for the graph.
option spring : Use spring layout to finalize the current layout.
option tree_orientation : The direction of tree branches -- 'up', 'down', 'left' or 'right'.
option tree_root : A vertex designation for drawing trees. A vertex of the tree to be used as the root for the layout='tree' option. If no root is specified, then one is chosen close to the center of the tree. Ignored unless layout='tree'

Some of them only apply to certain layout algorithms. For details,
see "layout_acyclic()", "layout_planar()", "layout_circular()",
"layout_spring()", ...

..warning: unknown optional arguments are silently ignored

..warning: "graphviz" and "dot2tex" are currently required to
obtain a nice 'acyclic' layout. See "layout_graphviz()" for
installation instructions.

A subclass may implement another layout algorithm blah, by
implementing a method ".layout_blah". It may override the default
layout by overriding "layout_default()", and similarly override the
predefined layouts.

TODO: use this feature for all the predefined graphs classes (like
for the Petersen graph, ...), rather than systematically building
the layout at construction time.

{('1', 1): [1.9663573868248632, -0.8383397326854385], ('0', 0): [0.7106046242716577, -0.46208299964206273], ('1', 0): [2.1318138728149734, 0.46208299965967126], ('0', 1): [0.8760611105219895, 0.8383397326678297]}
g = digraphs.ButterflyGraph(1)
g.layout()

{('1', 1): [1.9663573868248632, -0.8383397326854385], ('0', 0): [0.7106046242716577, -0.46208299964206273], ('1', 0): [2.1318138728149734, 0.46208299965967126], ('0', 1): [0.8760611105219895, 0.8383397326678297]}
g.level_sets?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.level_sets()
Docstring :
Returns the level set decomposition of the digraph.

OUTPUT:

* a list of non empty lists of vertices of this graph

The level set decomposition of the digraph is a list l such that
the level l[i] contains all the vertices having all their
predecessors in the levels l[j] for j<i, and at least one in level
l[i-1] (unless i=0).

The level decomposition contains exactly the vertices not occuring
in any cycle of the graph. In particular, the graph is acyclic if
and only if the decomposition forms a set partition of its
vertices, and we recover the usual level set decomposition of the
corresponding poset.

EXAMPLES:

sage: H = DiGraph({0:[1,2],1:[3],2:[3],3:[],5:[1,6],6:[2,3]})
sage: H.level_sets()
[[0, 5], [1, 6], [2], [3]]

sage: H = DiGraph({0:[1,2],1:[3],2:[3],3:[1],5:[1,6],6:[2,3]})
sage: H.level_sets()
[[0, 5], [6], [2]]

This routine is mostly used for Hasse diagrams of posets:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0:[1,2],1:[3],2:[3],3:[]})
sage: [len(x) for x in H.level_sets()]
[1, 2, 1]

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0:[1,2], 1:[3], 2:[4], 3:[4]})
sage: [len(x) for x in H.level_sets()]
[1, 2, 1, 1]

Complexity: O(n+m) in time and O(n) in memory (besides the storage
of the graph itself), where n and m are respectively the number of
vertices and edges (assuming that appending to a list is constant
time, which it is not quite).

g.latex_options?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.latex_options()
Docstring :
Returns an instance of "GraphLatex" for the graph.

Changes to this object will affect the LaTeX version of the graph.
For a full explanation of how to use LaTeX to render graphs, see
the introduction to the "graph_latex" module.

EXAMPLES:

sage: g = graphs.PetersenGraph()
sage: opts = g.latex_options()
sage: opts
LaTeX options for Petersen graph: {}
sage: opts.set_option('tkz_style', 'Classic')
sage: opts
LaTeX options for Petersen graph: {'tkz_style': 'Classic'}

g.lex_BFS?

g.min_spanning_tree?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.min_spanning_tree(self, weight_function=None, algorithm='Prim_Boost', starting_vertex=None, check=False)
Docstring :
Returns the edges of a minimum spanning tree.

At the moment, no algorithm for directed graph is implemented: if
the graph is directed, a minimum spanning tree of the corresponding
undirected graph is returned.

We expect all weights of the graph to be convertible to float.
Otherwise, an exception is raised.

INPUT:

* "weight_function" (function) - a function that inputs an edge
"e" and outputs its weight. An edge has the form "(u,v,l)", where
"u" and "v" are vertices, "l" is a label (that can be of any
kind). The "weight_function" can be used to transform the label
into a weight (note that, if the weight returned is not
convertible to a float, an error is raised). In particular:

* if "weight_function" is not "None", the weight of an edge "e"
is "weight_function(e)";

* if "weight_function" is "None" (default) and "g" is weighted
(that is, "g.weighted()==True"), for each edge "e=(u,v,l)", we
set weight "l";

* if "weight_function" is "None" and "g" is not weighted, we
set all weights to 1 (hence, the output can be any spanning
tree).

* "algorithm" -- The algorithm to use in computing a minimum
spanning tree of "G". The following algorithms are supported:

* ""Prim_Boost"" (default) -- Prim's algorithm (Boost
implementation).

* ""Prim_fringe"" -- a variant of Prim's algorithm.
""Prim_fringe"" ignores the labels on the edges.

* ""Prim_edge"" -- a variant of Prim's algorithm.

* ""Kruskal"" -- Kruskal's algorithm.

* ""Kruskal_Boost"" -- Kruskal's algorithm (Boost
implementation).

* "NetworkX" -- Uses NetworkX's minimum spanning tree
implementation.

* "starting_vertex" -- The vertex from which to begin the search
for a minimum spanning tree (available only for "Prim_fringe" and
"Prim_edge").

* "check" -- Boolean; default: "False". Whether to first perform
sanity checks on the input graph "G". If appropriate, "check" is
passed on to any minimum spanning tree functions that are invoked
from the current method. See the documentation of the
corresponding functions for details on what sort of sanity checks
will be performed.

OUTPUT:

The edges of a minimum spanning tree of "G", if one exists,
otherwise returns the empty list.

* "sage.graphs.spanning_tree.kruskal()"

* "sage.graphs.base.boost_graph.min_spanning_tree()"

EXAMPLES:

Kruskal's algorithm:

sage: g = graphs.CompleteGraph(5)
sage: len(g.min_spanning_tree())
4
sage: weight = lambda e: 1 / ((e[0] + 1) * (e[1] + 1))
sage: g.min_spanning_tree(weight_function=weight)
[(0, 4, None), (1, 4, None), (2, 4, None), (3, 4, None)]
sage: g.min_spanning_tree(weight_function=weight, algorithm='Kruskal_Boost')
[(0, 4, None), (1, 4, None), (2, 4, None), (3, 4, None)]
sage: g = graphs.PetersenGraph()
sage: g.allow_multiple_edges(True)
sage: g.min_spanning_tree()
[(0, 1, None), (0, 4, None), (0, 5, None), (1, 2, None), (1, 6, None), (3, 8, None), (5, 7, None), (5, 8, None), (6, 9, None)]

Prim's algorithm:

sage: g = graphs.CompleteGraph(5)
sage: g.min_spanning_tree(algorithm='Prim_edge', starting_vertex=2, weight_function=weight)
[(0, 4, None), (1, 4, None), (2, 4, None), (3, 4, None)]
sage: g.min_spanning_tree(algorithm='Prim_fringe', starting_vertex=2, weight_function=weight)
[(0, 4, None), (1, 4, None), (2, 4, None), (3, 4, None)]
sage: g.min_spanning_tree(weight_function=weight, algorithm='Prim_Boost')
[(0, 4, None), (1, 4, None), (2, 4, None), (3, 4, None)]

NetworkX algorithm:

sage: g.min_spanning_tree(algorithm='NetworkX')
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None)]

More complicated weights:

sage: G = Graph([(0,1,{'name':'a','weight':1}), (0,2,{'name':'b','weight':3}), (1,2,{'name':'b','weight':1})])
sage: G.min_spanning_tree(weight_function=lambda e: e[2]['weight'])
[(0, 1, {'name': 'a', 'weight': 1}), (1, 2, {'name': 'b', 'weight': 1})]

If the graph is not weighted, edge labels are not considered, even
if they are numbers:

sage: g = Graph([[1,2,1], [1,3,2], [2,3,1]])
sage: g.min_spanning_tree()
[(1, 2, 1), (1, 3, 2)]

In order to use weights, we need to set variable "weighted" to
"True":

sage: g.weighted(True)
sage: g.min_spanning_tree()
[(1, 2, 1), (2, 3, 1)]

g.multicommodity_flow?

g.neighbor_in_iterator?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.neighbor_in_iterator()
Docstring :
Returns an iterator over the in-neighbors of vertex.

An vertex u is an in-neighbor of a vertex v if uv in an edge.

EXAMPLES:

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

g.neighbors_in?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.neighbors_in()
Docstring :
Returns the list of the in-neighbors of a given vertex.

An vertex u is an in-neighbor of a vertex v if uv in an edge.

EXAMPLES:

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

g.edges()

[(0, 1, None), (0, 2, None), (0, 3, None), (1, 0, None), (1, 2, None), (1, 3, None), (2, 0, None), (2, 1, None), (2, 3, None), (3, 0, None), (3, 1, None), (3, 2, None)]
g.neighbors_in(0)

[1, 2, 3]
g.neighbors_out(0)

[1, 2, 3]
g.neighbor_out_iterator?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.neighbor_out_iterator()
Docstring :
Returns an iterator over the out-neighbors of a given vertex.

An vertex u is an out-neighbor of a vertex v if vu in an edge.

EXAMPLES:

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

g.num_edges()

12
g.num_verts()

4
g.order() # Returns the number of vertices.

4
g.out_degree?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.out_degree(self, vertices=None, labels=False)
Docstring :
Same as degree, but for out degree.

EXAMPLES:

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]
sage: D.out_degree(2)
1

g.out_degree(0)

3
g.out_degree_iterator?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.out_degree_iterator(self, vertices=None, labels=False)
Docstring :
Same as degree_iterator, but for out degree.

EXAMPLES:

sage: D = graphs.Grid2dGraph(2,4).to_directed()
sage: for i in D.out_degree_iterator():
....:     print(i)
3
3
2
2
3
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, 3), 2)
((1, 1), 3)
((1, 3), 2)
((1, 0), 2)
((0, 2), 3)

g.outgoing_edges(0)

[(0, 1, None), (0, 2, None), (0, 3, None)]
g.outgoing_edge_iterator?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.outgoing_edge_iterator(self, vertices, labels=True)
Docstring :
Return an iterator over all departing edges from vertices.

INPUT:

* "vertices" -- a vertex or a list of vertices

* "labels" (boolean) -- whether to return edges as pairs of
vertices, or as triples containing the labels.

EXAMPLES:

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)

g.parent()

<class 'sage.graphs.digraph.DiGraph'>
g.plot?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/misc/decorators.py
Signature : g.plot(**kwds)
Docstring :
Returns a graphics object representing the (di)graph.

INPUT:

* "pos" - an optional positioning dictionary

* "layout" - what kind of layout to use, takes precedence over
pos

* 'circular' -- plots the graph with vertices evenly
distributed on a circle

* 'spring' - uses the traditional spring layout, using the
graph's current positions as initial positions

* 'tree' - the (di)graph must be a tree. One can specify the
root of the tree using the keyword tree_root, otherwise a
root will be selected at random. Then the tree will be
plotted in levels, depending on minimum distance for the
root.

* "vertex_labels" - whether to print vertex labels

* "edge_labels" - whether to print edge labels. By default,
False, but if True, the result of str(l) is printed on the edge
for each label l. Labels equal to None are not printed (to set
edge labels, see set_edge_label).

* "vertex_size" - size of vertices displayed

* "vertex_shape" - the shape to draw the vertices, for example
""o"" for circle or ""s"" for square. Whole list is available at
http://matplotlib.org/api/markers_api.html. (Not available for
multiedge digraphs.)

* "graph_border" - whether to include a box around the graph

* "vertex_colors" - optional dictionary to specify vertex colors:
each key is a color recognizable by matplotlib, and each
corresponding entry is a list of vertices. If a vertex is not
listed, it looks invisible on the resulting plot (it doesn't get
drawn).

* "edge_colors" - a dictionary specifying edge colors: each key
is a color recognized by matplotlib, and each entry is a list of
edges.

* "partition" - a partition of the vertex set. if specified, plot
will show each cell in a different color. vertex_colors takes
precedence.

* "talk" - if true, prints large vertices with white backgrounds
so that labels are legible on slides

* "iterations" - how many iterations of the spring layout
algorithm to go through, if applicable

* "color_by_label" - a boolean or dictionary or function
(default: False) whether to color each edge with a different
color according to its label; the colors are chosen along a
rainbow, unless they are specified by a function or dictionary
mapping labels to colors; this option is incompatible with
"edge_color" and "edge_colors".

* "heights" - if specified, this is a dictionary from a set of
floating point heights to a set of vertices

* "edge_style" - keyword arguments passed into the edge-drawing
routine.  This currently only works for directed graphs, since we
pass off the undirected graph to networkx

* "tree_root" - a vertex of the tree to be used as the root for
the layout="tree" option. If no root is specified, then one is
chosen at random. Ignored unless layout='tree'.

* "tree_orientation" - "up" or "down" (default is "down"). If
"up" (resp., "down"), then the root of the tree will appear on
the bottom (resp., top) and the tree will grow upwards (resp.
downwards). Ignored unless layout='tree'.

* "save_pos" - save position computed during plotting

Note:

* This method supports any parameter accepted by
"sage.plot.graphics.Graphics.show()".

* See the documentation of the "sage.graphs.graph_plot" module
for information and examples of how to define parameters that
will be applied to **all** graph plots.

* Default parameters for this method *and a specific graph* can
also be set through the "options" mechanism. For more
information on this different way to set default parameters,
see the help of the "options decorator".

LaTeX to produce an image of a graph.

EXAMPLES:

sage: from sage.graphs.graph_plot import graphplot_options
sage: list(sorted(graphplot_options.iteritems()))
[...]

sage: from math import sin, cos, pi
sage: P = graphs.PetersenGraph()
sage: d = {'#FF0000':[0,5], '#FF9900':[1,6], '#FFFF00':[2,7], '#00FF00':[3,8], '#0000FF':[4,9]}
sage: pos_dict = {}
sage: for i in range(5):
...    x = float(cos(pi/2 + ((2*pi)/5)*i))
...    y = float(sin(pi/2 + ((2*pi)/5)*i))
...    pos_dict[i] = [x,y]
...
sage: for i in range(10)[5:]:
...    x = float(0.5*cos(pi/2 + ((2*pi)/5)*i))
...    y = float(0.5*sin(pi/2 + ((2*pi)/5)*i))
...    pos_dict[i] = [x,y]
...
sage: pl = P.plot(pos=pos_dict, vertex_colors=d)
sage: pl.show()

sage: C = graphs.CubeGraph(8)
sage: P = C.plot(vertex_labels=False, vertex_size=0, graph_border=True)
sage: P.show()

sage: G = graphs.HeawoodGraph()
sage: for u,v,l in G.edges():
...    G.set_edge_label(u,v,'(' + str(u) + ',' + str(v) + ')')
sage: G.plot(edge_labels=True).show()

sage: D = DiGraph( { 0: [1, 10, 19], 1: [8, 2], 2: [3, 6], 3: [19, 4], 4: [17, 5], 5: [6, 15], 6: [7], 7: [8, 14], 8: [9], 9: [10, 13], 10: [11], 11: [12, 18], 12: [16, 13], 13: [14], 14: [15], 15: [16], 16: [17], 17: [18], 18: [19], 19: []} , sparse=True)
sage: for u,v,l in D.edges():
...    D.set_edge_label(u,v,'(' + str(u) + ',' + str(v) + ')')
sage: D.plot(edge_labels=True, layout='circular').show()

sage: from sage.plot.colors import rainbow
sage: C = graphs.CubeGraph(5)
sage: R = rainbow(5)
sage: edge_colors = {}
sage: for i in range(5):
...    edge_colors[R[i]] = []
sage: for u,v,l in C.edges():
...    for i in range(5):
...        if u[i] != v[i]:
...            edge_colors[R[i]].append((u,v,l))
sage: C.plot(vertex_labels=False, vertex_size=0, edge_colors=edge_colors).show()

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

sage: G = graphs.PetersenGraph()
sage: G.allow_loops(True)
sage: G.show()

sage: D = DiGraph({0:[0,1], 1:[2], 2:[3]}, loops=True)
sage: D.show()
sage: D.show(edge_colors={(0,1,0):[(0,1,None),(1,2,None)],(0,0,0):[(2,3,None)]})

sage: pos = {0:[0.0, 1.5], 1:[-0.8, 0.3], 2:[-0.6, -0.8], 3:[0.6, -0.8], 4:[0.8, 0.3]}
sage: g = Graph({0:[1], 1:[2], 2:[3], 3:[4], 4:[0]})
sage: g.plot(pos=pos, layout='spring', iterations=0)
Graphics object consisting of 11 graphics primitives

sage: G = Graph()
sage: P = G.plot()
sage: P.axes()
False
sage: G = DiGraph()
sage: P = G.plot()
sage: P.axes()
False

sage: G = graphs.PetersenGraph()
sage: G.get_pos()
{0: (6.12..., 1.0...),
1: (-0.95..., 0.30...),
2: (-0.58..., -0.80...),
3: (0.58..., -0.80...),
4: (0.95..., 0.30...),
5: (1.53..., 0.5...),
6: (-0.47..., 0.15...),
7: (-0.29..., -0.40...),
8: (0.29..., -0.40...),
9: (0.47..., 0.15...)}
sage: P = G.plot(save_pos=True, layout='spring')

The following illustrates the format of a position dictionary.

sage: G.get_pos() # currently random across platforms, see #9593
{0: [1.17..., -0.855...],
1: [1.81..., -0.0990...],
2: [1.35..., 0.184...],
3: [1.51..., 0.644...],
4: [2.00..., -0.507...],
5: [0.597..., -0.236...],
6: [2.04..., 0.687...],
7: [1.46..., -0.473...],
8: [0.902..., 0.773...],
9: [2.48..., -0.119...]}

sage: T = list(graphs.trees(7))
sage: t = T[3]
sage: t.plot(heights={0:[0], 1:[4,5,1], 2:[2], 3:[3,6]})
Graphics object consisting of 14 graphics primitives

sage: T = list(graphs.trees(7))
sage: t = T[3]
sage: t.plot(heights={0:[0], 1:[4,5,1], 2:[2], 3:[3,6]})
Graphics object consisting of 14 graphics primitives
sage: t.set_edge_label(0,1,-7)
sage: t.set_edge_label(0,5,3)
sage: t.set_edge_label(0,5,99)
sage: t.set_edge_label(1,2,1000)
sage: t.set_edge_label(3,2,'spam')
sage: t.set_edge_label(2,6,3/2)
sage: t.set_edge_label(0,4,66)
sage: t.plot(heights={0:[0], 1:[4,5,1], 2:[2], 3:[3,6]}, edge_labels=True)
Graphics object consisting of 20 graphics primitives

sage: T = list(graphs.trees(7))
sage: t = T[3]
sage: t.plot(layout='tree')
Graphics object consisting of 14 graphics primitives

sage: t = DiGraph('[email protected]??GO??CO??GO??')
sage: t.plot(layout='tree', tree_root=0, tree_orientation="up")
Graphics object consisting of 22 graphics primitives
sage: D = DiGraph({0:[1,2,3], 2:[1,4], 3:[0]})
sage: D.plot()
Graphics object consisting of 16 graphics primitives

sage: D = DiGraph(multiedges=True,sparse=True)
sage: for i in range(5):
sage: D.plot(edge_labels=True,edge_colors=D._color_by_label())
Graphics object consisting of 34 graphics primitives
sage: D.plot(edge_labels=True, color_by_label={'a':'blue', 'b':'red'}, edge_style='dashed')
Graphics object consisting of 34 graphics primitives

sage: g = Graph({}, loops=True, multiedges=True,sparse=True)
...     (0,1,'e'),(0,1,'f'),(0,1,'f'),(2,1,'g'),(2,2,'h')])
sage: g.plot(edge_labels=True, color_by_label=True, edge_style='dashed')
Graphics object consisting of 22 graphics primitives

sage: S = SupersingularModule(389)
sage: H = S.hecke_matrix(2)
sage: D = DiGraph(H,sparse=True)
sage: P = D.plot()

sage: G=Graph({'a':['a','b','b','b','e'],'b':['c','d','e'],'c':['c','d','d','d'],'d':['e']},sparse=True)
sage: G.show(pos={'a':[0,1],'b':[1,1],'c':[2,0],'d':[1,0],'e':[0,0]})

g.plot3d?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.plot3d(self, bgcolor=(1, 1, 1), vertex_colors=None, vertex_size=0.06, vertex_labels=False, edge_colors=None, edge_size=0.02, edge_size2=0.0325, pos3d=None, color_by_label=False, engine='jmol', **kwds)
Docstring :
Plot a graph in three dimensions.

to produce an image of a graph.

INPUT:

* "bgcolor" - rgb tuple (default: (1,1,1))

* "vertex_size" - float (default: 0.06)

* "vertex_labels" -- a boolean (default: False) whether to
display vertices using text labels instead of spheres

* "vertex_colors" - optional dictionary to specify vertex colors:
each key is a color recognizable by tachyon (rgb tuple (default:
(1,0,0))), and each corresponding entry is a list of vertices. If
a vertex is not listed, it looks invisible on the resulting plot
(it doesn't get drawn).

* "edge_colors" - a dictionary specifying edge colors: each key
is a color recognized by tachyon ( default: (0,0,0) ), and each
entry is a list of edges.

* "color_by_label" - a boolean or dictionary or function
(default: False) whether to color each edge with a different
color according to its label; the colors are chosen along a
rainbow, unless they are specified by a function or dictionary
mapping labels to colors; this option is incompatible with
"edge_color" and "edge_colors".

* "edge_size" - float (default: 0.02)

* "edge_size2" - float (default: 0.0325), used for Tachyon
sleeves

* "pos3d" - a position dictionary for the vertices

* "layout", "iterations", ... - layout options; see "layout()"

* "engine" - which renderer to use. Options:

* "'jmol'" - default

* "'tachyon'"

* "xres" - resolution

* "yres" - resolution

* "**kwds" - passed on to the rendering engine

EXAMPLES:

sage: G = graphs.CubeGraph(5)
sage: G.plot3d(iterations=500, edge_size=None, vertex_size=0.04) # long time
Graphics3d Object

We plot a fairly complicated Cayley graph:

sage: A5 = AlternatingGroup(5); A5
Alternating group of order 5!/2 as a permutation group
sage: G = A5.cayley_graph()
sage: G.plot3d(vertex_size=0.03, edge_size=0.01, vertex_colors={(1,1,1):G.vertices()}, bgcolor=(0,0,0), color_by_label=True, iterations=200) # long time
Graphics3d Object

Some Tachyon examples:

sage: D = graphs.DodecahedralGraph()
sage: P3D = D.plot3d(engine='tachyon')
sage: P3D.show() # long time

sage: G = graphs.PetersenGraph()
sage: G.plot3d(engine='tachyon', vertex_colors={(0,0,1):G.vertices()}).show() # long time

sage: C = graphs.CubeGraph(4)
sage: C.plot3d(engine='tachyon', edge_colors={(0,1,0):C.edges()}, vertex_colors={(1,1,1):C.vertices()}, bgcolor=(0,0,0)).show() # long time

sage: K = graphs.CompleteGraph(3)
sage: K.plot3d(engine='tachyon', edge_colors={(1,0,0):[(0,1,None)], (0,1,0):[(0,2,None)], (0,0,1):[(1,2,None)]}).show() # long time

A directed version of the dodecahedron

sage: D = DiGraph( { 0: [1, 10, 19], 1: [8, 2], 2: [3, 6], 3: [19, 4], 4: [17, 5], 5: [6, 15], 6: [7], 7: [8, 14], 8: [9], 9: [10, 13], 10: [11], 11: [12, 18], 12: [16, 13], 13: [14], 14: [15], 15: [16], 16: [17], 17: [18], 18: [19], 19: []} )
sage: D.plot3d().show() # long time

sage: P = graphs.PetersenGraph().to_directed()
sage: from sage.plot.colors import rainbow
sage: edges = P.edges()
sage: R = rainbow(len(edges), 'rgbtuple')
sage: edge_colors = {}
sage: for i in range(len(edges)):
...       edge_colors[R[i]] = [edges[i]]
sage: P.plot3d(engine='tachyon', edge_colors=edge_colors).show() # long time

sage: G=Graph({'a':['a','b','b','b','e'],'b':['c','d','e'],'c':['c','d','d','d'],'d':['e']},sparse=True)
sage: G.show3d()
Traceback (most recent call last):
...
NotImplementedError: 3D plotting of multiple edges or loops not implemented.

* "plot()"

* "graphviz_string()"

g.random_edge?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.random_edge(**kwds)
Docstring :
Returns a random edge of self.

INPUT:

* "**kwds" - arguments to be passed down to the "edge_iterator"
method.

EXAMPLE:

The returned value is an edge of self:

sage: g = graphs.PetersenGraph()
sage: u,v = g.random_edge(labels=False)
sage: g.has_edge(u,v)
True

As the "edges()" method would, this function returns by default a
triple "(u,v,l)" of values, in which "l" is the label of edge
(u,v):

sage: g.random_edge()
(3, 4, None)

g.random_edge_iterator?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.random_edge_iterator(*args, **kwds)
Docstring :
Return an iterator over random edges of self.

The returned iterator enables to amortize the cost of accessing
random edges, as can be done with multiple calls to method
"random_edge()".

INPUT:

* "*args" and "**kwds" - arguments to be passed down to the
"edge_iterator()" method.

EXAMPLE:

The returned value is an iterator over the edges of self:

sage: g = graphs.PetersenGraph()
sage: it = g.random_edge_iterator()
sage: [g.has_edge(next(it)) for _ in range(5)]
[True, True, True, True, True]

As the "edges()" method would, this function returns by default a
triple "(u,v,l)" of values, in which "l" is the label of edge
"(u,v)":

sage: print(next(g.random_edge_iterator())) # random
(0, 5, None)
sage: print(next(g.random_edge_iterator(labels=False))) # random
(5, 7)

g.random_vertex?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.random_vertex(**kwds)
Docstring :
Returns a random vertex of self.

INPUT:

* "**kwds" - arguments to be passed down to the "vertex_iterator"
method.

EXAMPLE:

The returned value is a vertex of self:

sage: g = graphs.PetersenGraph()
sage: v = g.random_vertex()
sage: v in g
True

g.random_vertex_iterator?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.random_vertex_iterator(*args, **kwds)
Docstring :
Return an iterator over random vertices of self.

The returned iterator enables to amortize the cost of accessing
random vertices, as can be done with multiple calls to method
"random_vertex()".

INPUT:

* "*args" and "**kwds" - arguments to be passed down to the
"vertex_iterator()" method.

EXAMPLE:

The returned value is an iterator over the vertices of self:

sage: g = graphs.PetersenGraph()
sage: it = g.random_vertex_iterator()
sage: [next(it) in g for _ in range(5)]
[True, True, True, True, True]

g.relabel?

g.radius?

g.reverse_edge?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.reverse_edge(self, u, v=None, label=None, inplace=True, multiedges=None)
Docstring :
Reverses the edge from u to v.

INPUT:

* "inplace" -- (default: "True") if "False", a new digraph is
created and returned as output, otherwise "self" is modified.

* "multiedges" -- (default: "None") how to decide what should be
done in case of doubt (for instance when edge (1,2) is to be
reversed in a graph while (2,1) already exists):

* If set to "True", input graph will be forced to allow
parallel edges if necessary and edge (1,2) will appear twice in
the graph.

* If set to "False", only one edge (1,2) will remain in the
graph after (2,1) is reversed. Besides, the label of edge (1,2)
will be overwritten with the label of edge (2,1).

The default behaviour ("multiedges = None") will raise an
exception each time a subjective decision (setting "multiedges"
to "True" or "False") is necessary to perform the operation.

The following forms are all accepted:

* D.reverse_edge( 1, 2 )

* D.reverse_edge( (1, 2) )

* D.reverse_edge( [1, 2] )

* D.reverse_edge( 1, 2, 'label' )

* D.reverse_edge( ( 1, 2, 'label') )

* D.reverse_edge( [1, 2, 'label'] )

* D.reverse_edge( ( 1, 2), label='label') )

EXAMPLES:

If "inplace" is "True" (default value), "self" is modified:

sage: D = DiGraph([(0,1,2)])
sage: D.reverse_edge(0,1)
sage: D.edges()
[(1, 0, 2)]

If "inplace" is "False", "self" is not modified and a new digraph
is returned:

sage: D = DiGraph([(0,1,2)])
sage: re = D.reverse_edge(0,1, inplace=False)
sage: re.edges()
[(1, 0, 2)]
sage: D.edges()
[(0, 1, 2)]

If "multiedges" is "True", "self" will be forced to allow parallel
edges when and only when it is necessary:

sage: D = DiGraph( [(1, 2, 'A'), (2, 1, 'A'), (2, 3, None)] )
sage: D.reverse_edge(1,2, multiedges=True)
sage: D.edges()
[(2, 1, 'A'), (2, 1, 'A'), (2, 3, None)]
sage: D.allows_multiple_edges()
True

Even if "multiedges" is "True", "self" will not be forced to allow
parallel edges when it is not necessary:

sage: D = DiGraph( [(1,2,'A'), (2,1,'A'), (2, 3, None)] )
sage: D.reverse_edge(2,3, multiedges=True)
sage: D.edges()
[(1, 2, 'A'), (2, 1, 'A'), (3, 2, None)]
sage: D.allows_multiple_edges()
False

If user specifies "multiedges = False", "self" will not be forced
to allow parallel edges and a parallel edge will get deleted:

sage: D = DiGraph( [(1, 2, 'A'), (2, 1,'A'), (2, 3, None)] )
sage: D.edges()
[(1, 2, 'A'), (2, 1, 'A'), (2, 3, None)]
sage: D.reverse_edge(1,2, multiedges=False)
sage: D.edges()
[(2, 1, 'A'), (2, 3, None)]

Note that in the following graph, specifying "multiedges = False"
will result in overwriting the label of (1,2) with the label of
(2,1):

sage: D = DiGraph( [(1, 2, 'B'), (2, 1,'A'), (2, 3, None)] )
sage: D.edges()
[(1, 2, 'B'), (2, 1, 'A'), (2, 3, None)]
sage: D.reverse_edge(2,1, multiedges=False)
sage: D.edges()
[(1, 2, 'A'), (2, 3, None)]

If input edge in digraph has weight/label, then the weight/label
should be preserved in the output digraph.  User does not need to
specify the weight/label when calling function:

sage: D = DiGraph([[0,1,2],[1,2,1]], weighted=True)
sage: D.reverse_edge(0,1)
sage: D.edges()
[(1, 0, 2), (1, 2, 1)]
sage: re = D.reverse_edge([1,2],inplace=False)
sage: re.edges()
[(1, 0, 2), (2, 1, 1)]

If "self" has multiple copies (parallel edges) of the input edge,
only 1 of the parallel edges is reversed:

sage: D = DiGraph([(0,1,'01'),(0,1,'01'),(0,1,'cat'),(1,2,'12')], weighted = True, multiedges = true)
sage: re = D.reverse_edge([0,1,'01'],inplace=False)
sage: re.edges()
[(0, 1, '01'), (0, 1, 'cat'), (1, 0, '01'), (1, 2, '12')]

If "self" has multiple copies (parallel edges) of the input edge
but with distinct labels and no input label is specified, only 1 of
the parallel edges is reversed (the edge that is labeled by the
first label on the list returned by "edge_label()"):

sage: D = DiGraph([(0,1,'A'),(0,1,'B'),(0,1,'mouse'),(0,1,'cat')], multiedges = true)
sage: D.edge_label(0,1)
['cat', 'mouse', 'B', 'A']
sage: D.reverse_edge(0,1)
sage: D.edges()
[(0, 1, 'A'), (0, 1, 'B'), (0, 1, 'mouse'), (1, 0, 'cat')]

Finally, an exception is raised when Sage does not know how to
chose between allowing multiple edges and losing some data:

sage: D = DiGraph([(0,1,'A'),(1,0,'B')])
sage: D.reverse_edge(0,1)
Traceback (most recent call last):
...
ValueError: Reversing the given edge is about to create two parallel
edges but input digraph doesn't allow them - User needs to specify
multiedges is True or False.

The following syntax is supported, but note that you must use the
"label" keyword:

sage: D = DiGraph()
sage: D.edges()
[(1, 2, 'label')]
sage: D.reverse_edge((1,2),label ='label')
sage: D.edges()
[(2, 1, 'label')]
sage: D.edges()
[(2, 1, 'label'), ((1, 2), 'label', None)]
sage: D.reverse_edge((1,2), 'label')
sage: D.edges()
[(2, 1, 'label'), ('label', (1, 2), None)]

g.reverse_edges?

File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py
Signature : g.reverse_edges(self, edges, inplace=True, multiedges=None)
Docstring :
Reverses a list of edges.

INPUT:

* "edges" -- a list of edges in the DiGraph.

* "inplace" -- (default: "True") if "False", a new digraph is
created and returned as output, otherwise "self" is modified.

* "multiedges" -- (default: "None") if "True", input graph will
be forced to allow parallel edges when necessary (for more
information see the documentation of "reverse_edge()")

EXAMPLES:

If "inplace" is "True" (default value), "self" is modified:

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

If "inplace" is "False", "self" is not modified and a new digraph
is returned:

sage: D = DiGraph ([(0,1,'A'),(1,0,'B'),(1,2,'C')])
sage: re = D.reverse_edges( [ (0,1), (1,2) ],
...                         inplace = False,
...                         multiedges = True)
sage: re.edges()
[(1, 0, 'A'), (1, 0, 'B'), (2, 1, 'C')]
sage: D.edges()
[(0, 1, 'A'), (1, 0, 'B'), (1, 2, 'C')]
sage: D.allows_multiple_edges()
False
sage: re.allows_multiple_edges()
True

If "multiedges" is "True", "self" will be forced to allow parallel
edges when and only when it is necessary:

sage: D = DiGraph( [(1, 2, 'A'), (2, 1, 'A'), (2, 3, None)] )
sage: D.reverse_edges([(1,2),(2,3)], multiedges=True)
sage: D.edges()
[(2, 1, 'A'), (2, 1, 'A'), (3, 2, None)]
sage: D.allows_multiple_edges()
True

Even if "multiedges" is "True", "self" will not be forced to allow
parallel edges when it is not necessary:

sage: D = DiGraph( [(1, 2, 'A'), (2, 1, 'A'), (2,3, None)] )
sage: D.reverse_edges(`