Static sparse graph backend¶
This module implement a immutable sparse graph backend using the data structure
from sage.graphs.base.static_sparse_graph
. It supports both directed and
undirected graphs, as well as vertex/edge labels, loops and multiple edges. As
it uses a very compact C structure it should be very small in memory.
As it is a sparse data structure, you can expect it to be very efficient when
you need to list the graph’s edge, or those incident to a vertex, but an
adjacency test can be much longer than in a dense data structure (i.e. like in
sage.graphs.base.static_dense_graph
)
For an overview of graph data structures in sage, see
overview
.
Two classes¶
This module implements two classes
StaticSparseCGraph
extendsCGraph
and is a Cython class that manages the definition/deallocation of theshort_digraph
structure. It does not know anything about labels on vertices.StaticSparseBackend
extendsCGraphBackend
and is a Python class that does know about vertex labels and contains an instance ofStaticSparseCGraph
as an internal variable. The input/output of its methods are labeled vertices, which it translates to integer id before forwarding them to theStaticSparseCGraph
instance.
Classes and methods¶
-
class
sage.graphs.base.static_sparse_backend.
StaticSparseBackend
¶ Bases:
sage.graphs.base.c_graph.CGraphBackend
A graph
backend
for static sparse graphs.EXAMPLE:
sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(9) sage: D.add_edge(0,1,None,False) sage: list(D.iterator_edges(range(9), True)) [(0, 1, None)]
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: list(g.iterator_edges([0],1)) [(0, 1, None), (0, 4, None), (0, 5, None)]
sage: g=DiGraph(digraphs.DeBruijn(4,3),data_structure="static_sparse") sage: gi=DiGraph(g,data_structure="static_sparse") sage: gi.edges()[0] ('000', '000', '0') sage: gi.edges_incident('111') [('111', '110', '0'), ('111', '111', '1'), ('111', '112', '2'), ('111', '113', '3')] sage: sorted(g.edges()) == sorted(gi.edges()) True
sage: g = graphs.PetersenGraph() sage: gi=Graph(g,data_structure="static_sparse") sage: g == gi True sage: sorted(g.edges()) == sorted(gi.edges()) True
sage: gi = Graph( { 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2} }, data_structure="static_sparse") sage: (0,4,2) in gi.edges() True sage: gi.has_edge(0,4) True
sage: G = Graph({1:{2:28, 6:10}, 2:{3:16, 7:14}, 3:{4:12}, 4:{5:22, 7:18}, 5:{6:25, 7:24}}) sage: GI = Graph({1:{2:28, 6:10}, 2:{3:16, 7:14}, 3:{4:12}, 4:{5:22, 7:18}, 5:{6:25, 7:24}}, data_structure="static_sparse") sage: G == GI True
sage: G = graphs.OddGraph(4) sage: d = G.diameter() sage: H = G.distance_graph(range(d+1)) sage: HI = Graph(H,data_structure="static_sparse") sage: HI.size() == len(HI.edges()) True
sage: g = Graph({1:{1:[1,2,3]}}, data_structure="static_sparse") sage: g.size() 3 sage: g.order() 1 sage: g.vertices() [1] sage: g.edges() [(1, 1, 1), (1, 1, 2), (1, 1, 3)]
trac ticket #15810 is fixed:
sage: DiGraph({1:{2:['a','b'], 3:['c']}, 2:{3:['d']}}, immutable=True).is_directed_acyclic() True
-
add_vertex
(v)¶ Addition of vertices is not available on an immutable graph.
EXAMPLE:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse") sage: g.add_vertex(1) Traceback (most recent call last): ... ValueError: Thou shalt not add a vertex to an immutable graph sage: g.add_vertices([1,2,3]) Traceback (most recent call last): ... ValueError: Thou shalt not add a vertex to an immutable graph
-
allows_loops
(value=None)¶ Returns whether the graph allows loops
INPUT:
value
– only useful for compatibility with other graph backends, where this method can be used to define this boolean. This method raises an exception ifvalue
is not equal toNone
.
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: g.allows_loops() False sage: g = StaticSparseBackend(graphs.PetersenGraph(), loops=True) sage: g.allows_loops() True
-
degree
(v, directed)¶ Returns the degree of a vertex
INPUT:
v
– a vertexdirected
– boolean; whether to take into account the orientation of this graph in counting the degree ofv
.
EXAMPLE:
sage: g = Graph(graphs.PetersenGraph(), data_structure="static_sparse") sage: g.degree(0) 3
trac ticket #17225 about the degree of a vertex with a loop:
sage: Graph({0:[0]},immutable=True).degree(0) 2 sage: Graph({0:[0],1:[0,1,1,1]},immutable=True).degree(1) 7
-
del_vertex
(v)¶ Removal of vertices is not available on an immutable graph.
EXAMPLE:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse") sage: g.delete_vertex(1) Traceback (most recent call last): ... ValueError: Thou shalt not remove a vertex from an immutable graph sage: g.delete_vertices([1,2,3]) Traceback (most recent call last): ... ValueError: Thou shalt not remove a vertex from an immutable graph
-
get_edge_label
(u, v)¶ Returns the edge label for
(u,v)
.INPUT:
u,v
– two vertices
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: print(g.get_edge_label(0,1)) None sage: print(g.get_edge_label(0,"Hey")) Traceback (most recent call last): ... LookupError: One of the two vertices does not belong to the graph sage: print(g.get_edge_label(0,7)) Traceback (most recent call last): ... LookupError: The edge does not exist
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(digraphs.DeBruijn(3,2)) sage: g.has_edge('00','01','1') True sage: g.has_edge('00','01','0') False
-
has_edge
(u, v, l)¶ Returns whether this graph has edge
(u,v)
with labell
.If
l
isNone
, return whether this graph has an edge(u,v)
with any label.INPUT:
u,v
– two verticesl
– a label
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: g.has_edge(0,1,'e') False sage: g.has_edge(0,4,None) True
-
has_vertex
(v)¶ Tests if the vertex belongs to the graph
INPUT:
v
– a vertex (or not?)
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: g.has_vertex(0) True sage: g.has_vertex("Hey") False
-
in_degree
(v)¶ Returns the in-degree of a vertex
INPUT:
v
– a vertex
EXAMPLE:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse") sage: g.in_degree(0) 3
-
iterator_edges
(vertices, labels)¶ Returns an iterator over the graph’s edges.
INPUT:
vertices
– only returns the edges incident to at least one vertex ofvertices
.labels
– whether to return edge labels too
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: list(g.iterator_edges(g.iterator_verts(None), False)) [(0, 1), (0, 4), (0, 5), (1, 2), (1, 6), (2, 3), (2, 7), (3, 4), (3, 8), (4, 9), (5, 7), (5, 8), (6, 8), (6, 9), (7, 9)]
sage: Graph(immutable=True).edges() []
-
iterator_in_edges
(vertices, labels)¶ Iterate over the incoming edges incident to a sequence of vertices.
INPUT:
vertices
– a list of verticeslabels
– whether to return labels too
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: list(g.iterator_in_edges([0],False)) [(0, 1), (0, 4), (0, 5)] sage: list(g.iterator_in_edges([0],True)) [(0, 1, None), (0, 4, None), (0, 5, None)]
sage: DiGraph(digraphs.Path(5),immutable=False).incoming_edges([2]) [(1, 2, None)] sage: DiGraph(digraphs.Path(5),immutable=True).incoming_edges([2]) [(1, 2, None)]
-
iterator_in_nbrs
(v)¶ Returns the out-neighbors of a vertex
INPUT:
v
– a vertex
EXAMPLE:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse") sage: g.neighbors_in(0) [1, 4, 5]
-
iterator_nbrs
(v)¶ Returns the neighbors of a vertex
INPUT:
v
– a vertex
EXAMPLE:
sage: g = Graph(graphs.PetersenGraph(), data_structure="static_sparse") sage: g.neighbors(0) [1, 4, 5]
-
iterator_out_edges
(vertices, labels)¶ Iterate over the outbound edges incident to a sequence of vertices.
INPUT:
vertices
– a list of verticeslabels
– whether to return labels too
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: list(g.iterator_out_edges([0], False)) [(0, 1), (0, 4), (0, 5)] sage: list(g.iterator_out_edges([0],True)) [(0, 1, None), (0, 4, None), (0, 5, None)]
-
iterator_out_nbrs
(v)¶ Returns the out-neighbors of a vertex
INPUT:
v
– a vertex
EXAMPLE:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse") sage: g.neighbors_out(0) [1, 4, 5]
-
iterator_verts
(vertices)¶ Returns an iterator over the vertices
INPUT:
vertices
– a list of objects. The method will only return the elements of the graph which are contained invertices
. It’s not very efficient. Ifvertices
is equal toNone
, all the vertices are returned.
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: list(g.iterator_verts(None)) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: list(g.iterator_verts([1,"Hey","I am a french fry"])) [1]
-
multiple_edges
(value=None)¶ Returns whether the graph allows multiple edges
INPUT:
value
– only useful for compatibility with other graph backends, where this method can be used to define this boolean. This method raises an exception ifvalue
is not equal toNone
.
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: g.multiple_edges() False sage: g = StaticSparseBackend(graphs.PetersenGraph(), multiedges=True) sage: g.multiple_edges() True
-
num_edges
(directed)¶ Returns the number of edges
INPUT:
directed
(boolean) – whether to consider the graph as directed or not.
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: g.num_edges(False) 15
Testing the exception:
sage: g = StaticSparseBackend(digraphs.Circuit(4)) sage: g.num_edges(False) Traceback (most recent call last): ... NotImplementedError: Sorry, I have no idea what is expected in this situation. I don't think that it is well-defined either, especially for multigraphs.
sage: g=digraphs.RandomDirectedGNP(10,.3) sage: gi=DiGraph(g,data_structure="static_sparse") sage: gi.size() == len(gi.edges()) True
-
num_verts
()¶ Returns the number of vertices
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: g.num_verts() 10
-
out_degree
(v)¶ Returns the out-degree of a vertex
INPUT:
v
– a vertex
EXAMPLE:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse") sage: g.out_degree(0) 3
-
relabel
(perm, directed)¶ Relabel the graphs’ vertices. No way.
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend sage: g = StaticSparseBackend(graphs.PetersenGraph()) sage: g.relabel([],True) Traceback (most recent call last): ... ValueError: Thou shalt not relabel an immutable graph
-
-
class
sage.graphs.base.static_sparse_backend.
StaticSparseCGraph
¶ Bases:
sage.graphs.base.c_graph.CGraph
CGraph
class based on the sparse graph data structurestatic sparse graphs
.-
add_vertex
(k)¶ Adds a vertex to the graph. No way.
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph sage: g = StaticSparseCGraph(graphs.PetersenGraph()) sage: g.add_vertex(45) Traceback (most recent call last): ... ValueError: Thou shalt not add a vertex to an immutable graph
-
del_vertex
(k)¶ Removes a vertex from the graph. No way.
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph sage: g = StaticSparseCGraph(graphs.PetersenGraph()) sage: g.del_vertex(45) Traceback (most recent call last): ... ValueError: Thou shalt not remove a vertex from an immutable graph
-
has_arc
(u, v)¶ Tests if uv is an edge of the graph
INPUT:
u,v
– integers
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph sage: g = StaticSparseCGraph(graphs.PetersenGraph()) sage: g.has_arc(0,1) True sage: g.has_arc(0,7) False
-
has_vertex
(n)¶ Tests if a vertex belongs to the graph
INPUT:
n
– an integer
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph sage: g = StaticSparseCGraph(graphs.PetersenGraph()) sage: g.has_vertex(1) True sage: g.has_vertex(10) False
-
in_degree
(u)¶ Returns the in-degree of a vertex
INPUT:
u
– a vertex
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph sage: g = StaticSparseCGraph(graphs.PetersenGraph()) sage: g.in_degree(0) 3 sage: g.in_degree(10) Traceback (most recent call last): ... LookupError: The vertex does not belong to the graph
-
in_neighbors
(u)¶ Returns the in-neighbors of a vertex
INPUT:
u
– a vertex
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph sage: g = StaticSparseCGraph(graphs.PetersenGraph()) sage: g.in_neighbors(0) [1, 4, 5] sage: g.in_neighbors(10) Traceback (most recent call last): ... LookupError: The vertex does not belong to the graph
-
out_degree
(u)¶ Returns the out-degree of a vertex
INPUT:
u
– a vertex
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph sage: g = StaticSparseCGraph(graphs.PetersenGraph()) sage: g.out_degree(0) 3 sage: g.out_degree(10) Traceback (most recent call last): ... LookupError: The vertex does not belong to the graph
-
out_neighbors
(u)¶ List the out-neighbors of a vertex
INPUT:
u
– a vertex
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph sage: g = StaticSparseCGraph(graphs.PetersenGraph()) sage: g.out_neighbors(0) [1, 4, 5] sage: g.out_neighbors(10) Traceback (most recent call last): ... LookupError: The vertex does not belong to the graph
-
verts
()¶ Returns the list of vertices
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph sage: g = StaticSparseCGraph(graphs.PetersenGraph()) sage: g.verts() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
-