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