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 ![]() self , with label ![]() |
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 ![]() |
in_degree() |
Return the in-degree of ![]() |
out_degree() |
Return the out-degree of ![]() |
del_edge() |
Delete the edge ![]() ![]() |
del_vertex() |
Delete a labelled vertex in self . |
del_vertices() |
Delete labelled vertices in self . |
get_edge_label() |
Return the edge label of ![]() |
has_edge() |
True if self has an edge ![]() ![]() |
has_vertex() |
True if self has a vertex with label ![]() |
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 ![]() |
iterator_in_nbrs() |
Iterate over the vertices u such that the edge ![]() self (that is, predecessors of ![]() |
iterator_out_nbrs() |
Iterate over the vertices u such that the edge ![]() self (that is, successors of ![]() |
iterator_verts() |
Iterate over the vertices ![]() |
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 ![]() ![]() |
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
– verticesl
– edge labeldirected
– 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 allNone
values invertices
.
OUTPUT:
Generated names of new vertices if there is at least one
None
value present invertices
.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
.
INPUT:
v
– a vertex labeldirected
– boolean
OUTPUT:
degree of v
-
del_edge
(u, v, l, directed)¶ Delete the edge
with label
.
INPUT:
u,v
– verticesl
– edge labeldirected
– 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
.
INPUT:
u,v
– vertex labels
OUTPUT:
label of
-
has_edge
(u, v, l)¶ True if self has an edge (u,v) with label l.
INPUT:
u,v
– vertex labelsl
– 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
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 labelslabels
– 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 labelslabels
– 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 labelslabels
– 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) orNone
, in which case the current value is returned. It is set toNone
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) orNone
, in which case the current value is returned. It is set toNone
by default.
-
name
(new=None)¶ Get/set name of self.
INPUT:
new
– can be a string (in which case it sets the value) orNone
, in which case the current value is returned. It is set toNone
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
INPUT:
v
– a vertex label
-
relabel
(perm, directed)¶ Relabel the vertices of self by a permutation.
INPUT:
perm
– permutationdirected
– boolean
-
set_edge_label
(u, v, l, directed)¶ Label the edge (u,v) by l.
INPUT:
u,v
– verticesl
– edge labeldirected
– 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
– verticesl
– edge labeldirected
– 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 allNone
values invertices
.
OUTPUT:
Generated names of new vertices if there is at least one
None
value present invertices
.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
.
INPUT:
v
– a vertex labeldirected
– boolean
OUTPUT:
degree of v
-
del_edge
(u, v, l, directed)¶ Delete the edge
with label
.
INPUT:
u,v
– verticesl
– edge labeldirected
– 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
.
INPUT:
u,v
– vertex labels
- OUTPUT:
- label of
-
has_edge
(u, v, l)¶ True if self has an edge (u,v) with label l.
INPUT:
u,v
– vertex labelsl
– 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
.
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 labelslabels
– 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 labelslabels
– 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 labelslabels
– 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) orNone
, in which case the current value is returned. It is set toNone
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) orNone
, in which case the current value is returned. It is set toNone
by default.
-
name
(new=None)¶ Get/set name of self.
INPUT:
new
– can be a string (in which case it sets the value) orNone
, in which case the current value is returned. It is set toNone
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
.
INPUT:
v
– a vertex label
OUTPUT:
degree of v
-
relabel
(perm, directed)¶ Relabel the vertices of self by a permutation.
INPUT:
perm
– permutationdirected
– boolean
-
set_edge_label
(u, v, l, directed)¶ Label the edge (u,v) by l.
INPUT:
u,v
– verticesl
– edge labeldirected
– 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 runningf(*args)
. In particular, there is apparently no way to define a**kwargs
(i.e. define the value of keyword arguments off
), which means that one must know the order of all arguments off
(here,f
isGraph
orDiGraph
).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 edgeskwds
– any dictionary whose keywords will be forwarded to the graph constructor.
This function builds a
Graph
orDiGraph
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')]