Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download

DigraphDocsJumpStart

Views: 163

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 Signature : g.add_edges() 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() sage: H.add_edges( G.edge_iterator() ); H Graph on 20 vertices sage: G = graphs.DodecahedralGraph().to_directed() sage: H = DiGraph() sage: H.add_edges( G.edge_iterator() ); H Digraph on 20 vertices sage: H.add_edges(iter([])) sage: H = Graph() sage: H.add_edges([(0,1),(0,2)]) 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() g.add_edges([(0,1)]) 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 See also: * "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 an optimal valuation of the edges. For more information, see the 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 "MixedIntegerLinearProgram.solve" for more information. 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 "adjacency_matrix" or "weighted_adjacency_matrix" method. AUTHORS: * Tom Boothby * Jason Grout EXAMPLES: sage: G = Graph(sparse=True) sage: G.add_edges([(0,1,1),(1,2,2),(0,2,3),(0,3,4)]) sage: M = G.kirchhoff_matrix(weighted=True); M [ 8 -1 -3 -4] [-1 3 -2 0] [-3 -2 5 0] [-4 0 0 4] sage: M = G.kirchhoff_matrix(); M [ 3 -1 -1 -1] [-1 2 -1 0] [-1 -1 2 0] [-1 0 0 1] sage: M = G.laplacian_matrix(normalized=True); M [ 1 -1/6*sqrt(3)*sqrt(2) -1/6*sqrt(3)*sqrt(2) -1/3*sqrt(3)] [-1/6*sqrt(3)*sqrt(2) 1 -1/2 0] [-1/6*sqrt(3)*sqrt(2) -1/2 1 0] [ -1/3*sqrt(3) 0 0 1] sage: Graph({0:[],1:[2]}).laplacian_matrix(normalized=True) [ 0 0 0] [ 0 1 -1] [ 0 -1 1] A weighted directed graph with loops, changing the variable "indegree" sage: G = DiGraph({1:{1:2,2:3}, 2:{1:4}}, weighted=True,sparse=True) sage: G.laplacian_matrix() [ 4 -3] [-4 3] sage: G = DiGraph({1:{1:2,2:3}, 2:{1:4}}, weighted=True,sparse=True) sage: G.laplacian_matrix(indegree=False) [ 3 -3] [-4 4]
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. See also: * "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.add_edges(g.edges()) 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". * See also the "sage.graphs.graph_latex" module for ways to use 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.add_edge(0,0) 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('JCC???@A??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): ... D.add_edge((i,i+1,'a')) ... D.add_edge((i,i-1,'b')) 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) sage: g.add_edges([(0,0,'a'),(0,0,'b'),(0,1,'c'),(0,1,'d'), ... (0,1,'e'),(0,1,'f'),(0,1,'f'),(2,1,'g'),(2,2,'h')]) sage: 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. See also the "sage.graphs.graph_latex" module for ways to use LaTeX 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. See also: * "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.add_edge((1,2), label='label') sage: D.edges() [(1, 2, 'label')] sage: D.reverse_edge((1,2),label ='label') sage: D.edges() [(2, 1, 'label')] sage: D.add_edge((1,2),'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()") See also: "reverse_edge()" - Reverses a single 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([(2,3)], multiedges=True) sage: D.edges() [(1, 2, 'A'), (2, 1, 'A'), (3, 2, None)] sage: D.allows_multiple_edges() False If "multiedges" is "False", "self" will not be forced to allow parallel edges and an edge will get deleted: sage: D = DiGraph( [(1,2), (2,1)] ) sage: D.edges() [(1, 2, None), (2, 1, None)] sage: D.reverse_edges([(1,2)], multiedges=False) sage: D.edges() [(2, 1, 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,'01'),(1,2,1),(2,3,'23')], weighted = True) sage: D.reverse_edges([(0,1,'01'),(1,2),(2,3)]) sage: D.edges() [(1, 0, '01'), (2, 1, 1), (3, 2, '23')]
g.set_edge_label?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.set_edge_label() Docstring : Set the edge label of a given edge. Note: There can be only one edge from u to v for this to make sense. Otherwise, an error is raised. INPUT: * "u, v" - the vertices (and direction if digraph) of the edge * "l" - the new label EXAMPLES: sage: SD = DiGraph( { 1:[18,2], 2:[5,3], 3:[4,6], 4:[7,2], 5:[4], 6:[13,12], 7:[18,8,10], 8:[6,9,10], 9:[6], 10:[11,13], 11:[12], 12:[13], 13:[17,14], 14:[16,15], 15:[2], 16:[13], 17:[15,13], 18:[13] }, sparse=True) sage: SD.set_edge_label(1, 18, 'discrete') sage: SD.set_edge_label(4, 7, 'discrete') sage: SD.set_edge_label(2, 5, 'h = 0') sage: SD.set_edge_label(7, 18, 'h = 0') sage: SD.set_edge_label(7, 10, 'aut') sage: SD.set_edge_label(8, 10, 'aut') sage: SD.set_edge_label(8, 9, 'label') sage: SD.set_edge_label(8, 6, 'no label') sage: SD.set_edge_label(13, 17, 'k > h') sage: SD.set_edge_label(13, 14, 'k = h') sage: SD.set_edge_label(17, 15, 'v_k finite') sage: SD.set_edge_label(14, 15, 'v_k m.c.r.') sage: posn = {1:[ 3,-3], 2:[0,2], 3:[0, 13], 4:[3,9], 5:[3,3], 6:[16, 13], 7:[6,1], 8:[6,6], 9:[6,11], 10:[9,1], 11:[10,6], 12:[13,6], 13:[16,2], 14:[10,-6], 15:[0,-10], 16:[14,-6], 17:[16,-10], 18:[6,-4]} sage: SD.plot(pos=posn, vertex_size=400, vertex_colors={'#FFFFFF':range(1,19)}, edge_labels=True).show() # long time sage: G = graphs.HeawoodGraph() sage: for u,v,l in G.edges(): ... G.set_edge_label(u,v,'(' + str(u) + ',' + str(v) + ')') sage: G.edges() [(0, 1, '(0,1)'), (0, 5, '(0,5)'), (0, 13, '(0,13)'), ... (11, 12, '(11,12)'), (12, 13, '(12,13)')] sage: g = Graph({0: [0,1,1,2]}, loops=True, multiedges=True, sparse=True) sage: g.set_edge_label(0,0,'test') sage: g.edges() [(0, 0, 'test'), (0, 1, None), (0, 1, None), (0, 2, None)] sage: g.add_edge(0,0,'test2') sage: g.set_edge_label(0,0,'test3') Traceback (most recent call last): ... RuntimeError: Cannot set edge label, since there are multiple edges from 0 to 0. sage: dg = DiGraph({0 : [1], 1 : [0]}, sparse=True) sage: dg.set_edge_label(0,1,5) sage: dg.set_edge_label(1,0,9) sage: dg.outgoing_edges(1) [(1, 0, 9)] sage: dg.incoming_edges(1) [(0, 1, 5)] sage: dg.outgoing_edges(0) [(0, 1, 5)] sage: dg.incoming_edges(0) [(1, 0, 9)] sage: G = Graph({0:{1:1}}, sparse=True) sage: G.num_edges() 1 sage: G.set_edge_label(0,1,1) sage: G.num_edges() 1
g.set_edge_label(0,1,'hi') print g.edges()
[(0, 1, 'hi'), (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.set_edge_label(0,1,'shut the f*(-#| up!') print g.edges()
[(0, 1, 'shut the f*(-#| up!'), (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.set_planar_positions?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.set_planar_positions(self, test=False, **kwds) Docstring : Compute a planar layout for self using Schnyder's algorithm, and save it as default layout. EXAMPLES: sage: g = graphs.CycleGraph(7) sage: g.set_planar_positions(test=True) True This method is deprecated since Sage-4.4.1.alpha2. Please use instead: sage: g.layout(layout = "planar", save_pos = True) {0: [1, 1], 1: [2, 2], 2: [3, 2], 3: [1, 4], 4: [5, 1], 5: [0, 5], 6: [1, 0]}
g.set_pos?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.set_pos(self, pos, dim=2) Docstring : Sets the position dictionary, a dictionary specifying the coordinates of each vertex. EXAMPLES: Note that set_pos will allow you to do ridiculous things, which will not blow up until plotting: sage: G = graphs.PetersenGraph() sage: G.get_pos() {0: (..., ...), ... 9: (..., ...)} sage: G.set_pos('spam') sage: P = G.plot() Traceback (most recent call last): ... TypeError: string indices must be integers, not str
g.shortest_path?
g.show?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.show(self, method='matplotlib', **kwds) Docstring : Shows the (di)graph. INPUT: * "method" -- set to ""matplotlib"" (default) to display the graph using matplotlib, or to ""js"" to visualize it in a browser using d3.js. * Any other argument supported by the drawing functions: * ""matplotlib"" -- see "GenericGraph.plot" and "sage.plot.graphics.Graphics.show()". * ""js"" -- see "gen_html_code()". EXAMPLES: sage: C = graphs.CubeGraph(8) sage: P = C.plot(vertex_labels=False, vertex_size=0, graph_border=True) sage: P.show() # long time (3s on sage.math, 2011)
g.sinks?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py Signature : g.sinks() Docstring : Returns a list of sinks of the digraph. OUTPUT: * list, the vertices of the digraph that have no edges beginning at them EXAMPLES: sage: G = DiGraph({1:{3:['a']}, 2:{3:['b']}}) sage: G.sinks() [3] sage: T = DiGraph({1:{}}) sage: T.sinks() [1]
g.sinks()
[]
g.sources?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py Signature : g.sources() Docstring : Returns a list of sources of the digraph. OUTPUT: * list, the vertices of the digraph that have no edges going into them EXAMPLES: sage: G = DiGraph({1:{3:['a']}, 2:{3:['b']}}) sage: G.sources() [1, 2] sage: T = DiGraph({1:{}}) sage: T.sources() [1]
g.sources()
[]
g.size?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.size() Docstring : Returns the number of edges. EXAMPLES: sage: G = graphs.PetersenGraph() sage: G.size() 15
g.size()
12
g.sinks() g.sources()
[] []
g.strongly_connected_component_containing_vertex?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py Signature : g.strongly_connected_component_containing_vertex() Docstring : Returns the strongly connected component containing a given vertex INPUT: * "v" -- a vertex EXAMPLE: In the symmetric digraph of a graph, the strongly connected components are the connected components: sage: g = graphs.PetersenGraph() sage: d = DiGraph(g) sage: d.strongly_connected_component_containing_vertex(0) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
g.strongly_connected_components_digraph?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/digraph.py Signature : g.strongly_connected_components_digraph(self, keep_labels=False) Docstring : Returns the digraph of the strongly connected components INPUT: * "keep_labels" -- boolean (default: False) The digraph of the strongly connected components of a graph G has a vertex per strongly connected component included in G. There is an edge from a component C_1 to a component C_2 if there is an edge from one to the other in G. EXAMPLE: Such a digraph is always acyclic sage: g = digraphs.RandomDirectedGNP(15,.1) sage: scc_digraph = g.strongly_connected_components_digraph() sage: scc_digraph.is_directed_acyclic() True The vertices of the digraph of strongly connected components are exactly the strongly connected components: sage: g = digraphs.ButterflyGraph(2) sage: scc_digraph = g.strongly_connected_components_digraph() sage: g.is_directed_acyclic() True sage: all([ Set(scc) in scc_digraph.vertices() for scc in g.strongly_connected_components()]) True The following digraph has three strongly connected components, and the digraph of those is a chain: sage: g = DiGraph({0:{1:"01", 2: "02", 3: "03"}, 1: {2: "12"}, 2:{1: "21", 3: "23"}}) sage: scc_digraph = g.strongly_connected_components_digraph() sage: scc_digraph.vertices() [{0}, {3}, {1, 2}] sage: scc_digraph.edges() [({0}, {1, 2}, None), ({0}, {3}, None), ({1, 2}, {3}, None)] By default, the labels are discarded, and the result has no loops nor multiple edges. If "keep_labels" is "True", then the labels are kept, and the result is a multi digraph, possibly with multiple edges and loops. However, edges in the result with same source, target, and label are not duplicated (see the edges from 0 to the strongly connected component {1,2} below): sage: g = DiGraph({0:{1:"0-12", 2: "0-12", 3: "0-3"}, 1: {2: "1-2", 3: "1-3"}, 2:{1: "2-1", 3: "2-3"}}) sage: scc_digraph = g.strongly_connected_components_digraph(keep_labels = True) sage: scc_digraph.vertices() [{0}, {3}, {1, 2}] sage: scc_digraph.edges() [({0}, {1, 2}, '0-12'), ({0}, {3}, '0-3'), ({1, 2}, {1, 2}, '1-2'), ({1, 2}, {1, 2}, '2-1'), ({1, 2}, {3}, '1-3'), ({1, 2}, {3}, '2-3')]
g.szeged_index?
g.tensor_product?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.tensor_product() Docstring : Returns the tensor product of self and other. The tensor product of G and H is the graph L with vertex set V(L) equal to the Cartesian product of the vertices V(G) and V(H), and ((u,v), (w,x)) is an edge iff - (u, w) is an edge of self, and - (v, x) is an edge of other. The tensor product is also known as the categorical product and the kronecker product (refering to the kronecker matrix product). See https://en.wikipedia.org/wiki/Kronecker_product. EXAMPLES: sage: Z = graphs.CompleteGraph(2) sage: C = graphs.CycleGraph(5) sage: T = C.tensor_product(Z); T Graph on 10 vertices sage: T.size() 10 sage: T.plot() # long time Graphics object consisting of 21 graphics primitives sage: D = graphs.DodecahedralGraph() sage: P = graphs.PetersenGraph() sage: T = D.tensor_product(P); T Graph on 200 vertices sage: T.size() 900 sage: T.plot() # long time Graphics object consisting of 1101 graphics primitives
g.to_dictionary?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.to_dictionary(self, edge_labels=False, multiple_edges=False) Docstring : Returns the graph as a dictionary. INPUT: * "edge_labels" (boolean) -- whether to include edge labels in the output. * "multiple_edges" (boolean) -- whether to include multiple edges in the output. OUTPUT: The output depends on the input: * If "edge_labels == False" and "multiple_edges == False", the output is a dictionary associating to each vertex the list of its neighbors. * If "edge_labels == False" and "multiple_edges == True", the output is a dictionary the same as previously with one difference: the neighbors are listed with multiplicity. * If "edge_labels == True" and "multiple_edges == False", the output is a dictionary associating to each vertex u [a dictionary associating to each vertex v incident to u the label of edge (u,v)]. * If "edge_labels == True" and "multiple_edges == True", the output is a dictionary associating to each vertex u [a dictionary associating to each vertex v incident to u [the list of labels of all edges between u and v]]. Note: When used on directed graphs, the explanations above can be understood by replacing the word "neigbours" by "out-neighbors" EXAMPLES: sage: g = graphs.PetersenGraph().to_dictionary() sage: [(key, sorted(g[key])) for key in g] [(0, [1, 4, 5]), (1, [0, 2, 6]), (2, [1, 3, 7]), (3, [2, 4, 8]), (4, [0, 3, 9]), (5, [0, 7, 8]), (6, [1, 8, 9]), (7, [2, 5, 9]), (8, [3, 5, 6]), (9, [4, 6, 7])] sage: graphs.PetersenGraph().to_dictionary(multiple_edges=True) {0: [1, 4, 5], 1: [0, 2, 6], 2: [1, 3, 7], 3: [2, 4, 8], 4: [0, 3, 9], 5: [0, 7, 8], 6: [1, 8, 9], 7: [2, 5, 9], 8: [3, 5, 6], 9: [4, 6, 7]} sage: graphs.PetersenGraph().to_dictionary(edge_labels=True) {0: {1: None, 4: None, 5: None}, 1: {0: None, 2: None, 6: None}, 2: {1: None, 3: None, 7: None}, 3: {2: None, 4: None, 8: None}, 4: {0: None, 3: None, 9: None}, 5: {0: None, 7: None, 8: None}, 6: {1: None, 8: None, 9: None}, 7: {2: None, 5: None, 9: None}, 8: {3: None, 5: None, 6: None}, 9: {4: None, 6: None, 7: None}} sage: graphs.PetersenGraph().to_dictionary(edge_labels=True,multiple_edges=True) {0: {1: [None], 4: [None], 5: [None]}, 1: {0: [None], 2: [None], 6: [None]}, 2: {1: [None], 3: [None], 7: [None]}, 3: {2: [None], 4: [None], 8: [None]}, 4: {0: [None], 3: [None], 9: [None]}, 5: {0: [None], 7: [None], 8: [None]}, 6: {1: [None], 8: [None], 9: [None]}, 7: {2: [None], 5: [None], 9: [None]}, 8: {3: [None], 5: [None], 6: [None]}, 9: {4: [None], 6: [None], 7: [None]}}
g.topological_sort?
g.traveling_salesman_problem?
g.triangles_count?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.triangles_count(self, algorithm=None) Docstring : Returns the number of triangles in the (di)graph. For digraphs, we count the number of directed circuit of length 3. INPUT: * "algorithm" -- (default: "None") specifies the algorithm to use (note that only "'iter'" is available for directed graphs): * "'sparse_copy'" -- counts the triangles in a sparse copy of the graph (see "sage.graphs.base.static_sparse_graph"). Calls "static_sparse_graph.triangles_count" * "'dense_copy'" -- counts the triangles in a dense copy of the graph (see "sage.graphs.base.static_dense_graph"). Calls "static_dense_graph.triangles_count" * "'matrix'" uses the trace of the cube of the adjacency matrix. * "'iter'" iterates over the pairs of neighbors of each vertex. No copy of the graph is performed * "None" -- for undirected graphs, uses ""sparse_copy"" or ""dense_copy"" depending on whether the graph is stored as dense or sparse. For directed graphs, uses "'iter'". EXAMPLES: The Petersen graph is triangle free and thus: sage: G = graphs.PetersenGraph() sage: G.triangles_count() 0 Any triple of vertices in the complete graph induces a triangle so we have: sage: G = graphs.CompleteGraph(150) sage: G.triangles_count() == binomial(150,3) True The 2-dimensional DeBruijn graph of 2 symbols has 2 directed C3: sage: G = digraphs.DeBruijn(2,2) sage: G.triangles_count() 2 The directed n-cycle is trivially triangle free for n > 3: sage: G = digraphs.Circuit(10) sage: G.triangles_count() 0
g.union?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.union(self, other, immutable=None) Docstring : Returns the union of self and other. If the graphs have common vertices, the common vertices will be identified. If one of the two graphs allows loops (or multiple edges), the resulting graph will allow loops (or multiple edges). If both graphs are immutable, the resulting graph is immutable, unless requested otherwise. INPUT: * "immutable" (boolean) -- whether to create a mutable/immutable union. "immutable=None" (default) means that the graphs and their union will behave the same way. See also: * "disjoint_union()" * "join()" EXAMPLES: sage: G = graphs.CycleGraph(3) sage: H = graphs.CycleGraph(4) sage: J = G.union(H); J Graph on 4 vertices sage: J.vertices() [0, 1, 2, 3] sage: J.edges(labels=False) [(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)]
g.vertex_boundary?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.vertex_boundary(self, vertices1, vertices2=None) Docstring : Returns a list of all vertices in the external boundary of vertices1, intersected with vertices2. If vertices2 is None, then vertices2 is the complement of vertices1. This is much faster if vertices1 is smaller than vertices2. The external boundary of a set of vertices is the union of the neighborhoods of each vertex in the set. Note that in this implementation, since vertices2 defaults to the complement of vertices1, if a vertex v has a loop, then vertex_boundary(v) will not contain v. In a digraph, the external boundary of a vertex v are those vertices u with an arc (v, u). EXAMPLES: sage: G = graphs.CubeGraph(4) sage: l = ['0111', '0000', '0001', '0011', '0010', '0101', '0100', '1111', '1101', '1011', '1001'] sage: G.vertex_boundary(['0000', '1111'], l) ['0111', '0001', '0010', '0100', '1101', '1011'] sage: D = DiGraph({0:[1,2], 3:[0]}) sage: D.vertex_boundary([0]) [1, 2]
g.vertex_connectivity?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.vertex_connectivity(self, value_only=True, sets=False, solver=None, verbose=0) Docstring : Returns the vertex connectivity of the graph. For more information, see the Wikipedia article on connectivity. Note: * When the graph is a directed graph, this method actually computes the *strong* connectivity, (i.e. a directed graph is strongly k-connected if there are k disjoint paths between any two vertices u, v). If you do not want to consider strong connectivity, the best is probably to convert your "DiGraph" object to a "Graph" object, and compute the connectivity of this other graph. * By convention, a complete graph on n vertices is n-1 connected. In this case, no certificate can be given as there is no pair of vertices split by a cut of size k-1. For this reason, the certificates returned in this situation are empty. INPUT: * "value_only" -- boolean (default: "True") * When set to "True" (default), only the value is returned. * When set to "False" , both the value and a minimum vertex cut are returned. * "sets" -- boolean (default: "False") * When set to "True", also returns the two sets of vertices that are disconnected by the cut. Implies "value_only=False" * "solver" -- (default: "None") Specify a Linear Program (LP) solver to be used. If set to "None", the default one is used. For more information on LP solvers and which default solver is used, see the method "solve" of the class "MixedIntegerLinearProgram". * "verbose" -- integer (default: "0"). Sets the level of verbosity. Set to 0 by default, which means quiet. EXAMPLES: A basic application on a "PappusGraph": sage: g=graphs.PappusGraph() sage: g.vertex_connectivity() 3 In a grid, the vertex connectivity is equal to the minimum degree, in which case one of the two sets is of cardinality 1: sage: g = graphs.GridGraph([ 3,3 ]) sage: [value, cut, [ setA, setB ]] = g.vertex_connectivity(sets=True) sage: len(setA) == 1 or len(setB) == 1 True A vertex cut in a tree is any internal vertex: sage: g = graphs.RandomGNP(15,.5) sage: tree = Graph() sage: tree.add_edges(g.min_spanning_tree()) sage: [val, [cut_vertex]] = tree.vertex_connectivity(value_only=False) sage: tree.degree(cut_vertex) > 1 True When "value_only = True", this function is optimized for small connectivity values and does not need to build a linear program. It is the case for connected graphs which are not connected: sage: g = 2 * graphs.PetersenGraph() sage: g.vertex_connectivity() 0 Or if they are just 1-connected: sage: g = graphs.PathGraph(10) sage: g.vertex_connectivity() 1 For directed graphs, the strong connectivity is tested through the dedicated function: sage: g = digraphs.ButterflyGraph(3) sage: g.vertex_connectivity() 0 A complete graph on 10 vertices is 9-connected: sage: g = graphs.CompleteGraph(10) sage: g.vertex_connectivity() 9 A complete digraph on 10 vertices is 9-connected: sage: g = DiGraph(graphs.CompleteGraph(10)) sage: g.vertex_connectivity() 9
g.vertex_iterator?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.vertex_iterator(self, vertices=None) Docstring : Returns an iterator over the given vertices. Returns False if not given a vertex, sequence, iterator or None. None is equivalent to a list of every vertex. Note that "for v in G" syntax is allowed. INPUT: * "vertices" - iterated vertices are these intersected with the vertices of the (di)graph EXAMPLES: sage: P = graphs.PetersenGraph() sage: for v in P.vertex_iterator(): ....: print(v) 0 1 2 ... 8 9 sage: G = graphs.TetrahedralGraph() sage: for i in G: ....: print(i) 0 1 2 3 Note that since the intersection option is available, the vertex_iterator() function is sub-optimal, speed-wise, but note the following optimization: sage: timeit V = P.vertices() # not tested 100000 loops, best of 3: 8.85 [micro]s per loop sage: timeit V = list(P.vertex_iterator()) # not tested 100000 loops, best of 3: 5.74 [micro]s per loop sage: timeit V = list(P._nxg.adj.iterkeys()) # not tested 100000 loops, best of 3: 3.45 [micro]s per loop In other words, if you want a fast vertex iterator, call the dictionary directly.
g.vertices()
[0, 1, 2, 3]
g.weighted?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.weighted(self, new=None) Docstring : Whether the (di)graph is to be considered as a weighted (di)graph. INPUT: * "new" (optional bool): If it is provided, then the weightedness flag is set accordingly. This is not allowed for immutable graphs. Note: Changing the weightedness flag changes the "=="-class of a graph and is thus not allowed for immutable graphs.Edge weightings can still exist for (di)graphs "G" where "G.weighted()" is "False". EXAMPLES: Here we have two graphs with different labels, but "weighted()" is "False" for both, so we just check for the presence of edges: sage: G = Graph({0:{1:'a'}}, sparse=True) sage: H = Graph({0:{1:'b'}}, sparse=True) sage: G == H True Now one is weighted and the other is not, and thus the graphs are not equal: sage: G.weighted(True) sage: H.weighted() False sage: G == H False However, if both are weighted, then we finally compare 'a' to 'b': sage: H.weighted(True) sage: G == H False
g.copy?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : g.copy(self, weighted=None, implementation='c_graph', data_structure=None, sparse=None, immutable=None) Docstring : Change the graph implementation INPUT: * "weighted" boolean (default: "None") -- weightedness for the copy. Might change the equality class if not "None". * "sparse" (boolean) -- "sparse=True" is an alias for "data_structure="sparse"", and "sparse=False" is an alias for "data_structure="dense"". Only used when "implementation='c_graph'" and "data_structure=None". * "data_structure" -- one of ""sparse"", ""static_sparse"", or ""dense"". See the documentation of "Graph" or "DiGraph". Only used when "implementation='c_graph'". * "immutable" (boolean) -- whether to create a mutable/immutable copy. Only used when "implementation='c_graph'" and "data_structure=None". * "immutable=None" (default) means that the graph and its copy will behave the same way. * "immutable=True" is a shortcut for "data_structure='static_sparse'" and "implementation='c_graph'" * "immutable=False" sets "implementation" to "'c_graph'". When "immutable=False" is used to copy an immutable graph, the data structure used is ""sparse"" unless anything else is specified. Note: If the graph uses "StaticSparseBackend" and the "_immutable" flag, then "self" is returned rather than a copy (unless one of the optional arguments is used). OUTPUT: A Graph object. Warning: Please use this method only if you need to copy but change the underlying implementation or weightedness. Otherwise simply do "copy(g)" instead of "g.copy()". Warning: If "weighted" is passed and is not the weightedness of the original, then the copy will not equal the original. EXAMPLES: sage: g=Graph({0:[0,1,1,2]},loops=True,multiedges=True,sparse=True) sage: g==copy(g) True sage: g=DiGraph({0:[0,1,1,2],1:[0,1]},loops=True,multiedges=True,sparse=True) sage: g==copy(g) True Note that vertex associations are also kept: sage: d = {0 : graphs.DodecahedralGraph(), 1 : graphs.FlowerSnark(), 2 : graphs.MoebiusKantorGraph(), 3 : graphs.PetersenGraph() } sage: T = graphs.TetrahedralGraph() sage: T.set_vertices(d) sage: T2 = copy(T) sage: T2.get_vertex(0) Dodecahedron: Graph on 20 vertices Notice that the copy is at least as deep as the objects: sage: T2.get_vertex(0) is T.get_vertex(0) False Examples of the keywords in use: sage: G = graphs.CompleteGraph(19) sage: H = G.copy(implementation='c_graph') sage: H == G; H is G True False sage: G1 = G.copy(sparse=True) sage: G1==G True sage: G1 is G False sage: G2 = copy(G) sage: G2 is G False Argument "weighted" affects the equality class: sage: G = graphs.CompleteGraph(5) sage: H1 = G.copy(weighted=False) sage: H2 = G.copy(weighted=True) sage: [G.weighted(), H1.weighted(), H2.weighted()] [False, False, True] sage: [G == H1, G == H2, H1 == H2] [True, False, False] sage: G.weighted(True) sage: [G == H1, G == H2, H1 == H2] [False, True, False]
gw = g.copy(weighted=True) gw.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)]
gw.weighted_adjacency_matrix?
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Signature : gw.weighted_adjacency_matrix(self, sparse=True) Docstring : Returns the weighted adjacency matrix of the graph. Each vertex is represented by its position in the list returned by the vertices() function. EXAMPLES: sage: G = Graph(sparse=True, weighted=True) sage: G.add_edges([(0,1,1),(1,2,2),(0,2,3),(0,3,4)]) sage: M = G.weighted_adjacency_matrix(); M [0 1 3 4] [1 0 2 0] [3 2 0 0] [4 0 0 0] sage: H = Graph(data=M, format='weighted_adjacency_matrix', sparse=True) sage: H == G True The following doctest verifies that #4888 is fixed: sage: G = DiGraph({0:{}, 1:{0:1}, 2:{0:1}}, weighted = True,sparse=True) sage: G.weighted_adjacency_matrix() [0 0 0] [1 0 0] [1 0 0]
g.wiener_index?
︠75f0a055-6597-4f48-a085-909ef88fc690︠