Implements various backends for Sage graphs.

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)

Returns 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)

Deletes 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)

Returns 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()
doctest:...
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)

Returns 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)

Deletes 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)

Returns 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)

Returns the in-degree of v.

INPUT:

  • v – a vertex label

OUTPUT:

degree of v

TESTS:

sage: G = DiGraph(digraphs.Path(5),implementation="networkx")
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 iterator_edges 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)

Returns the out-degree of v.

INPUT:

  • v – a vertex label

OUTPUT:

degree of v

TESTS:

sage: G = DiGraph(digraphs.Path(5),implementation="networkx")
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()
doctest:...
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: {}})]

Previous topic

Static sparse graph backend

Next topic

Hypergraph generators

This Page