# 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 in-degree of $$v$$ out_degree() Return the out-degree 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 in-neighbors of vertex $$v$$. iterator_out_nbrs() Iterate over the out-neighbors 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

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 – vertices
• l – edge label
• directed – 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 all None values in vertices

OUTPUT:

Generated names of new vertices if there is at least one None value present in vertices. None otherwise.

EXAMPLES:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
Traceback (most recent call last):
...
NotImplementedError

degree(v, directed)

Return the total number of vertices incident to $$v$$.

INPUT:

• v – a vertex label
• directed – boolean

OUTPUT:

degree of $$v$$

del_edge(u, v, l, directed)

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

INPUT:

• u,v – vertices
• l – edge label
• directed – 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 labels
• l – 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 in-degree 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 in self.

INPUT:

• vertices – a list of vertex labels
• labels – 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 in self.

INPUT:

• vertices – a list of vertex labels
• labels – boolean
OUTPUT:
a generator which yields edges, with or without labels depending on the labels parameter.
iterator_in_nbrs(v)

Iterate over the in-neighbors 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 in self.

INPUT:

• vertices – a list of vertex labels
• labels – boolean

OUTPUT:

a generator which yields edges, with or without labels depending on the labels parameter.
iterator_out_nbrs(v)

Iterate over the out-neighbors 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) or None, in which case the current value is returned. It is set to None 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) or None, in which case the current value is returned. It is set to None by default.
name(new=None)

Get/set name of self.

INPUT:

• new – can be a string (in which case it sets the value) or None, in which case the current value is returned. It is set to None 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 out-degree of $$v$$

INPUT:

• v – a vertex label
relabel(perm, directed)

Relabel the vertices of self by a permutation.

INPUT:

• perm – permutation
• directed – boolean
set_edge_label(u, v, l, directed)

Label the edge $$(u,v)$$ by $$l$$.

INPUT:

• u,v – vertices
• l – edge label
• directed – 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 running f(*args). In particular, there is apparently no way to define a **kwargs (i.e. define the value of keyword arguments of f), which means that one must know the order of all arguments of f (here, f is Graph or DiGraph).

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 edges
• kwds – any dictionary whose keywords will be forwarded to the graph constructor

This function builds a Graph or DiGraph 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')]