Backends for Sage (di)graphs.

This module implements GenericGraphBackend (the base class for backends) and NetworkXGraphBackend (a wrapper for NetworkX graphs)

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.

TESTS:

sage: import sage.graphs.base.graph_backends
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

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.add_edge(1,2,'a',True)
Traceback (most recent call last):
...
NotImplementedError
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

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.add_edges([],True)
Traceback (most recent call last):
...
NotImplementedError
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.add_vertex(0)
Traceback (most recent call last):
...
NotImplementedError
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

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.degree(1, False)
Traceback (most recent call last):
...
NotImplementedError
del_edge(u, v, l, directed)

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

INPUT:

  • u,v – vertices
  • l – edge label
  • directed – boolean

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.del_edge(1,2,'a',True)
Traceback (most recent call last):
...
NotImplementedError
del_vertex(v)

Delete a labelled vertex in self.

INPUT:

  • v – vertex label

TESTS:

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

Delete labelled vertices in self.

INPUT:

  • vertices – iterator of vertex labels

TESTS:

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

Return the edge label of \((u,v)\).

INPUT:

  • u,v – vertex labels

OUTPUT:

label of \((u,v)\)

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.get_edge_label(1,2)
Traceback (most recent call last):
...
NotImplementedError
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

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.has_edge(1,2,'a')
Traceback (most recent call last):
...
NotImplementedError
has_vertex(v)

True if self has a vertex with label v.

INPUT:

  • v – vertex label
OUTPUT:
boolean

TESTS:

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

Return the in-degree of \(v\)

INPUT:

  • v – a vertex label

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.in_degree(1)
Traceback (most recent call last):
...
NotImplementedError
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.iterator_edges([],True)
Traceback (most recent call last):
...
NotImplementedError
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.iterator_in_edges([],True)
Traceback (most recent call last):
...
NotImplementedError
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

TESTS:

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

Iterate over the vertices adjacent to v.

INPUT:

  • v – vertex label

OUTPUT:

a generator which yields vertex labels

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.iterator_nbrs(0)
Traceback (most recent call last):
...
NotImplementedError
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.iterator_out_edges([],True)
Traceback (most recent call last):
...
NotImplementedError
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

TESTS:

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

Iterate over the vertices v with labels in verts.

INPUT:

  • vertex – vertex labels

OUTPUT:

a generator which yields vertices

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.iterator_verts(0)
Traceback (most recent call last):
...
NotImplementedError
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.loops(True)
Traceback (most recent call last):
...
NotImplementedError
sage: G.loops(None)
Traceback (most recent call last):
...
NotImplementedError
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.multiple_edges(True)
Traceback (most recent call last):
...
NotImplementedError
sage: G.multiple_edges(None)
Traceback (most recent call last):
...
NotImplementedError
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.name("A Generic Graph")
Traceback (most recent call last):
...
NotImplementedError
sage: G.name(None)
Traceback (most recent call last):
...
NotImplementedError
num_edges(directed)

The number of edges in self

INPUT:

  • directed – boolean

TESTS:

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

The number of vertices in self

TESTS:

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

Return the out-degree of \(v\)

INPUT:

  • v – a vertex label

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.out_degree(1)
Traceback (most recent call last):
...
NotImplementedError
relabel(perm, directed)

Relabel the vertices of self by a permutation.

INPUT:

  • perm – permutation
  • directed – boolean

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.relabel([],False)
Traceback (most recent call last):
...
NotImplementedError
set_edge_label(u, v, l, directed)

Label the edge (u,v) by l.

INPUT:

  • u,v – vertices
  • l – edge label
  • directed – boolean

TESTS:

sage: G = sage.graphs.base.graph_backends.GenericGraphBackend()
sage: G.set_edge_label(1,2,'a',True)
Traceback (most recent call last):
...
NotImplementedError
class sage.graphs.base.graph_backends.NetworkXDiGraphDeprecated

Bases: sage.structure.sage_object.SageObject

Class for unpickling old networkx.XDiGraph formats

TESTS:

sage: import sage.graphs.base.graph_backends
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()
[(1, 2), (2, 1), (2, 3)]
sage: G.edges(data=True)
[(1, 2, {'weight': 7}),
 (2, 1, {7: {}, 8: {}}),
 (2, 3, {4: {}, 5: {}, 6: {}, 7: {}})]
class sage.graphs.base.graph_backends.NetworkXGraphBackend(N=None)

Bases: sage.graphs.base.graph_backends.GenericGraphBackend

A wrapper for NetworkX as the backend of a graph.

TESTS:

sage: import sage.graphs.base.graph_backends
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

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.add_edge(1,2,'a',True)
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

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.add_edges([],True)
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.add_vertex(0)
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.NetworkXGraphBackend()
sage: G.add_vertices([1,2,3])
sage: G.add_vertices([4,None,None,5])
[0, 6]
degree(v, directed)

Return the total number of vertices incident to \(v\).

INPUT:

  • v – a vertex label
  • directed – boolean

OUTPUT:

degree of v

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.add_vertices(range(3))
sage: G.degree(1, False)
0
del_edge(u, v, l, directed)

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

INPUT:

  • u,v – vertices
  • l – edge label
  • directed – boolean

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.del_edge(1,2,'a',True)
del_vertex(v)

Delete a labelled vertex in self.

INPUT:

  • v – vertex label

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.del_vertex(0)
Traceback (most recent call last):
...
NetworkXError: The node 0 is not in the graph.
del_vertices(vertices)

Delete labelled vertices in self.

INPUT:

  • vertices – iterator of vertex labels

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.del_vertices([1,2,3])
Traceback (most recent call last):
...
NetworkXError: The node 1 is not in the graph.
get_edge_label(u, v)

Return the edge label of \((u,v)\).

INPUT:

  • u,v – vertex labels
OUTPUT:
label of \((u,v)\)

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.get_edge_label(1,2)
Traceback (most recent call last):
...
NetworkXError: Edge (1,2) requested via get_edge_label does not exist.
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

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.has_edge(1,2,'a')
False
has_vertex(v)

True if self has a vertex with label v.

INPUT:

  • v – vertex label
OUTPUT:
boolean

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.has_vertex(0)
False
in_degree(v)

Return the in-degree of \(v\).

INPUT:

  • v – a vertex label

OUTPUT:

degree of v

TESTS:

sage: G = DiGraph(digraphs.Path(5),implementation="networkx")
doctest:...: DeprecationWarning: The 'implementation' keyword is deprecated, and the graphs has been stored as a 'c_graph'
See http://trac.sagemath.org/18375 for details.
sage: G = G._backend
sage: G.in_degree(0)
0
sage: G.in_degree(4)
1
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.iterator_edges([],True)
<generator object at ...>
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: i = G.iterator_in_edges([],True)
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

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.iterator_in_nbrs(0)
Traceback (most recent call last):
...
AttributeError: 'MultiGraph' object has no attribute 'predecessors_iter'
iterator_nbrs(v)

Iterate over the vertices adjacent to v.

INPUT:

  • v – vertex label
OUTPUT:
a generator which yields vertex labels

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.add_vertex(0)
sage: G.iterator_nbrs(0)
<dictionary-keyiterator object at ...>
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: i = G.iterator_out_edges([],True)
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

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.iterator_out_nbrs(0)
Traceback (most recent call last):
...
AttributeError: 'MultiGraph' object has no attribute 'successors_iter'
iterator_verts(verts)

Iterate over the vertices v with labels in verts.

INPUT:

  • vertex – vertex labels
OUTPUT:
a generator which yields vertices

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.iterator_verts(0)
<generator object bunch_iter at ...>
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.loops(True)
sage: G.loops(None)
True
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.multiple_edges(True)
sage: G.multiple_edges(None)
True
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.

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.name("A NetworkX Graph")
sage: G.name(None)
'A NetworkX Graph'
num_edges(directed)

The number of edges in self

INPUT:

  • directed – boolean

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.num_edges(True)
0
sage: G.num_edges(False)
0
num_verts()

The number of vertices in self

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.num_verts()
0
out_degree(v)

Return the out-degree of \(v\).

INPUT:

  • v – a vertex label

OUTPUT:

degree of v

TESTS:

sage: G = DiGraph(digraphs.Path(5),implementation="networkx")
doctest:...: DeprecationWarning: The 'implementation' keyword is deprecated, and the graphs has been stored as a 'c_graph'
See http://trac.sagemath.org/18375 for details.
sage: G = G._backend
sage: G.out_degree(0)
1
sage: G.out_degree(4)
0
relabel(perm, directed)

Relabel the vertices of self by a permutation.

INPUT:

  • perm – permutation
  • directed – boolean

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.relabel([],False)
set_edge_label(u, v, l, directed)

Label the edge (u,v) by l.

INPUT:

  • u,v – vertices
  • l – edge label
  • directed – boolean

TESTS:

sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend()
sage: G.set_edge_label(1,2,'a',True)
class sage.graphs.base.graph_backends.NetworkXGraphDeprecated

Bases: sage.structure.sage_object.SageObject

Class for unpickling old networkx.XGraph formats

TESTS:

sage: from sage.graphs.base.graph_backends import NetworkXGraphDeprecated as NXGD
sage: X = NXGD()
doctest:...
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()
[(1, 2), (2, 3)]
sage: G.edges(data=True)
[(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.

EXAMPLE:

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
<type 'sage.graphs.base.sparse_graph.SparseGraphBackend'>
sage: list(b.iterator_edges(range(4),1))
[(0, 0, 1), (0, 3, 'label')]