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#

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

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(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))
True

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

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

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(sort=False))
True

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

trac ticket #15810 is fixed:

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

Set edge label. No way.

add_edges(edges, directed)#

Set edge label. No way.

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: 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())
add_vertices(vertices)#

Set edge label. No way.

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

degree(v, directed)#

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

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_edge(u, v, l, directed)#

Set edge label. No way.

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: 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())
get_edge_label(u, v)#

Return the edge label for (u, v).

INPUT:

  • u,v – two vertices

has_edge(u, v, l)#

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

Test if the vertex belongs to the graph

INPUT:

  • v – a vertex (or not?)

in_degree(v)#

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
iterator_edges(vertices, labels)#

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

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

INPUT:

  • vertices – a list of vertices

  • labels – whether to return labels too

iterator_in_nbrs(v)#

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]
iterator_nbrs(v)#

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]
iterator_out_edges(vertices, labels)#

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

INPUT:

  • vertices – a list of vertices

  • labels – whether to return labels too

iterator_out_nbrs(v)#

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]
iterator_unsorted_edges(vertices, labels)#

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

Iterate over the vertices

INPUT:

  • vertices – a 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)#

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

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 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
relabel(perm, directed)#

Relabel the graphs’ vertices. No way.

set_edge_label(u, v, l, directed)#

Set edge label. No way.

class sage.graphs.base.static_sparse_backend.StaticSparseCGraph#

Bases: CGraph

CGraph class based on the sparse graph data structure static 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 in-degree of a vertex

INPUT:

  • u – a vertex

in_neighbors(u)#

Return the in-neighbors of a vertex

INPUT:

  • u – a vertex

out_degree(u)#

Return the out-degree of a vertex

INPUT:

  • u – a vertex

out_neighbors(u)#

List the out-neighbors of a vertex

INPUT:

  • u – a vertex

verts()#

Returns the list of vertices