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

Bases: 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 – 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

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.add_vertices([1,2,3])
Traceback (most recent call last):
...
NotImplementedError

Python

>>> from sage.all import *
>>> G = sage.graphs.base.graph_backends.GenericGraphBackend()
>>> G.add_vertices([Integer(1),Integer(2),Integer(3)])
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 – 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 – 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 – 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

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

Python

>>> from sage.all import *
>>> from sage.graphs.base.graph_backends import unpickle_graph_backend
>>> b = unpickle_graph_backend(Integer(0), [Integer(0), Integer(1), Integer(2), Integer(3)], [(Integer(0), Integer(3), 'label'), (Integer(0), Integer(0), Integer(1))], {'loops': True})
>>> b
<sage.graphs.base.sparse_graph.SparseGraphBackend object at ...>
>>> list(b.iterator_edges(range(Integer(4)), True))
[(0, 0, 1), (0, 3, 'label')]