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)
This module implements two classes
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
Returns whether the graph allows loops
INPUT:
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
Returns the degree of a vertex
INPUT:
EXAMPLE:
sage: g = Graph(graphs.PetersenGraph(), data_structure="static_sparse")
sage: g.degree(0)
3
Returns the edge label for (u,v).
INPUT:
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
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:
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
Tests if the vertex belongs to the graph
INPUT:
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
Returns the in-degree of a vertex
INPUT:
EXAMPLE:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse")
sage: g.in_degree(0)
3
Returns an iterator over the graph’s edges.
INPUT:
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)]
sage: Graph(immutable=True).edges()
[]
Iterate over the incoming edges incident to a sequence of vertices.
INPUT:
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)]
Returns the out-neighbors of a vertex
INPUT:
EXAMPLE:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse")
sage: g.neighbors_in(0)
[1, 4, 5]
Returns the neighbors of a vertex
INPUT:
EXAMPLE:
sage: g = Graph(graphs.PetersenGraph(), data_structure="static_sparse")
sage: g.neighbors(0)
[1, 4, 5]
Iterate over the outbound edges incident to a sequence of vertices.
INPUT:
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)]
Returns the out-neighbors of a vertex
INPUT:
EXAMPLE:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse")
sage: g.neighbors_out(0)
[1, 4, 5]
Returns an iterator over the vertices
INPUT:
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]
Returns whether the graph allows multiple edges
INPUT:
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
Returns the number of edges
INPUT:
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.
sage: g=digraphs.RandomDirectedGNP(10,.3)
sage: gi=DiGraph(g,data_structure="static_sparse")
sage: gi.size() == len(gi.edges())
True
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
Returns the out-degree of a vertex
INPUT:
EXAMPLE:
sage: g = DiGraph(graphs.PetersenGraph(), data_structure="static_sparse")
sage: g.out_degree(0)
3
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
Bases: sage.graphs.base.c_graph.CGraph
CGraph class based on the sparse graph data structure static sparse graphs.
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
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
Tests if uv is an edge of the graph
INPUT:
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
Tests if a vertex belongs to the graph
INPUT:
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
Returns the in-degree of a vertex
INPUT:
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph
sage: g = StaticSparseCGraph(graphs.PetersenGraph())
sage: g.in_degree(0)
3
Returns the in-neighbors of a vertex
INPUT:
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph
sage: g = StaticSparseCGraph(graphs.PetersenGraph())
sage: g.in_neighbors(0)
[1, 4, 5]
Returns the out-degree of a vertex
INPUT:
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph
sage: g = StaticSparseCGraph(graphs.PetersenGraph())
sage: g.out_degree(0)
3
List the out-neighbors of a vertex
INPUT:
TEST:
sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph
sage: g = StaticSparseCGraph(graphs.PetersenGraph())
sage: g.out_neighbors(0)
[1, 4, 5]
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]