To see a graph
you are working with, right now there are two main options.
You can view the graph in two dimensions via matplotlib with show().
sage: G = graphs.RandomGNP(15,.3) sage: G.show()
Or you can view it in three dimensions via jmol with show3d().
sage: G.show3d()
Module-level Functions
g, partition) |
Helper function for canonical labeling of edge labeled (di)graphs.
Translates to a bipartite incidence-structure type graph appropriate for computing canonical labels of edge labeled graphs. Note that this is actually computationally equivalent to implementing a change on an inner loop of the main algorithm- namely making the refinement procedure sort for each label.
If the graph is a multigraph, it is translated to a non-multigraph, where each edge is labeled with a dictionary describing how many edges of each label were originally there. Then in either case we are working on a graph without multiple edges. At this point, we create another (bipartite) graph, whose left vertices are the original vertices of the graph, and whose right vertices represent the edges. We partition the left vertices as they were originally, and the right vertices by common labels: only automorphisms taking edges to like-labeled edges are allowed, and this additional partition information enforces this on the bipartite graph.
sage: G = Graph(multiedges=True, implementation='networkx') sage: G.add_edges([(0,1,i) for i in range(10)]) sage: G.add_edge(1,2,'string') sage: G.add_edge(2,3) sage: from sage.graphs.graph import graph_isom_equivalent_non_edge_labeled_graph sage: graph_isom_equivalent_non_edge_labeled_graph(G, [G.vertices()]) (Graph on 7 vertices, [[('o', 0), ('o', 1), ('o', 2), ('o', 3)], [('x', 0)], [('x', 1)], [('x', 2)]])
g, partition) |
Helper function for canonical labeling of multi-(di)graphs.
The idea for this function is that the main algorithm for computing isomorphism
of graphs does not allow multiple edges. Instead of making some very difficult
changes to that, we can simply modify the multigraph into a non-multi graph
that carries essentially the same information. For each pair of vertices
, if there is at most one edge between
and
, we do nothing,
but if there are more than one, we split each edge into two, introducing a new
vertex. These vertices really represent edges, so we keep them in their own
part of a partition - to distinguish them from genuine vertices. Then the
canonical label and automorphism group is computed, and in the end, we strip
off the parts of the generators that describe how these new vertices move,
and we have the automorphism group of the original multi-graph. Similarly, by
putting the additional vertices in their own cell of the partition, we guarantee
that the relabeling leading to a canonical label moves genuine vertices amongst
themselves, and hence the canonical label is still well-defined, when we forget
about the additional vertices.
sage: from sage.graphs.graph import graph_isom_equivalent_non_multi_graph sage: G = Graph(multiedges=True) sage: G.add_edge((0,1,1)) sage: G.add_edge((0,1,2)) sage: G.add_edge((0,1,3)) sage: graph_isom_equivalent_non_multi_graph(G, [[0,1]]) (Graph on 5 vertices, [[('o', 0), ('o', 1)], [('x', 0), ('x', 1), ('x', 2)]])
g, [bgcolor=(1, 1, 1)], [vertex_colors=None], [vertex_size=0.06], [pos3d=None], [iterations=50]) |
Class: DiGraph
Input:
pos - a positioning dictionary: for example, the spring layout from NetworkX for the 5-cycle is 0: [-0.91679746, 0.88169588], 1: [ 0.47294849, 1.125 ], 2: [ 1.125 ,-0.12867615], 3: [ 0.12743933,-1.125 ], 4: [-1.125 ,-0.50118505] name - (must be an explicitly named parameter, i.e., name="complete") gives the graph a name loops - boolean, whether to allow loops (ignored if data is an instance of the DiGraph class) multiedges - boolean, whether to allow multiple edges (ignored if data is an instance of the DiGraph class) weighted - whether digraph thinks of itself as weighted or not. See self.weighted() format - if None, DiGraph tries to guess- can be several values, including: 'adjacency_matrix' - a square Sage matrix M, with M[i,j] equal to the number of edges {i,j} 'incidence_matrix' - a Sage matrix, with one column C for each edge, where if C represents {i, j}, C[i] is -1 and C[j] is 1 'weighted_adjacency_matrix' - a square Sage matrix M, with M[i,j] equal to the weight of the single edge {i,j}. Given this format, weighted is ignored (assumed True). boundary - a list of boundary vertices, if none, digraph is considered as a 'digraph without boundary' implementation - what to use as a backend for the graph. Currently, the options are either 'networkx' or 'c_graph' sparse - only for implementation == 'c_graph'. Whether to use sparse or dense graphs as backend. Note that currently dense graphs do not have edge labels, nor can they be multigraphs vertex_labels - only for implementation == 'c_graph'. Whether to allow any object as a vertex (slower), or only the integers 0, ..., n-1, where n is the number of vertices.
1. A NetworkX XDiGraph:
sage: import networkx sage: g = networkx.XDiGraph({0:[1,2,3], 2:[4]}) sage: DiGraph(g) Digraph on 5 vertices
In this single case, we do not make a copy of g, but just wrap the actual NetworkX passed. We do this for performance reasons.
sage: import networkx sage: g = networkx.XDiGraph({0:[1,2,3], 2:[4]}) sage: G = DiGraph(g, implementation='networkx') sage: H = DiGraph(g, implementation='networkx') sage: G._backend._nxg is H._backend._nxg True
2. A NetworkX digraph:
sage: import networkx sage: g = networkx.DiGraph({0:[1,2,3], 2:[4]}) sage: DiGraph(g) Digraph on 5 vertices
Note that in this case, we copy the networkX structure.
sage: import networkx sage: g = networkx.DiGraph({0:[1,2,3], 2:[4]}) sage: G = DiGraph(g, implementation='networkx') sage: H = DiGraph(g, implementation='networkx') sage: G._backend._nxg is H._backend._nxg False
3. A dictionary of dictionaries:
sage: g = DiGraph({0:{1:'x',2:'z',3:'a'}, 2:{5:'out'}}, implementation='networkx'); g Digraph on 5 vertices
The labels ('x', 'z', 'a', 'out') are labels for edges. For example, 'out' is the label for the edge from 2 to 5. Labels can be used as weights, if all the labels share some common parent.
4. A dictionary of lists:
sage: g = DiGraph({0:[1,2,3], 2:[4]}); g Digraph on 5 vertices
5. A list of vertices and a function describing adjacencies. Note that the list of vertices and the function must be enclosed in a list (i.e., [list of vertices, function]).
We construct a graph on the integers 1 through 12 such that there is a directed edge from i to j if and only if i divides j.
sage: g=DiGraph([[1..12],lambda i,j: i!=j and i.divides(j)], implementation='networkx') sage: g.vertices() [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] sage: g.adjacency_matrix() [0 1 1 1 1 1 1 1 1 1 1 1] [0 0 0 1 0 1 0 1 0 1 0 1] [0 0 0 0 0 1 0 0 1 0 0 1] [0 0 0 0 0 0 0 1 0 0 0 1] [0 0 0 0 0 0 0 0 0 1 0 0] [0 0 0 0 0 0 0 0 0 0 0 1] [0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0]
6. A numpy matrix or ndarray:
sage: import numpy sage: A = numpy.array([[0,1,0],[1,0,0],[1,1,0]]) sage: DiGraph(A, implementation='networkx') Digraph on 3 vertices
7. A Sage matrix: Note: If format is not specified, then Sage assumes a square matrix is an adjacency matrix, and a nonsquare matrix is an incidence matrix.
A. an adjacency matrix:
sage: M = Matrix([[0, 1, 1, 1, 0],[0, 0, 0, 0, 0],[0, 0, 0, 0, 1],[0, 0, 0, 0, 0],[0, 0, 0, 0, 0]]); M [0 1 1 1 0] [0 0 0 0 0] [0 0 0 0 1] [0 0 0 0 0] [0 0 0 0 0] sage: DiGraph(M) Digraph on 5 vertices
B. an incidence matrix:
sage: M = Matrix(6, [-1,0,0,0,1, 1,-1,0,0,0, 0,1,-1,0,0, 0,0,1,-1,0, 0,0,0,1,-1, 0,0,0,0,0]); M [-1 0 0 0 1] [ 1 -1 0 0 0] [ 0 1 -1 0 0] [ 0 0 1 -1 0] [ 0 0 0 1 -1] [ 0 0 0 0 0] sage: DiGraph(M) Digraph on 6 vertices
self, [data=None], [pos=None], [loops=False], [format=None], [boundary=[]], [weighted=False], [implementation=networkx], [sparse=True], [vertex_labels=True]) |
Functions: dig6_string,
graphviz_string,
in_degree,
in_degree_iterator,
incoming_edge_iterator,
incoming_edges,
is_directed,
is_directed_acyclic,
out_degree,
out_degree_iterator,
outgoing_edge_iterator,
outgoing_edges,
predecessor_iterator,
predecessors,
reverse,
successor_iterator,
successors,
to_directed,
to_undirected,
topological_sort,
topological_sort_generator
self) |
Returns the dig6 representation of the digraph as an ASCII string. Valid for single (no multiple edges) digraphs on 0 to 262143 vertices.
TODO
self) |
Returns a representation in the DOT language, ready to render in graphviz.
REFERENCES: http://www.graphviz.org/doc/info/lang.html
sage: G = DiGraph({0:{1:None,2:None}, 1:{2:None}, 2:{3:'foo'}, 3:{}}, implementation='networkx') sage: s = G.graphviz_string(); s 'digraph {\n"0";"1";"2";"3";\n"0"->"1";"0"->"2";"1"->"2";"2"->"3"[label="fo o"];\n}'
self, [vertices=None], [labels=False]) |
Same as degree, but for in degree.
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.in_degree(vertices = [0,1,2], labels=True) {0: 2, 1: 2, 2: 2} sage: D.in_degree() [2, 2, 2, 2, 1, 1] sage: G = graphs.PetersenGraph().to_directed() sage: G.in_degree(0) 3
self, [vertices=None], [labels=False]) |
Same as degree_iterator, but for in degree.
sage: D = graphs.Grid2dGraph(2,4).to_directed() sage: for i in D.in_degree_iterator(): ... print i 3 3 2 3 2 2 2 3 sage: for i in D.in_degree_iterator(labels=True): ... print i ((0, 1), 3) ((1, 2), 3) ((0, 0), 2) ((0, 2), 3) ((1, 3), 2) ((1, 0), 2) ((0, 3), 2) ((1, 1), 3)
self, [vertices=None], [labels=True]) |
Return an iterator over all arriving edges from vertices, or over all edges if vertices is None.
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: for a in D.incoming_edge_iterator([0]): ... print a (1, 0, None) (4, 0, None)
self, [vertices=None], [labels=True]) |
Returns a list of edges arriving at vertices.
Input:
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)]
self) |
Since digraph is directed, returns True.
self) |
Returns whether the digraph is acyclic or not.
A directed graph is acyclic if for any vertex v, there is no directed path that starts and ends at v. Every directed acyclic graph (dag) corresponds to a partial ordering of its vertices, however multiple dags may lead to the same partial ordering.
sage: D = DiGraph({ 0:[1,2,3], 4:[2,5], 1:[8], 2:[7], 3:[7], 5:[6,7], 7:[8], 6:[9], 8:[10], 9:[10] }) sage: D.plot(layout='circular').show() sage: D.is_directed_acyclic() True
sage: D.add_edge(9,7) sage: D.is_directed_acyclic() True
sage: D.add_edge(7,4) sage: D.is_directed_acyclic() False
self, [vertices=None], [labels=False]) |
Same as degree, but for out degree.
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.out_degree(vertices = [0,1,2], labels=True) {0: 3, 1: 2, 2: 1} sage: D.out_degree() [3, 2, 1, 1, 2, 1]
self, [vertices=None], [labels=False]) |
Same as degree_iterator, but for out degree.
sage: D = graphs.Grid2dGraph(2,4).to_directed() sage: for i in D.out_degree_iterator(): ... print i 3 3 2 3 2 2 2 3 sage: for i in D.out_degree_iterator(labels=True): ... print i ((0, 1), 3) ((1, 2), 3) ((0, 0), 2) ((0, 2), 3) ((1, 3), 2) ((1, 0), 2) ((0, 3), 2) ((1, 1), 3)
self, [vertices=None], [labels=True]) |
Return an iterator over all departing edges from vertices, or over all edges if vertices is None.
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: for a in D.outgoing_edge_iterator([0]): ... print a (0, 1, None) (0, 2, None) (0, 3, None)
self, [vertices=None], [labels=True]) |
Returns a list of edges departing from vertices.
Input:
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.outgoing_edges([0]) [(0, 1, None), (0, 2, None), (0, 3, None)]
self, vertex) |
Returns an iterator over predecessor vertices of vertex.
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: for a in D.predecessor_iterator(0): ... print a 1 4
self, vertex) |
Returns a list of predecessor vertices of vertex.
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.predecessors(0) [1, 4]
self) |
Returns a copy of digraph with edges reversed in direction.
sage: D = DiGraph({ 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] }) sage: D.reverse() Reverse of (): Digraph on 6 vertices
self, vertex) |
Returns an iterator over successor vertices of vertex.
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: for a in D.successor_iterator(0): ... print a 1 2 3
self, vertex) |
Returns a list of successor vertices of vertex.
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.successors(0) [1, 2, 3]
self) |
Since the graph is already directed, simply returns a copy of itself.
sage: DiGraph({0:[1,2,3],4:[5,1]}).to_directed() Digraph on 6 vertices
self, [implementation=networkx]) |
Returns an undirected version of the graph. Every directed edge becomes an edge.
sage: D = DiGraph({0:[1,2],1:[0]}) sage: G = D.to_undirected() sage: D.edges(labels=False) [(0, 1), (0, 2), (1, 0)] sage: G.edges(labels=False) [(0, 1), (0, 2)]
self) |
Returns a topological sort of the digraph if it is acyclic, and raises a TypeError if the digraph contains a directed cycle.
A topological sort is an ordering of the vertices of the digraph such that each vertex comes before all of its successors. That is, if u comes before v in the sort, then there may be a directed path from u to v, but there will be no directed path from v to u.
sage: D = DiGraph({ 0:[1,2,3], 4:[2,5], 1:[8], 2:[7], 3:[7], 5:[6,7], 7:[8], 6:[9], 8:[10], 9:[10] }) sage: D.plot(layout='circular').show() sage: D.topological_sort() [4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10]
sage: D.add_edge(9,7) sage: D.topological_sort() [4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10]
sage: D.add_edge(7,4) sage: D.topological_sort() Traceback (most recent call last): ... TypeError: Digraph is not acyclic-- there is no topological sort.
NOTE: There is a recursive version of this in NetworkX, but it has problems:
sage: import networkx sage: D = DiGraph({ 0:[1,2,3], 4:[2,5], 1:[8], 2:[7], 3:[7], 5:[6,7], 7:[8], 6:[9], 8:[10], 9:[10] }) sage: N = D.networkx_graph() sage: networkx.topological_sort(N) [4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10] sage: networkx.topological_sort_recursive(N) is None True
self) |
Returns a list of all topological sorts of the digraph if it is acyclic, and raises a TypeError if the digraph contains a directed cycle.
A topological sort is an ordering of the vertices of the digraph such that each vertex comes before all of its successors. That is, if u comes before v in the sort, then there may be a directed path from u to v, but there will be no directed path from v to u. See also Graph.topological_sort().
Author Log:
REFERENCE: [1] Pruesse, Gara and Ruskey, Frank. Generating Linear Extensions Fast. SIAM J. Comput., Vol. 23 (1994), no. 2, pp. 373-386.
sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] }) sage: D.plot(layout='circular').show() sage: D.topological_sort_generator() [[0, 1, 2, 3, 4], [0, 1, 2, 4, 3], [0, 2, 1, 3, 4], [0, 2, 1, 4, 3], [0, 2, 4, 1, 3]]
sage: for sort in D.topological_sort_generator(): ... for edge in D.edge_iterator(): ... u,v,l = edge ... if sort.index(u) > sort.index(v): ... print "This should never happen."
Special Functions: __init__
Class: GenericGraph
Functions: add_cycle,
add_edge,
add_edges,
add_path,
add_vertex,
add_vertices,
adjacency_matrix,
all_paths,
am,
antisymmetric,
automorphism_group,
blocks_and_cut_vertices,
breadth_first_search,
canonical_label,
cartesian_product,
categorical_product,
center,
characteristic_polynomial,
check_embedding_validity,
clear,
cluster_transitivity,
cluster_triangles,
clustering_average,
clustering_coeff,
coarsest_equitable_refinement,
complement,
connected_component_containing_vertex,
connected_components,
connected_components_number,
connected_components_subgraphs,
copy,
cores,
degree,
degree_histogram,
degree_iterator,
degree_to_cell,
delete_edge,
delete_edges,
delete_multiedge,
delete_vertex,
delete_vertices,
density,
depth_first_search,
diameter,
disjoint_union,
disjunctive_product,
distance,
eccentricity,
edge_boundary,
edge_iterator,
edge_label,
edge_labels,
edges,
edges_incident,
eigenspaces,
genus,
get_boundary,
get_embedding,
get_pos,
get_vertex,
get_vertices,
girth,
graphviz_string,
graphviz_to_file_named,
has_edge,
has_vertex,
incidence_matrix,
interior_paths,
is_circular_planar,
is_clique,
is_connected,
is_drawn_free_of_edge_crossings,
is_equitable,
is_eulerian,
is_forest,
is_independent_set,
is_isomorphic,
is_planar,
is_subgraph,
is_tree,
is_vertex_transitive,
kirchhoff_matrix,
laplacian_matrix,
lexicographic_product,
line_graph,
loop_edges,
loop_vertices,
loops,
multiple_edges,
name,
neighbor_iterator,
neighbors,
networkx_graph,
num_edges,
num_verts,
number_of_loops,
order,
periphery,
plot,
plot3d,
radius,
random_subgraph,
relabel,
remove_loops,
remove_multiple_edges,
set_boundary,
set_edge_label,
set_embedding,
set_planar_positions,
set_pos,
set_vertex,
set_vertices,
shortest_path,
shortest_path_all_pairs,
shortest_path_length,
shortest_path_lengths,
shortest_paths,
show,
show3d,
size,
spectrum,
strong_product,
subgraph,
tensor_product,
to_simple,
trace_faces,
transitive_closure,
transitive_reduction,
union,
vertex_boundary,
vertex_iterator,
vertices,
weighted,
weighted_adjacency_matrix
self, vertices) |
Adds a cycle to the graph with the given vertices. If the vertices are already present, only the edges are added.
For digraphs, adds the directed cycle, whose orientation is determined by the list. Adds edges (vertices[u], vertices[u+1]) and (vertices[-1], vertices[0]).
Input:
sage: G = Graph(implementation='networkx') sage: G.add_vertices(range(10)); G Graph on 10 vertices sage: show(G) sage: G.add_cycle(range(20)[10:20]) sage: show(G) sage: G.add_cycle(range(10)) sage: show(G)
sage: D = DiGraph(implementation='networkx') sage: D.add_cycle(range(4)) sage: D.edges() [(0, 1, None), (1, 2, None), (2, 3, None), (3, 0, None)]
self, u, [v=None], [label=None]) |
Adds an edge from u and v.
Input: The following forms are all accepted:
G.add_edge( 1, 2 ) G.add_edge( (1, 2) ) G.add_edges( [ (1, 2) ] ) G.add_edge( 1, 2, 'label' ) G.add_edge( (1, 2, 'label') ) G.add_edges( [ (1, 2, 'label') ] )
WARNING: The following intuitive input results in nonintuitive output:
sage: G = Graph(implementation='networkx') sage: G.add_edge((1,2), 'label') sage: G.networkx_graph().adj # random output order {'label': {(1, 2): None}, (1, 2): {'label': None}}
Use one of these instead:
sage: G = Graph(implementation='networkx') sage: G.add_edge((1,2), label="label") sage: G.networkx_graph().adj # random output order {1: {2: 'label'}, 2: {1: 'label'}}
sage: G = Graph(implementation='networkx') sage: G.add_edge(1,2,'label') sage: G.networkx_graph().adj # random output order {1: {2: 'label'}, 2: {1: 'label'}}
self, edges) |
Add edges from an iterable container.
sage: G = graphs.DodecahedralGraph() sage: H = Graph(implementation='networkx') sage: H.add_edges( G.edge_iterator() ); H Graph on 20 vertices sage: G = graphs.DodecahedralGraph().to_directed() sage: H = DiGraph(implementation='networkx') sage: H.add_edges( G.edge_iterator() ); H Digraph on 20 vertices
self, vertices) |
Adds a cycle to the graph with the given vertices. If the vertices are already present, only the edges are added.
For digraphs, adds the directed path vertices[0], ..., vertices[-1].
Input:
sage: G = Graph(implementation='networkx') sage: G.add_vertices(range(10)); G Graph on 10 vertices sage: show(G) sage: G.add_path(range(20)[10:20]) sage: show(G) sage: G.add_path(range(10)) sage: show(G)
sage: D = DiGraph(sparse=True) sage: D.add_path(range(4)) sage: D.edges() [(0, 1, None), (1, 2, None), (2, 3, None)]
self, [name=None]) |
Creates an isolated vertex. If the vertex already exists, then nothing is done.
Input:
As it is implemented now, if a graph
has a large number of
vertices with numeric labels, then G.add_vertex() could
potentially be slow.
sage: G = Graph(sparse=True); G.add_vertex(); G Graph on 1 vertex
sage: D = DiGraph(sparse=True); D.add_vertex(); D Digraph on 1 vertex
self, vertices) |
Add vertices to the (di)graph from an iterable container of vertices. Vertices that already exist in the graph will not be added again.
sage: d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7,8], 6: [8,9], 7: [9]} sage: G = Graph(d, sparse=True) sage: G.add_vertices([10,11,12]) sage: G.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] sage: G.add_vertices(graphs.CycleGraph(25).vertices()) sage: G.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
self, [sparse=None], [boundary_first=False]) |
Returns the adjacency matrix of the (di)graph. Each vertex is represented by its position in the list returned by the vertices() function.
The matrix returned is over the integers. If a different ring is desired, use either the change_ring function or the matrix function.
Input:
sage: G = graphs.CubeGraph(4) sage: G.adjacency_matrix() [0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0] [1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0] [1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0] [0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0] [1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0] [0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0] [0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0] [0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1] [1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0] [0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0] [0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0] [0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1] [0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0] [0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1] [0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1] [0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]
sage: matrix(GF(2),G) # matrix over GF(2) [0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0] [1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0] [1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0] [0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0] [1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0] [0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0] [0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0] [0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1] [1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0] [0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0] [0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0] [0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1] [0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0] [0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1] [0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1] [0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.adjacency_matrix() [0 1 1 1 0 0] [1 0 1 0 0 0] [0 0 0 1 0 0] [0 0 0 0 1 0] [1 0 0 0 0 1] [0 1 0 0 0 0]
TESTS:
sage: graphs.CubeGraph(8).adjacency_matrix().parent() Full MatrixSpace of 256 by 256 dense matrices over Integer Ring sage: graphs.CubeGraph(9).adjacency_matrix().parent() Full MatrixSpace of 512 by 512 sparse matrices over Integer Ring
self, start, end) |
Returns a list of all paths (also lists) between a pair of vertices (start, end) in the (di)graph.
sage: eg1 = Graph({0:[1,2], 1:[4], 2:[3,4], 4:[5], 5:[6]}) sage: eg1.all_paths(0,6) [[0, 1, 4, 5, 6], [0, 2, 4, 5, 6]] sage: eg2 = graphs.PetersenGraph() sage: sorted(eg2.all_paths(1,4)) [[1, 0, 4], [1, 0, 5, 7, 2, 3, 4], [1, 0, 5, 7, 2, 3, 8, 6, 9, 4], [1, 0, 5, 7, 9, 4], [1, 0, 5, 7, 9, 6, 8, 3, 4], [1, 0, 5, 8, 3, 2, 7, 9, 4], [1, 0, 5, 8, 3, 4], [1, 0, 5, 8, 6, 9, 4], [1, 0, 5, 8, 6, 9, 7, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 8, 5, 0, 4], [1, 2, 3, 8, 5, 7, 9, 4], [1, 2, 3, 8, 6, 9, 4], [1, 2, 3, 8, 6, 9, 7, 5, 0, 4], [1, 2, 7, 5, 0, 4], [1, 2, 7, 5, 8, 3, 4], [1, 2, 7, 5, 8, 6, 9, 4], [1, 2, 7, 9, 4], [1, 2, 7, 9, 6, 8, 3, 4], [1, 2, 7, 9, 6, 8, 5, 0, 4], [1, 6, 8, 3, 2, 7, 5, 0, 4], [1, 6, 8, 3, 2, 7, 9, 4], [1, 6, 8, 3, 4], [1, 6, 8, 5, 0, 4], [1, 6, 8, 5, 7, 2, 3, 4], [1, 6, 8, 5, 7, 9, 4], [1, 6, 9, 4], [1, 6, 9, 7, 2, 3, 4], [1, 6, 9, 7, 2, 3, 8, 5, 0, 4], [1, 6, 9, 7, 5, 0, 4], [1, 6, 9, 7, 5, 8, 3, 4]] sage: dg = DiGraph({0:[1,3], 1:[3], 2:[0,3]}) sage: sorted(dg.all_paths(0,3)) [[0, 1, 3], [0, 3]] sage: ug = dg.to_undirected() sage: sorted(ug.all_paths(0,3)) [[0, 1, 3], [0, 2, 3], [0, 3]]
self, [sparse=None], [boundary_first=False]) |
Returns the adjacency matrix of the (di)graph. Each vertex is represented by its position in the list returned by the vertices() function.
The matrix returned is over the integers. If a different ring is desired, use either the change_ring function or the matrix function.
Input:
sage: G = graphs.CubeGraph(4) sage: G.adjacency_matrix() [0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0] [1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0] [1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0] [0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0] [1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0] [0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0] [0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0] [0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1] [1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0] [0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0] [0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0] [0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1] [0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0] [0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1] [0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1] [0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]
sage: matrix(GF(2),G) # matrix over GF(2) [0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0] [1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0] [1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0] [0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0] [1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0] [0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0] [0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0] [0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1] [1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0] [0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0] [0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0] [0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1] [0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0] [0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1] [0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1] [0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.adjacency_matrix() [0 1 1 1 0 0] [1 0 1 0 0 0] [0 0 0 1 0 0] [0 0 0 0 1 0] [1 0 0 0 0 1] [0 1 0 0 0 0]
TESTS:
sage: graphs.CubeGraph(8).adjacency_matrix().parent() Full MatrixSpace of 256 by 256 dense matrices over Integer Ring sage: graphs.CubeGraph(9).adjacency_matrix().parent() Full MatrixSpace of 512 by 512 sparse matrices over Integer Ring
self) |
Returns True if the relation given by the graph is antisymmetric and False otherwise.
A graph represents an antisymmetric relation if there being a path from a vertex x to a vertex y implies that there is not a path from y to x unless x=y.
A directed acyclic graph is antisymmetric. An undirected graph is never antisymmetric unless it is just a union of isolated vertices.
sage: graphs.RandomGNP(20,0.5).antisymmetric() False sage: digraphs.RandomDirectedGNR(20,0.5).antisymmetric() True
self, [partition=None], [translation=False], [verbosity=0], [edge_labels=False], [order=False], [return_group=True], [orbits=False]) |
Returns the largest subgroup of the automorphism group of the (di)graph whose orbit partition is finer than the partition given. If no partition is given, the unit partition is used and the entire automorphism group is given.
Input:
Graphs:
sage: graphs_query = GraphDatabase() sage: L = graphs_query.get_list(num_vertices=4) sage: graphs_list.show_graphs(L) sage: for g in L: ... G = g.automorphism_group() ... G.order(), G.gens() (24, ((2,3), (1,2), (1,4))) (4, ((2,3), (1,4))) (2, ((1,2),)) (8, ((1,2), (1,4)(2,3))) (6, ((1,2), (1,4))) (6, ((2,3), (1,2))) (2, ((1,4)(2,3),)) (2, ((1,2),)) (8, ((2,3), (1,4), (1,3)(2,4))) (4, ((2,3), (1,4))) (24, ((2,3), (1,2), (1,4)))
sage: C = graphs.CubeGraph(4) sage: G = C.automorphism_group() sage: M = G.character_table() sage: M.determinant() -712483534798848 sage: G.order() 384
sage: D = graphs.DodecahedralGraph() sage: G = D.automorphism_group() sage: A5 = AlternatingGroup(5) sage: Z2 = CyclicPermutationGroup(2) sage: H = A5.direct_product(Z2)[0] #see documentation for direct_product to explain the [0] sage: G.is_isomorphic(H) True
Multigraphs:
sage: G = Graph(multiedges=True, implementation='networkx') sage: G.add_edge(('a', 'b')) sage: G.add_edge(('a', 'b')) sage: G.add_edge(('a', 'b')) sage: G.automorphism_group() Permutation Group with generators [(1,2)]
Digraphs:
sage: D = DiGraph( { 0:[1], 1:[2], 2:[3], 3:[4], 4:[0] } ) sage: D.automorphism_group() Permutation Group with generators [(1,2,3,4,5)]
Edge labeled graphs:
sage: G = Graph(implementation='networkx') sage: G.add_edges( [(0,1,'a'),(1,2,'b'),(2,3,'c'),(3,4,'b'),(4,0,'a')] ) sage: G.automorphism_group(edge_labels=True) Permutation Group with generators [(1,4)(2,3)]
You can also ask for just the order of the group:
sage: G = graphs.PetersenGraph() sage: G.automorphism_group(return_group=False, order=True) 120
Or, just the orbits (recall the Petersen graph is transitive!)
sage: G = graphs.PetersenGraph() sage: G.automorphism_group(return_group=False, orbits=True) [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]
self) |
Computes the blocks and cut vertices of the graph. In the case of a digraph, this computation is done on the underlying graph.
A cut vertex is one whose deletion increases the number of connected components. A block is a maximal induced subgraph which itself has no cut vertices. Two distinct blocks cannot overlap in more than a single cut vertex.
Output: ( B, C ), where B is a list of blocks- each is a list of vertices and the blocks are the corresponding induced subgraphs- and C is a list of cut vertices.
sage: graphs.PetersenGraph().blocks_and_cut_vertices() ([[0, 1, 2, 3, 8, 5, 7, 9, 4, 6]], []) sage: graphs.PathGraph(6).blocks_and_cut_vertices() ([[5, 4], [4, 3], [3, 2], [2, 1], [0, 1]], [4, 3, 2, 1]) sage: graphs.CycleGraph(7).blocks_and_cut_vertices() ([[0, 1, 2, 3, 4, 5, 6]], []) sage: graphs.KrackhardtKiteGraph().blocks_and_cut_vertices() ([[9, 8], [8, 7], [0, 1, 3, 2, 5, 6, 4, 7]], [8, 7])
ALGORITHM: 8.3.8 in [1]. Notice the typo - the stack must also be considered as one of the blocks at termination.
REFERENCE: [1] D. Jungnickel, Graphs, Networks and Algorithms, Springer, 2005.
self, u, [ignore_direction=False]) |
Returns an iterator over vertices in a breadth-first ordering.
Input:
sage: G = Graph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} } ) sage: list(G.breadth_first_search(0)) [0, 1, 4, 2, 3] sage: list(G.depth_first_search(0)) [0, 4, 3, 2, 1]
sage: D = DiGraph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} } ) sage: list(D.breadth_first_search(0)) [0, 1, 2, 3, 4] sage: list(D.depth_first_search(0)) [0, 1, 2, 3, 4]
sage: D = DiGraph({1:[0], 2:[0]}) sage: list(D.breadth_first_search(0)) [0] sage: list(D.breadth_first_search(0, ignore_direction=True)) [0, 1, 2]
self, [partition=None], [certify=False], [verbosity=0], [edge_labels=False]) |
Returns the canonical label with respect to the partition. If no partition is given, uses the unit partition.
Input:
sage: D = graphs.DodecahedralGraph() sage: E = D.canonical_label(); E Dodecahedron: Graph on 20 vertices sage: D.canonical_label(certify=True) (Dodecahedron: Graph on 20 vertices, {0: 0, 1: 19, 2: 16, 3: 15, 4: 9, 5: 1, 6: 10, 7: 8, 8: 14, 9: 12, 10: 17, 11: 11, 12: 5, 13: 6, 14: 2, 15: 4, 16: 3, 17: 7, 18: 13, 19: 18}) sage: D.is_isomorphic(E) True
Multigraphs:
sage: G = Graph(multiedges=True) sage: G.add_edge((0,1)) sage: G.add_edge((0,1)) sage: G.add_edge((0,1)) sage: G.canonical_label() Multi-graph on 2 vertices
Digraphs:
sage: P = graphs.PetersenGraph() sage: DP = P.to_directed() sage: DP.canonical_label().adjacency_matrix() [0 0 0 0 0 0 0 1 1 1] [0 0 0 0 1 0 1 0 0 1] [0 0 0 1 0 0 1 0 1 0] [0 0 1 0 0 1 0 0 0 1] [0 1 0 0 0 1 0 0 1 0] [0 0 0 1 1 0 0 1 0 0] [0 1 1 0 0 0 0 1 0 0] [1 0 0 0 0 1 1 0 0 0] [1 0 1 0 1 0 0 0 0 0] [1 1 0 1 0 0 0 0 0 0]
Edge labeled graphs:
sage: G = Graph(implementation='networkx') sage: G.add_edges( [(0,1,'a'),(1,2,'b'),(2,3,'c'),(3,4,'b'),(4,0,'a')] ) sage: G.canonical_label(edge_labels=True) Graph on 5 vertices
self, other) |
Returns the Cartesian product of self and other.
The Cartesian product of G and H is the graph L with vertex set V(L) equal to the Cartesian product of the vertices V(G) and V(H), and ((u,v), (w,x)) is an edge iff either - (u, w) is an edge of self and v = x, or - (v, x) is an edge of other and u = w.
sage: Z = graphs.CompleteGraph(2) sage: C = graphs.CycleGraph(5) sage: P = C.cartesian_product(Z); P Graph on 10 vertices sage: P.plot().show()
sage: D = graphs.DodecahedralGraph() sage: P = graphs.PetersenGraph() sage: C = D.cartesian_product(P); C Graph on 200 vertices sage: C.plot().show()
self, other) |
Returns the tensor product, also called the categorical product, of self and other.
The tensor product of G and H is the graph L with vertex set V(L) equal to the Cartesian product of the vertices V(G) and V(H), and ((u,v), (w,x)) is an edge iff - (u, w) is an edge of self, and - (v, x) is an edge of other.
sage: Z = graphs.CompleteGraph(2) sage: C = graphs.CycleGraph(5) sage: T = C.tensor_product(Z); T Graph on 10 vertices sage: T.plot().show()
sage: D = graphs.DodecahedralGraph() sage: P = graphs.PetersenGraph() sage: T = D.tensor_product(P); T Graph on 200 vertices sage: T.plot().show()
self) |
Returns the set of vertices in the center, i.e. whose eccentricity is equal to the radius of the (di)graph.
In other words, the center is the set of vertices achieving the minimum eccentricity.
sage: G = graphs.DiamondGraph() sage: G.center() [1, 2] sage: P = graphs.PetersenGraph() sage: P.subgraph(P.center()) == P True sage: S = graphs.StarGraph(19) sage: S.center() [0] sage: G = Graph(sparse=True) sage: G.center() [] sage: G.add_vertex() sage: G.center() [0]
self, [var=x], [laplacian=False]) |
Returns the characteristic polynomial of the adjacency matrix of the (di)graph.
Input:
sage: P = graphs.PetersenGraph() sage: P.characteristic_polynomial() x^10 - 15*x^8 + 75*x^6 - 24*x^5 - 165*x^4 + 120*x^3 + 120*x^2 - 160*x + 48 sage: P.characteristic_polynomial(laplacian=True) x^10 - 30*x^9 + 390*x^8 - 2880*x^7 + 13305*x^6 - 39882*x^5 + 77640*x^4 - 94800*x^3 + 66000*x^2 - 20000*x
self, [embedding=None]) |
Checks whether an _embedding attribute is defined on self and if so, checks for accuracy. Returns True if everything is okay, False otherwise.
If embedding=None will test the attribute _embedding.
sage: d = {0: [1, 5, 4], 1: [0, 2, 6], 2: [1, 3, 7], 3: [8, 2, 4], 4: [0, 9, 3], 5: [0, 8, 7], 6: [8, 1, 9], 7: [9, 2, 5], 8: [3, 5, 6], 9: [4, 6, 7]} sage: G = graphs.PetersenGraph() sage: G.check_embedding_validity(d) True
self) |
Empties the graph of vertices and edges and removes name, boundary, associated objects, and position information.
sage: G=graphs.CycleGraph(4); G.set_vertices({0:'vertex0'}) sage: G.order(); G.size() 4 4 sage: len(G._pos) 4 sage: G.name() 'Cycle graph' sage: G.get_vertex(0) 'vertex0' sage: H = G.copy(implementation='c_graph', sparse=True) sage: H.clear() sage: H.order(); H.size() 0 0 sage: len(H._pos) 0 sage: H.name() '' sage: H.get_vertex(0) sage: H = G.copy(implementation='networkx') sage: H.clear() sage: H.order(); H.size() 0 0 sage: len(H._pos) 0 sage: H.name() '' sage: H.get_vertex(0)
self) |
Returns the transitivity (fraction of transitive triangles) of the graph.
The clustering coefficient of a graph is the fraction of possible triangles that are triangles, c_i = triangles_i / (k_i*(k_i-1)/2) where k_i is the degree of vertex i, [1]. A coefficient for the whole graph is the average of the c_i. Transitivity is the fraction of all possible triangles which are triangles, T = 3*triangles/triads, [1].
REFERENCE: [1] Aric Hagberg, Dan Schult and Pieter Swart. NetworkX documentation. [Online] Available: https://networkx.lanl.gov/reference/networkx/
sage: (graphs.FruchtGraph()).cluster_transitivity() 0.25
self, [nbunch=None], [with_labels=False]) |
Returns the number of triangles for nbunch of vertices as an ordered list.
The clustering coefficient of a graph is the fraction of possible triangles that are triangles, c_i = triangles_i / (k_i*(k_i-1)/2) where k_i is the degree of vertex i, [1]. A coefficient for the whole graph is the average of the c_i. Transitivity is the fraction of all possible triangles which are triangles, T = 3*triangles/triads, [1].
Input:
REFERENCE: [1] Aric Hagberg, Dan Schult and Pieter Swart. NetworkX documentation. [Online] Available: https://networkx.lanl.gov/reference/networkx/
sage: (graphs.FruchtGraph()).cluster_triangles() [1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0] sage: (graphs.FruchtGraph()).cluster_triangles(with_labels=True) {0: 1, 1: 1, 2: 0, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 0, 9: 1, 10: 1, 11: 0} sage: (graphs.FruchtGraph()).cluster_triangles(nbunch=[0,1,2]) [1, 1, 0]
self) |
Returns the average clustering coefficient.
The clustering coefficient of a graph is the fraction of possible triangles that are triangles, c_i = triangles_i / (k_i*(k_i-1)/2) where k_i is the degree of vertex i, [1]. A coefficient for the whole graph is the average of the c_i. Transitivity is the fraction of all possible triangles which are triangles, T = 3*triangles/triads, [1].
REFERENCE: [1] Aric Hagberg, Dan Schult and Pieter Swart. NetworkX documentation. [Online] Available: https://networkx.lanl.gov/reference/networkx/
sage: (graphs.FruchtGraph()).clustering_average() 0.25
self, [nbunch=None], [with_labels=False], [weights=False]) |
Returns the clustering coefficient for each vertex in nbunch as an ordered list.
The clustering coefficient of a graph is the fraction of possible triangles that are triangles, c_i = triangles_i / (k_i*(k_i-1)/2) where k_i is the degree of vertex i, [1]. A coefficient for the whole graph is the average of the c_i. Transitivity is the fraction of all possible triangles which are triangles, T = 3*triangles/triads, [1].
Input:
REFERENCE: [1] Aric Hagberg, Dan Schult and Pieter Swart. NetworkX documentation. [Online] Available: https://networkx.lanl.gov/reference/networkx/
sage: (graphs.FruchtGraph()).clustering_coeff() [0.33333333333333331, 0.33333333333333331, 0.0, 0.33333333333333331, 0.33333333333333331, 0.33333333333333331, 0.33333333333333331, 0.33333333333333331, 0.0, 0.33333333333333331, 0.33333333333333331, 0.0] sage: (graphs.FruchtGraph()).clustering_coeff(with_labels=True) {0: 0.33333333333333331, 1: 0.33333333333333331, 2: 0.0, 3: 0.33333333333333331, 4: 0.33333333333333331, 5: 0.33333333333333331, 6: 0.33333333333333331, 7: 0.33333333333333331, 8: 0.0, 9: 0.33333333333333331, 10: 0.33333333333333331, 11: 0.0} sage: (graphs.FruchtGraph()).clustering_coeff(with_labels=True,weights=True) ({0: 0.33333333333333331, 1: 0.33333333333333331, 2: 0.0, 3: 0.33333333333333331, 4: 0.33333333333333331, 5: 0.33333333333333331, 6: 0.33333333333333331, 7: 0.33333333333333331, 8: 0.0, 9: 0.33333333333333331, 10: 0.33333333333333331, 11: 0.0}, {0: 0.083333333333333329, 1: 0.083333333333333329, 2: 0.083333333333333329, 3: 0.083333333333333329, 4: 0.083333333333333329, 5: 0.083333333333333329, 6: 0.083333333333333329, 7: 0.083333333333333329, 8: 0.083333333333333329, 9: 0.083333333333333329, 10: 0.083333333333333329, 11: 0.083333333333333329}) sage: (graphs.FruchtGraph()).clustering_coeff(nbunch=[0,1,2]) [0.33333333333333331, 0.33333333333333331, 0.0] sage: (graphs.FruchtGraph()).clustering_coeff(nbunch=[0,1,2],with_labels=True,weights=True) ({0: 0.33333333333333331, 1: 0.33333333333333331, 2: 0.0}, {0: 0.083333333333333329, 1: 0.083333333333333329, 2: 0.083333333333333329})
self, partition, [sparse=False]) |
Returns the coarsest partition which is finer than the input partition, and equitable with respect to self.
A partition is equitable with respect to a graph if for every pair of cells C1, C2 of the partition, the number of edges from a vertex of C1 to C2 is the same, over all vertices in C1.
A partition P1 is finer than P2 (P2 is coarser than P1) if every cell of P1 is a subset of a cell of P2.
Input:
sage: G = graphs.PetersenGraph() sage: G.coarsest_equitable_refinement([[0],range(1,10)]) [[0], [2, 3, 6, 7, 8, 9], [1, 4, 5]] sage: G = graphs.CubeGraph(3) sage: verts = G.vertices() sage: Pi = [verts[:1], verts[1:]] sage: Pi [['000'], ['001', '010', '011', '100', '101', '110', '111']] sage: G.coarsest_equitable_refinement(Pi) [['000'], ['011', '101', '110'], ['111'], ['001', '010', '100']]
Note that given an equitable partition, this function returns that partition:
sage: P = graphs.PetersenGraph() sage: prt = [[0], [1, 4, 5], [2, 3, 6, 7, 8, 9]] sage: P.coarsest_equitable_refinement(prt) [[0], [1, 4, 5], [2, 3, 6, 7, 8, 9]]
sage: ss = (graphs.WheelGraph(6)).line_graph(labels=False) sage: prt = [[(0, 1)], [(0, 2), (0, 3), (0, 4), (1, 2), (1, 4)], [(2, 3), (3, 4)]] sage: ss.coarsest_equitable_refinement(prt) Traceback (most recent call last): ... TypeError: Partition ([[(0, 1)], [(0, 2), (0, 3), (0, 4), (1, 2), (1, 4)], [(2, 3), (3, 4)]]) is not valid for this graph: vertices are incorrect.
sage: ss = (graphs.WheelGraph(5)).line_graph(labels=False) sage: ss.coarsest_equitable_refinement(prt) [[(0, 1)], [(1, 2), (1, 4)], [(0, 3)], [(0, 2), (0, 4)], [(2, 3), (3, 4)]]
ALGORITHM: Brendan D. McKay's Master's Thesis, University of Melbourne, 1976.
self) |
Returns the complement of the (di)graph.
The complement of a graph has the same vertices, but exactly those edges that are not in the original graph. This is not well defined for graphs with multiple edges.
sage: P = graphs.PetersenGraph() sage: P.plot().show() sage: PC = P.complement() sage: PC.plot().show()
sage: graphs.TetrahedralGraph().complement().size() 0 sage: graphs.CycleGraph(4).complement().edges() [(0, 2, None), (1, 3, None)] sage: graphs.CycleGraph(4).complement() complement(Cycle graph): Graph on 4 vertices sage: Graph(multiedges=True).complement() Traceback (most recent call last): ... TypeError: Complement not well defined for (di)graphs with multiple edges.
self, vertex) |
Returns a list of the vertices connected to vertex.
sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: G.connected_component_containing_vertex(0) [0, 1, 2, 3] sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: D.connected_component_containing_vertex(0) [0, 1, 2, 3]
self) |
Returns a list of lists of vertices, each list representing a connected component. The list is ordered from largest to smallest component.
sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: G.connected_components() [[0, 1, 2, 3], [4, 5, 6]] sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: D.connected_components() [[0, 1, 2, 3], [4, 5, 6]]
self) |
Returns the number of connected components.
sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: G.connected_components_number() 2 sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: D.connected_components_number() 2
self) |
Returns a list of connected components as graph objects.
sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: L = G.connected_components_subgraphs() sage: graphs_list.show_graphs(L) sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: L = D.connected_components_subgraphs() sage: graphs_list.show_graphs(L)
self, [implementation=networkx], [sparse=True]) |
Creates a copy of the graph.
sage: g=Graph({0:[0,1,1,2]},loops=True,multiedges=True,implementation='networkx') sage: g==g.copy() True sage: g=DiGraph({0:[0,1,1,2],1:[0,1]},loops=True,multiedges=True,implementation='networkx') sage: g==g.copy() True
Note that vertex associations are also kept:
sage: d = {0 : graphs.DodecahedralGraph(), 1 : graphs.FlowerSnark(), 2 : graphs.MoebiusKantorGraph(), 3 : graphs.PetersenGraph() } sage: T = graphs.TetrahedralGraph() sage: T.set_vertices(d) sage: T2 = T.copy() sage: T2.get_vertex(0) Dodecahedron: Graph on 20 vertices
Notice that the copy is at least as deep as the objects:
sage: T2.get_vertex(0) is T.get_vertex(0) False
TESTS: We make copies of the _pos and _boundary attributes.
sage: g = graphs.PathGraph(3) sage: h = g.copy() sage: h._pos is g._pos False sage: h._boundary is g._boundary False
self, [with_labels=False]) |
Returns the core number for each vertex in an ordered list.
'K-cores in graph theory were introduced by Seidman in 1983 and by Bollobas in 1984 as a method of (destructively) simplifying graph topology to aid in analysis and visualization. They have been more recently defined as the following by Batagelj et al: given a graph G with vertices set V and edges set E, the k-core is computed by pruning all the vertices (with their respective edges) with degree less than k. That means that if a vertex u has degree d_u, and it has n neighbors with degree less than k, then the degree of u becomes d_u - n, and it will be also pruned if k > d_u - n. This operation can be useful to filter or to study some properties of the graphs. For instance, when you compute the 2-core of graph G, you are cutting all the vertices which are in a tree part of graph. (A tree is a graph with no loops),' [1].
Input:
REFERENCE: [1] K-core. Wikipedia. (2007). [Online] Available: http://en.wikipedia.org/wiki/K-core [2] Boris Pittel, Joel Spencer and Nicholas Wormald. Sudden Emergence of a Giant k-Core in a Random Graph. (1996). J. Combinatorial Theory. Ser B 67. pages 111-151. [Online] Available: http://cs.nyu.edu/cs/faculty/spencer/papers/k-core.pdf
sage: (graphs.FruchtGraph()).cores() [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3] sage: (graphs.FruchtGraph()).cores(with_labels=True) {0: 3, 1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3, 7: 3, 8: 3, 9: 3, 10: 3, 11: 3}
self, [vertices=None], [labels=False]) |
Gives the degree (in + out for digraphs) of a vertex or of vertices.
Input:
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]
self) |
Returns a list, whose ith entry is the frequency of degree i.
sage: G = graphs.Grid2dGraph(9,12) sage: G.degree_histogram() [0, 0, 4, 34, 70]
sage: G = graphs.Grid2dGraph(9,12).to_directed() sage: G.degree_histogram() [0, 0, 0, 0, 4, 0, 34, 0, 70]
self, [vertices=None], [labels=False]) |
Returns an iterator over the degrees of the (di)graph. In the case of a digraph, the degree is defined as the sum of the in-degree and the out-degree, i.e. the total number of edges incident to a given vertex.
Input: labels=False: returns an iterator over degrees. labels=True: returns an iterator over tuples (vertex, degree).
sage: G = graphs.Grid2dGraph(3,4) sage: for i in G.degree_iterator(): ... print i 3 4 2 ... 2 3 sage: for i in G.degree_iterator(labels=True): ... print i ((0, 1), 3) ((1, 2), 4) ((0, 0), 2) ... ((0, 3), 2) ((0, 2), 3)
sage: D = graphs.Grid2dGraph(2,4).to_directed() sage: for i in D.degree_iterator(): ... print i 6 6 ... 4 6 sage: for i in D.degree_iterator(labels=True): ... print i ((0, 1), 6) ((1, 2), 6) ... ((0, 3), 4) ((1, 1), 6)
self, vertex, cell) |
Returns the number of edges from vertex to an edge in cell. In the case of a digraph, returns a tuple (in_degree, out_degree).
sage: G = graphs.CubeGraph(3) sage: cell = G.vertices()[:3] sage: G.degree_to_cell('011', cell) 2 sage: G.degree_to_cell('111', cell) 0
sage: D = DiGraph({ 0:[1,2,3], 1:[3,4], 3:[4,5]}) sage: cell = [0,1,2] sage: D.degree_to_cell(5, cell) (0, 0) sage: D.degree_to_cell(3, cell) (2, 0) sage: D.degree_to_cell(0, cell) (0, 2)
self, u, [v=None], [label=None]) |
Delete the edge from u to v, returning silently if vertices or edge does not exist.
Input: The following forms are all accepted:
G.delete_edge( 1, 2 ) G.delete_edge( (1, 2) ) G.delete_edges( [ (1, 2) ] ) G.delete_edge( 1, 2, 'label' ) G.delete_edge( (1, 2, 'label') ) G.delete_edges( [ (1, 2, 'label') ] )
sage: G = graphs.CompleteGraph(19) sage: G.size() 171 sage: G.delete_edge( 1, 2 ) sage: G.delete_edge( (3, 4) ) sage: G.delete_edges( [ (5, 6), (7, 8) ] ) sage: G.delete_edge( 9, 10, 'label' ) sage: G.delete_edge( (11, 12, 'label') ) sage: G.delete_edges( [ (13, 14, 'label') ] ) sage: G.size() 164 sage: G.has_edge( (11, 12) ) False
Note that even though the edge (11, 12) has no label, it still gets deleted: NetworkX does not pay attention to labels here.
sage: D = graphs.CompleteGraph(19).to_directed() sage: D.size() 342 sage: D.delete_edge( 1, 2 ) sage: D.delete_edge( (3, 4) ) sage: D.delete_edges( [ (5, 6), (7, 8) ] ) sage: D.delete_edge( 9, 10, 'label' ) sage: D.delete_edge( (11, 12, 'label') ) sage: D.delete_edges( [ (13, 14, 'label') ] ) sage: D.size() 335 sage: D.has_edge( (11, 12) ) False
self, edges) |
Delete edges from an iterable container.
sage: K12 = graphs.CompleteGraph(12) sage: K4 = graphs.CompleteGraph(4) sage: K12.size() 66 sage: K12.delete_edges(K4.edge_iterator()) sage: K12.size() 60
sage: K12 = graphs.CompleteGraph(12).to_directed() sage: K4 = graphs.CompleteGraph(4).to_directed() sage: K12.size() 132 sage: K12.delete_edges(K4.edge_iterator()) sage: K12.size() 120
self, u, v) |
Deletes all edges from u and v.
sage: G = Graph(multiedges=True, implementation='networkx') sage: G.add_edges([(0,1), (0,1), (0,1), (1,2), (2,3)]) sage: G.edges() [(0, 1, None), (0, 1, None), (0, 1, None), (1, 2, None), (2, 3, None)] sage: G.delete_multiedge( 0, 1 ) sage: G.edges() [(1, 2, None), (2, 3, None)]
sage: D = DiGraph(multiedges=True) sage: D.add_edges([(0,1,1), (0,1,2), (0,1,3), (1,0), (1,2), (2,3)]) sage: D.edges() [(0, 1, 1), (0, 1, 2), (0, 1, 3), (1, 0, None), (1, 2, None), (2, 3, None)] sage: D.delete_multiedge( 0, 1 ) sage: D.edges() [(1, 0, None), (1, 2, None), (2, 3, None)]
self, vertex, [in_order=False]) |
Deletes vertex, removing all incident edges. Deleting a non-existant vertex will raise an exception.
Input:
sage: G = Graph(graphs.WheelGraph(9), sparse=True) sage: G.delete_vertex(0); G.show()
sage: D = DiGraph({0:[1,2,3,4,5],1:[2],2:[3],3:[4],4:[5],5:[1]}, implementation='networkx') sage: D.delete_vertex(0); D Digraph on 5 vertices sage: D.vertices() [1, 2, 3, 4, 5] sage: D.delete_vertex(0) Traceback (most recent call last): ... NetworkXError: node 0 not in graph
sage: G = graphs.CompleteGraph(4).line_graph(labels=False) sage: G.vertices() [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] sage: G.delete_vertex(0, in_order=True) sage: G.vertices() [(0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
self, vertices) |
Remove vertices from the (di)graph taken from an iterable container of vertices. Deleting a non-existant vertex will raise an exception.
sage: D = DiGraph({0:[1,2,3,4,5],1:[2],2:[3],3:[4],4:[5],5:[1]}, implementation='networkx') sage: D.delete_vertices([1,2,3,4,5]); D Digraph on 1 vertex sage: D.vertices() [0] sage: D.delete_vertices([1]) Traceback (most recent call last): ... NetworkXError: node 1 not in graph
self) |
Returns the density (number of edges divided by number of possible edges).
In the case of a multigraph, raises an error, since there is an infinite number of possible edges.
sage: d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7, 8], 6: [8,9], 7: [9]} sage: G = Graph(d); G.density() 1/3 sage: G = Graph({0:[1,2], 1:[0] }); G.density() 2/3 sage: G = DiGraph({0:[1,2], 1:[0] }); G.density() 1/2
Note that there are more possible edges on a looped graph:
sage: G.loops(True) sage: G.density() 1/3
self, u, [ignore_direction=False]) |
Returns an iterator over vertices in a depth-first ordering.
Input:
sage: G = Graph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} } ) sage: list(G.breadth_first_search(0)) [0, 1, 4, 2, 3] sage: list(G.depth_first_search(0)) [0, 4, 3, 2, 1]
sage: D = DiGraph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} } ) sage: list(D.breadth_first_search(0)) [0, 1, 2, 3, 4] sage: list(D.depth_first_search(0)) [0, 1, 2, 3, 4]
sage: D = DiGraph({1:[0], 2:[0]}) sage: list(D.depth_first_search(0)) [0] sage: list(D.depth_first_search(0, ignore_direction=True)) [0, 2, 1]
self) |
Returns the largest distance between any two vertices. Returns Infinity if the (di)graph is not connected.
sage: G = graphs.PetersenGraph() sage: G.diameter() 2 sage: G = Graph( { 0 : [], 1 : [], 2 : [1] } ) sage: G.diameter() +Infinity
Although max( ) is usually defined as -Infinity, since the diameter will never be negative, we define it to be zero:
sage: G = graphs.EmptyGraph() sage: G.diameter() 0
self, other, [verbose_relabel=True]) |
Returns the disjoint union of self and other.
If the graphs have common vertices, the vertices will be renamed to form disjoint sets.
Input:
sage: G = graphs.CycleGraph(3) sage: H = graphs.CycleGraph(4) sage: J = G.disjoint_union(H); J Cycle graph disjoint_union Cycle graph: Graph on 7 vertices sage: J.vertices() [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (1, 3)] sage: J = G.disjoint_union(H, verbose_relabel=False); J Cycle graph disjoint_union Cycle graph: Graph on 7 vertices sage: J.vertices() [0, 1, 2, 3, 4, 5, 6]
If the vertices are already disjoint and verbose_relabel is True, then the vertices are not relabeled.
sage: G=Graph({'a': ['b']}, implementation='networkx') sage: G.name("Custom path") sage: G.name() 'Custom path' sage: H=graphs.CycleGraph(3) sage: J=G.disjoint_union(H); J Custom path disjoint_union Cycle graph: Graph on 5 vertices sage: J.vertices() [0, 1, 2, 'a', 'b']
self, other) |
Returns the disjunctive product of self and other.
The disjunctive product of G and H is the graph L with vertex set V(L) equal to the Cartesian product of the vertices V(G) and V(H), and ((u,v), (w,x)) is an edge iff either - (u, w) is an edge of self, or - (v, x) is an edge of other.
sage: Z = graphs.CompleteGraph(2) sage: D = Z.disjunctive_product(Z); D Graph on 4 vertices sage: D.plot().show()
sage: C = graphs.CycleGraph(5) sage: D = C.disjunctive_product(Z); D Graph on 10 vertices sage: D.plot().show()
self, u, v) |
Returns the (directed) distance from u to v in the (di)graph, i.e. the length of the shortest path from u to v.
sage: G = graphs.CycleGraph(9) sage: G.distance(0,1) 1 sage: G.distance(0,4) 4 sage: G.distance(0,5) 4 sage: G = Graph( {0:[], 1:[]} ) sage: G.distance(0,1) +Infinity
self, [v=None], [dist_dict=None], [with_labels=False]) |
Return the eccentricity of vertex (or vertices) v.
The eccentricity of a vertex is the maximum distance to any other vertex.
Input:
sage: G = graphs.KrackhardtKiteGraph() sage: G.eccentricity() [4, 4, 4, 4, 4, 3, 3, 2, 3, 4] sage: G.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: G.eccentricity(7) 2 sage: G.eccentricity([7,8,9]) [3, 4, 2] sage: G.eccentricity([7,8,9], with_labels=True) == {8: 3, 9: 4, 7: 2} True sage: G = Graph( { 0 : [], 1 : [], 2 : [1] } ) sage: G.eccentricity() [+Infinity, +Infinity, +Infinity] sage: G = Graph({0:[]}) sage: G.eccentricity(with_labels=True) {0: 0} sage: G = Graph({0:[], 1:[]}) sage: G.eccentricity(with_labels=True) {0: +Infinity, 1: +Infinity}
self, vertices1, [vertices2=None], [labels=True]) |
Returns a list of edges (u,v,l) with u in vertices1 and v in vertices2. If vertices2 is None, then it is set to the complement of vertices1.
In a digraph, the external boundary of a vertex v are those vertices u with an arc (v, u).
Input:
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)]
self, [vertices=None], [labels=True], [ignore_direction=False]) |
Returns an iterator over the edges incident with any vertex given. If the graph is directed, iterates over edges going out only. If vertices is None, then returns an iterator over all edges. If self is directed, returns outgoing edges only.
Input:
sage: for i in graphs.PetersenGraph().edge_iterator([0]): ... print i (0, 1, None) (0, 4, None) (0, 5, None) sage: D = DiGraph( { 0 : [1,2], 1: [0] } ) sage: for i in D.edge_iterator([0]): ... print i (0, 1, None) (0, 2, None)
sage: G = graphs.TetrahedralGraph() sage: list(G.edge_iterator(labels=False)) [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
sage: D = DiGraph({1:[0], 2:[0]}) sage: list(D.edge_iterator(0)) [] sage: list(D.edge_iterator(0, ignore_direction=True)) [(1, 0, None), (2, 0, None)]
self, u, [v=None]) |
Returns the label of an edge. Note that if the graph allows multiple edges, then a list of labels on the edge is returned.
sage: G = Graph({0 : {1 : 'edgelabel'}}, implementation='networkx') sage: G.edges(labels=False) [(0, 1)] sage: G.edge_label( 0, 1 ) 'edgelabel' sage: D = DiGraph({0 : {1 : 'edgelabel'}}, implementation='networkx') sage: D.edges(labels=False) [(0, 1)] sage: D.edge_label( 0, 1 ) 'edgelabel'
sage: G = Graph(multiedges=True) sage: [G.add_edge(0,1,i) for i in range(1,6)] [None, None, None, None, None] sage: sorted(G.edge_label(0,1)) [1, 2, 3, 4, 5]
self) |
Returns a list of edge labels.
sage: G = Graph({0:{1:'x',2:'z',3:'a'}, 2:{5:'out'}}, implementation='networkx') sage: G.edge_labels() ['x', 'z', 'a', 'out'] sage: G = DiGraph({0:{1:'x',2:'z',3:'a'}, 2:{5:'out'}}, implementation='networkx') sage: G.edge_labels() ['x', 'z', 'a', 'out']
self, [labels=True], [sort=True]) |
Return a list of edges. Each edge is a triple (u,v,l) where u and v are vertices and l is a label.
Input:
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)]
self, [vertices=None], [labels=True]) |
Returns a list of edges incident with any vertex given. If vertices is None, returns a list of all edges in graph. For digraphs, only lists outward edges.
Input:
sage: graphs.PetersenGraph().edges_incident([0,9], labels=False) [(0, 1), (0, 4), (0, 5), (9, 4), (9, 6), (9, 7)] sage: D = DiGraph({0:[1]}) sage: D.edges_incident([0]) [(0, 1, None)] sage: D.edges_incident([1]) []
self, [laplacian=False]) |
Returns the eigenspaces of the adjacency matrix of the graph.
Input:
sage: C = graphs.CycleGraph(5) sage: E = C.eigenspaces() sage: E[0][0] -1.618... sage: E[1][0] # eigenspace computation is somewhat random Vector space of degree 5 and dimension 1 over Real Double Field User basis matrix: [ 0.632... -0.632... -0.447... -0.013... 0.073...]
sage: D = C.to_directed() sage: F = D.eigenspaces() sage: abs(E[0][0] - F[0][0]) < 0.00001 True
self, [set_embedding=True], [on_embedding=None], [minimal=True], [maximal=False], [circular=False], [ordered=True]) |
Returns the minimal genus of the graph. The genus of a compact surface is the number of handles it has. The genus of a graph is the minimal genus of the surface it can be embedded into.
Note - This function uses Euler's formula and thus it is necessary to consider only connected graphs.
Input:
sage: g = graphs.PetersenGraph() sage: g.genus() # tests for minimal genus by default 1 sage: g.genus(on_embedding=True, maximal=True) # on_embedding overrides minimal and maximal arguments 1 sage: g.genus(maximal=True) # setting maximal to True overrides default minimal=True 3 sage: g.genus(on_embedding=g.get_embedding()) # can also send a valid combinatorial embedding dict 3 sage: (graphs.CubeGraph(3)).genus() 0 sage: K23 = graphs.CompleteBipartiteGraph(2,3) sage: K23.genus() 0 sage: K33 = graphs.CompleteBipartiteGraph(3,3) sage: K33.genus() 1
Using the circular argument, we can compute the minimal genus preserving a planar, ordered boundary:
sage: cube = graphs.CubeGraph(3) sage: cube.set_boundary(['001','110']) sage: cube.genus() 0 sage: cube.is_circular_planar() False sage: cube.genus(circular=True) #long time 1 sage: cube.genus(circular=True, maximal=True) #long time 3 sage: cube.genus(circular=True, on_embedding=True) #long time 3
self) |
Returns the boundary of the (di)graph.
sage: G = graphs.PetersenGraph() sage: G.set_boundary([0,1,2,3,4]) sage: G.get_boundary() [0, 1, 2, 3, 4]
self) |
Returns the attribute _embedding if it exists. _embedding is a dictionary organized with vertex labels as keys and a list of each vertex's neighbors in clockwise order.
Error-checked to insure valid embedding is returned.
sage: G = graphs.PetersenGraph() sage: G.genus() 1 sage: G.get_embedding() {0: [1, 5, 4], 1: [0, 2, 6], 2: [1, 3, 7], 3: [8, 2, 4], 4: [0, 9, 3], 5: [0, 8, 7], 6: [8, 1, 9], 7: [9, 2, 5], 8: [3, 5, 6], 9: [4, 6, 7]}
self) |
Returns the position dictionary, a dictionary specifying the coordinates of each vertex.
self, vertex) |
Retrieve the object associated with a given vertex.
Input:
sage: d = {0 : graphs.DodecahedralGraph(), 1 : graphs.FlowerSnark(), 2 : graphs.MoebiusKantorGraph(), 3 : graphs.PetersenGraph() } sage: d[2] Moebius-Kantor Graph: Graph on 16 vertices sage: T = graphs.TetrahedralGraph() sage: T.vertices() [0, 1, 2, 3] sage: T.set_vertices(d) sage: T.get_vertex(1) Flower Snark: Graph on 20 vertices
self, [verts=None]) |
Return a dictionary of the objects associated to each vertex.
Input:
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}
self) |
Computes the girth of the graph. For directed graphs, computes the girth of the undirected graph.
The girth is the length of the shortest cycle in the graph. Graphs without cycles have infinite girth.
sage: graphs.TetrahedralGraph().girth() 3 sage: graphs.CubeGraph(3).girth() 4 sage: graphs.PetersenGraph().girth() 5 sage: graphs.HeawoodGraph().girth() 6 sage: graphs.trees(9).next().girth() +Infinity
self) |
Returns a representation in the DOT language, ready to render in graphviz.
sage: G = Graph({0:{1:None,2:None}, 1:{0:None,2:None}, 2:{0:None,1:None,3:'foo'}, 3:{2:'foo'}}, implementation='networkx') sage: s = G.graphviz_string() sage: s 'graph {\n"0";"1";"2";"3";\n"0"--"1";"0"--"2";"1"--"2";"2"--"3"[label="foo" ];\n}'
self, filename) |
Write a representation in the DOT language to the named file, ready to render in graphviz.
sage: G = Graph({0:{1:None,2:None}, 1:{0:None,2:None}, 2:{0:None,1:None,3:'foo'}, 3:{2:'foo'}}, implementation='networkx') sage: G.graphviz_to_file_named(os.environ['SAGE_TESTDIR']+'/temp_graphviz') sage: open(os.environ['SAGE_TESTDIR']+'/temp_graphviz').read() 'graph {\n"0";"1";"2";"3";\n"0"--"1";"0"--"2";"1"--"2";"2"--"3"[label="foo" ];\n}'
self, u, [v=None], [label=None]) |
Returns True if (u, v) is an edge, False otherwise.
Input: The following forms are accepted by NetworkX:
G.has_edge( 1, 2 ) G.has_edge( (1, 2) ) G.has_edge( 1, 2, 'label' )
sage: graphs.EmptyGraph().has_edge(9,2) False sage: DiGraph().has_edge(9,2) False sage: G = Graph(implementation='networkx') sage: G.add_edge(0,1,"label") sage: G.has_edge(0,1,"different label") False sage: G.has_edge(0,1,"label") True
self, vertex) |
Return True if vertex is one of the vertices of this graph.
Input:
sage: g = Graph({0:[1,2,3], 2:[4]}); g Graph on 5 vertices sage: 2 in g True sage: 10 in g False sage: graphs.PetersenGraph().has_vertex(99) False
self, [sparse=True]) |
Returns an incidence matrix of the (di)graph. Each row is a vertex, and each column is an edge. Note that in the case of graphs, there is a choice of orientation for each edge.
sage: G = graphs.CubeGraph(3) sage: G.incidence_matrix() [ 0 1 0 0 0 0 1 -1 0 0 0 0] [ 0 0 0 1 0 -1 -1 0 0 0 0 0] [-1 -1 -1 0 0 0 0 0 0 0 0 0] [ 1 0 0 -1 -1 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 1 0 0 1 -1] [ 0 0 0 0 0 1 0 0 1 0 0 1] [ 0 0 1 0 0 0 0 0 0 1 -1 0] [ 0 0 0 0 1 0 0 0 -1 -1 0 0]
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } ) sage: D.incidence_matrix() [-1 -1 -1 1 0 0 0 1 0 0] [ 1 0 0 -1 -1 0 0 0 0 1] [ 0 1 0 0 1 -1 0 0 0 0] [ 0 0 1 0 0 1 -1 0 0 0] [ 0 0 0 0 0 0 1 -1 -1 0] [ 0 0 0 0 0 0 0 0 1 -1]
self, start, end) |
Returns an exhaustive list of paths (also lists) through only interior vertices from vertex start to vertex end in the (di)graph.
Note - start and end do not necessarily have to be boundary vertices.
Input:
sage: eg1 = Graph({0:[1,2], 1:[4], 2:[3,4], 4:[5], 5:[6]}) sage: sorted(eg1.all_paths(0,6)) [[0, 1, 4, 5, 6], [0, 2, 4, 5, 6]] sage: eg2 = eg1.copy() sage: eg2.set_boundary([0,1,3]) sage: sorted(eg2.interior_paths(0,6)) [[0, 2, 4, 5, 6]] sage: sorted(eg2.all_paths(0,6)) [[0, 1, 4, 5, 6], [0, 2, 4, 5, 6]] sage: eg3 = graphs.PetersenGraph() sage: eg3.set_boundary([0,1,2,3,4]) sage: sorted(eg3.all_paths(1,4)) [[1, 0, 4], [1, 0, 5, 7, 2, 3, 4], [1, 0, 5, 7, 2, 3, 8, 6, 9, 4], [1, 0, 5, 7, 9, 4], [1, 0, 5, 7, 9, 6, 8, 3, 4], [1, 0, 5, 8, 3, 2, 7, 9, 4], [1, 0, 5, 8, 3, 4], [1, 0, 5, 8, 6, 9, 4], [1, 0, 5, 8, 6, 9, 7, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 8, 5, 0, 4], [1, 2, 3, 8, 5, 7, 9, 4], [1, 2, 3, 8, 6, 9, 4], [1, 2, 3, 8, 6, 9, 7, 5, 0, 4], [1, 2, 7, 5, 0, 4], [1, 2, 7, 5, 8, 3, 4], [1, 2, 7, 5, 8, 6, 9, 4], [1, 2, 7, 9, 4], [1, 2, 7, 9, 6, 8, 3, 4], [1, 2, 7, 9, 6, 8, 5, 0, 4], [1, 6, 8, 3, 2, 7, 5, 0, 4], [1, 6, 8, 3, 2, 7, 9, 4], [1, 6, 8, 3, 4], [1, 6, 8, 5, 0, 4], [1, 6, 8, 5, 7, 2, 3, 4], [1, 6, 8, 5, 7, 9, 4], [1, 6, 9, 4], [1, 6, 9, 7, 2, 3, 4], [1, 6, 9, 7, 2, 3, 8, 5, 0, 4], [1, 6, 9, 7, 5, 0, 4], [1, 6, 9, 7, 5, 8, 3, 4]] sage: sorted(eg3.interior_paths(1,4)) [[1, 6, 8, 5, 7, 9, 4], [1, 6, 9, 4]] sage: dg = DiGraph({0:[1,3,4], 1:[3], 2:[0,3,4],4:[3]}, boundary=[4]) sage: sorted(dg.all_paths(0,3)) [[0, 1, 3], [0, 3], [0, 4, 3]] sage: sorted(dg.interior_paths(0,3)) [[0, 1, 3], [0, 3]] sage: ug = dg.to_undirected() sage: sorted(ug.all_paths(0,3)) [[0, 1, 3], [0, 2, 3], [0, 2, 4, 3], [0, 3], [0, 4, 2, 3], [0, 4, 3]] sage: sorted(ug.interior_paths(0,3)) [[0, 1, 3], [0, 2, 3], [0, 3]]
self, [ordered=True], [kuratowski=False], [set_embedding=False], [set_pos=False]) |
A graph (with nonempty boundary) is circular planar if it has a planar embedding in which all boundary vertices can be drawn in order on a disc boundary, with all the interior vertices drawn inside the disc.
Returns True if the graph is circular planar, and False if it is not. If kuratowski is set to True, then this function will return a tuple, with boolean first entry and second entry the Kuratowski subgraph or minor isolated by the Boyer-Myrvold algorithm. Note that this graph might contain a vertex or edges that were not in the initial graph. These would be elements referred to below as parts of the wheel and the star, which were added to the graph to require that the boundary can be drawn on the boundary of a disc, with all other vertices drawn inside (and no edge crossings). For more information, refer to reference [2].
This is a linear time algorithm to test for circular planarity. It relies on the edge-addition planarity algorithm due to Boyer-Myrvold. We accomplish linear time for circular planarity by modifying the graph before running the general planarity algorithm.
REFERENCE: [1] John M. Boyer and Wendy J. Myrvold, On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. Journal of Graph Algorithms and Applications, Vol. 8, No. 3, pp. 241-273, 2004. [2] Kirkman, Emily A. O(n) Circular Planarity Testing. [Online] Available: soon!
Input:
sage: g439 = Graph({1:[5,7], 2:[5,6], 3:[6,7], 4:[5,6,7]}, implementation='networkx') sage: g439.set_boundary([1,2,3,4]) sage: g439.show(figsize=[2,2], vertex_labels=True, vertex_size=175) sage: g439.is_circular_planar() False sage: g439.is_circular_planar(kuratowski=True) (False, Graph on 7 vertices) sage: g439.set_boundary([1,2,3]) sage: g439.is_circular_planar(set_embedding=True, set_pos=False) True sage: g439.is_circular_planar(kuratowski=True) (True, None) sage: g439.get_embedding() {1: [7, 5], 2: [5, 6], 3: [6, 7], 4: [7, 6, 5], 5: [4, 2, 1], 6: [4, 3, 2], 7: [3, 4, 1]}
Order matters:
sage: K23 = graphs.CompleteBipartiteGraph(2,3) sage: K23.set_boundary([0,1,2,3]) sage: K23.is_circular_planar() False sage: K23.is_circular_planar(ordered=False) True sage: K23.set_boundary([0,2,1,3]) # Diff Order! sage: K23.is_circular_planar(set_embedding=True) True
self, [vertices=None], [directed_clique=False]) |
Returns True if the set vertices
is a clique, False if not. A
clique is a set of vertices such that there is an edge between
any two vertices.
Input:
sage: g = graphs.CompleteGraph(4) sage: g.is_clique([1,2,3]) True sage: g.is_clique() True sage: h = graphs.CycleGraph(4) sage: h.is_clique([1,2]) True sage: h.is_clique([1,2,3]) False sage: h.is_clique() False sage: i = graphs.CompleteGraph(4).to_directed() sage: i.delete_edge([0,1]) sage: i.is_clique() True sage: i.is_clique(directed_clique=True) False
self) |
Indicates whether the (di)graph is connected. Note that in a graph, path connected is equivalent to connected.
sage: G = Graph( { 0 : [1, 2], 1 : [2], 3 : [4, 5], 4 : [5] } ) sage: G.is_connected() False sage: G.add_edge(0,3) sage: G.is_connected() True sage: D = DiGraph( { 0 : [1, 2], 1 : [2], 3 : [4, 5], 4 : [5] } ) sage: D.is_connected() False sage: D.add_edge(0,3) sage: D.is_connected() True sage: D = DiGraph({1:[0], 2:[0]}) sage: D.is_connected() True
self) |
Returns True is the position dictionary for this graph is set and that position dictionary gives a planar embedding.
This simply checks all pairs of edges that don't share a vertex to make sure that they don't intersect.
NOTE: This function require that _pos attribute is set. (Returns false otherwise.)
sage: D = graphs.DodecahedralGraph() sage: D.set_planar_positions() sage: D.is_drawn_free_of_edge_crossings() True
self, partition, [quotient_matrix=False]) |
Checks whether the given partition is equitable with respect to self.
A partition is equitable with respect to a graph if for every pair of cells C1, C2 of the partition, the number of edges from a vertex of C1 to C2 is the same, over all vertices in C1.
Input:
sage: G = graphs.PetersenGraph() sage: G.is_equitable([[0,4],[1,3,5,9],[2,6,8],[7]]) False sage: G.is_equitable([[0,4],[1,3,5,9],[2,6,8,7]]) True sage: G.is_equitable([[0,4],[1,3,5,9],[2,6,8,7]], quotient_matrix=True) [1 2 0] [1 0 2] [0 2 1]
sage: ss = (graphs.WheelGraph(6)).line_graph(labels=False) sage: prt = [[(0, 1)], [(0, 2), (0, 3), (0, 4), (1, 2), (1, 4)], [(2, 3), (3, 4)]]
sage: ss.is_equitable(prt) Traceback (most recent call last): ... TypeError: Partition ([[(0, 1)], [(0, 2), (0, 3), (0, 4), (1, 2), (1, 4)], [(2, 3), (3, 4)]]) is not valid for this graph: vertices are incorrect.
sage: ss = (graphs.WheelGraph(5)).line_graph(labels=False) sage: ss.is_equitable(prt) False
self) |
Return true if the graph has an tour that visits each edge exactly once.
sage: graphs.CompleteGraph(4).is_eulerian() False sage: graphs.CycleGraph(4).is_eulerian() True sage: g = DiGraph({0:[1,2], 1:[2]}); g.is_eulerian() False sage: g = DiGraph({0:[2], 1:[3], 2:[0,1], 3:[2]}); g.is_eulerian() True
self) |
Return True if the graph is a forest, i.e. a disjoint union of trees.
sage: seven_acre_wood = sum(graphs.trees(7), Graph()) sage: seven_acre_wood.is_forest() True
self, [vertices=None]) |
Returns True if the set vertices
is an independent set, False
if not. An independent set is a set of vertices such that
there is no edge between any two vertices.
Input:
sage: graphs.CycleGraph(4).is_independent_set([1,3]) True sage: graphs.CycleGraph(4).is_independent_set([1,2,3]) False
self, other, [certify=False], [verbosity=0], [edge_labels=False]) |
Tests for isomorphism between self and other.
Input:
Graphs:
sage: from sage.groups.perm_gps.permgroup_named import SymmetricGroup sage: D = graphs.DodecahedralGraph() sage: E = D.copy() sage: gamma = SymmetricGroup(20).random_element() sage: E.relabel(gamma) sage: D.is_isomorphic(E) True
sage: D = graphs.DodecahedralGraph() sage: S = SymmetricGroup(20) sage: gamma = S.random_element() sage: E = D.copy() sage: E.relabel(gamma) sage: a,b = D.is_isomorphic(E, certify=True); a True sage: from sage.plot.plot import GraphicsArray sage: from sage.graphs.graph_fast import spring_layout_fast sage: position_D = spring_layout_fast(D) sage: position_E = {} sage: for vert in position_D: ... position_E[b[vert]] = position_D[vert] sage: GraphicsArray([D.plot(pos=position_D), E.plot(pos=position_E)]).show()
Multigraphs:
sage: G = Graph(multiedges=True) sage: G.add_edge((0,1,1)) sage: G.add_edge((0,1,2)) sage: G.add_edge((0,1,3)) sage: G.add_edge((0,1,4)) sage: H = Graph(multiedges=True, implementation='networkx') sage: H.add_edge((3,4)) sage: H.add_edge((3,4)) sage: H.add_edge((3,4)) sage: H.add_edge((3,4)) sage: G.is_isomorphic(H) True
Digraphs:
sage: A = DiGraph( { 0 : [1,2] } ) sage: B = DiGraph( { 1 : [0,2] } ) sage: A.is_isomorphic(B, certify=True) (True, {0: 1, 1: 0, 2: 2})
Edge labeled graphs:
sage: G = Graph(implementation='networkx') sage: G.add_edges( [(0,1,'a'),(1,2,'b'),(2,3,'c'),(3,4,'b'),(4,0,'a')] ) sage: H = G.relabel([1,2,3,4,0], inplace=False) sage: G.is_isomorphic(H, edge_labels=True) True
self, [on_embedding=None], [kuratowski=False], [set_embedding=False], [set_pos=False]) |
Returns True if the graph is planar, and False otherwise. This wraps the reference implementation provided by John Boyer of the linear time planarity algorithm by edge addition due to Boyer Myrvold. (See reference code in graphs.planarity).
Note - the argument on_embedding takes precedence over set_embedding. This means that only the on_embedding combinatorial embedding will be tested for planarity and no _embedding attribute will be set as a result of this function call, unless on_embedding is None.
REFERENCE: [1] John M. Boyer and Wendy J. Myrvold, On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. Journal of Graph Algorithms and Applications, Vol. 8, No. 3, pp. 241-273, 2004.
Input:
sage: g = graphs.CubeGraph(4) sage: g.is_planar() False
sage: g = graphs.CircularLadderGraph(4) sage: g.is_planar(set_embedding=True) True sage: g.get_embedding() {0: [1, 4, 3], 1: [2, 5, 0], 2: [3, 6, 1], 3: [0, 7, 2], 4: [0, 5, 7], 5: [1, 6, 4], 6: [2, 7, 5], 7: [4, 6, 3]}
sage: g = graphs.PetersenGraph() sage: (g.is_planar(kuratowski=True))[1].adjacency_matrix() [0 1 0 0 0 1 0 0 0 0] [1 0 1 0 0 0 1 0 0 0] [0 1 0 1 0 0 0 0 0 0] [0 0 1 0 1 0 0 0 1 0] [0 0 0 1 0 0 0 0 0 1] [1 0 0 0 0 0 0 1 1 0] [0 1 0 0 0 0 0 0 1 1] [0 0 0 0 0 1 0 0 0 1] [0 0 0 1 0 1 1 0 0 0] [0 0 0 0 1 0 1 1 0 0]
sage: k43 = graphs.CompleteBipartiteGraph(4,3) sage: result = k43.is_planar(kuratowski=True); result (False, Graph on 6 vertices) sage: result[1].is_isomorphic(graphs.CompleteBipartiteGraph(3,3)) True
self, other) |
Tests whether self is a subgraph of other.
sage: P = graphs.PetersenGraph() sage: G = P.subgraph(range(6)) sage: G.is_subgraph(P) True
self) |
Return True if the graph is a tree.
sage: for g in graphs.trees(6): ... g.is_tree() True True True True True True
self, [partition=None], [verbosity=0], [edge_labels=False], [order=False], [return_group=True], [orbits=False]) |
Returns whether the automorphism group of self is transitive within the partition provided, by default the unit partition of the vertices of self (thus by default tests for vertex transitivity in the usual sense).
sage: G = Graph({0:[1],1:[2]}) sage: G.is_vertex_transitive() False sage: P = graphs.PetersenGraph() sage: P.is_vertex_transitive() True sage: D = graphs.DodecahedralGraph() sage: D.is_vertex_transitive() True sage: R = graphs.RandomGNP(2000, .01) sage: R.is_vertex_transitive() False
self, [weighted=None], [boundary_first=False]) |
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 weighted == True, the weighted adjacency matrix is used for M, and the diagonal entries are the row-sums of M.
Author: Tom Boothby
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: G.set_boundary([2,3]) sage: M = G.kirchhoff_matrix(weighted=True, boundary_first=True); M [ 5 0 -3 -2] [ 0 4 -4 0] [-3 -4 8 -1] [-2 0 -1 3] sage: M = G.kirchhoff_matrix(boundary_first=True); M [ 2 0 -1 -1] [ 0 1 -1 0] [-1 -1 3 -1] [-1 0 -1 2] sage: M = G.laplacian_matrix(boundary_first=True); M [ 2 0 -1 -1] [ 0 1 -1 0] [-1 -1 3 -1] [-1 0 -1 2]
self, [weighted=None], [boundary_first=False]) |
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 weighted == True, the weighted adjacency matrix is used for M, and the diagonal entries are the row-sums of M.
Author: Tom Boothby
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: G.set_boundary([2,3]) sage: M = G.kirchhoff_matrix(weighted=True, boundary_first=True); M [ 5 0 -3 -2] [ 0 4 -4 0] [-3 -4 8 -1] [-2 0 -1 3] sage: M = G.kirchhoff_matrix(boundary_first=True); M [ 2 0 -1 -1] [ 0 1 -1 0] [-1 -1 3 -1] [-1 0 -1 2] sage: M = G.laplacian_matrix(boundary_first=True); M [ 2 0 -1 -1] [ 0 1 -1 0] [-1 -1 3 -1] [-1 0 -1 2]
self, other) |
Returns the lexicographic product of self and other.
The lexicographic 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, or - u = w and (v, x) is an edge of other.
sage: Z = graphs.CompleteGraph(2) sage: C = graphs.CycleGraph(5) sage: L = C.lexicographic_product(Z); L Graph on 10 vertices sage: L.plot().show()
sage: D = graphs.DodecahedralGraph() sage: P = graphs.PetersenGraph() sage: L = D.lexicographic_product(P); L Graph on 200 vertices sage: L.plot().show()
self, [labels=True]) |
Returns the line graph of the (di)graph.
The line graph of an undirected graph G is an undirected graph H such that the vertices of H are the edges of G and two vertices e and f of H are adjacent if e and f share a common vertex in G. In other words, an edge in H represents a path of length 2 in G.
The line graph of a directed graph G is a directed graph H such that the vertices of H are the edges of G and two vertices e and f of H are adjacent if e and f share a common vertex in G and the terminal vertex of e is the initial vertex of f. In other words, an edge in H represents a (directed) path of length 2 in G.
sage: g=graphs.CompleteGraph(4) sage: h=g.line_graph() sage: h.vertices() [(0, 1, None), (0, 2, None), (0, 3, None), (1, 2, None), (1, 3, None), (2, 3, None)] sage: h.am() [0 1 1 1 1 0] [1 0 1 1 0 1] [1 1 0 0 1 1] [1 1 0 0 1 1] [1 0 1 1 0 1] [0 1 1 1 1 0] sage: h2=g.line_graph(labels=False) sage: h2.vertices() [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] sage: h2.am()==h.am() True sage: g = DiGraph([[1..4],lambda i,j: i<j], implementation='networkx') sage: h = g.line_graph() sage: h.vertices() [(1, 2, None), (1, 3, None), (1, 4, None), (2, 3, None), (2, 4, None), (3, 4, None)] sage: h.edges() [((1, 2, None), (2, 3, None), None), ((1, 2, None), (2, 4, None), None), ((1, 3, None), (3, 4, None), None), ((2, 3, None), (3, 4, None), None)]
self) |
Returns a list of all loops in the graph.
sage: G = Graph(4, loops=True) sage: G.add_edges( [ (0,0), (1,1), (2,2), (3,3), (2,3) ] ) sage: G.loop_edges() [(0, 0, None), (1, 1, None), (2, 2, None), (3, 3, None)]
sage: D = DiGraph(4, loops=True) sage: D.add_edges( [ (0,0), (1,1), (2,2), (3,3), (2,3) ] ) sage: D.loop_edges() [(0, 0, None), (1, 1, None), (2, 2, None), (3, 3, None)]
sage: G = Graph(4, loops=True, multiedges=True) sage: G.add_edges([(i,i) for i in range(4)]) sage: G.loop_edges() [(0, 0, None), (1, 1, None), (2, 2, None), (3, 3, None)]
self) |
Returns a list of vertices with loops.
sage: G = Graph({0 : [0], 1: [1,2,3], 2: [3]}, loops=True) sage: G.loop_vertices() [0, 1]
self, [new=None]) |
Returns whether loops are permitted in the graph.
Input:
sage: G = Graph(); G Graph on 0 vertices sage: G.loops(True)
sage: D = DiGraph(); D Digraph on 0 vertices sage: D.loops() False sage: D.loops(True) sage: D.loops() True
self, [new=None]) |
Returns whether multiple edges are permitted in the (di)graph.
Input:
sage: G = Graph(multiedges=True); G Multi-graph on 0 vertices sage: G.multiple_edges(False); G Graph on 0 vertices sage: D = DiGraph(multiedges=True); D Multi-digraph on 0 vertices sage: D.multiple_edges(False); D Digraph on 0 vertices
self, [new=None]) |
Returns the name of the (di)graph.
Input:
sage: d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7, 8], 6: [8,9], 7: [9]} sage: G = Graph(d); G Graph on 10 vertices sage: G.name("Petersen Graph"); G Petersen Graph: Graph on 10 vertices sage: G.name(new=""); G Graph on 10 vertices sage: G.name() ''
self, vertex) |
Return an iterator over neighbors of vertex.
sage: G = graphs.CubeGraph(3) sage: for i in G.neighbor_iterator('010'): ... print i 011 000 110 sage: D = G.to_directed() sage: for i in D.neighbor_iterator('010'): ... print i 011 000 110
sage: D = DiGraph({0:[1,2], 3:[0]}) sage: list(D.neighbor_iterator(0)) [1, 2, 3]
self, vertex) |
Return a list of neighbors (in and out if directed) of vertex.
G[vertex] also works.
sage: P = graphs.PetersenGraph() sage: sorted(P.neighbors(3)) [2, 4, 8] sage: sorted(P[4]) [0, 3, 9]
self, [copy=True]) |
Creates a new NetworkX graph from the SAGE graph.
Input:
sage: G = graphs.TetrahedralGraph() sage: N = G.networkx_graph() sage: type(N) <class 'networkx.xgraph.XGraph'>
sage: G = graphs.TetrahedralGraph() sage: G = Graph(G, implementation='networkx') sage: N = G.networkx_graph() sage: G._backend._nxg is N False
sage: G = Graph(graphs.TetrahedralGraph(), implementation='networkx') sage: N = G.networkx_graph(copy=False) sage: G._backend._nxg is N True
self) |
Returns the number of edges.
sage: G = graphs.PetersenGraph() sage: G.size() 15
self) |
Returns the number of vertices. Note that len(G) returns the number of vertices in G also.
sage: G = graphs.PetersenGraph() sage: G.order() 10
sage: G = graphs.TetrahedralGraph() sage: len(G) 4
self) |
Returns the number of edges that are loops.
sage: G = Graph(4, loops=True) sage: G.add_edges( [ (0,0), (1,1), (2,2), (3,3), (2,3) ] ) sage: G.edges(labels=False) [(0, 0), (1, 1), (2, 2), (2, 3), (3, 3)] sage: G.number_of_loops() 4
sage: D = DiGraph(4, loops=True) sage: D.add_edges( [ (0,0), (1,1), (2,2), (3,3), (2,3) ] ) sage: D.edges(labels=False) [(0, 0), (1, 1), (2, 2), (2, 3), (3, 3)] sage: D.number_of_loops() 4
self) |
Returns the number of vertices. Note that len(G) returns the number of vertices in G also.
sage: G = graphs.PetersenGraph() sage: G.order() 10
sage: G = graphs.TetrahedralGraph() sage: len(G) 4
self) |
Returns the set of vertices in the periphery, i.e. whose eccentricity is equal to the diameter of the (di)graph.
In other words, the periphery is the set of vertices achieving the maximum eccentricity.
sage: G = graphs.DiamondGraph() sage: G.periphery() [0, 3] sage: P = graphs.PetersenGraph() sage: P.subgraph(P.periphery()) == P True sage: S = graphs.StarGraph(19) sage: S.periphery() [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] sage: G = Graph(sparse=True) sage: G.periphery() [] sage: G.add_vertex() sage: G.periphery() [0]
self, [pos=None], [layout=None], [vertex_labels=True], [edge_labels=False], [vertex_size=200], [graph_border=False], [vertex_colors=None], [partition=None], [edge_colors=None], [scaling_term=0.05], [iterations=50], [loop_size=0.1], [talk=False], [color_by_label=False], [heights=None], [edge_style=None]) |
Returns a graphics object representing the (di)graph.
Input:
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: []}, implementation='networkx' ) 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.plot 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.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: from sage.graphs.bruhat_sn import * sage: S = BruhatSn(5) sage: S.to_directed().show(heights = S.lengths, vertex_labels=False, vertex_size=0, figsize=[10,10], edge_style={'width': 0.1, 'rgbcolor': (0,1,0)})
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)
sage: G = Graph() sage: P = G.plot() sage: P.axes() False sage: G = DiGraph() sage: P = G.plot() sage: P.axes() False
self, [bgcolor=(1, 1, 1)], [vertex_colors=None], [vertex_size=0.06], [edge_colors=None], [edge_size=0.02], [edge_size2=0.0325], [pos3d=None], [iterations=50], [color_by_label=False], [engine=jmol]) |
Plot a graph in three dimensions.
Input:
sage: G = graphs.CubeGraph(5) sage: G.plot3d(iterations=500, edge_size=None, vertex_size=0.04)
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)
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.plot 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
self) |
Returns the radius of the (di)graph.
The radius is defined to be the minimum eccentricity of any vertex, where the eccentricity is the maximum distance to any other vertex.
The more symmetric a graph is, the smaller (diameter - radius) is.
sage: G = graphs.BarbellGraph(9, 3) sage: G.radius() 3 sage: G.diameter() 6
sage: G = graphs.OctahedralGraph() sage: G.radius() 2 sage: G.diameter() 2
self, p, [inplace=False]) |
Return a random subgraph that contains each vertex with prob. p.
sage: P = graphs.PetersenGraph() sage: P.random_subgraph(.25) Subgraph of (Petersen graph): Graph on 4 vertices
self, [perm=None], [inplace=True], [return_map=False]) |
Uses a dictionary, list, or permutation to relabel the (di)graph. If perm is a dictionary d, each old vertex v is a key in the dictionary, and its new label is d[v].
If perm is a list, we think of it as a map
with the assumption that the vertices are
.
If perm is a permutation, the permutation is simply applied to
the graph, under the assumption that the vertices are
. The permutation acts on the set
, where we think of
.
If no arguments are provided, the graph is relabeled to be on the
vertices
.
Input:
sage: G = graphs.PathGraph(3) sage: G.am() [0 1 0] [1 0 1] [0 1 0]
Relabeling using a dictionary:
sage: G.relabel({1:2,2:1}, inplace=False).am() [0 0 1] [0 0 1] [1 1 0]
Relabeling using a list:
sage: G.relabel([0,2,1], inplace=False).am() [0 0 1] [0 0 1] [1 1 0]
Relabeling using a SAGE permutation:
sage: from sage.groups.perm_gps.permgroup_named import SymmetricGroup sage: S = SymmetricGroup(3) sage: gamma = S('(1,2)') sage: G.relabel(gamma, inplace=False).am() [0 0 1] [0 0 1] [1 1 0]
Relabeling to simpler labels:
sage: G = graphs.CubeGraph(3) sage: G.vertices() ['000', '001', '010', '011', '100', '101', '110', '111'] sage: G.relabel() sage: G.vertices() [0, 1, 2, 3, 4, 5, 6, 7]
sage: G = graphs.CubeGraph(3) sage: expecting = {'000': 0, '001': 1, '010': 2, '011': 3, '100': 4, '101': 5, '110': 6, '111': 7} sage: G.relabel(return_map=True) == expecting True
TESTS:
sage: P = Graph(graphs.PetersenGraph(), sparse=True) sage: P.delete_edge([0,1]) sage: P.add_edge((4,5)) sage: P.add_edge((2,6)) sage: P.delete_vertices([0,1]) sage: P.relabel()
self, [vertices=None]) |
Removes loops on vertices in vertices. If vertices is None, removes all loops.
EXAMPLE
sage: G = Graph(4, loops=True) sage: G.add_edges( [ (0,0), (1,1), (2,2), (3,3), (2,3) ] ) sage: G.edges(labels=False) [(0, 0), (1, 1), (2, 2), (2, 3), (3, 3)] sage: G.remove_loops() sage: G.edges(labels=False) [(2, 3)] sage: G.loops() True
sage: D = DiGraph(4, loops=True) sage: D.add_edges( [ (0,0), (1,1), (2,2), (3,3), (2,3) ] ) sage: D.edges(labels=False) [(0, 0), (1, 1), (2, 2), (2, 3), (3, 3)] sage: D.remove_loops() sage: D.edges(labels=False) [(2, 3)] sage: D.loops() True
self) |
Removes all multiple edges, retaining one edge for each.
sage: G = Graph(multiedges=True, implementation='networkx') sage: G.add_edges( [ (0,1), (0,1), (0,1), (0,1), (1,2) ] ) sage: G.edges(labels=False) [(0, 1), (0, 1), (0, 1), (0, 1), (1, 2)]
sage: G.remove_multiple_edges() sage: G.edges(labels=False) [(0, 1), (1, 2)]
sage: D = DiGraph(multiedges=True) sage: D.add_edges( [ (0,1,1), (0,1,2), (0,1,3), (0,1,4), (1,2) ] ) sage: D.edges(labels=False) [(0, 1), (0, 1), (0, 1), (0, 1), (1, 2)] sage: D.remove_multiple_edges() sage: D.edges(labels=False) [(0, 1), (1, 2)]
self, boundary) |
Sets the boundary of the (di)graph.
sage: G = graphs.PetersenGraph() sage: G.set_boundary([0,1,2,3,4]) sage: G.get_boundary() [0, 1, 2, 3, 4]
self, u, v, l) |
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:
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] }, implementation='networkx') 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()
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, implementation='networkx') 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)]
self, embedding) |
Sets a combinatorial embedding dictionary to _embedding attribute. Dictionary is organized with vertex labels as keys and a list of each vertex's neighbors in clockwise order.
Dictionary is error-checked for validity.
Input:
sage: G = graphs.PetersenGraph() sage: G.set_embedding({0: [1, 5, 4], 1: [0, 2, 6], 2: [1, 3, 7], 3: [8, 2, 4], 4: [0, 9, 3], 5: [0, 8, 7], 6: [8, 1, 9], 7: [9, 2, 5], 8: [3, 5, 6], 9: [4, 6, 7]}) sage: G.set_embedding({'s': [1, 5, 4], 1: [0, 2, 6], 2: [1, 3, 7], 3: [8, 2, 4], 4: [0, 9, 3], 5: [0, 8, 7], 6: [8, 1, 9], 7: [9, 2, 5], 8: [3, 5, 6], 9: [4, 6, 7]}) Traceback (most recent call last): ... Exception: embedding is not valid for Petersen graph
self, [set_embedding=False], [on_embedding=None], [external_face=None], [test=False], [circular=False]) |
Uses Schnyder's algorithm to determine positions for a planar embedding of self, raising an error if self is not planar.
Input:
sage: g = graphs.PathGraph(10) sage: g.set_planar_positions(test=True) True sage: g = graphs.BalancedTree(3,4) sage: g.set_planar_positions(test=True) True sage: g = graphs.CycleGraph(7) sage: g.set_planar_positions(test=True) True sage: g = graphs.CompleteGraph(5) sage: g.set_planar_positions(test=True,set_embedding=True) Traceback (most recent call last): ... Exception: Complete graph is not a planar graph.
self, pos) |
Sets the position dictionary, a dictionary specifying the coordinates of each vertex.
self, vertex, object) |
Associate an arbitrary object with a vertex.
Input:
sage: T = graphs.TetrahedralGraph() sage: T.vertices() [0, 1, 2, 3] sage: T.set_vertex(1, graphs.FlowerSnark()) sage: T.get_vertex(1) Flower Snark: Graph on 20 vertices
self, vertex_dict) |
Associate arbitrary objects with each vertex, via an association dictionary.
Input:
sage: d = {0 : graphs.DodecahedralGraph(), 1 : graphs.FlowerSnark(), 2 : graphs.MoebiusKantorGraph(), 3 : graphs.PetersenGraph() } sage: d[2] Moebius-Kantor Graph: Graph on 16 vertices sage: T = graphs.TetrahedralGraph() sage: T.vertices() [0, 1, 2, 3] sage: T.set_vertices(d) sage: T.get_vertex(1) Flower Snark: Graph on 20 vertices
self, u, v, [by_weight=False], [bidirectional=True]) |
Returns a list of vertices representing some shortest path from u to v: if there is no path from u to v, the list is empty.
Input:
sage: D = graphs.DodecahedralGraph() sage: D.shortest_path(4, 9) [4, 17, 16, 12, 13, 9] sage: D.shortest_path(5, 5) [5] sage: D.delete_edges(D.edges_incident(13)) sage: D.shortest_path(13, 4) [] sage: G = Graph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} }, sparse=True ) sage: G.plot(edge_labels=True).show() sage: G.shortest_path(0, 3) [0, 4, 3] sage: G.shortest_path(0, 3, by_weight=True) [0, 1, 2, 3]
self, [by_weight=True], [default_weight=1]) |
Uses the Floyd-Warshall algorithm to find a shortest weighted path for each pair of vertices.
The weights (labels) on the vertices can be anything that can be compared and can be summed.
Input:
sage: G = Graph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} }, sparse=True ) sage: G.plot(edge_labels=True).show() sage: dist, pred = G.shortest_path_all_pairs() sage: dist {0: {0: 0, 1: 1, 2: 2, 3: 3, 4: 2}, 1: {0: 1, 1: 0, 2: 1, 3: 2, 4: 3}, 2: {0: 2, 1: 1, 2: 0, 3: 1, 4: 3}, 3: {0: 3, 1: 2, 2: 1, 3: 0, 4: 2}, 4: {0: 2, 1: 3, 2: 3, 3: 2, 4: 0}} sage: pred {0: {0: None, 1: 0, 2: 1, 3: 2, 4: 0}, 1: {0: 1, 1: None, 2: 1, 3: 2, 4: 0}, 2: {0: 1, 1: 2, 2: None, 3: 2, 4: 3}, 3: {0: 1, 1: 2, 2: 3, 3: None, 4: 3}, 4: {0: 4, 1: 0, 2: 3, 3: 4, 4: None}} sage: pred[0] {0: None, 1: 0, 2: 1, 3: 2, 4: 0}
So for example the shortest weighted path from 0 to 3 is obtained as follows. The predecessor of 3 is pred[0][3] == 2, the predecessor of 2 is pred[0][2] == 1, and the predecessor of 1 is pred[0][1] == 0.
sage: G = Graph( { 0: {1:None}, 1: {2:None}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} }, sparse=True ) sage: G.shortest_path_all_pairs(by_weight=False) ({0: {0: 0, 1: 1, 2: 2, 3: 2, 4: 1}, 1: {0: 1, 1: 0, 2: 1, 3: 2, 4: 2}, 2: {0: 2, 1: 1, 2: 0, 3: 1, 4: 2}, 3: {0: 2, 1: 2, 2: 1, 3: 0, 4: 1}, 4: {0: 1, 1: 2, 2: 2, 3: 1, 4: 0}}, {0: {0: None, 1: 0, 2: 1, 3: 4, 4: 0}, 1: {0: 1, 1: None, 2: 1, 3: 2, 4: 0}, 2: {0: 1, 1: 2, 2: None, 3: 2, 4: 3}, 3: {0: 4, 1: 2, 2: 3, 3: None, 4: 3}, 4: {0: 4, 1: 0, 2: 3, 3: 4, 4: None}}) sage: G.shortest_path_all_pairs() ({0: {0: 0, 1: 1, 2: 2, 3: 3, 4: 2}, 1: {0: 1, 1: 0, 2: 1, 3: 2, 4: 3}, 2: {0: 2, 1: 1, 2: 0, 3: 1, 4: 3}, 3: {0: 3, 1: 2, 2: 1, 3: 0, 4: 2}, 4: {0: 2, 1: 3, 2: 3, 3: 2, 4: 0}}, {0: {0: None, 1: 0, 2: 1, 3: 2, 4: 0}, 1: {0: 1, 1: None, 2: 1, 3: 2, 4: 0}, 2: {0: 1, 1: 2, 2: None, 3: 2, 4: 3}, 3: {0: 1, 1: 2, 2: 3, 3: None, 4: 3}, 4: {0: 4, 1: 0, 2: 3, 3: 4, 4: None}}) sage: G.shortest_path_all_pairs(default_weight=200) ({0: {0: 0, 1: 200, 2: 5, 3: 4, 4: 2}, 1: {0: 200, 1: 0, 2: 200, 3: 201, 4: 202}, 2: {0: 5, 1: 200, 2: 0, 3: 1, 4: 3}, 3: {0: 4, 1: 201, 2: 1, 3: 0, 4: 2}, 4: {0: 2, 1: 202, 2: 3, 3: 2, 4: 0}}, {0: {0: None, 1: 0, 2: 3, 3: 4, 4: 0}, 1: {0: 1, 1: None, 2: 1, 3: 2, 4: 0}, 2: {0: 4, 1: 2, 2: None, 3: 2, 4: 3}, 3: {0: 4, 1: 2, 2: 3, 3: None, 4: 3}, 4: {0: 4, 1: 0, 2: 3, 3: 4, 4: None}})
self, u, v, [by_weight=False], [bidirectional=True], [weight_sum=None]) |
Returns the minimal length of paths from u to v: if there is no path from u to v, returns Infinity.
Input:
sage: D = graphs.DodecahedralGraph() sage: D.shortest_path_length(4, 9) 5 sage: D.shortest_path_length(5, 5) 0 sage: D.delete_edges(D.edges_incident(13)) sage: D.shortest_path_length(13, 4) +Infinity sage: G = Graph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} }, sparse=True ) sage: G.plot(edge_labels=True).show() sage: G.shortest_path_length(0, 3) 2 sage: G.shortest_path_length(0, 3, by_weight=True) 3
self, u, [by_weight=False], [weight_sums=None]) |
Returns a dictionary of shortest path lengths keyed by targets that are connected by a path from u.
Input:
sage: D = graphs.DodecahedralGraph() sage: D.shortest_path_lengths(0) {0: 0, 1: 1, 2: 2, 3: 2, 4: 3, 5: 4, 6: 3, 7: 3, 8: 2, 9: 2, 10: 1, 11: 2, 12: 3, 13: 3, 14: 4, 15: 5, 16: 4, 17: 3, 18: 2, 19: 1} sage: G = Graph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} }, sparse=True ) sage: G.plot(edge_labels=True).show() sage: G.shortest_path_lengths(0, by_weight=True) {0: 0, 1: 1, 2: 2, 3: 3, 4: 2}
self, u, [by_weight=False], [cutoff=None]) |
Returns a dictionary d of shortest paths d[v] from u to v, for each vertex v connected by a path from u.
Input:
sage: D = graphs.DodecahedralGraph() sage: D.shortest_paths(0) {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 19, 3], 4: [0, 19, 3, 4], 5: [0, 19, 3, 4, 5], 6: [0, 1, 2, 6], 7: [0, 1, 8, 7], 8: [0, 1, 8], 9: [0, 10, 9], 10: [0, 10], 11: [0, 10, 11], 12: [0, 10, 11, 12], 13: [0, 10, 9, 13], 14: [0, 1, 8, 7, 14], 15: [0, 10, 11, 12, 16, 15], 16: [0, 10, 11, 12, 16], 17: [0, 19, 18, 17], 18: [0, 19, 18], 19: [0, 19]} sage: D.shortest_paths(0, cutoff=2) {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 19, 3], 8: [0, 1, 8], 9: [0, 10, 9], 10: [0, 10], 11: [0, 10, 11], 18: [0, 19, 18], 19: [0, 19]} sage: G = Graph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} }, sparse=True ) sage: G.plot(edge_labels=True).show() sage: G.shortest_paths(0, by_weight=True) {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 4]}
self, [pos=None], [layout=None], [vertex_labels=True], [edge_labels=False], [vertex_size=200], [graph_border=False], [vertex_colors=None], [edge_colors=None], [partition=None], [scaling_term=0.05], [talk=False], [iterations=50], [loop_size=0.1], [color_by_label=False], [heights=None], [edge_style=None]) |
Shows the (di)graph.
Input:
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: []}, implementation='networkx' ) 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.plot 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.loops(True) sage: G.add_edge(0,0) sage: G.show()
self, [bgcolor=(1, 1, 1)], [vertex_colors=None], [vertex_size=0.06], [edge_colors=None], [edge_size=0.02], [edge_size2=0.0325], [pos3d=None], [iterations=50], [color_by_label=False], [engine=jmol]) |
Plots the graph using Tachyon, and shows the resulting plot.
Input:
sage: G = graphs.CubeGraph(5) sage: G.show3d(iterations=500, edge_size=None, vertex_size=0.04)
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.show3d(vertex_size=0.03, edge_size=0.01, edge_size2=0.02, vertex_colors={(1,1,1):G.vertices()}, bgcolor=(0,0,0), color_by_label=True, iterations=200)
Some Tachyon examples:
sage: D = graphs.DodecahedralGraph() sage: D.show3d(engine='tachyon') # long time
sage: G = graphs.PetersenGraph() sage: G.show3d(engine='tachyon', vertex_colors={(0,0,1):G.vertices()}) # long time
sage: C = graphs.CubeGraph(4) sage: C.show3d(engine='tachyon', edge_colors={(0,1,0):C.edges()}, vertex_colors={(1,1,1):C.vertices()}, bgcolor=(0,0,0)) # long time
sage: K = graphs.CompleteGraph(3) sage: K.show3d(engine='tachyon', edge_colors={(1,0,0):[(0,1,None)], (0,1,0):[(0,2,None)], (0,0,1):[(1,2,None)]}) # long time
self) |
Returns the number of edges.
sage: G = graphs.PetersenGraph() sage: G.size() 15
self, [laplacian=False]) |
Returns the spectrum of the graph, the eigenvalues of the adjacency matrix
Input:
sage: P = graphs.PetersenGraph() sage: P.spectrum() [-2.0, -2.0, -2.0, -2.0, 1.0, 1.0, 1.0, 1.0, 1.0, 3.0] sage: P.spectrum(laplacian=True) # random low-order bits (at least for first eigenvalue) [-1.41325497305e-16, 2.0, 2.0, 2.0, 2.0, 2.0, 5.0, 5.0, 5.0, 5.0]
sage: D = P.to_directed() sage: D.delete_edge(7,9) sage: D.spectrum() [-2.0, -2.0, -2.0, -1.7..., 0.8..., 1.0, 1.0, 1.0, 1.0, 2.9...]
self, other) |
Returns the strong product of self and other.
The strong product of G and H is the graph L with vertex set V(L) equal to the Cartesian product of the vertices V(G) and V(H), and ((u,v), (w,x)) is an edge iff either - (u, w) is an edge of self and v = x, or - (v, x) is an edge of other and u = w, or - (u, w) is an edge of self and (v, x) is an edge of other. In other words, the edges of the strong product is the union of the edges of the tensor and Cartesian products.
sage: Z = graphs.CompleteGraph(2) sage: C = graphs.CycleGraph(5) sage: S = C.strong_product(Z); S Graph on 10 vertices sage: S.plot().show()
sage: D = graphs.DodecahedralGraph() sage: P = graphs.PetersenGraph() sage: S = D.strong_product(P); S Graph on 200 vertices sage: S.plot().show()
self, [vertices=None], [edges=None], [inplace=False], [vertex_property=None], [edge_property=None]) |
Returns the subgraph containing the given vertices and edges. If either vertices or edges are not specified, they are assumed to be all vertices or edges. If edges are not specified, returns the subgraph induced by the vertices.
Input:
sage: G = graphs.CompleteGraph(9) sage: H = G.subgraph([0,1,2]); H Subgraph of (Complete graph): Graph on 3 vertices sage: G Complete graph: Graph on 9 vertices sage: J = G.subgraph(edges=[(0,1)]) sage: J.edges(labels=False) [(0, 1)] sage: J.vertices()==G.vertices() True sage: G.subgraph([0,1,2], inplace=True); G Subgraph of (Complete graph): Graph on 3 vertices sage: G.subgraph()==G True
sage: D = graphs.CompleteGraph(9).to_directed() sage: H = D.subgraph([0,1,2]); H Subgraph of (Complete graph): Digraph on 3 vertices sage: H = D.subgraph(edges=[(0,1), (0,2)]) sage: H.edges(labels=False) [(0, 1), (0, 2)] sage: H.vertices()==D.vertices() True sage: D Complete graph: Digraph on 9 vertices sage: D.subgraph([0,1,2], inplace=True); D Subgraph of (Complete graph): Digraph on 3 vertices sage: D.subgraph()==D True
A more complicated example involving multiple edges and labels.
sage: G = Graph(multiedges=True, implementation='networkx') sage: G.add_edges([(0,1,'a'), (0,1,'b'), (1,0,'c'), (0,2,'d'), (0,2,'e'), (2,0,'f'), (1,2,'g')]) sage: G.subgraph(edges=[(0,1), (0,2,'d'), (0,2,'not in graph')]).edges() [(0, 1, 'a'), (0, 1, 'b'), (0, 1, 'c'), (0, 2, 'd')] sage: J = G.subgraph(vertices=[0,1], edges=[(0,1,'a'), (0,2,'c')]) sage: J.edges() [(0, 1, 'a')] sage: J.vertices() [0, 1]
sage: D = DiGraph(multiedges=True, implementation='networkx') sage: D.add_edges([(0,1,'a'), (0,1,'b'), (1,0,'c'), (0,2,'d'), (0,2,'e'), (2,0,'f'), (1,2,'g')]) sage: D.subgraph(edges=[(0,1), (0,2,'d'), (0,2,'not in graph')]).edges() [(0, 1, 'a'), (0, 1, 'b'), (0, 2, 'd')] sage: H = D.subgraph(vertices=[0,1], edges=[(0,1,'a'), (0,2,'c')]) sage: H.edges() [(0, 1, 'a')] sage: H.vertices() [0, 1]
Using the property arguments:
sage: P = graphs.PetersenGraph() sage: S = P.subgraph(vertex_property = lambda v : v%2 == 0) sage: S.vertices() [0, 2, 4, 6, 8]
sage: C = graphs.CubeGraph(2) sage: S = C.subgraph(edge_property=(lambda e: e[0][0] == e[1][0])) sage: C.edges() [('00', '01', None), ('10', '00', None), ('11', '01', None), ('11', '10', None)] sage: S.edges() [('00', '01', None), ('11', '10', None)]
TESTS: We should delete unused _pos dictionary entries
sage: g = graphs.PathGraph(10) sage: h = g.subgraph([3..5]) sage: h._pos.keys() [3, 4, 5]
self, other) |
Returns the tensor product, also called the categorical product, of self and other.
The tensor product of G and H is the graph L with vertex set V(L) equal to the Cartesian product of the vertices V(G) and V(H), and ((u,v), (w,x)) is an edge iff - (u, w) is an edge of self, and - (v, x) is an edge of other.
sage: Z = graphs.CompleteGraph(2) sage: C = graphs.CycleGraph(5) sage: T = C.tensor_product(Z); T Graph on 10 vertices sage: T.plot().show()
sage: D = graphs.DodecahedralGraph() sage: P = graphs.PetersenGraph() sage: T = D.tensor_product(P); T Graph on 200 vertices sage: T.plot().show()
self) |
Returns a simple version of itself (i.e., undirected and loops and multiple edges are removed).
sage: G = DiGraph(loops=True,multiedges=True,sparse=True) sage: G.add_edges( [ (0,0), (1,1), (2,2), (2,3,1), (2,3,2), (3,2) ] ) sage: G.edges(labels=False) [(0, 0), (1, 1), (2, 2), (2, 3), (2, 3), (3, 2)] sage: H=G.to_simple() sage: H.edges(labels=False) [(2, 3)] sage: H.is_directed() False sage: H.loops() False sage: H.multiple_edges() False
self, comb_emb) |
A helper function for finding the genus of a graph. Given a graph and a combinatorial embedding (rot_sys), this function will compute the faces (returned as a list of lists of edges (tuples) of the particular embedding.
Note - rot_sys is an ordered list based on the hash order of the vertices of graph. To avoid confusion, it might be best to set the rot_sys based on a 'nice_copy' of the graph.
Input:
sage: T = graphs.TetrahedralGraph() sage: T.trace_faces({0: [1, 3, 2], 1: [0, 2, 3], 2: [0, 3, 1], 3: [0, 1, 2]}) [[(0, 1), (1, 2), (2, 0)], [(3, 2), (2, 1), (1, 3)], [(2, 3), (3, 0), (0, 2)], [(0, 3), (3, 1), (1, 0)]]
self) |
Computes the transitive closure of a graph and returns it. The original graph is not modified.
The transitive closure of a graph G has an edge (x,y) if and only if there is a path between x and y in G.
The transitive closure of any strongly connected component of a graph is a complete graph. In particular, the transitive closure of a connected undirected graph is a complete graph. The transitive closure of a directed acyclic graph is a directed acyclic graph representing the full partial order.
sage: g=graphs.PathGraph(4) sage: g.transitive_closure()==graphs.CompleteGraph(4) True sage: g=DiGraph({0:[1,2], 1:[3], 2:[4,5]}) sage: g.transitive_closure().edges(labels=False) [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 3), (2, 4), (2, 5)]
self) |
Returns a transitive reduction of a graph. The original graph is not modified.
A transitive reduction H of G has a path from x to y if and only if there was a path from x to y in G. Deleting any edge of H destroys this property. A transitive reduction is not unique in general. A transitive reduction has the same transitive closure as the original graph.
A transitive reduction of a complete graph is a tree. A transitive reduction of a tree is itself.
sage: g=graphs.PathGraph(4) sage: g.transitive_reduction()==g True sage: g=graphs.CompleteGraph(5) sage: edges = g.transitive_reduction().edges(); len(edges) 4 sage: g=DiGraph({0:[1,2], 1:[2,3,4,5], 2:[4,5]}) sage: g.transitive_reduction().size() 5
self, other) |
Returns the union of self and other.
If the graphs have common vertices, the common vertices will be identified.
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)]
self, vertices1, [vertices2=None]) |
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
has a loop, then vertex_boundary(v)
will not contain
.
In a digraph, the external boundary of a vertex v are those vertices u with an arc (v, u).
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]
self, [vertices=None]) |
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:
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, speedwise, 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.
self, [boundary_first=False]) |
Return a list of the vertices.
Input:
sage: P = graphs.PetersenGraph() sage: P.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Note that the output of the vertices() function is always sorted. This is sub-optimal, speedwise, but note the following optimizations:
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.
self, [new=None]) |
Returns whether the (di)graph is to be considered as a weighted (di)graph.
Note that edge weightings can still exist for (di)graphs G where G.weighted() is False.
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'}}, implementation='networkx') sage: H = Graph({0:{1:'b'}}, implementation='networkx') sage: G == H True
Now one is weighted and the other is not, so the comparison is done as if neither is weighted:
sage: G.weighted(True) sage: H.weighted() False sage: G == H True
However, if both are weighted, then we finally compare 'a' to 'b'.
sage: H.weighted(True) sage: G == H False
self, [sparse=True], [boundary_first=False]) |
Returns the weighted adjacency matrix of the graph. Each vertex is represented by its position in the list returned by the vertices() function.
sage: G = Graph(sparse=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
Special Functions: __add__,
__contains__,
__eq__,
__getitem__,
__iter__,
__len__,
__mul__,
__ne__,
__rmul__,
__str__,
_bit_vector,
_color_by_label,
_graphviz_string_helper,
_latex_,
_matrix_,
_repr_
self, other_graph) |
Returns the disjoint union of self and other.
If there are common vertices to both, they will be renamed.
sage: G = graphs.CycleGraph(3) sage: H = graphs.CycleGraph(4) sage: J = G + H; J Cycle graph disjoint_union Cycle graph: Graph on 7 vertices sage: J.vertices() [0, 1, 2, 3, 4, 5, 6]
self, vertex) |
Return True if vertex is one of the vertices of this graph.
Input:
sage: g = Graph({0:[1,2,3], 2:[4]}); g Graph on 5 vertices sage: 2 in g True sage: 10 in g False sage: graphs.PetersenGraph().has_vertex(99) False
self, other) |
Comparison of self and other. For equality, must be in the same class, have the same settings for loops and multiedges, output the same vertex list (in order) and the same adjacency matrix.
Note that this is _not_ an isomorphism test.
sage: G = graphs.EmptyGraph() sage: H = Graph() sage: G == H True sage: G.to_directed() == H.to_directed() True sage: G = graphs.RandomGNP(8,.9999) sage: H = graphs.CompleteGraph(8) sage: G == H # most often true True sage: G = Graph( {0:[1,2,3,4,5,6,7]} ) sage: H = Graph( {1:[0], 2:[0], 3:[0], 4:[0], 5:[0], 6:[0], 7:[0]} ) sage: G == H True sage: G.loops(True) sage: G == H False sage: G = graphs.RandomGNP(9,.3).to_directed() sage: H = graphs.RandomGNP(9,.3).to_directed() sage: G == H # most often false False sage: G = Graph(multiedges=True) sage: G.add_edge(0,1) sage: H = G.copy() sage: H.add_edge(0,1) sage: G == H False
self, vertex) |
Return a list of neighbors (in and out if directed) of vertex.
G[vertex] also works.
sage: P = graphs.PetersenGraph() sage: sorted(P.neighbors(3)) [2, 4, 8] sage: sorted(P[4]) [0, 3, 9]
self, [vertices=None]) |
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:
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, speedwise, 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.
self) |
Returns the number of vertices. Note that len(G) returns the number of vertices in G also.
sage: G = graphs.PetersenGraph() sage: G.order() 10
sage: G = graphs.TetrahedralGraph() sage: len(G) 4
self, n) |
Returns the sum of a graph with itself n times.
sage: G = graphs.CycleGraph(3) sage: H = G*3; H Cycle graph disjoint_union Cycle graph disjoint_union Cycle graph: Graph on 9 vertices sage: H.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8]
self, other) |
Tests for inequality, complement of __eq__.
sage: g = Graph() sage: g2 = g.copy() sage: g == g True sage: g != g False sage: g2 == g True sage: g2 != g False sage: g is g True sage: g2 is g False
self, n) |
Returns the sum of a graph with itself n times.
sage: G = graphs.CycleGraph(3) sage: H = int(3)*G; H Cycle graph disjoint_union Cycle graph disjoint_union Cycle graph: Graph on 9 vertices sage: H.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8]
self) |
str(G) returns the name of the graph, unless the name is the empty string, in which case it returns the default representation.
sage: G = graphs.PetersenGraph() sage: str(G) 'Petersen graph'
self, [format=hex]) |
Logic for coloring by label (factored out from plot() for use in 3d plots, etc)
self, graph_string, edge_string) |
Returns a representation in the DOT language, ready to render in graphviz.
Use graphviz_string
instead.
Input:
WARNING: Internal function, not for external use!
REFERENCES: http://www.graphviz.org/doc/info/lang.html
sage: G = Graph({0:{1:None,2:None}, 1:{0:None,2:None}, 2:{0:None,1:None,3:'foo'}, 3:{2:'foo'}}, implementation='networkx') sage: s = G.graphviz_string() # indirect doctest sage: s 'graph {\n"0";"1";"2";"3";\n"0"--"1";"0"--"2";"1"--"2";"2"--"3"[label="foo" ];\n}'
self) |
To include a graph in LaTeX document, see function Graph.write_to_eps().
sage: G = graphs.PetersenGraph() sage: latex(G) Traceback (most recent call last): ... NotImplementedError: To include a graph in LaTeX document, see function Graph.write_to_eps().
self, [R=None]) |
Returns the adjacency matrix of the graph over the specified ring.
sage: G = graphs.CompleteBipartiteGraph(2,3) sage: m = matrix(G); m.parent() Full MatrixSpace of 5 by 5 dense matrices over Integer Ring sage: m [0 0 1 1 1] [0 0 1 1 1] [1 1 0 0 0] [1 1 0 0 0] [1 1 0 0 0] sage: factor(m.charpoly()) x^3 * (x^2 - 6)
Class: Graph
Input:
pos - a positioning dictionary: for example, the spring layout from NetworkX for the 5-cycle is 0: [-0.91679746, 0.88169588], 1: [ 0.47294849, 1.125 ], 2: [ 1.125 ,-0.12867615], 3: [ 0.12743933,-1.125 ], 4: [-1.125 ,-0.50118505] name - (must be an explicitly named parameter, i.e., name="complete") gives the graph a name loops - boolean, whether to allow loops (ignored if data is an instance of the Graph class) multiedges - boolean, whether to allow multiple edges (ignored if data is an instance of the Graph class) weighted - whether graph thinks of itself as weighted or not. See self.weighted() format - if None, Graph tries to guess- can be several values, including: 'graph6' - Brendan McKay's graph6 format, in a string (if the string has multiple graphs, the first graph is taken) 'sparse6' - Brendan McKay's sparse6 format, in a string (if the string has multiple graphs, the first graph is taken) 'adjacency_matrix' - a square SAGE matrix M, with M[i,j] equal to the number of edges {i,j} 'weighted_adjacency_matrix' - a square SAGE matrix M, with M[i,j] equal to the weight of the single edge {i,j}. Given this format, weighted is ignored (assumed True). 'incidence_matrix' - a SAGE matrix, with one column C for each edge, where if C represents {i, j}, C[i] is -1 and C[j] is 1 'elliptic_curve_congruence' - data must be an iterable container of elliptic curves, and the graph produced has each curve as a vertex (it's Cremona label) and an edge E-F labelled p if and only if E is congruent to F mod p boundary - a list of boundary vertices, if empty, graph is considered as a 'graph without boundary' implementation - what to use as a backend for the graph. Currently, the options are either 'networkx' or 'c_graph' sparse - only for implementation == 'c_graph'. Whether to use sparse or dense graphs as backend. Note that currently dense graphs do not have edge labels, nor can they be multigraphs vertex_labels - only for implementation == 'c_graph'. Whether to allow any object as a vertex (slower), or only the integers 0, ..., n-1, where n is the number of vertices.
We illustrate the first six input formats (the other two involve packages that are currently not standard in SAGE):
1. A NetworkX XGraph:
sage: import networkx sage: g = networkx.XGraph({0:[1,2,3], 2:[4]}) sage: Graph(g) Graph on 5 vertices
In this single case, we do not make a copy of g, but just wrap the actual NetworkX passed- the Sage graph becomes a wrapper for the NetworkX graph.
sage: import networkx sage: g = networkx.XGraph({0:[1,2,3], 2:[4]}) sage: G = Graph(g, implementation='networkx') sage: H = Graph(g, implementation='networkx') sage: G._backend._nxg is H._backend._nxg True
2. A NetworkX graph:
sage: import networkx sage: g = networkx.Graph({0:[1,2,3], 2:[4]}) sage: DiGraph(g) Digraph on 5 vertices
Note that in this case, we copy the networkX structure.
sage: import networkx sage: g = networkx.Graph({0:[1,2,3], 2:[4]}) sage: G = Graph(g, implementation='networkx') sage: H = Graph(g, implementation='networkx') sage: G._backend._nxg is H._backend._nxg False
3. A dictionary of dictionaries:
sage: g = Graph({0:{1:'x',2:'z',3:'a'}, 2:{5:'out'}}, implementation='networkx'); g Graph on 5 vertices
The labels ('x', 'z', 'a', 'out') are labels for edges. For example, 'out' is the label for the edge on 2 and 5. Labels can be used as weights, if all the labels share some common parent.
4. A dictionary of lists:
sage: g = Graph({0:[1,2,3], 2:[4]}); g Graph on 5 vertices
5. A list of vertices and a function describing adjacencies. Note that the list of vertices and the function must be enclosed in a list (i.e., [list of vertices, function]).
Construct the Paley graph over GF(13).
sage: g=Graph([GF(13), lambda i,j: i!=j and (i-j).is_square()], implementation='networkx') sage: g.vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] sage: g.adjacency_matrix() [0 1 0 1 1 0 0 0 0 1 1 0 1] [1 0 1 0 1 1 0 0 0 0 1 1 0] [0 1 0 1 0 1 1 0 0 0 0 1 1] [1 0 1 0 1 0 1 1 0 0 0 0 1] [1 1 0 1 0 1 0 1 1 0 0 0 0] [0 1 1 0 1 0 1 0 1 1 0 0 0] [0 0 1 1 0 1 0 1 0 1 1 0 0] [0 0 0 1 1 0 1 0 1 0 1 1 0] [0 0 0 0 1 1 0 1 0 1 0 1 1] [1 0 0 0 0 1 1 0 1 0 1 0 1] [1 1 0 0 0 0 1 1 0 1 0 1 0] [0 1 1 0 0 0 0 1 1 0 1 0 1] [1 0 1 1 0 0 0 0 1 1 0 1 0]
Construct the line graph of a complete graph.
sage: g=graphs.CompleteGraph(4) sage: line_graph=Graph([g.edges(labels=false), \ lambda i,j: len(set(i).intersection(set(j)))>0], implementation='networkx') sage: line_graph.vertices() [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] sage: line_graph.adjacency_matrix() [0 1 1 1 1 0] [1 0 1 1 0 1] [1 1 0 0 1 1] [1 1 0 0 1 1] [1 0 1 1 0 1] [0 1 1 1 1 0]
6. A numpy matrix or ndarray:
sage: import numpy sage: A = numpy.array([[0,1,1],[1,0,1],[1,1,0]]) sage: Graph(A, implementation='networkx') Graph on 3 vertices
7. A graph6 or sparse6 string: Sage automatically recognizes whether a string is in graph6 or sparse6 format:
sage: s = ':I`AKGsaOs`cI]Gb~' sage: Graph(s, sparse=True) Looped multi-graph on 10 vertices
There are also list functions to take care of lists of graphs:
sage: s = ':IgMoqoCUOqeb\n:I`AKGsaOs`cI]Gb~\n:I`EDOAEQ?PccSsge\N\n' sage: graphs_list.from_sparse6(s) [Looped multi-graph on 10 vertices, Looped multi-graph on 10 vertices, Looped multi-graph on 10 vertices]
8. A SAGE matrix: Note: If format is not specified, then SAGE assumes a square matrix is an adjacency matrix, and a nonsquare matrix is an incidence matrix.
A. an adjacency matrix:
sage: M = graphs.PetersenGraph().am(); M [0 1 0 0 1 1 0 0 0 0] [1 0 1 0 0 0 1 0 0 0] [0 1 0 1 0 0 0 1 0 0] [0 0 1 0 1 0 0 0 1 0] [1 0 0 1 0 0 0 0 0 1] [1 0 0 0 0 0 0 1 1 0] [0 1 0 0 0 0 0 0 1 1] [0 0 1 0 0 1 0 0 0 1] [0 0 0 1 0 1 1 0 0 0] [0 0 0 0 1 0 1 1 0 0] sage: Graph(M) Graph on 10 vertices
sage: Graph(matrix([[1,2],[3,4]]),loops=True) Looped graph on 2 vertices
B. an incidence matrix:
sage: M = Matrix(6, [-1,0,0,0,1, 1,-1,0,0,0, 0,1,-1,0,0, 0,0,1,-1,0, 0,0,0,1,-1, 0,0,0,0,0]); M [-1 0 0 0 1] [ 1 -1 0 0 0] [ 0 1 -1 0 0] [ 0 0 1 -1 0] [ 0 0 0 1 -1] [ 0 0 0 0 0] sage: Graph(M) Graph on 6 vertices
self, [data=None], [pos=None], [loops=False], [format=None], [boundary=[]], [weighted=False], [implementation=networkx], [sparse=True], [vertex_labels=True]) |
Functions: bipartite_color,
bipartite_sets,
centrality_betweenness,
centrality_closeness,
centrality_degree,
chromatic_number,
chromatic_polynomial,
clique_number,
cliques,
cliques_containing_vertex,
cliques_get_clique_bipartite,
cliques_get_max_clique_graph,
cliques_number_of,
cliques_vertex_clique_number,
eulerian_circuit,
graph6_string,
graphviz_string,
is_bipartite,
is_directed,
min_spanning_tree,
sparse6_string,
to_directed,
to_undirected,
write_to_eps
self) |
Returns a dictionary with vertices as the keys and the color class as the values. Fails with an error if the graph is not bipartite.
sage: graphs.CycleGraph(4).bipartite_color() {0: 1, 1: 0, 2: 1, 3: 0} sage: graphs.CycleGraph(5).bipartite_color() Traceback (most recent call last): ... RuntimeError: Graph is not bipartite.
self) |
Returns (X,Y) where X and Y are the nodes in each bipartite set of graph G. Fails with an error if graph is not bipartite.
sage: graphs.CycleGraph(4).bipartite_sets() ([0, 2], [1, 3]) sage: graphs.CycleGraph(5).bipartite_sets() Traceback (most recent call last): ... RuntimeError: Graph is not bipartite.
self, [normalized=True]) |
Returns the betweenness centrality (fraction of number of shortest paths that go through each vertex) as a dictionary keyed by vertices. The betweenness is normalized by default to be in range (0,1). This wraps Networkx's implementation of the algorithm described in [1].
Measures of the centrality of a vertex within a graph determine the relative importance of that vertex to its graph. Vertices that occur on more shortest paths between other vertices have higher betweenness than vertices that occur on less.
Input:
REFERENCE: [1] Ulrik Brandes. (2003). Faster Evaluation of Shortest-Path Based Centrality Indices. [Online] Available: http://citeseer.nj.nec.com/brandes00faster.html
sage: (graphs.ChvatalGraph()).centrality_betweenness() {0: 0.069696969696969688, 1: 0.069696969696969688, 2: 0.060606060606060601, 3: 0.060606060606060601, 4: 0.069696969696969688, 5: 0.069696969696969688, 6: 0.060606060606060601, 7: 0.060606060606060601, 8: 0.060606060606060601, 9: 0.060606060606060601, 10: 0.060606060606060601, 11: 0.060606060606060601} sage: (graphs.ChvatalGraph()).centrality_betweenness(normalized=False) {0: 7.6666666666666661, 1: 7.6666666666666661, 2: 6.6666666666666661, 3: 6.6666666666666661, 4: 7.6666666666666661, 5: 7.6666666666666661, 6: 6.6666666666666661, 7: 6.6666666666666661, 8: 6.6666666666666661, 9: 6.6666666666666661, 10: 6.6666666666666661, 11: 6.6666666666666661} sage: D = DiGraph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: D.show(figsize=[2,2]) sage: D = D.to_undirected() sage: D.show(figsize=[2,2]) sage: D.centrality_betweenness() {0: 0.16666666666666666, 1: 0.16666666666666666, 2: 0.0, 3: 0.0}
self, [v=None]) |
Returns the closeness centrality (1/average distance to all vertices) as a dictionary of values keyed by vertex. The degree centrality is normalized to be in range (0,1).
Measures of the centrality of a vertex within a graph determine the relative importance of that vertex to its graph. 'Closeness centrality may be defined as the total graph-theoretic distance of a given vertex from all other vertices... Closeness is an inverse measure of centrality in that a larger value indicates a less central actor while a smaller value indicates a more central actor,' [1].
Input:
REFERENCE: [1] Stephen P Borgatti. (1995). Centrality and AIDS. [Online] Available: http://www.analytictech.com/networks/centaids.htm
sage: (graphs.ChvatalGraph()).centrality_closeness() {0: 0.61111111111111116, 1: 0.61111111111111116, 2: 0.61111111111111116, 3: 0.61111111111111116, 4: 0.61111111111111116, 5: 0.61111111111111116, 6: 0.61111111111111116, 7: 0.61111111111111116, 8: 0.61111111111111116, 9: 0.61111111111111116, 10: 0.61111111111111116, 11: 0.61111111111111116} sage: D = DiGraph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: D.show(figsize=[2,2]) sage: D = D.to_undirected() sage: D.show(figsize=[2,2]) sage: D.centrality_closeness() {0: 1.0, 1: 1.0, 2: 0.75, 3: 0.75} sage: D.centrality_closeness(v=1) 1.0
self, [v=None]) |
Returns the degree centrality (fraction of vertices connected to) as a dictionary of values keyed by vertex. The degree centrality is normalized to be in range (0,1).
Measures of the centrality of a vertex within a graph determine the relative importance of that vertex to its graph. Degree centrality measures the number of links incident upon a vertex.
Input:
sage: (graphs.ChvatalGraph()).centrality_degree() {0: 0.36363636363636365, 1: 0.36363636363636365, 2: 0.36363636363636365, 3: 0.36363636363636365, 4: 0.36363636363636365, 5: 0.36363636363636365, 6: 0.36363636363636365, 7: 0.36363636363636365, 8: 0.36363636363636365, 9: 0.36363636363636365, 10: 0.36363636363636365, 11: 0.36363636363636365} sage: D = DiGraph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: D.show(figsize=[2,2]) sage: D = D.to_undirected() sage: D.show(figsize=[2,2]) sage: D.centrality_degree() {0: 1.0, 1: 1.0, 2: 0.66666666666666663, 3: 0.66666666666666663} sage: D.centrality_degree(v=1) 1.0
self) |
Returns the minimal number of colors needed to color the vertices of the graph G.
sage: G = Graph({0:[1,2,3],1:[2]}) sage: G.chromatic_number() 3
self) |
Returns the chromatic polynomial of the graph G.
sage: G = Graph({0:[1,2,3],1:[2]}) sage: factor(G.chromatic_polynomial()) (x - 2) * x * (x - 1)^2
sage: g = graphs.trees(5).next() sage: g.chromatic_polynomial().factor() x * (x - 1)^4
sage: seven_acre_wood = sum(graphs.trees(7), Graph()) sage: seven_acre_wood.chromatic_polynomial() x^77 - 66*x^76 ... - 2515943049305400*x^60 ... - 66*x^12 + x^11
sage: for i in range(2,7): ... graphs.CompleteGraph(i).chromatic_polynomial().factor() (x - 1) * x (x - 2) * (x - 1) * x (x - 3) * (x - 2) * (x - 1) * x (x - 4) * (x - 3) * (x - 2) * (x - 1) * x (x - 5) * (x - 4) * (x - 3) * (x - 2) * (x - 1) * x
self, [cliques=None]) |
Returns the size of the largest clique of the graph (clique number).
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
Input:
sage: C = Graph('DJ{') sage: C.clique_number() 4 sage: E = C.cliques() sage: E [[4, 1, 2, 3], [4, 0]] sage: C.clique_number(cliques=E) 4 sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: G.show(figsize=[2,2]) sage: G.clique_number() 3
self) |
Returns the list of maximal cliques. Each maximal clique is represented by a list of vertices.
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
Maximal cliques are the largest complete subgraphs containing a given point. This function is based on Networkx's implementation of the Bron and Kerbosch Algorithm, [1].
REFERENCE: [1] Coen Bron and Joep Kerbosch. (1973). Algorithm 457: Finding All Cliques of an Undirected Graph. Commun. ACM. v 16. n 9. pages 575-577. ACM Press. [Online] Available: http://www.ram.org/computing/rambin/rambin.html
sage: (graphs.ChvatalGraph()).cliques() [[0, 1], [0, 4], [0, 6], [0, 9], [2, 1], [2, 3], [2, 6], [2, 8], [3, 4], [3, 7], [3, 9], [5, 1], [5, 4], [5, 10], [5, 11], [7, 1], [7, 8], [7, 11], [8, 4], [8, 10], [10, 6], [10, 9], [11, 6], [11, 9]] sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: G.show(figsize=[2,2]) sage: G.cliques() [[0, 1, 2], [0, 1, 3]]
self, [vertices=None], [cliques=None], [with_labels=False]) |
Returns the cliques containing each vertex, represented as a list of lists. (Returns a single list if only one input vertex).
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
Input:
sage: C = Graph('DJ{') sage: C.cliques_containing_vertex() [[[4, 0]], [[4, 1, 2, 3]], [[4, 1, 2, 3]], [[4, 1, 2, 3]], [[4, 1, 2, 3], [4, 0]]] sage: E = C.cliques() sage: E [[4, 1, 2, 3], [4, 0]] sage: C.cliques_containing_vertex(cliques=E) [[[4, 0]], [[4, 1, 2, 3]], [[4, 1, 2, 3]], [[4, 1, 2, 3]], [[4, 1, 2, 3], [4, 0]]] sage: F = graphs.Grid2dGraph(2,3) sage: F.cliques_containing_vertex(with_labels=True) {(0, 1): [[(0, 1), (0, 0)], [(0, 1), (0, 2)], [(0, 1), (1, 1)]], (1, 2): [[(1, 2), (0, 2)], [(1, 2), (1, 1)]], (0, 0): [[(0, 1), (0, 0)], [(1, 0), (0, 0)]], (1, 1): [[(0, 1), (1, 1)], [(1, 2), (1, 1)], [(1, 0), (1, 1)]], (1, 0): [[(1, 0), (0, 0)], [(1, 0), (1, 1)]], (0, 2): [[(0, 1), (0, 2)], [(1, 2), (0, 2)]]} sage: F.cliques_containing_vertex(vertices=[(0, 1), (1, 2)]) [[[(0, 1), (0, 0)], [(0, 1), (0, 2)], [(0, 1), (1, 1)]], [[(1, 2), (0, 2)], [(1, 2), (1, 1)]]] sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: G.show(figsize=[2,2]) sage: G.cliques_containing_vertex() [[[0, 1, 2], [0, 1, 3]], [[0, 1, 2], [0, 1, 3]], [[0, 1, 2]], [[0, 1, 3]]]
self) |
Returns a bipartite graph constructed such that cliques are the right vertices and the left vertices are retained from the given graph. Right and left vertices are connected if the bottom vertex belongs to the clique represented by a top vertex.
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
sage: (graphs.ChvatalGraph()).cliques_get_clique_bipartite() Bipartite graph on 36 vertices sage: ((graphs.ChvatalGraph()).cliques_get_clique_bipartite()).show(figsize=[2,2], vertex_size=20, vertex_labels=False) sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: G.show(figsize=[2,2]) sage: G.cliques_get_clique_bipartite() Bipartite graph on 6 vertices sage: (G.cliques_get_clique_bipartite()).show(figsize=[2,2])
self, [name=]) |
Returns a graph constructed with maximal cliques as vertices, and edges between maximal cliques with common members in the original graph.
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
Input:
sage: (graphs.ChvatalGraph()).cliques_get_max_clique_graph() Graph on 24 vertices sage: ((graphs.ChvatalGraph()).cliques_get_max_clique_graph()).show(figsize=[2,2], vertex_size=20, vertex_labels=False) sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: G.show(figsize=[2,2]) sage: G.cliques_get_max_clique_graph() Graph on 2 vertices sage: (G.cliques_get_max_clique_graph()).show(figsize=[2,2])
self, [vertices=None], [cliques=None], [with_labels=False]) |
Returns a list of the number of maximal cliques containing each vertex. (Returns a single value if only one input vertex).
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
Input:
sage: C = Graph('DJ{') sage: C.cliques_number_of() [1, 1, 1, 1, 2] sage: E = C.cliques() sage: E [[4, 1, 2, 3], [4, 0]] sage: C.cliques_number_of(cliques=E) [1, 1, 1, 1, 2] sage: F = graphs.Grid2dGraph(2,3) sage: F.cliques_number_of(with_labels=True) {(0, 1): 3, (1, 2): 2, (0, 0): 2, (1, 1): 3, (1, 0): 2, (0, 2): 2} sage: F.cliques_number_of(vertices=[(0, 1), (1, 2)]) [3, 2] sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: G.show(figsize=[2,2]) sage: G.cliques_number_of() [2, 2, 1, 1]
self, [vertices=None], [with_labels=False], [cliques=None]) |
Returns a list of sizes of the largest maximal cliques containing each vertex. (Returns a single value if only one input vertex).
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
Input:
sage: C = Graph('DJ{') sage: C.cliques_vertex_clique_number() [2, 4, 4, 4, 4] sage: E = C.cliques() sage: E [[4, 1, 2, 3], [4, 0]] sage: C.cliques_vertex_clique_number(cliques=E) [2, 4, 4, 4, 4] sage: F = graphs.Grid2dGraph(2,3) sage: F.cliques_vertex_clique_number(with_labels=True) {(0, 1): 2, (1, 2): 2, (0, 0): 2, (1, 1): 2, (1, 0): 2, (0, 2): 2} sage: F.cliques_vertex_clique_number(vertices=[(0, 1), (1, 2)]) [2, 2] sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: G.show(figsize=[2,2]) sage: G.cliques_vertex_clique_number() [3, 3, 3, 3]
self, [return_vertices=False], [labels=True]) |
Return a list of edges forming an eulerian circuit if one exists. Otherwise return False.
This is implemented using Fleury's algorithm. This could be extended to find eulerian paths too (check for existence and make sure you start on an odd-degree vertex if one exists).
Input:
sage: g=graphs.CycleGraph(5); sage: g.eulerian_circuit() [(0, 1, None), (1, 2, None), (2, 3, None), (3, 4, None), (4, 0, None)] sage: g.eulerian_circuit(labels=False) [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)] sage: g = graphs.CompleteGraph(7) sage: edges, vertices = g.eulerian_circuit(return_vertices=True) sage: vertices [0, 1, 2, 0, 3, 1, 4, 0, 5, 1, 6, 2, 3, 4, 2, 5, 3, 6, 4, 5, 6, 0] sage: graphs.CompleteGraph(4).eulerian_circuit() False
self) |
Returns the graph6 representation of the graph as an ASCII string. Only valid for simple (no loops, multiple edges) graphs on 0 to 262143 vertices.
sage: G = graphs.KrackhardtKiteGraph() sage: G.graph6_string() 'IvUqwK@?G'
self) |
Returns a representation in the DOT language, ready to render in graphviz.
REFERENCES: http://www.graphviz.org/doc/info/lang.html
sage: G = Graph({0:{1:None,2:None}, 1:{0:None,2:None}, 2:{0:None,1:None,3:'foo'}, 3:{2:'foo'}}, implementation='networkx') sage: s = G.graphviz_string() sage: s 'graph {\n"0";"1";"2";"3";\n"0"--"1";"0"--"2";"1"--"2";"2"--"3"[label="foo" ];\n}'
self) |
Returns True if graph G is bipartite, False if not.
Traverse the graph G with depth-first-search and color nodes. This function uses the corresponding NetworkX function.
sage: graphs.CycleGraph(4).is_bipartite() True sage: graphs.CycleGraph(5).is_bipartite() False
self) |
Since graph is undirected, returns False.
self, [weight_function=<function <lambda> at 0x253f140>], [algorithm=Kruskal], [starting_vertex=None]) |
Returns the edges of a minimum spanning tree, if one exists, otherwise returns False.
Input:
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) [(3, 4, None), (2, 4, None), (1, 4, None), (0, 4, None)] sage: g.min_spanning_tree(algorithm='Prim edge', starting_vertex=2, weight_function=weight) [(2, 4, None), (3, 4, None), (1, 3, None), (0, 4, None)] sage: g.min_spanning_tree(algorithm='Prim fringe', starting_vertex=2, weight_function=weight) [(4, 2), (3, 4), (1, 4), (0, 4)]
self) |
Returns the sparse6 representation of the graph as an ASCII string. Only valid for undirected graphs on 0 to 262143 vertices, but loops and multiple edges are permitted.
sage: G = graphs.BullGraph() sage: G.sparse6_string() ':Da@en'
self, [implementation=networkx]) |
Returns a directed version of the graph. A single edge becomes two edges, one in each direction.
sage: graphs.PetersenGraph().to_directed() Petersen graph: Digraph on 10 vertices
self) |
Since the graph is already undirected, simply returns a copy of itself.
sage: graphs.PetersenGraph().to_undirected() Petersen graph: Graph on 10 vertices
self, filename, [iterations=50]) |
Writes a plot of the graph to filename in eps format.
It is relatively simple to include this file in a latex document:
Input: filename
must appear before the beginning
of the document, and
usepackagegraphics
will include it in your latex doc. Note: you cannot use
pdflatex to print the resulting document, use TeX and
Ghostscript or something similar instead.
includegraphics filename.eps
sage: P = graphs.PetersenGraph() sage: P.write_to_eps('sage.eps')
Special Functions: __init__
See About this document... for information on suggesting changes.