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