Backends for Sage (di)graphs.¶
This module implements GenericGraphBackend
(the base class for
backends).
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
– 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 \(v\).
INPUT:
v
– a vertex labeldirected
– boolean
OUTPUT:
degree of v
-
del_edge
(u, v, l, directed)¶ Delete the edge \((u,v)\) with label \(l\).
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 \((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 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 \(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 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 \(v\)
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() OutMultiEdgeDataView([(1, 2), (2, 1), (2, 3)]) sage: G.edges(data=True) OutMultiEdgeDataView([(1, 2, {'weight': 7}), (2, 1, {8: {}, 7: {}}), (2, 3, {4: {}, 5: {}, 6: {}, 7: {}})])
-
-
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() MultiEdgeDataView([(1, 2), (2, 3)]) sage: G.edges(data=True) MultiEdgeDataView([(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 <sage.graphs.base.sparse_graph.SparseGraphBackend object at ...> sage: list(b.iterator_edges(range(4),1)) [(0, 0, 1), (0, 3, 'label')]