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: 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 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_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 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)

Return an iterator 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
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 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)

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 vertices
  • labels – whether to return labels too
iterator_out_nbrs(v)

Return an iterator 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_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 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.

class sage.graphs.base.static_sparse_backend.StaticSparseCGraph

Bases: sage.graphs.base.c_graph.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