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 vertices u such that the edge \((u,v)\) is in self (that is, predecessors of \(v\)).
iterator_out_nbrs() Iterate over the vertices u such that the edge \((v,u)\) is in self (that is, successors of \(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)

True if self has an edge (u,v) with label l.

INPUT:

  • u,v – vertex labels
  • l – label

OUTPUT:

boolean
has_vertex(v)

True if 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.

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.

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 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.

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.

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

  • vertex – 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)

The number of edges in self

INPUT:

  • directed – boolean
num_verts()

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
class sage.graphs.base.graph_backends.NetworkXDiGraphDeprecated

Bases: sage.structure.sage_object.SageObject

Class for unpickling old networkx.XDiGraph formats

mutate()

Change the old networkx XDiGraph format into the new one.

OUTPUT:

  • The networkx.DiGraph or networkx.MultiDiGraph corresponding to the unpickled data.

EXAMPLES:

sage: from sage.graphs.base.graph_backends import NetworkXDiGraphDeprecated as NXDGD
sage: X = NXDGD()
sage: X.adj = {1:{2:7}, 2:{1:[7,8], 3:[4,5,6,7]}}
sage: X.multiedges = True
sage: G = X.mutate()
sage: G.edges()
OutMultiEdgeDataView([(1, 2), (2, 1), (2, 3)])
sage: G.edges(data=True)
OutMultiEdgeDataView([(1, 2, {'weight': 7}),
                      (2, 1, {8: {}, 7: {}}),
                      (2, 3, {4: {}, 5: {}, 6: {}, 7: {}})])
class sage.graphs.base.graph_backends.NetworkXGraphDeprecated

Bases: sage.structure.sage_object.SageObject

Class for unpickling old networkx.XGraph formats

mutate()

Change the old networkx XGraph format into the new one.

OUTPUT:

  • The networkx.Graph or networkx.MultiGraph corresponding to the unpickled data.

EXAMPLES:

sage: from sage.graphs.base.graph_backends import NetworkXGraphDeprecated as NXGD
sage: X = NXGD()
sage: X.adj = {1:{2:7}, 2:{1:7}, 3:{2:[4,5,6,7]}, 2:{3:[4,5,6,7]}}
sage: X.multiedges = True
sage: G = X.mutate()
sage: G.edges()
MultiEdgeDataView([(1, 2), (2, 3)])
sage: G.edges(data=True)
MultiEdgeDataView([(1, 2, {'weight': 7}), (2, 3, {4: {}, 5: {}, 6: {}, 7: {}})])
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),1))
[(0, 0, 1), (0, 3, 'label')]