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 an edge \((u,v)\) to 

Add a sequence of edges to 

Add a labelled vertex to 

Add labelled vertices to 

Return the total number of vertices incident to \(v\). 

Return the indegree of \(v\) 

Return the outdegree of \(v\) 

Delete the edge \((u,v)\) with label \(l\). 

Delete a labelled vertex in 

Delete labelled vertices in 

Return the edge label of \((u,v)\). 

True if 

True if 

Iterate over the edges incident to a sequence of vertices. 

Iterate over the incoming edges incident to a sequence of vertices. 

Iterate over the outbound edges incident to a sequence of vertices. 

Iterate over the vertices adjacent to \(v\). 

Iterate over the inneighbors of vertex \(v\). 

Iterate over the outneighbors of vertex \(v\). 

Iterate over the vertices \(v\) with labels in verts. 

Get/set whether or not 

Get/set whether or not 

Get/set name of 

The number of edges in 

The number of vertices in 

Relabel the vertices of 

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


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')]