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 extends CGraph and is a Cython class that manages the definition/deallocation of the short_digraph structure. It does not know anything about labels on vertices.

  • StaticSparseBackend extends CGraphBackend and is a Python class that does know about vertex labels and contains an instance of StaticSparseCGraph as an internal variable. The input/output of its methods are labeled vertices, which it translates to integer id before forwarding them to the StaticSparseCGraph instance.

Classes and methods

class sage.graphs.base.static_sparse_backend.StaticSparseBackend[source]

Bases: 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)]

>>> from sage.all import *
>>> D = sage.graphs.base.sparse_graph.SparseGraphBackend(Integer(9))
>>> D.add_edge(Integer(0), Integer(1), None, False)
>>> list(D.iterator_edges(range(Integer(9)), True))
[(0, 1, None)]

D = sage.graphs.base.sparse_graph.SparseGraphBackend(9)
D.add_edge(0, 1, None, False)
list(D.iterator_edges(range(9), True))
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)]

>>> from sage.all import *
>>> from sage.graphs.base.static_sparse_backend import StaticSparseBackend
>>> g = StaticSparseBackend(graphs.PetersenGraph())
>>> list(g.iterator_edges([Integer(0)], Integer(1)))
[(0, 1, None), (0, 4, None), (0, 5, None)]

from sage.graphs.base.static_sparse_backend import StaticSparseBackend
g = StaticSparseBackend(graphs.PetersenGraph())
list(g.iterator_edges([0], 1))
>>> from sage.all import *
>>> from sage.graphs.base.static_sparse_backend import StaticSparseBackend
>>> g = StaticSparseBackend(graphs.PetersenGraph())
>>> list(g.iterator_edges([Integer(0)], Integer(1)))
[(0, 1, None), (0, 4, None), (0, 5, None)]

from sage.graphs.base.static_sparse_backend import StaticSparseBackend
g = StaticSparseBackend(graphs.PetersenGraph())
list(g.iterator_edges([0], 1))
sage: # needs sage.combinat
sage: g = DiGraph(digraphs.DeBruijn(4, 3), data_structure='static_sparse')
sage: gi = DiGraph(g, data_structure='static_sparse')
sage: gi.edges(sort=True)[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(sort=False)) == set(gi.edges(sort=False))                 # needs sage.combinat
True

>>> from sage.all import *
>>> # needs sage.combinat
>>> g = DiGraph(digraphs.DeBruijn(Integer(4), Integer(3)), data_structure='static_sparse')
>>> gi = DiGraph(g, data_structure='static_sparse')
>>> gi.edges(sort=True)[Integer(0)]
('000', '000', '0')
>>> sorted(gi.edges_incident('111'))
[('111', '110', '0'),
('111', '111', '1'),
('111', '112', '2'),
('111', '113', '3')]

>>> set(g.edges(sort=False)) == set(gi.edges(sort=False))                 # needs sage.combinat
True

# needs sage.combinat
g = DiGraph(digraphs.DeBruijn(4, 3), data_structure='static_sparse')
gi = DiGraph(g, data_structure='static_sparse')
gi.edges(sort=True)[0]
sorted(gi.edges_incident('111'))
set(g.edges(sort=False)) == set(gi.edges(sort=False))                 # needs sage.combinat
>>> from sage.all import *
>>> # needs sage.combinat
>>> g = DiGraph(digraphs.DeBruijn(Integer(4), Integer(3)), data_structure='static_sparse')
>>> gi = DiGraph(g, data_structure='static_sparse')
>>> gi.edges(sort=True)[Integer(0)]
('000', '000', '0')
>>> sorted(gi.edges_incident('111'))
[('111', '110', '0'),
('111', '111', '1'),
('111', '112', '2'),
('111', '113', '3')]

>>> set(g.edges(sort=False)) == set(gi.edges(sort=False))                 # needs sage.combinat
True

# needs sage.combinat
g = DiGraph(digraphs.DeBruijn(4, 3), data_structure='static_sparse')
gi = DiGraph(g, data_structure='static_sparse')
gi.edges(sort=True)[0]
sorted(gi.edges_incident('111'))
set(g.edges(sort=False)) == set(gi.edges(sort=False))                 # needs sage.combinat
sage: g = graphs.PetersenGraph()
sage: gi = Graph(g, data_structure='static_sparse')
sage: g == gi
True
sage: set(g.edges(sort=False)) == set(gi.edges(sort=False))
True

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> gi = Graph(g, data_structure='static_sparse')
>>> g == gi
True
>>> set(g.edges(sort=False)) == set(gi.edges(sort=False))
True

g = graphs.PetersenGraph()
gi = Graph(g, data_structure='static_sparse')
g == gi
set(g.edges(sort=False)) == set(gi.edges(sort=False))
>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> gi = Graph(g, data_structure='static_sparse')
>>> g == gi
True
>>> set(g.edges(sort=False)) == set(gi.edges(sort=False))
True

g = graphs.PetersenGraph()
gi = Graph(g, data_structure='static_sparse')
g == gi
set(g.edges(sort=False)) == set(gi.edges(sort=False))
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(sort=False)
True
sage: gi.has_edge(0, 4)
True

>>> from sage.all import *
>>> gi = Graph({ Integer(0): {Integer(1): Integer(1)}, Integer(1): {Integer(2): Integer(1)}, Integer(2): {Integer(3): Integer(1)}, Integer(3): {Integer(4): Integer(2)}, Integer(4): {Integer(0): Integer(2)}}, data_structure='static_sparse')
>>> (Integer(0), Integer(4), Integer(2)) in gi.edges(sort=False)
True
>>> gi.has_edge(Integer(0), Integer(4))
True

gi = Graph({ 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2}}, data_structure='static_sparse')
(0, 4, 2) in gi.edges(sort=False)
gi.has_edge(0, 4)
>>> from sage.all import *
>>> gi = Graph({ Integer(0): {Integer(1): Integer(1)}, Integer(1): {Integer(2): Integer(1)}, Integer(2): {Integer(3): Integer(1)}, Integer(3): {Integer(4): Integer(2)}, Integer(4): {Integer(0): Integer(2)}}, data_structure='static_sparse')
>>> (Integer(0), Integer(4), Integer(2)) in gi.edges(sort=False)
True
>>> gi.has_edge(Integer(0), Integer(4))
True

gi = Graph({ 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2}}, data_structure='static_sparse')
(0, 4, 2) in gi.edges(sort=False)
gi.has_edge(0, 4)
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

>>> from sage.all import *
>>> G = Graph({Integer(1):{Integer(2):Integer(28), Integer(6):Integer(10)}, Integer(2):{Integer(3):Integer(16), Integer(7):Integer(14)}, Integer(3):{Integer(4):Integer(12)}, Integer(4):{Integer(5):Integer(22), Integer(7):Integer(18)}, Integer(5):{Integer(6):Integer(25), Integer(7):Integer(24)}})
>>> GI = Graph({Integer(1):{Integer(2):Integer(28), Integer(6):Integer(10)}, Integer(2):{Integer(3):Integer(16), Integer(7):Integer(14)}, Integer(3):{Integer(4):Integer(12)}, Integer(4):{Integer(5):Integer(22), Integer(7):Integer(18)}, Integer(5):{Integer(6):Integer(25), Integer(7):Integer(24)}}, data_structure='static_sparse')
>>> G == GI
True

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}})
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')
G == GI
>>> from sage.all import *
>>> G = Graph({Integer(1):{Integer(2):Integer(28), Integer(6):Integer(10)}, Integer(2):{Integer(3):Integer(16), Integer(7):Integer(14)}, Integer(3):{Integer(4):Integer(12)}, Integer(4):{Integer(5):Integer(22), Integer(7):Integer(18)}, Integer(5):{Integer(6):Integer(25), Integer(7):Integer(24)}})
>>> GI = Graph({Integer(1):{Integer(2):Integer(28), Integer(6):Integer(10)}, Integer(2):{Integer(3):Integer(16), Integer(7):Integer(14)}, Integer(3):{Integer(4):Integer(12)}, Integer(4):{Integer(5):Integer(22), Integer(7):Integer(18)}, Integer(5):{Integer(6):Integer(25), Integer(7):Integer(24)}}, data_structure='static_sparse')
>>> G == GI
True

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}})
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')
G == GI
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(sort=False))
True

>>> from sage.all import *
>>> G = graphs.OddGraph(Integer(4))
>>> d = G.diameter()
>>> H = G.distance_graph(list(range(d + Integer(1))))
>>> HI = Graph(H, data_structure='static_sparse')
>>> HI.size() == len(HI.edges(sort=False))
True

G = graphs.OddGraph(4)
d = G.diameter()
H = G.distance_graph(list(range(d + 1)))
HI = Graph(H, data_structure='static_sparse')
HI.size() == len(HI.edges(sort=False))
>>> from sage.all import *
>>> G = graphs.OddGraph(Integer(4))
>>> d = G.diameter()
>>> H = G.distance_graph(list(range(d + Integer(1))))
>>> HI = Graph(H, data_structure='static_sparse')
>>> HI.size() == len(HI.edges(sort=False))
True

G = graphs.OddGraph(4)
d = G.diameter()
H = G.distance_graph(list(range(d + 1)))
HI = Graph(H, data_structure='static_sparse')
HI.size() == len(HI.edges(sort=False))
sage: g = Graph({1: {1: [1, 2, 3]}}, data_structure='static_sparse')
sage: g.size()
3
sage: g.order()
1
sage: g.vertices(sort=False)
[1]
sage: g.edges(sort=True)
[(1, 1, 1), (1, 1, 2), (1, 1, 3)]

>>> from sage.all import *
>>> g = Graph({Integer(1): {Integer(1): [Integer(1), Integer(2), Integer(3)]}}, data_structure='static_sparse')
>>> g.size()
3
>>> g.order()
1
>>> g.vertices(sort=False)
[1]
>>> g.edges(sort=True)
[(1, 1, 1), (1, 1, 2), (1, 1, 3)]

g = Graph({1: {1: [1, 2, 3]}}, data_structure='static_sparse')
g.size()
g.order()
g.vertices(sort=False)
g.edges(sort=True)
>>> from sage.all import *
>>> g = Graph({Integer(1): {Integer(1): [Integer(1), Integer(2), Integer(3)]}}, data_structure='static_sparse')
>>> g.size()
3
>>> g.order()
1
>>> g.vertices(sort=False)
[1]
>>> g.edges(sort=True)
[(1, 1, 1), (1, 1, 2), (1, 1, 3)]

g = Graph({1: {1: [1, 2, 3]}}, data_structure='static_sparse')
g.size()
g.order()
g.vertices(sort=False)
g.edges(sort=True)

Issue #15810 is fixed:

sage: DiGraph({1: {2: ['a', 'b'], 3: ['c']}, 2: {3: ['d']}}, immutable=True).is_directed_acyclic()
True

>>> from sage.all import *
>>> DiGraph({Integer(1): {Integer(2): ['a', 'b'], Integer(3): ['c']}, Integer(2): {Integer(3): ['d']}}, immutable=True).is_directed_acyclic()
True

DiGraph({1: {2: ['a', 'b'], 3: ['c']}, 2: {3: ['d']}}, immutable=True).is_directed_acyclic()
add_edge(u, v, l, directed)[source]

Set edge label. No way.

add_edges(edges, directed)[source]

Set edge label. No way.

add_vertex(v)[source]

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: graph is immutable; please change a copy instead (use function copy())
sage: g.add_vertices([1,2,3])
Traceback (most recent call last):
...
ValueError: graph is immutable; please change a copy instead (use function copy())

>>> from sage.all import *
>>> g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
>>> g.add_vertex(Integer(1))
Traceback (most recent call last):
...
ValueError: graph is immutable; please change a copy instead (use function copy())
>>> g.add_vertices([Integer(1),Integer(2),Integer(3)])
Traceback (most recent call last):
...
ValueError: graph is immutable; please change a copy instead (use function copy())

g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
g.add_vertex(1)
g.add_vertices([1,2,3])
add_vertices(vertices)[source]

Set edge label. No way.

allows_loops(value=None)[source]

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 if value is not equal to None.

degree(v, directed)[source]

Return the degree of a vertex.

INPUT:

  • v – a vertex

  • directed – boolean; whether to take into account the orientation of this graph in counting the degree of v

EXAMPLES:

sage: g = Graph(graphs.PetersenGraph(), data_structure='static_sparse')
sage: g.degree(0)
3

>>> from sage.all import *
>>> g = Graph(graphs.PetersenGraph(), data_structure='static_sparse')
>>> g.degree(Integer(0))
3

g = Graph(graphs.PetersenGraph(), data_structure='static_sparse')
g.degree(0)

Issue #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

>>> from sage.all import *
>>> Graph({Integer(0): [Integer(0)]}, immutable=True).degree(Integer(0))
2
>>> Graph({Integer(0): [Integer(0)], Integer(1): [Integer(0), Integer(1), Integer(1), Integer(1)]}, immutable=True).degree(Integer(1))
7

Graph({0: [0]}, immutable=True).degree(0)
Graph({0: [0], 1: [0, 1, 1, 1]}, immutable=True).degree(1)
del_edge(u, v, l, directed)[source]

Set edge label. No way.

del_vertex(v)[source]

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: graph is immutable; please change a copy instead (use function copy())
sage: g.delete_vertices([1,2,3])
Traceback (most recent call last):
...
ValueError: graph is immutable; please change a copy instead (use function copy())

>>> from sage.all import *
>>> g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
>>> g.delete_vertex(Integer(1))
Traceback (most recent call last):
...
ValueError: graph is immutable; please change a copy instead (use function copy())
>>> g.delete_vertices([Integer(1),Integer(2),Integer(3)])
Traceback (most recent call last):
...
ValueError: graph is immutable; please change a copy instead (use function copy())

g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
g.delete_vertex(1)
g.delete_vertices([1,2,3])
get_edge_label(u, v)[source]

Return the edge label for (u, v).

INPUT:

  • u, v – two vertices

has_edge(u, v, l)[source]

Return whether this graph has edge (u, v) with label l.

If l is None, return whether this graph has an edge (u, v) with any label.

INPUT:

  • u, v – two vertices

  • l – a label

has_vertex(v)[source]

Test if the vertex belongs to the graph.

INPUT:

  • v – a vertex (or not?)

in_degree(v)[source]

Return the in-degree of a vertex.

INPUT:

  • v – a vertex

EXAMPLES:

sage: g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
sage: g.in_degree(0)
3

>>> from sage.all import *
>>> g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
>>> g.in_degree(Integer(0))
3

g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
g.in_degree(0)
iterator_edges(vertices, labels)[source]

Iterate over the graph’s edges.

INPUT:

  • vertices – list; only returns the edges incident to at least one vertex of vertices

  • labels – boolean; whether to return edge labels too

iterator_in_edges(vertices, labels)[source]

Iterate over the incoming edges incident to a sequence of vertices.

INPUT:

  • vertices – list of vertices

  • labels – whether to return labels too

iterator_in_nbrs(v)[source]

Iterate over the in-neighbors 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]

>>> from sage.all import *
>>> g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
>>> g.neighbors_in(Integer(0))
[1, 4, 5]

g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
g.neighbors_in(0)
iterator_nbrs(v)[source]

Iterate 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]

>>> from sage.all import *
>>> g = Graph(graphs.PetersenGraph(), data_structure='static_sparse')
>>> g.neighbors(Integer(0))
[1, 4, 5]

g = Graph(graphs.PetersenGraph(), data_structure='static_sparse')
g.neighbors(0)
iterator_out_edges(vertices, labels)[source]

Iterate over the outbound edges incident to a sequence of vertices.

INPUT:

  • vertices – list of vertices

  • labels – whether to return labels too

iterator_out_nbrs(v)[source]

Iterate over the out-neighbors 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]

>>> from sage.all import *
>>> g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
>>> g.neighbors_out(Integer(0))
[1, 4, 5]

g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
g.neighbors_out(0)
iterator_unsorted_edges(vertices, labels)[source]

Iterate over the graph’s edges.

INPUT:

  • vertices – list; only returns the edges incident to at least one vertex of vertices

  • labels – boolean; whether to return edge labels too

iterator_verts(vertices)[source]

Iterate over the vertices.

INPUT:

  • vertices – list of objects; the method will only return the elements of the graph which are contained in vertices. It’s not very efficient. If vertices is equal to None, all the vertices are returned.

multiple_edges(value=None)[source]

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 if value is not equal to None.

num_edges(directed)[source]

Return the number of edges.

INPUT:

  • directed – boolean; whether to consider the graph as directed or not

num_verts()[source]

Return the number of vertices.

out_degree(v)[source]

Return the out-degree of a vertex.

INPUT:

  • v – a vertex

EXAMPLES:

sage: g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
sage: g.out_degree(0)
3

>>> from sage.all import *
>>> g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
>>> g.out_degree(Integer(0))
3

g = DiGraph(graphs.PetersenGraph(), data_structure='static_sparse')
g.out_degree(0)
relabel(perm, directed)[source]

Relabel the graphs’ vertices. No way.

set_edge_label(u, v, l, directed)[source]

Set edge label. No way.

class sage.graphs.base.static_sparse_backend.StaticSparseCGraph[source]

Bases: CGraph

CGraph class based on the sparse graph data structure static sparse graphs.

add_vertex(k)[source]

Add a vertex to the graph. No way.

del_vertex(k)[source]

Remove a vertex from the graph. No way.

has_arc(u, v)[source]

Test if \(uv\) is an edge of the graph

INPUT:

  • u, v – integers

has_vertex(v)[source]

Test if a vertex belongs to the graph

INPUT:

  • n – integer

in_degree(u)[source]

Return the in-degree of a vertex

INPUT:

  • u – a vertex

in_neighbors(u)[source]

Return the in-neighbors of a vertex.

INPUT:

  • u – a vertex

out_degree(u)[source]

Return the out-degree of a vertex

INPUT:

  • u – a vertex

out_neighbors(u)[source]

List the out-neighbors of a vertex.

INPUT:

  • u – a vertex

verts()[source]

Return the list of vertices.