# Implements various backends for Sage graphs.¶

class sage.graphs.base.graph_backends.GenericGraphBackend

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 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()
Traceback (most recent call last):
...
NotImplementedError


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()
Traceback (most recent call last):
...
NotImplementedError


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()
Traceback (most recent call last):
...
NotImplementedError


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

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)

A wrapper for NetworkX as the backend of a graph.

TESTS:

sage: import sage.graphs.base.graph_backends


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


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


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


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

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