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.EXAMPLES:
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: sorted(gi.edges_incident('111')) [('111', '110', '0'), ('111', '111', '1'), ('111', '112', '2'), ('111', '113', '3')] sage: set(g.edges()) == set(gi.edges()) True
sage: g = graphs.PetersenGraph() sage: gi = Graph(g, data_structure="static_sparse") sage: g == gi True sage: set(g.edges()) == set(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(list(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.
EXAMPLES:
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)¶ Return 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
.

degree
(v, directed)¶ Return 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
EXAMPLES:
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.
EXAMPLES:
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)¶ Return the edge label for
(u, v)
.INPUT:
u,v
– two vertices
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)¶ Return 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

has_vertex
(v)¶ Test if the vertex belongs to the graph
INPUT:
v
– a vertex (or not?)

in_degree
(v)¶ Return the indegree of a vertex
INPUT:
v
– a vertex
EXAMPLES:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse") sage: g.in_degree(0) 3

iterator_edges
(vertices, labels)¶ Return an iterator over the graph’s edges.
INPUT:
vertices
– list; only returns the edges incident to at least one vertex ofvertices
labels
– boolean; whether to return edge labels too

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
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)¶ Return an iterator over the inneighbors of a vertex
INPUT:
v
– a vertex
EXAMPLES:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse") sage: g.neighbors_in(0) [1, 4, 5]

iterator_nbrs
(v)¶ Return an iterator over the neighbors of a vertex
INPUT:
v
– a vertex
EXAMPLES:
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

iterator_out_nbrs
(v)¶ Return an iterator over the outneighbors of a vertex
INPUT:
v
– a vertex
EXAMPLES:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse") sage: g.neighbors_out(0) [1, 4, 5]

iterator_verts
(vertices)¶ Return 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.

multiple_edges
(value=None)¶ Return 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
.

num_edges
(directed)¶ Return the number of edges
INPUT:
directed
– boolean; whether to consider the graph as directed or not.

num_verts
()¶ Return the number of vertices

out_degree
(v)¶ Return the outdegree of a vertex
INPUT:
v
– a vertex
EXAMPLES:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse") sage: g.out_degree(0) 3

relabel
(perm, directed)¶ Relabel the graphs’ vertices. No way.


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)¶ Add a vertex to the graph. No way.

del_vertex
(k)¶ Remove a vertex from the graph. No way.

has_arc
(u, v)¶ Test if \(uv\) is an edge of the graph
INPUT:
u,v
– integers

has_vertex
(v)¶ Test if a vertex belongs to the graph
INPUT:
n
– an integer

in_degree
(u)¶ Return the indegree of a vertex
INPUT:
u
– a vertex

in_neighbors
(u)¶ Return the inneighbors of a vertex
INPUT:
u
– a vertex

out_degree
(u)¶ Return the outdegree of a vertex
INPUT:
u
– a vertex

out_neighbors
(u)¶ List the outneighbors of a vertex
INPUT:
u
– a vertex

verts
()¶ Returns the list of vertices
