| Home | Trees | Indices | Help |
|---|
|
|
object --+
|
structure.sage_object.SageObject --+
|
GenericGraph
Base class for graphs and digraphs.
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
Inherited from Inherited from |
|||
|
|||
graphics_array_defaults = |
|||
|
|||
|
Inherited from |
|||
|
|||
Returns the disjoint union of self and other.
If there are common vertices to both, they will be renamed.
EXAMPLE:
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]
|
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.
EXAMPLES:
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
|
Since graphs are mutable, they should not be hashable, so we return a type error.
EXAMPLES:
sage: hash(Graph())
Traceback (most recent call last):
...
TypeError: graphs are mutable, and thus not hashable
|
Returns the sum of a graph with itself n times.
EXAMPLE:
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]
|
Tests for inequality, complement of __eq__.
EXAMPLES:
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
|
Returns the sum of a graph with itself n times.
EXAMPLE:
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]
|
str(G) returns the name of the graph, unless the name is the empty string, in
which case it returns the default representation.
EXAMPLE:
sage: G = graphs.PetersenGraph()
sage: str(G)
'Petersen graph'
|
To include a graph in LaTeX document, see function
Graph.write_to_eps().
EXAMPLE:
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().
|
Returns the adjacency matrix of the graph over the specified ring.
EXAMPLES:
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)
|
Creates a copy of the graph.
EXAMPLES:
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
|
Creates a new NetworkX graph from the SAGE graph.
INPUT:
copy -- if False, and the underlying implementation is a NetworkX graph,
then the actual object itself is returned.
EXAMPLES:
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
|
Returns the adjacency matrix of the (di)graph. Each vertex is
represented by its position in the list returned by the vertices()
function.
The matrix returned is over the integers. If a different ring
is desired, use either the change_ring function or the matrix
function.
INPUT:
sparse -- whether to represent with a sparse matrix
boundary_first -- whether to represent the boundary vertices in
the upper left block
EXAMPLES:
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
|
Returns the adjacency matrix of the (di)graph. Each vertex is
represented by its position in the list returned by the vertices()
function.
The matrix returned is over the integers. If a different ring
is desired, use either the change_ring function or the matrix
function.
INPUT:
sparse -- whether to represent with a sparse matrix
boundary_first -- whether to represent the boundary vertices in
the upper left block
EXAMPLES:
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
|
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.
EXAMPLE:
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]
|
Returns the weighted adjacency matrix of the graph. Each vertex is
represented by its position in the list returned by the vertices()
function.
EXAMPLES:
sage: G = Graph(sparse=True)
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
|
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
EXAMPLES:
sage: G = Graph(sparse=True)
sage: G.add_edges([(0,1,1),(1,2,2),(0,2,3),(0,3,4)])
sage: M = G.kirchhoff_matrix(weighted=True); M
[ 8 -1 -3 -4]
[-1 3 -2 0]
[-3 -2 5 0]
[-4 0 0 4]
sage: M = G.kirchhoff_matrix(); M
[ 3 -1 -1 -1]
[-1 2 -1 0]
[-1 -1 2 0]
[-1 0 0 1]
sage: 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]
|
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
EXAMPLES:
sage: G = Graph(sparse=True)
sage: G.add_edges([(0,1,1),(1,2,2),(0,2,3),(0,3,4)])
sage: M = G.kirchhoff_matrix(weighted=True); M
[ 8 -1 -3 -4]
[-1 3 -2 0]
[-3 -2 5 0]
[-4 0 0 4]
sage: M = G.kirchhoff_matrix(); M
[ 3 -1 -1 -1]
[-1 2 -1 0]
[-1 -1 2 0]
[-1 0 0 1]
sage: 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]
|
Returns the boundary of the (di)graph.
EXAMPLE:
sage: G = graphs.PetersenGraph()
sage: G.set_boundary([0,1,2,3,4])
sage: G.get_boundary()
[0, 1, 2, 3, 4]
|
Sets the boundary of the (di)graph.
EXAMPLE:
sage: G = graphs.PetersenGraph()
sage: G.set_boundary([0,1,2,3,4])
sage: G.get_boundary()
[0, 1, 2, 3, 4]
|
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:
embedding -- a dictionary
EXAMPLES:
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
|
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.
EXAMPLES:
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]}
|
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.
EXAMPLES:
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
|
Returns whether loops are permitted in the graph.
INPUT:
new -- boolean, changes whether loops are permitted in the graph.
EXAMPLE:
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
|
Returns whether multiple edges are permitted in the (di)graph.
INPUT:
new -- boolean. If specified, changes whether multiple edges are
permitted in the graph.
EXAMPLE:
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
|
Returns the name of the (di)graph.
INPUT:
new -- if not None, then this becomes the new name of the (di)graph.
(if new == '', removes any name)
EXAMPLE:
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()
''
|
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.
EXAMPLE:
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
|
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 |
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.
EXAMPLE:
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
|
Return true if the graph has an tour that visits each edge exactly once.
EXAMPLES:
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
|
Return True if the graph is a tree.
EXAMPLES:
sage: for g in graphs.trees(6):
... g.is_tree()
True
True
True
True
True
True
|
Return True if the graph is a forest, i.e. a disjoint union of trees.
EXAMPLE:
sage: seven_acre_wood = sum(graphs.trees(7), Graph())
sage: seven_acre_wood.is_forest()
True
|
Returns the number of vertices. Note that len(G) returns the number of
vertices in G also.
EXAMPLE:
sage: G = graphs.PetersenGraph()
sage: G.order()
10
sage: G = graphs.TetrahedralGraph()
sage: len(G)
4
|
Returns the number of vertices. Note that len(G) returns the number of
vertices in G also.
EXAMPLE:
sage: G = graphs.PetersenGraph()
sage: G.order()
10
sage: G = graphs.TetrahedralGraph()
sage: len(G)
4
|
Returns the number of vertices. Note that len(G) returns the number of
vertices in G also.
EXAMPLE:
sage: G = graphs.PetersenGraph()
sage: G.order()
10
sage: G = graphs.TetrahedralGraph()
sage: len(G)
4
|
Returns the number of edges.
EXAMPLE:
sage: G = graphs.PetersenGraph()
sage: G.size()
15
|
Returns the number of edges.
EXAMPLE:
sage: G = graphs.PetersenGraph()
sage: G.size()
15
|
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:
kuratowski -- returns a tuple with boolean as first entry. If the
graph is nonplanar, will return the Kuratowski subgraph
or minor as the second tuple entry. If the graph is
planar, returns None as the second entry.
on_embedding -- the embedding dictionary to test planarity on. (i.e.:
will return True or False only for the given embedding.)
set_embedding -- whether or not to set the instance field variable that
contains a combinatorial embedding (clockwise ordering
of neighbors at each vertex). This value will only be
set if a planar embedding is found. It is stored as a
Python dict: {v1: [n1,n2,n3]} where v1 is a vertex and
n1,n2,n3 are its neighbors.
set_pos -- whether or not to set the position dictionary (for
plotting) to reflect the combinatorial embedding. Note
that this value will default to False if set_emb is set
to False. Also, the position dictionary will only be
updated if a planar embedding is found.
EXAMPLES:
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
|
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:
ordered -- whether or not to consider the order of the boundary
(set ordered=False to see if there is any possible
boundary order that will satisfy circular planarity)
kuratowski -- if set to True, returns a tuple with boolean first
entry and the Kuratowski subgraph or minor as the second
entry. See notes above.
on_embedding -- the embedding dictionary to test planarity on. (i.e.:
will return True or False only for the given embedding.)
set_embedding -- whether or not to set the instance field variable that
contains a combinatorial embedding (clockwise ordering
of neighbors at each vertex). This value will only be
set if a circular planar embedding is found. It is
stored as a Python dict: {v1: [n1,n2,n3]} where v1 is
a vertex and n1,n2,n3 are its neighbors.
set_pos -- whether or not to set the position dictionary (for
plotting) to reflect the combinatorial embedding. Note
that this value will default to False if set_emb is set
to False. Also, the position dictionary will only be
updated if a circular planar embedding is found.
EXAMPLES:
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
|
Uses Schnyder's algorithm to determine positions for a planar embedding of
self, raising an error if self is not planar.
INPUT:
set_embedding -- if True, sets the combinatorial embedding used (see
self.get_embedding())
on_embedding -- dict: provide a combinatorial embedding
external_face -- ignored
test -- if True, perform sanity tests along the way
circular -- ignored
EXAMPLES:
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.
|
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.)
EXAMPLES:
sage: D = graphs.DodecahedralGraph()
sage: D.set_planar_positions()
sage: D.is_drawn_free_of_edge_crossings()
True
|
Returns the minimal genus of the graph. The genus of a compact
surface is the number of handles it has. The genus of a graph
is the minimal genus of the surface it can be embedded into.
Note -- This function uses Euler's formula and thus it is
necessary to consider only connected graphs.
INPUT:
set_embedding (boolean) -- whether or not to store an embedding attribute of the computed
(minimal) genus of the graph. (Default is True).
on_embedding (dict) -- a combinatorial embedding to compute the genus of the graph on.
Note that this must be a valid embedding for the graph. The
dictionary structure is given by:
{ vertex1: [neighbor1, neighbor2, neighbor3], vertex2: [neighbor] }
where there is a key for each vertex in the graph and a (clockwise)
ordered list of each vertex's neighbors as values. on_embedding
takes precedence over a stored _embedding attribute if minimal is
set to False.
Note that as a shortcut, the user can enter on_embedding=True to
compute the genus on the current _embedding attribute. (see eg's.)
minimal (boolean) -- whether or not to compute the minimal genus of the graph (i.e., testing
all embeddings). If minimal is False, then either maximal must be
True or on_embedding must not be None. If on_embedding is not None,
it will take priority over minimal. Similarly, if maximal is True,
it will take priority over minimal.
maximal (boolean) -- whether or not to compute the maximal genus of the graph (i.e., testin
all embeddings). If maximal is False, then either minimal must be
True or on_embedding must not be None. If on_embedding is not None,
it will take priority over maximal. However, maximal takes priority
over the default minimal.
circular (boolean) -- whether or not to compute the genus preserving a planar embedding of the
boundary. (Default is False). If circular is True, on_embedding is
not a valid option.
ordered (boolean) -- if circular is True, then whether or not the boundary order may be permuted.
(Default is True, which means the boundary order is preserved.)
EXAMPLES:
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
|
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:
comb_emb -- a combinatorial embedding dictionary. Format:
{ v1:[v2,v3], v2:[v1], v3:[v1] } (clockwise ordering
of neighbors at each vertex.)
EXAMPLES:
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)]]
|
Indicates whether the (di)graph is connected. Note that in a graph, path
connected is equivalent to connected.
EXAMPLE:
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
|
Returns a list of lists of vertices, each list representing a
connected component. The list is ordered from largest to smallest
component.
EXAMPLE:
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]]
|
Returns the number of connected components.
EXAMPLE:
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
|
Returns a list of connected components as graph objects.
EXAMPLE:
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)
|
Returns a list of the vertices connected to vertex.
EXAMPLE:
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]
|
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.
EXAMPLES:
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.
|
Creates an isolated vertex. If the vertex already exists, then nothing is done.
INPUT:
n -- Name of the new vertex. If no name is specified, then the vertex
will be represented by the least integer not already representing a
vertex. Name must be an immutable object.
As it is implemented now, if a graph $G$ has a large number of
vertices with numeric labels, then G.add_vertex() could
potentially be slow.
EXAMPLES:
sage: G = Graph(sparse=True); G.add_vertex(); G
Graph on 1 vertex
sage: D = DiGraph(sparse=True); D.add_vertex(); D
Digraph on 1 vertex
|
Add vertices to the (di)graph from an iterable container of vertices.
Vertices that already exist in the graph will not be added again.
EXAMPLES:
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]
|
Deletes vertex, removing all incident edges. Deleting a non-existant
vertex will raise an exception.
INPUT:
in_order -- (default False) If True, this deletes the ith vertex in
the sorted list of vertices, i.e. G.vertices()[i]
EXAMPLES:
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)]
|
Remove vertices from the (di)graph taken from an iterable container of
vertices. Deleting a non-existant vertex will raise an exception.
EXAMPLE:
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
|
Return True if vertex is one of the vertices of this graph.
INPUT:
vertex -- an integer
OUTPUT:
bool -- True or False
EXAMPLES:
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
|
Return True if vertex is one of the vertices of this graph.
INPUT:
vertex -- an integer
OUTPUT:
bool -- True or False
EXAMPLES:
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
|
Returns a list of all vertices in the external boundary of vertices1,
intersected with vertices2. If vertices2 is None, then vertices2 is the
complement of vertices1. This is much faster if vertices1 is smaller than
vertices2.
The external boundary of a set of vertices is the union of the
neighborhoods of each vertex in the set. Note that in this
implementation, since vertices2 defaults to the complement of
vertices1, if a vertex $v$ has a loop, then vertex_boundary(v)
will not contain $v$.
In a digraph, the external boundary of a vertex v are those vertices u
with an arc (v, u).
EXAMPLE:
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]
|
Associate arbitrary objects with each vertex, via an association dictionary.
INPUT:
vertex_dict -- the association dictionary
EXAMPLES:
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
|
Associate an arbitrary object with a vertex.
INPUT:
vertex -- which vertex
object -- object to associate to vertex
EXAMPLE:
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
|
Retrieve the object associated with a given vertex.
INPUT:
vertex -- the given vertex
EXAMPLES:
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
|
Return a dictionary of the objects associated to each vertex.
INPUT:
verts -- iterable container of vertices
EXAMPLES:
sage: d = {0 : graphs.DodecahedralGraph(), 1 : graphs.FlowerSnark(), 2 : graphs.MoebiusKantorGraph(), 3 : graphs.PetersenGraph() }
sage: T = graphs.TetrahedralGraph()
sage: T.set_vertices(d)
sage: T.get_vertices([1,2])
{1: Flower Snark: Graph on 20 vertices,
2: Moebius-Kantor Graph: Graph on 16 vertices}
|
Returns a list of vertices with loops.
EXAMPLE:
sage: G = Graph({0 : [0], 1: [1,2,3], 2: [3]}, loops=True)
sage: G.loop_vertices()
[0, 1]
|
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 \code{for v in G} syntax is allowed.
INPUT:
vertices -- iterated vertices are these intersected with the
vertices of the (di)graph
EXAMPLE:
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.
|
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 \code{for v in G} syntax is allowed.
INPUT:
vertices -- iterated vertices are these intersected with the
vertices of the (di)graph
EXAMPLE:
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.
|
Return an iterator over neighbors of vertex.
EXAMPLE:
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]
|
Return a list of the vertices.
INPUT:
boundary_first -- Return the boundary vertices first.
EXAMPLE:
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.
|
Return a list of neighbors (in and out if directed) of vertex.
G[vertex] also works.
EXAMPLE:
sage: P = graphs.PetersenGraph()
sage: sorted(P.neighbors(3))
[2, 4, 8]
sage: sorted(P[4])
[0, 3, 9]
|
Return a list of neighbors (in and out if directed) of vertex.
G[vertex] also works.
EXAMPLE:
sage: P = graphs.PetersenGraph()
sage: sorted(P.neighbors(3))
[2, 4, 8]
sage: sorted(P[4])
[0, 3, 9]
|
Adds an edge from u and v.
INPUT:
The following forms are all accepted:
G.add_edge( 1, 2 )
G.add_edge( (1, 2) )
G.add_edges( [ (1, 2) ] )
G.add_edge( 1, 2, 'label' )
G.add_edge( (1, 2, 'label') )
G.add_edges( [ (1, 2, 'label') ] )
WARNING:
The following intuitive input results in nonintuitive output:
sage: G = Graph(implementation='networkx')
sage: G.add_edge((1,2), 'label')
sage: G.networkx_graph().adj # random output order
{'label': {(1, 2): None}, (1, 2): {'label': None}}
Use one of these instead:
sage: G = Graph(implementation='networkx')
sage: G.add_edge((1,2), label="label")
sage: G.networkx_graph().adj # random output order
{1: {2: 'label'}, 2: {1: 'label'}}
sage: G = Graph(implementation='networkx')
sage: G.add_edge(1,2,'label')
sage: G.networkx_graph().adj # random output order
{1: {2: 'label'}, 2: {1: 'label'}}
|
Add edges from an iterable container.
EXAMPLE:
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
|
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') ] )
EXAMPLES:
sage: G = graphs.CompleteGraph(19)
sage: G.size()
171
sage: G.delete_edge( 1, 2 )
sage: G.delete_edge( (3, 4) )
sage: G.delete_edges( [ (5, 6), (7, 8) ] )
sage: G.delete_edge( 9, 10, 'label' )
sage: G.delete_edge( (11, 12, 'label') )
sage: G.delete_edges( [ (13, 14, 'label') ] )
sage: G.size()
164
sage: G.has_edge( (11, 12) )
False
Note that even though the edge (11, 12) has no label, it still gets
deleted: NetworkX does not pay attention to labels here.
sage: D = graphs.CompleteGraph(19).to_directed()
sage: D.size()
342
sage: D.delete_edge( 1, 2 )
sage: D.delete_edge( (3, 4) )
sage: D.delete_edges( [ (5, 6), (7, 8) ] )
sage: D.delete_edge( 9, 10, 'label' )
sage: D.delete_edge( (11, 12, 'label') )
sage: D.delete_edges( [ (13, 14, 'label') ] )
sage: D.size()
335
sage: D.has_edge( (11, 12) )
False
|
Delete edges from an iterable container.
EXAMPLE:
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
|
Deletes all edges from u and v.
EXAMPLE:
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)]
|
Set the edge label of a given edge.
NOTE:
There can be only one edge from u to v for this to make sense.
Otherwise, an error is raised.
INPUT:
u, v -- the vertices (and direction if digraph) of the edge
l -- the new label
EXAMPLES:
sage: SD = DiGraph( { 1:[18,2], 2:[5,3], 3:[4,6], 4:[7,2], 5:[4], 6:[13,12], 7:[18,8,10], 8:[6,9,10], 9:[6], 10:[11,13], 11:[12], 12:[13], 13:[17,14], 14:[16,15], 15:[2], 16:[13], 17:[15,13], 18:[13] }, 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)]
|
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' )
EXAMPLE:
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
|
Return a list of edges. Each edge is a triple (u,v,l) where u
and v are vertices and l is a label.
INPUT:
labels -- (bool; default: True) if False, each edge is a
tuple (u,v) of vertices.
sort -- (bool; default: True) if True, ensure that the list
of edges is sorted.
OUTPUT:
A list of tuples. It is safe to change the returned list.
EXAMPLES:
sage: graphs.DodecahedralGraph().edges()
[(0, 1, None), (0, 10, None), (0, 19, None), (1, 2, None), (1, 8, None), (2, 3, None), (2, 6, None), (3, 4, None), (3, 19, None), (4, 5, None), (4, 17, None), (5, 6, None), (5, 15, None), (6, 7, None), (7, 8, None), (7, 14, None), (8, 9, None), (9, 10, None), (9, 13, None), (10, 11, None), (11, 12, None), (11, 18, None), (12, 13, None), (12, 16, None), (13, 14, None), (14, 15, None), (15, 16, None), (16, 17, None), (17, 18, None), (18, 19, None)]
sage: graphs.DodecahedralGraph().edges(labels=False)
[(0, 1), (0, 10), (0, 19), (1, 2), (1, 8), (2, 3), (2, 6), (3, 4), (3, 19), (4, 5), (4, 17), (5, 6), (5, 15), (6, 7), (7, 8), (7, 14), (8, 9), (9, 10), (9, 13), (10, 11), (11, 12), (11, 18), (12, 13), (12, 16), (13, 14), (14, 15), (15, 16), (16, 17), (17, 18), (18, 19)]
sage: D = graphs.DodecahedralGraph().to_directed()
sage: D.edges()
[(0, 1, None), (0, 10, None), (0, 19, None), (1, 0, None), (1, 2, None), (1, 8, None), (2, 1, None), (2, 3, None), (2, 6, None), (3, 2, None), (3, 4, None), (3, 19, None), (4, 3, None), (4, 5, None), (4, 17, None), (5, 4, None), (5, 6, None), (5, 15, None), (6, 2, None), (6, 5, None), (6, 7, None), (7, 6, None), (7, 8, None), (7, 14, None), (8, 1, None), (8, 7, None), (8, 9, None), (9, 8, None), (9, 10, None), (9, 13, None), (10, 0, None), (10, 9, None), (10, 11, None), (11, 10, None), (11, 12, None), (11, 18, None), (12, 11, None), (12, 13, None), (12, 16, None), (13, 9, None), (13, 12, None), (13, 14, None), (14, 7, None), (14, 13, None), (14, 15, None), (15, 5, None), (15, 14, None), (15, 16, None), (16, 12, None), (16, 15, None), (16, 17, None), (17, 4, None), (17, 16, None), (17, 18, None), (18, 11, None), (18, 17, None), (18, 19, None), (19, 0, None), (19, 3, None), (19, 18, None)]
sage: D.edges(labels = False)
[(0, 1), (0, 10), (0, 19), (1, 0), (1, 2), (1, 8), (2, 1), (2, 3), (2, 6), (3, 2), (3, 4), (3, 19), (4, 3), (4, 5), (4, 17), (5, 4), (5, 6), (5, 15), (6, 2), (6, 5), (6, 7), (7, 6), (7, 8), (7, 14), (8, 1), (8, 7), (8, 9), (9, 8), (9, 10), (9, 13), (10, 0), (10, 9), (10, 11), (11, 10), (11, 12), (11, 18), (12, 11), (12, 13), (12, 16), (13, 9), (13, 12), (13, 14), (14, 7), (14, 13), (14, 15), (15, 5), (15, 14), (15, 16), (16, 12), (16, 15), (16, 17), (17, 4), (17, 16), (17, 18), (18, 11), (18, 17), (18, 19), (19, 0), (19, 3), (19, 18)]
|
Returns a list of edges (u,v,l) with u in vertices1 and v in vertices2.
If vertices2 is None, then it is set to the complement of vertices1.
In a digraph, the external boundary of a vertex v are those vertices u
with an arc (v, u).
INPUT:
labels -- if False, each edge is a tuple (u,v) of vertices.
EXAMPLE:
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)]
|
Returns an iterator over the edges incident with any vertex given. If
the graph is directed, iterates over edges going out only. If vertices
is None, then returns an iterator over all edges. If self is directed,
returns outgoing edges only.
INPUT:
labels -- if False, each edge is a tuple (u,v) of vertices.
ignore_direction -- (default False) only applies to directed graphs. If
True, searches across edges in either direction.
EXAMPLE:
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)]
|
Returns a list of edges incident with any vertex given. If vertices is
None, returns a list of all edges in graph. For digraphs, only lists
outward edges.
INPUT:
label -- if False, each edge is a tuple (u,v) of vertices.
EXAMPLE:
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])
[]
|
Returns the label of an edge. Note that if the graph allows multiple
edges, then a list of labels on the edge is returned.
EXAMPLE:
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]
|
Returns a list of edge labels.
EXAMPLE:
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']
|
Removes all multiple edges, retaining one edge for each.
EXAMPLE:
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)]
|
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
|
Returns a list of all loops in the graph.
EXAMPLE:
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)]
|
Returns the number of edges that are 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.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
|
Empties the graph of vertices and edges and removes name,
boundary, associated objects, and position information.
EXAMPLE:
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)
|
Gives the degree (in + out for digraphs) of a vertex or of vertices.
INPUT:
vertices -- If vertices is a single vertex, returns the number of
neighbors of vertex. If vertices is an iterable container of vertices,
returns a list of degrees. If vertices is None, same as listing all vertices.
labels -- see OUTPUT
OUTPUT:
Single vertex- an integer. Multiple vertices- a list of integers. If
labels is True, then returns a dictionary mapping each vertex to
its degree.
EXAMPLES:
sage: P = graphs.PetersenGraph()
sage: P.degree(5)
3
sage: K = graphs.CompleteGraph(9)
sage: K.degree()
[8, 8, 8, 8, 8, 8, 8, 8, 8]
sage: D = DiGraph( { 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] } )
sage: D.degree(vertices = [0,1,2], labels=True)
{0: 5, 1: 4, 2: 3}
sage: D.degree()
[5, 4, 3, 3, 3, 2]
|
Returns a list, whose ith entry is the frequency of degree i.
EXAMPLE:
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]
|
Returns an iterator over the degrees of the (di)graph. In the case of a
digraph, the degree is defined as the sum of the in-degree and the
out-degree, i.e. the total number of edges incident to a given vertex.
INPUT:
labels=False: returns an iterator over degrees.
labels=True: returns an iterator over tuples (vertex, degree).
vertices -- if specified, restrict to this subset.
EXAMPLES:
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)
|
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:
inplace -- Using inplace is True will simply delete the extra vertices
and edges from the current graph. This will modify the graph.
vertices -- Vertices can be a single vertex or an iterable container
of vertices, e.g. a list, set, graph, file or numeric array.
If not passed, defaults to the entire graph.
edges -- As with vertices, edges can be a single edge or an iterable
container of edges (e.g., a list, set, file, numeric array,
etc.). If not edges are not specified, then all edges are
assumed and the returned graph is an induced subgraph. In
the case of multiple edges, specifying an edge as (u,v)
means to keep all edges (u,v), regardless of the label.
vertex_property -- If specified, this is expected to be a function on
vertices, which is intersected with the vertices specified, if any are.
edge_property -- If specified, this is expected to be a function on
edges, which is intersected with the edges specified, if any are.
EXAMPLES:
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]
|
Return a random subgraph that contains each vertex with prob. p.
EXAMPLE:
sage: P = graphs.PetersenGraph()
sage: P.random_subgraph(.25)
Subgraph of (Petersen graph): Graph on 4 vertices
|
Returns True if the set \code{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:
vertices -- Vertices can be a single vertex or an iterable
container of vertices, e.g. a list, set, graph, file or
numeric array. If not passed, defaults to the entire graph.
directed_clique -- (default False) If set to False, only
consider the underlying undirected graph. If set to True and the
graph is directed, only return True if all possible edges in
_both_ directions exist.
EXAMPLE:
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
|
Returns True if the set \code{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:
vertices -- Vertices can be a single vertex or an iterable
container of vertices, e.g. a list, set, graph, file or
numeric array. If not passed, defaults to the entire graph.
EXAMPLE:
sage: graphs.CycleGraph(4).is_independent_set([1,3])
True
sage: graphs.CycleGraph(4).is_independent_set([1,2,3])
False
|
Tests whether self is a subgraph of other.
EXAMPLE:
sage: P = graphs.PetersenGraph()
sage: G = P.subgraph(range(6))
sage: G.is_subgraph(P)
True
|
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:
-- nbunch - The vertices to inspect. If nbunch=None, returns
data for all vertices in the graph
-- with_labels - (boolean) default False returns list as above
True returns dict keyed by vertex labels.
REFERENCE:
[1] Aric Hagberg, Dan Schult and Pieter Swart. NetworkX
documentation. [Online] Available:
https://networkx.lanl.gov/reference/networkx/
EXAMPLES:
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]
|
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/
EXAMPLES:
sage: (graphs.FruchtGraph()).clustering_average()
0.25
|
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:
-- nbunch - the vertices to inspect (default None returns
data on all vertices in graph)
-- with_labels - (boolean) default False returns list as above
True returns dict keyed by vertex labels.
-- weights - default is False. If both with_labels and weights
are True, then returns a clustering coefficient dict
and a dict of weights based on degree. Weights are
the fraction of connected triples in the graph that
include the keyed vertex.
REFERENCE:
[1] Aric Hagberg, Dan Schult and Pieter Swart. NetworkX
documentation. [Online] Available:
https://networkx.lanl.gov/reference/networkx/
EXAMPLES:
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})
|
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/
EXAMPLES:
sage: (graphs.FruchtGraph()).cluster_transitivity()
0.25
|
Returns the core number for each vertex in an ordered list.
'K-cores in graph theory were introduced by Seidman in 1983
and by Bollobas in 1984 as a method of (destructively) simplifying
graph topology to aid in analysis and visualization. They have been
more recently defined as the following by Batagelj et al: given a
graph G with vertices set V and edges set E, the k-core is computed
by pruning all the vertices (with their respective edges) with degree
less than k. That means that if a vertex u has degree d_u, and it has
n neighbors with degree less than k, then the degree of u becomes d_u - n,
and it will be also pruned if k > d_u - n. This operation can be
useful to filter or to study some properties of the graphs. For
instance, when you compute the 2-core of graph G, you are cutting
all the vertices which are in a tree part of graph. (A tree is a
graph with no loops),' [1].
INPUT:
-- with_labels - default False returns list as described above.
True returns dict keyed by vertex labels.
REFERENCE:
[1] K-core. Wikipedia. (2007). [Online] Available:
http://en.wikipedia.org/wiki/K-core
[2] Boris Pittel, Joel Spencer and Nicholas Wormald. Sudden
Emergence of a Giant k-Core in a Random Graph. (1996).
J. Combinatorial Theory. Ser B 67. pages 111-151. [Online]
Available: http://cs.nyu.edu/cs/faculty/spencer/papers/k-core.pdf
EXAMPLES:
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}
|
Returns the (directed) distance from u to v in the (di)graph, i.e. the
length of the shortest path from u to v.
EXAMPLES:
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
|
Return the eccentricity of vertex (or vertices) v.
The eccentricity of a vertex is the maximum distance to any other
vertex.
INPUT:
v -- either a single vertex or a list of vertices. If it is not
specified, then it is taken to be all vertices.
dist_dict -- optional, a dict of dicts of distance.
with_labels -- Whether to return a list or a dict.
EXAMPLES:
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}
|
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.
EXAMPLES:
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
|
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.
EXAMPLES:
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]
|
Returns the largest distance between any two vertices. Returns
Infinity if the (di)graph is not connected.
EXAMPLES:
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
|
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.
EXAMPLES:
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
|
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.
EXAMPLES:
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]
|
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:
start -- the vertex of the graph to search for paths from
end -- the vertex of the graph to search for paths to
EXAMPLES:
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]]
|
Returns a list of all paths (also lists) between a pair of
vertices (start, end) in the (di)graph.
EXAMPLES:
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]]
|
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:
by_weight -- if False, uses a breadth first search. If True, takes
edge weightings into account, using Dijkstra's algorithm.
bidirectional -- if True, the algorithm will expand vertices from
u and v at the same time, making two spheres of half the usual radius.
This generally doubles the speed (consider the total volume in each
case).
EXAMPLE:
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]
|
Returns the minimal length of paths from u to v: if there is no path
from u to v, returns Infinity.
INPUT:
by_weight -- if False, uses a breadth first search. If True, takes
edge weightings into account, using Dijkstra's algorithm.
bidirectional -- if True, the algorithm will expand vertices from
u and v at the same time, making two spheres of half the usual radius.
This generally doubles the speed (consider the total volume in each
case).
weight_sum -- if False, returns the number of edges in the path.
If True, returns the sum of the weights of these edges. Default
behavior is to have the same value as by_weight.
EXAMPLE:
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
|
Returns a dictionary d of shortest paths d[v] from u to v, for each
vertex v connected by a path from u.
INPUT:
by_weight -- if False, uses a breadth first search. If True, uses
Dijkstra's algorithm to find the shortest paths by weight.
cutoff -- integer depth to stop search. Ignored if by_weight is
True.
EXAMPLES:
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]}
|
Returns a dictionary of shortest path lengths keyed by targets that
are connected by a path from u.
INPUT:
by_weight -- if False, uses a breadth first search. If True, takes
edge weightings into account, using Dijkstra's algorithm.
weight_sums -- if False, returns the number of edges in each path.
If True, returns the sum of the weights of these edges. Default
behavior is to have the same value as by_weight.
EXAMPLES:
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}
|
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:
by_weight -- If False, figure distances by the numbers of edges.
default_weight -- (defaults to 1) The default weight to
assign edges that don't have a weight (i.e., a label).
OUTPUT:
A tuple (dist, pred). They are both dicts of dicts. The first
indicates the length dist[u][v] of the shortest weighted path from u
to v. The second is more complicated-- it indicates the predecessor
pred[u][v] of v in the shortest path from u to v.
EXAMPLE:
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}})
|
Returns an iterator over vertices in a breadth-first ordering.
INPUT:
u -- vertex at which to start search
ignore_direction -- (default False) only applies to directed graphs. If
True, searches across edges in either direction.
EXAMPLES:
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]
|
Returns an iterator over vertices in a depth-first ordering.
INPUT:
u -- vertex at which to start search
ignore_direction -- (default False) only applies to directed graphs. If
True, searches across edges in either direction.
EXAMPLES:
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]
|
Adds a cycle to the graph with the given vertices. If the vertices are
already present, only the edges are added.
For digraphs, adds the directed cycle, whose orientation is determined
by the list. Adds edges (vertices[u], vertices[u+1]) and (vertices[-1],
vertices[0]).
INPUT:
vertices -- a list of indices for the vertices of the cycle to be
added.
EXAMPLES:
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)]
|
Adds a cycle to the graph with the given vertices. If the vertices are
already present, only the edges are added.
For digraphs, adds the directed path vertices[0], ..., vertices[-1].
INPUT:
vertices -- a list of indices for the vertices of the cycle to be
added.
EXAMPLES:
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)]
|
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.
EXAMPLE:
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.
|
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.
EXAMPLE:
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)]
|
Returns a simple version of itself (i.e., undirected and loops
and multiple edges are removed).
EXAMPLE:
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
|
Returns the disjoint union of self and other.
If the graphs have common vertices, the vertices will be
renamed to form disjoint sets.
INPUT:
verbose_relabel -- (defaults to True) If True and the
graphs have common vertices, then each vertex v in the
first graph will be changed to '0,v' and each vertex u in
the second graph will be changed to '1,u'. If False, the
vertices of the first graph and the second graph will be
relabeled with consecutive integers.
EXAMPLE:
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']
|
Returns the union of self and other.
If the graphs have common vertices, the common vertices will
be identified.
EXAMPLE:
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)]
|
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.
EXAMPLES:
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()
|
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.
EXAMPLES:
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()
|
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.
EXAMPLES:
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()
|
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.
EXAMPLES:
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()
|
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.
EXAMPLES:
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()
|
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.
EXAMPLES:
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()
|
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.
EXAMPLES:
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)]
|
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.
EXAMPLES:
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
|
Logic for coloring by label (factored out from plot() for use in 3d plots, etc) |
Returns a graphics object representing the (di)graph.
INPUT:
pos -- an optional positioning dictionary
layout -- what kind of layout to use, takes precedence over pos
'circular' -- plots the graph with vertices evenly distributed
on a circle
'spring' -- uses the traditional spring layout, using the
graph's current positions as initial positions
vertex_labels -- whether to print vertex labels
edge_labels -- whether to print edge labels. By default, False, but
if True, the result of str(l) is printed on the edge for each
label l. Labels equal to None are not printed.
vertex_size -- size of vertices displayed
graph_border -- whether to include a box around the graph
vertex_colors -- optional dictionary to specify vertex colors: each
key is a color recognizable by matplotlib, and each corresponding
entry is a list of vertices. If a vertex is not listed, it looks
invisible on the resulting plot (it doesn't get drawn).
edge_colors -- a dictionary specifying edge colors: each key is a
color recognized by matplotlib, and each entry is a list of edges.
partition -- a partition of the vertex set. if specified, plot will
show each cell in a different color. vertex_colors takes precedence.
scaling_term -- default is 0.05. if vertices are getting chopped off,
increase; if graph is too small, decrease. should be positive, but
values much bigger than 1/8 won't be useful unless the vertices
are huge
talk -- if true, prints large vertices with white backgrounds so that
labels are legible on slides
iterations -- how many iterations of the spring layout algorithm to
go through, if applicable
color_by_label -- if True, color edges by their labels
heights -- if specified, this is a dictionary from a set of
floating point heights to a set of vertices
edge_style -- keyword arguments passed into the
edge-drawing routine. This currently only works for
directed graphs, since we pass off the undirected graph to
networkx
EXAMPLES:
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
|
Shows the (di)graph.
INPUT:
pos -- an optional positioning dictionary
layout -- what kind of layout to use, takes precedence over pos
'circular' -- plots the graph with vertices evenly distributed
on a circle
'spring' -- uses the traditional spring layout, ignores the
graphs current positions
vertex_labels -- whether to print vertex labels
edge_labels -- whether to print edgeedge labels. By default, False,
but if True, the result of str(l) is printed on the edge for
each label l. Labels equal to None are not printed.
vertex_size -- size of vertices displayed
graph_border -- whether to include a box around the graph
vertex_colors -- optional dictionary to specify vertex colors: each
key is a color recognizable by matplotlib, and each corresponding
entry is a list of vertices. If a vertex is not listed, it looks
invisible on the resulting plot (it doesn't get drawn).
edge_colors -- a dictionary specifying edge colors: each key is a
color recognized by matplotlib, and each entry is a list of edges.
partition -- a partition of the vertex set. if specified, plot will
show each cell in a different color. vertex_colors takes precedence.
scaling_term -- default is 0.05. if vertices are getting chopped off,
increase; if graph is too small, decrease. should be positive, but
values much bigger than 1/8 won't be useful unless the vertices
are huge
talk -- if true, prints large vertices with white backgrounds so that
labels are legible on slies
iterations -- how many iterations of the spring layout algorithm to
go through, if applicable
color_by_label -- if True, color edges by their labels
heights -- if specified, this is a dictionary from a set of
floating point heights to a set of vertices
edge_style -- options for the arrows of directed graphs
EXAMPLES:
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()
|
Plot a graph in three dimensions.
INPUT:
bgcolor -- rgb tuple (default: (1,1,1))
vertex_size -- float (default: 0.06)
vertex_colors -- optional dictionary to specify vertex colors:
each key is a color recognizable by tachyon (rgb tuple
(default: (1,0,0))), and each corresponding entry is a list of
vertices. If a vertex is not listed, it looks invisible on the
resulting plot (it doesn't get drawn).
edge_colors -- a dictionary specifying edge colors: each key is a
color recognized by tachyon ( default: (0,0,0) ), and each
entry is a list of edges.
edge_size -- float (default: 0.02)
edge_size2 -- float (default: 0.0325), used for Tachyon sleeves
pos3d -- a position dictionary for the vertices
iterations -- how many iterations of the spring layout algorithm to
go through, if applicable
engine -- which renderer to use. Options:
'jmol' -- default
'tachyon'
xres -- resolution
yres -- resolution
**kwds -- passed on to the rendering engine
EXAMPLES:
sage: G = graphs.CubeGraph(5)
sage: G.plot3d(iterations=500, edge_size=None, vertex_size=0.04)
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
|
Plots the graph using Tachyon, and shows the resulting plot.
INPUT:
bgcolor -- rgb tuple (default: (1,1,1))
vertex_size -- float (default: 0.06)
vertex_colors -- optional dictionary to specify vertex colors:
each key is a color recognizable by tachyon (rgb tuple
(default: (1,0,0))), and each corresponding entry is a list of
vertices. If a vertex is not listed, it looks invisible on the
resulting plot (it doesn't get drawn).
edge_colors -- a dictionary specifying edge colors: each key is a
color recognized by tachyon ( default: (0,0,0) ), and each
entry is a list of edges.
edge_size -- float (default: 0.02)
edge_size2 -- float (default: 0.0325), used for Tachyon sleeves
pos3d -- a position dictionary for the vertices
iterations -- how many iterations of the spring layout algorithm to
go through, if applicable
engine -- which renderer to use. Options:
'jmol' -- default
'tachyon'
xres -- resolution
yres -- resolution
**kwds -- passed on to the Tachyon command
EXAMPLES:
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
|
Returns a representation in the DOT language, ready to render in graphviz.
Use \code{graphviz_string} instead.
INPUT:
-- graph_string: a string, "graph" for undirected graphs or
"digraph" for directed graphs.
-- edge_string: a string, "--" for undirected graphs or "->" for
directed graphs.
WARNING:
Internal function, not for external use!
REFERENCES:
http://www.graphviz.org/doc/info/lang.html
EXAMPLE:
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}'
|
Returns a representation in the DOT language, ready to render in graphviz.
EXAMPLES:
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}'
|
Write a representation in the DOT language to the named file, ready to
render in graphviz.
EXAMPLES:
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}'
|
Returns the spectrum of the graph, the eigenvalues of the adjacency
matrix
INPUT:
laplacian -- if True, use the Laplacian matrix instead (see
self.kirchhoff_matrix())
EXAMPLE:
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...]
|
Returns the characteristic polynomial of the adjacency matrix
of the (di)graph.
INPUT:
laplacian -- if True, use the Laplacian matrix instead (see
self.kirchhoff_matrix())
EXAMPLE:
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
|
Returns the eigenspaces of the adjacency matrix of the graph.
INPUT:
laplacian -- if True, use the Laplacian matrix instead (see
self.kirchhoff_matrix())
EXAMPLE:
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
|
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 $i \mapsto perm[i]$
with the assumption that the vertices are $\{0,1,...,n-1\}$.
If perm is a permutation, the permutation is simply applied to
the graph, under the assumption that the vertices are
$\{0,1,...,n-1\}$. The permutation acts on the set
$\{1,2,...,n\}$, where we think of $n = 0$.
If no arguments are provided, the graph is relabeled to be on the
vertices $\{0,1,...,n-1\}$.
INPUT:
inplace -- default is True. If True, modifies the graph and returns
nothing. If False, returns a relabeled copy of the graph.
return_map -- default is False. If True, returns the dictionary
representing the map.
EXAMPLES:
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()
|
Returns the number of edges from vertex to an edge in cell. In the case
of a digraph, returns a tuple (in_degree, out_degree).
EXAMPLES:
sage: 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)
|
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:
partition -- a list of lists
quotient_matrix -- (default False) if True, and the partition is
equitable, returns a matrix over the integers whose rows and columns
represent cells of the partition, and whose i,j entry is the number of
vertices in cell j adjacent to each vertex in cell i (since the
partition is equitable, this is well defined)
EXAMPLE:
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
|
Returns the coarsest partition which is finer than the input partition,
and equitable with respect to self.
A partition is equitable with respect to a graph if for every pair of
cells C1, C2 of the partition, the number of edges from a vertex of C1
to C2 is the same, over all vertices in C1.
A partition P1 is finer than P2 (P2 is coarser than P1) if every cell of
P1 is a subset of a cell of P2.
INPUT:
partition -- a list of lists
sparse -- (default False) whether to use sparse or dense
representation- for small graphs, use dense for speed
EXAMPLES:
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.
|
Returns the largest subgroup of the automorphism group of the (di)graph
whose orbit partition is finer than the partition given. If no
partition is given, the unit partition is used and the entire
automorphism group is given.
INPUT:
translation -- if True, then output includes a a dictionary
translating from keys == vertices to entries == elements of
{1,2,...,n} (since permutation groups can currently only act on
positive integers).
partition -- default is the unit partition, otherwise computes the
subgroup of the full automorphism group respecting the partition.
edge_labels -- default False, otherwise allows only permutations
respecting edge labels.
order -- (default False) if True, compute the order of the automorphism
group
return_group -- default True
orbits -- returns the orbits of the group acting on the vertices of the
graph
OUTPUT:
The order of the output is group, translation, order, orbits.
However, there are options to turn each of these on or off.
EXAMPLES:
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]]
|
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).
EXAMPLE:
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
|
Tests for isomorphism between self and other.
INPUT:
certify -- if True, then output is (a,b), where a is a boolean and b
is either a map or None.
edge_labels -- default False, otherwise allows only permutations
respecting edge labels.
EXAMPLES:
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
|
Returns the canonical label with respect to the partition. If no
partition is given, uses the unit partition.
INPUT:
partition -- if given, the canonical label with respect to this
partition will be computed. The default is the unit partition.
certify -- if True, a dictionary mapping from the (di)graph to its
canonical label will be given.
verbosity -- gets passed to nice: prints helpful output.
edge_labels -- default False, otherwise allows only permutations
respecting edge labels.
EXAMPLE:
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
|
|
|||
graphics_array_defaults
|
| Home | Trees | Indices | Help |
|---|
| Generated by Epydoc 3.0beta1 on Thu Jul 17 04:23:41 2008 | http://epydoc.sourceforge.net |