Static sparse graph backend

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)

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(G, loops=False, multiedges=False)

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

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 vertex
  • directed – boolean; whether to take into account the orientation of this graph in counting the degree of v.

EXAMPLE:

sage: g = Graph(graphs.PetersenGraph(), data_structure="static_sparse")
sage: g.degree(0)
3
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 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

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 of vertices.
  • 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)]

trac ticket #15665:

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 vertices
  • labels – 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 vertices
  • labels – 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 in vertices. It’s not very efficient. If vertices is equal to None, 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 if value is not equal to None.

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.

trac ticket #15491:

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 structure static 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
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]
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
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]
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]

Table Of Contents

Previous topic

Static Sparse Graphs

Next topic

Implements various backends for Sage graphs.

This Page