Backends for Sage (di)graphs.¶
This module implements GenericGraphBackend
(the base class for
backends).
Any graph backend must redefine the following methods (for which
GenericGraphBackend
raises a NotImplementedError
)
add_edge() 
Add an edge \((u,v)\) to self , with label \(l\). 
add_edges() 
Add a sequence of edges to self . 
add_vertex() 
Add a labelled vertex to self . 
add_vertices() 
Add labelled vertices to self . 
degree() 
Return the total number of vertices incident to \(v\). 
in_degree() 
Return the indegree of \(v\) 
out_degree() 
Return the outdegree of \(v\) 
del_edge() 
Delete the edge \((u,v)\) with label \(l\). 
del_vertex() 
Delete a labelled vertex in self . 
del_vertices() 
Delete labelled vertices in self . 
get_edge_label() 
Return the edge label of \((u,v)\). 
has_edge() 
True if self has an edge \((u,v)\) with label \(l\). 
has_vertex() 
True if self has a vertex with label \(v\). 
iterator_edges() 
Iterate over the edges incident to a sequence of vertices. 
iterator_in_edges() 
Iterate over the incoming edges incident to a sequence of vertices. 
iterator_out_edges() 
Iterate over the outbound edges incident to a sequence of vertices. 
iterator_nbrs() 
Iterate over the vertices adjacent to \(v\). 
iterator_in_nbrs() 
Iterate over the vertices u such that the edge \((u,v)\) is in self (that is, predecessors of \(v\)). 
iterator_out_nbrs() 
Iterate over the vertices u such that the edge \((v,u)\) is in self (that is, successors of \(v\)). 
iterator_verts() 
Iterate over the vertices \(v\) with labels in verts. 
loops() 
Get/set whether or not self allows loops. 
multiple_edges() 
Get/set whether or not self allows multiple edges. 
name() 
Get/set name of self . 
num_edges() 
The number of edges in self 
num_verts() 
The number of vertices in self 
relabel() 
Relabel the vertices of self by a permutation. 
set_edge_label() 
Label the edge \((u,v)\) by \(l\). 
For an overview of graph data structures in sage, see
overview
.
Classes and methods¶

class
sage.graphs.base.graph_backends.
GenericGraphBackend
¶ Bases:
sage.structure.sage_object.SageObject
A generic wrapper for the backend of a graph. Various graph classes use extensions of this class. Note, this graph has a number of placeholder functions, so the doctests are rather silly.

add_edge
(u, v, l, directed)¶ Add an edge (u,v) to self, with label l. If directed is True, this is interpreted as an arc from u to v.
INPUT:
u,v
– verticesl
– edge labeldirected
– boolean

add_edges
(edges, directed)¶ Add a sequence of edges to self. If directed is True, these are interpreted as arcs.
INPUT:
edges
– list/iterator of edges to be added.directed
– boolean

add_vertex
(name)¶ Add a labelled vertex to self.
INPUT:
name
– vertex label
OUTPUT:
If
name=None
, the new vertex name is returned,None
otherwise.

add_vertices
(vertices)¶ Add labelled vertices to self.
INPUT:
vertices
– iterator of vertex labels. A new label is created, used and returned in the output list for allNone
values invertices
.
OUTPUT:
Generated names of new vertices if there is at least one
None
value present invertices
.None
otherwise.EXAMPLES:
sage: G = sage.graphs.base.graph_backends.GenericGraphBackend() sage: G.add_vertices([1,2,3]) Traceback (most recent call last): ... NotImplementedError

degree
(v, directed)¶ Return the total number of vertices incident to \(v\).
INPUT:
v
– a vertex labeldirected
– boolean
OUTPUT:
degree of v

del_edge
(u, v, l, directed)¶ Delete the edge \((u,v)\) with label \(l\).
INPUT:
u,v
– verticesl
– edge labeldirected
– boolean

del_vertex
(v)¶ Delete a labelled vertex in self.
INPUT:
v
– vertex label

del_vertices
(vertices)¶ Delete labelled vertices in self.
INPUT:
vertices
– iterator of vertex labels

get_edge_label
(u, v)¶ Return the edge label of \((u,v)\).
INPUT:
u,v
– vertex labels
OUTPUT:
label of \((u,v)\)

has_edge
(u, v, l)¶ True if self has an edge (u,v) with label l.
INPUT:
u,v
– vertex labelsl
– label
OUTPUT:
boolean

has_vertex
(v)¶ True if self has a vertex with label v.
INPUT:
v
– vertex label
 OUTPUT:
 boolean

in_degree
(v)¶ Return the indegree of \(v\)
INPUT:
v
– a vertex label

iterator_edges
(vertices, labels)¶ Iterate over the edges incident to a sequence of vertices. Edges are assumed to be undirected.
INPUT:
vertices
– a list of vertex labelslabels
– boolean
OUTPUT:
a generator which yields edges, with or without labels depending on the labels parameter.

iterator_in_edges
(vertices, labels)¶ Iterate over the incoming edges incident to a sequence of vertices.
INPUT:
vertices
– a list of vertex labelslabels
– boolean
 OUTPUT:
 a generator which yields edges, with or without labels depending on the labels parameter.

iterator_in_nbrs
(v)¶ Iterate over the vertices u such that the edge (u,v) is in self (that is, predecessors of v).
INPUT:
v
– vertex label
OUTPUT:
a generator which yields vertex labels

iterator_nbrs
(v)¶ Iterate over the vertices adjacent to v.
INPUT:
v
– vertex label
OUTPUT:
a generator which yields vertex labels

iterator_out_edges
(vertices, labels)¶ Iterate over the outbound edges incident to a sequence of vertices.
INPUT:
vertices
– a list of vertex labelslabels
– boolean
OUTPUT:
a generator which yields edges, with or without labels depending on the labels parameter.

iterator_out_nbrs
(v)¶ Iterate over the vertices u such that the edge (v,u) is in self (that is, successors of v).
INPUT:
v
– vertex label
OUTPUT:
a generator which yields vertex labels

iterator_verts
(verts)¶ Iterate over the vertices v with labels in verts.
INPUT:
vertex
– vertex labels
OUTPUT:
a generator which yields vertices

loops
(new=None)¶ Get/set whether or not self allows loops.
INPUT:
new
– can be a boolean (in which case it sets the value) orNone
, in which case the current value is returned. It is set toNone
by default.

multiple_edges
(new=None)¶ Get/set whether or not self allows multiple edges.
INPUT:
new
– can be a boolean (in which case it sets the value) orNone
, in which case the current value is returned. It is set toNone
by default.

name
(new=None)¶ Get/set name of self.
INPUT:
new
– can be a string (in which case it sets the value) orNone
, in which case the current value is returned. It is set toNone
by default.

num_edges
(directed)¶ The number of edges in self
INPUT:
directed
– boolean

num_verts
()¶ The number of vertices in self

out_degree
(v)¶ Return the outdegree of \(v\)
INPUT:
v
– a vertex label

relabel
(perm, directed)¶ Relabel the vertices of self by a permutation.
INPUT:
perm
– permutationdirected
– boolean

set_edge_label
(u, v, l, directed)¶ Label the edge (u,v) by l.
INPUT:
u,v
– verticesl
– edge labeldirected
– boolean


class
sage.graphs.base.graph_backends.
NetworkXDiGraphDeprecated
¶ Bases:
sage.structure.sage_object.SageObject
Class for unpickling old networkx.XDiGraph formats

mutate
()¶ Change the old networkx XDiGraph format into the new one.
OUTPUT:
 The networkx.DiGraph or networkx.MultiDiGraph corresponding to the unpickled data.
EXAMPLES:
sage: from sage.graphs.base.graph_backends import NetworkXDiGraphDeprecated as NXDGD sage: X = NXDGD() sage: X.adj = {1:{2:7}, 2:{1:[7,8], 3:[4,5,6,7]}} sage: X.multiedges = True sage: G = X.mutate() sage: G.edges() OutMultiEdgeDataView([(1, 2), (2, 1), (2, 3)]) sage: G.edges(data=True) OutMultiEdgeDataView([(1, 2, {'weight': 7}), (2, 1, {8: {}, 7: {}}), (2, 3, {4: {}, 5: {}, 6: {}, 7: {}})])


class
sage.graphs.base.graph_backends.
NetworkXGraphDeprecated
¶ Bases:
sage.structure.sage_object.SageObject
Class for unpickling old networkx.XGraph formats

mutate
()¶ Change the old networkx XGraph format into the new one.
OUTPUT:
 The networkx.Graph or networkx.MultiGraph corresponding to the unpickled data.
EXAMPLES:
sage: from sage.graphs.base.graph_backends import NetworkXGraphDeprecated as NXGD sage: X = NXGD() sage: X.adj = {1:{2:7}, 2:{1:7}, 3:{2:[4,5,6,7]}, 2:{3:[4,5,6,7]}} sage: X.multiedges = True sage: G = X.mutate() sage: G.edges() MultiEdgeDataView([(1, 2), (2, 3)]) sage: G.edges(data=True) MultiEdgeDataView([(1, 2, {'weight': 7}), (2, 3, {4: {}, 5: {}, 6: {}, 7: {}})])


sage.graphs.base.graph_backends.
unpickle_graph_backend
(directed, vertices, edges, kwds)¶ Return a backend from its pickled data
This methods is defined because Python’s pickling mechanism can only build objects from a pair
(f,args)
by runningf(*args)
. In particular, there is apparently no way to define a**kwargs
(i.e. define the value of keyword arguments off
), which means that one must know the order of all arguments off
(here,f
isGraph
orDiGraph
).As a consequence, this means that the order cannot change in the future, which is something we cannot swear.
INPUT:
directed
(boolean)vertices
– list of vertices.edges
– list of edgeskwds
– any dictionary whose keywords will be forwarded to the graph constructor.
This function builds a
Graph
orDiGraph
from its data, and returns the_backend
attribute of this object.EXAMPLES:
sage: from sage.graphs.base.graph_backends import unpickle_graph_backend sage: b = unpickle_graph_backend(0,[0,1,2,3],[(0,3,'label'),(0,0,1)],{'loops':True}) sage: b <sage.graphs.base.sparse_graph.SparseGraphBackend object at ...> sage: list(b.iterator_edges(range(4),1)) [(0, 0, 1), (0, 3, 'label')]