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 inneighbors of vertex \(v\). 
iterator_out_nbrs() 
Iterate over the outneighbors of vertex \(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
isTrue
, 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
isTrue
, these are interpreted as arcs.INPUT:
edges
– list/iterator of edges to be addeddirected
– 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)¶ Check whether
self
has an edge \((u,v)\) with label \(l\).INPUT:
u,v
– vertex labelsl
– label
OUTPUT:
boolean

has_vertex
(v)¶ Check whether
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.
This method returns an iterator over the edges \((u, v)\) such that either \(u\) or \(v\) is in
vertices
and the edge \((u, v)\) is inself
.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.
This method returns an iterator over the edges \((u, v)\) such that \(v\) is in
vertices
and the edge \((u, v)\) is inself
.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 inneighbors of vertex \(v\).
This method returns an iterator 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\).
This method returns an iterator over the vertices \(u\) such that either the edge \((u, v)\) or the edge \((v, u)\) is in
self
(that is, neighbors of \(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.
This method returns an iterator over the edges \((v, u)\) such that \(v\) is in
vertices
and the edge \((v, u)\) is inself
.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 outneighbors of \(v\).
This method returns an iterator 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:
verts
– 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)¶ Return the number of edges in
self
INPUT:
directed
– boolean

num_verts
()¶ Return 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
– booleanvertices
– list of verticesedges
– 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), True)) [(0, 0, 1), (0, 3, 'label')]