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.

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()
[(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.

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

OUTPUT:

degree of v
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

OUTPUT:

degree of v
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.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()
[(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.

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