Fast sparse graphs#

For an overview of graph data structures in sage, see overview.

Usage Introduction#

sage: from sage.graphs.base.sparse_graph import SparseGraph

>>> from sage.all import *
>>> from sage.graphs.base.sparse_graph import SparseGraph

Sparse graphs are initialized as follows:

sage: S = SparseGraph(nverts = 10, expected_degree = 3, extra_vertices = 10)

>>> from sage.all import *
>>> S = SparseGraph(nverts = Integer(10), expected_degree = Integer(3), extra_vertices = Integer(10))

This example initializes a sparse graph with room for twenty vertices, the first ten of which are in the graph. In general, the first nverts are “active.” For example, see that 9 is already in the graph:

sage: S.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: S.add_vertex(9)
9
sage: S.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> from sage.all import *
>>> S.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> S.add_vertex(Integer(9))
9
>>> S.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

But 10 is not, until we add it:

sage: S.add_vertex(10)
10
sage: S.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

>>> from sage.all import *
>>> S.add_vertex(Integer(10))
10
>>> S.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

You can begin working with unlabeled arcs right away as follows:

sage: S.add_arc(0,1)
sage: S.add_arc(1,2)
sage: S.add_arc(1,0)
sage: S.has_arc(7,3)
False
sage: S.has_arc(0,1)
True
sage: S.in_neighbors(1)
[0]
sage: S.out_neighbors(1)
[0, 2]
sage: S.del_all_arcs(0,1)
sage: S.all_arcs(0,1)
[]
sage: S.all_arcs(1,2)
[0]
sage: S.del_vertex(7)
sage: S.all_arcs(7,3)
Traceback (most recent call last):
...
LookupError: vertex (7) is not a vertex of the graph

>>> from sage.all import *
>>> S.add_arc(Integer(0),Integer(1))
>>> S.add_arc(Integer(1),Integer(2))
>>> S.add_arc(Integer(1),Integer(0))
>>> S.has_arc(Integer(7),Integer(3))
False
>>> S.has_arc(Integer(0),Integer(1))
True
>>> S.in_neighbors(Integer(1))
[0]
>>> S.out_neighbors(Integer(1))
[0, 2]
>>> S.del_all_arcs(Integer(0),Integer(1))
>>> S.all_arcs(Integer(0),Integer(1))
[]
>>> S.all_arcs(Integer(1),Integer(2))
[0]
>>> S.del_vertex(Integer(7))
>>> S.all_arcs(Integer(7),Integer(3))
Traceback (most recent call last):
...
LookupError: vertex (7) is not a vertex of the graph

Sparse graphs support multiple edges and labeled edges, but requires that the labels be positive integers (the case label = 0 is treated as no label).

sage: S.add_arc_label(0,1,-1)
Traceback (most recent call last):
...
ValueError: Label (-1) must be a nonnegative integer.
sage: S.add_arc(0,1)
sage: S.arc_label(0,1)
0

>>> from sage.all import *
>>> S.add_arc_label(Integer(0),Integer(1),-Integer(1))
Traceback (most recent call last):
...
ValueError: Label (-1) must be a nonnegative integer.
>>> S.add_arc(Integer(0),Integer(1))
>>> S.arc_label(Integer(0),Integer(1))
0

Note that arc_label only returns the first edge label found in the specified place, and this can be in any order (if you want all arc labels, use all_arcs):

sage: S.add_arc_label(0,1,1)
sage: S.arc_label(0,1)
1
sage: S.all_arcs(0,1)
[0, 1]

>>> from sage.all import *
>>> S.add_arc_label(Integer(0),Integer(1),Integer(1))
>>> S.arc_label(Integer(0),Integer(1))
1
>>> S.all_arcs(Integer(0),Integer(1))
[0, 1]

Zero specifies only that there is no labeled arc:

sage: S.arc_label(1,2)
0

>>> from sage.all import *
>>> S.arc_label(Integer(1),Integer(2))
0

So do not be fooled:

sage: S.all_arcs(1,2)
[0]
sage: S.add_arc(1,2)
sage: S.arc_label(1,2)
0

>>> from sage.all import *
>>> S.all_arcs(Integer(1),Integer(2))
[0]
>>> S.add_arc(Integer(1),Integer(2))
>>> S.arc_label(Integer(1),Integer(2))
0

Instead, if you work with unlabeled edges, be sure to use the right functions:

sage: T = SparseGraph(nverts = 3, expected_degree = 2)
sage: T.add_arc(0,1)
sage: T.add_arc(1,2)
sage: T.add_arc(2,0)
sage: T.has_arc(0,1)
True

>>> from sage.all import *
>>> T = SparseGraph(nverts = Integer(3), expected_degree = Integer(2))
>>> T.add_arc(Integer(0),Integer(1))
>>> T.add_arc(Integer(1),Integer(2))
>>> T.add_arc(Integer(2),Integer(0))
>>> T.has_arc(Integer(0),Integer(1))
True

Sparse graphs are by their nature directed. As of this writing, you need to do operations in pairs to treat the undirected case (or use a backend or a Sage graph):

sage: T.has_arc(1,0)
False

>>> from sage.all import *
>>> T.has_arc(Integer(1),Integer(0))
False

Multiple unlabeled edges are also possible:

sage: for _ in range(10): S.add_arc(5,4)
sage: S.all_arcs(5,4)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

>>> from sage.all import *
>>> for _ in range(Integer(10)): S.add_arc(Integer(5),Integer(4))
>>> S.all_arcs(Integer(5),Integer(4))
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

The curious developer is encouraged to check out the unsafe functions, which do not check input but which run in pure C.

Underlying Data Structure#

The class SparseGraph contains the following variables which are inherited from CGraph (for explanation, refer to the documentation there):

cdef int num_verts
cdef int num_arcs
cdef int *in_degrees
cdef int *out_degrees
cdef bitset_t active_vertices

It also contains the following variables:

cdef int hash_length
cdef int hash_mask
cdef SparseGraphBTNode **vertices
cdef SparseGraphBTNode **vertices_rev
cdef bint _directed

For each vertex u, a hash table of length hash_length is instantiated. An arc (u, v) is stored at u * hash_length + hash(v) of the array vertices, where hash should be thought of as an arbitrary but fixed hash function which takes values in 0 <= hash < hash_length. Each address may represent different arcs, say (u, v1) and (u, v2) where hash(v1) == hash(v2). Thus, a binary tree structure is used at this step to speed access to individual arcs, whose nodes (each of which represents a pair (u,v)) are instances of the following type:

cdef struct SparseGraphBTNode:
    int vertex
    int number
    SparseGraphLLNode *labels
    SparseGraphBTNode *left
    SparseGraphBTNode *right

Which range of the vertices array the root of the tree is in determines u, and vertex stores v. The integer number stores only the number of unlabeled arcs from u to v.

Currently, labels are stored in a simple linked list, whose nodes are instances of the following type:

cdef struct SparseGraphLLNode:
    int label
    int number
    SparseGraphLLNode *next

The int label must be a positive integer, since 0 indicates no label, and negative numbers indicate errors. The int number is the number of arcs with the given label.

TODO: Optimally, edge labels would also be represented by a binary tree, which would help performance in graphs with many overlapping edges. Also, a more efficient binary tree structure could be used, although in practice the trees involved will usually have very small order, unless the degree of vertices becomes significantly larger than the expected_degree given, because this is the size of each hash table. Indeed, the expected size of the binary trees is \(\frac{\text{actual degree}}{\text{expected degree}}\). Ryan Dingman, e.g., is working on a general-purpose Cython-based red black tree, which would be optimal for both of these uses.

class sage.graphs.base.sparse_graph.SparseGraph[source]#

Bases: CGraph

Compiled sparse graphs.

sage: from sage.graphs.base.sparse_graph import SparseGraph

>>> from sage.all import *
>>> from sage.graphs.base.sparse_graph import SparseGraph

Sparse graphs are initialized as follows:

sage: S = SparseGraph(nverts = 10, expected_degree = 3, extra_vertices = 10)

>>> from sage.all import *
>>> S = SparseGraph(nverts = Integer(10), expected_degree = Integer(3), extra_vertices = Integer(10))

INPUT:

  • nverts – non-negative integer, the number of vertices.

  • expected_degree – non-negative integer (default: 16), expected upper

    bound on degree of vertices.

  • extra_vertices – non-negative integer (default: 0), how many extra

    vertices to allocate.

  • verts – optional list of vertices to add

  • arcs – optional list of arcs to add

The first nverts are created as vertices of the graph, and the next extra_vertices can be freely added without reallocation. See top level documentation for more details. The input verts and arcs are mainly for use in pickling.

add_arc_label(u, v, l=0)[source]#

Add arc (u, v) to the graph with label l.

INPUT:

  • u, v – non-negative integers, must be in self

  • l – a positive integer label, or zero for no label

EXAMPLES:

sage: from sage.graphs.base.sparse_graph import SparseGraph
sage: G = SparseGraph(5)
sage: G.add_arc_label(0,1)
sage: G.add_arc_label(4,7)
Traceback (most recent call last):
...
LookupError: vertex (7) is not a vertex of the graph
sage: G.has_arc(1,0)
False
sage: G.has_arc(0,1)
True
sage: G.add_arc_label(1,2,2)
sage: G.arc_label(1,2)
2

>>> from sage.all import *
>>> from sage.graphs.base.sparse_graph import SparseGraph
>>> G = SparseGraph(Integer(5))
>>> G.add_arc_label(Integer(0),Integer(1))
>>> G.add_arc_label(Integer(4),Integer(7))
Traceback (most recent call last):
...
LookupError: vertex (7) is not a vertex of the graph
>>> G.has_arc(Integer(1),Integer(0))
False
>>> G.has_arc(Integer(0),Integer(1))
True
>>> G.add_arc_label(Integer(1),Integer(2),Integer(2))
>>> G.arc_label(Integer(1),Integer(2))
2
in_degree(v)[source]#

Returns the in-degree of v

INPUT:

  • v – integer

EXAMPLES:

sage: from sage.graphs.base.sparse_graph import SparseGraph
sage: G = SparseGraph(5)
sage: G.add_arc(0,1)
sage: G.add_arc(1,2)
sage: G.add_arc(1,3)
sage: G.in_degree(0)
0
sage: G.in_degree(1)
1

>>> from sage.all import *
>>> from sage.graphs.base.sparse_graph import SparseGraph
>>> G = SparseGraph(Integer(5))
>>> G.add_arc(Integer(0),Integer(1))
>>> G.add_arc(Integer(1),Integer(2))
>>> G.add_arc(Integer(1),Integer(3))
>>> G.in_degree(Integer(0))
0
>>> G.in_degree(Integer(1))
1
is_directed()[source]#

Return whether the graph is directed.

EXAMPLES:

sage: from sage.graphs.base.sparse_graph import SparseGraph
sage: G = SparseGraph(5)
sage: G.is_directed()
True
sage: G = SparseGraph(5, directed=False)
sage: G.is_directed()
False

>>> from sage.all import *
>>> from sage.graphs.base.sparse_graph import SparseGraph
>>> G = SparseGraph(Integer(5))
>>> G.is_directed()
True
>>> G = SparseGraph(Integer(5), directed=False)
>>> G.is_directed()
False
out_degree(u)[source]#

Returns the out-degree of v

INPUT:

  • u – integer

EXAMPLES:

sage: from sage.graphs.base.sparse_graph import SparseGraph
sage: G = SparseGraph(5)
sage: G.add_arc(0,1)
sage: G.add_arc(1,2)
sage: G.add_arc(1,3)
sage: G.out_degree(0)
1
sage: G.out_degree(1)
2

>>> from sage.all import *
>>> from sage.graphs.base.sparse_graph import SparseGraph
>>> G = SparseGraph(Integer(5))
>>> G.add_arc(Integer(0),Integer(1))
>>> G.add_arc(Integer(1),Integer(2))
>>> G.add_arc(Integer(1),Integer(3))
>>> G.out_degree(Integer(0))
1
>>> G.out_degree(Integer(1))
2
realloc(total)[source]#

Reallocate the number of vertices to use, without actually adding any.

INPUT:

  • total – integer, the total size to make the array

Returns -1 and fails if reallocation would destroy any active vertices.

EXAMPLES:

sage: from sage.graphs.base.sparse_graph import SparseGraph
sage: S = SparseGraph(nverts=4, extra_vertices=4)
sage: S.current_allocation()
8
sage: S.add_vertex(6)
6
sage: S.current_allocation()
8
sage: S.add_vertex(10)
10
sage: S.current_allocation()
16
sage: S.add_vertex(40)
Traceback (most recent call last):
...
RuntimeError: requested vertex is past twice the allocated range: use realloc
sage: S.realloc(50)
sage: S.add_vertex(40)
40
sage: S.current_allocation()
50
sage: S.realloc(30)
-1
sage: S.current_allocation()
50
sage: S.del_vertex(40)
sage: S.realloc(30)
sage: S.current_allocation()
30

>>> from sage.all import *
>>> from sage.graphs.base.sparse_graph import SparseGraph
>>> S = SparseGraph(nverts=Integer(4), extra_vertices=Integer(4))
>>> S.current_allocation()
8
>>> S.add_vertex(Integer(6))
6
>>> S.current_allocation()
8
>>> S.add_vertex(Integer(10))
10
>>> S.current_allocation()
16
>>> S.add_vertex(Integer(40))
Traceback (most recent call last):
...
RuntimeError: requested vertex is past twice the allocated range: use realloc
>>> S.realloc(Integer(50))
>>> S.add_vertex(Integer(40))
40
>>> S.current_allocation()
50
>>> S.realloc(Integer(30))
-1
>>> S.current_allocation()
50
>>> S.del_vertex(Integer(40))
>>> S.realloc(Integer(30))
>>> S.current_allocation()
30
class sage.graphs.base.sparse_graph.SparseGraphBackend[source]#

Bases: CGraphBackend

Backend for Sage graphs using SparseGraphs.

sage: from sage.graphs.base.sparse_graph import SparseGraphBackend

>>> from sage.all import *
>>> from sage.graphs.base.sparse_graph import SparseGraphBackend

This class is only intended for use by the Sage Graph and DiGraph class. If you are interested in using a SparseGraph, you probably want to do something like the following example, which creates a Sage Graph instance which wraps a SparseGraph object:

sage: G = Graph(30, sparse=True)
sage: G.add_edges([(0,1), (0,3), (4,5), (9, 23)])
sage: G.edges(sort=True, labels=False)
[(0, 1), (0, 3), (4, 5), (9, 23)]

>>> from sage.all import *
>>> G = Graph(Integer(30), sparse=True)
>>> G.add_edges([(Integer(0),Integer(1)), (Integer(0),Integer(3)), (Integer(4),Integer(5)), (Integer(9), Integer(23))])
>>> G.edges(sort=True, labels=False)
[(0, 1), (0, 3), (4, 5), (9, 23)]

Note that Sage graphs using the backend are more flexible than SparseGraphs themselves. This is because SparseGraphs (by design) do not deal with Python objects:

sage: G.add_vertex((0,1,2))
sage: sorted(list(G),
....:        key=lambda x: (isinstance(x, tuple), x))
[0,
...
 29,
 (0, 1, 2)]
sage: from sage.graphs.base.sparse_graph import SparseGraph
sage: SG = SparseGraph(30)
sage: SG.add_vertex((0,1,2))
Traceback (most recent call last):
...
TypeError: an integer is required

>>> from sage.all import *
>>> G.add_vertex((Integer(0),Integer(1),Integer(2)))
>>> sorted(list(G),
...        key=lambda x: (isinstance(x, tuple), x))
[0,
...
 29,
 (0, 1, 2)]
>>> from sage.graphs.base.sparse_graph import SparseGraph
>>> SG = SparseGraph(Integer(30))
>>> SG.add_vertex((Integer(0),Integer(1),Integer(2)))
Traceback (most recent call last):
...
TypeError: an integer is required
get_edge_label(u, v)[source]#

Return the edge label for (u, v).

INPUT:

  • u, v – the vertices of the edge

EXAMPLES:

sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(9)
sage: D.add_edges([(0,1,1), (2,3,2), (4,5,3), (5,6,2)], False)
sage: list(D.iterator_edges(range(9), True))
[(0, 1, 1), (2, 3, 2), (4, 5, 3), (5, 6, 2)]
sage: D.get_edge_label(3,2)
2

>>> from sage.all import *
>>> D = sage.graphs.base.sparse_graph.SparseGraphBackend(Integer(9))
>>> D.add_edges([(Integer(0),Integer(1),Integer(1)), (Integer(2),Integer(3),Integer(2)), (Integer(4),Integer(5),Integer(3)), (Integer(5),Integer(6),Integer(2))], False)
>>> list(D.iterator_edges(range(Integer(9)), True))
[(0, 1, 1), (2, 3, 2), (4, 5, 3), (5, 6, 2)]
>>> D.get_edge_label(Integer(3),Integer(2))
2
has_edge(u, v, l)[source]#

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 – the vertices of the edge

  • l – the edge label, or None

EXAMPLES:

sage: D = sage.graphs.base.sparse_graph.SparseGraphBackend(9)
sage: D.add_edges([(0,1), (2,3), (4,5), (5,6)], False)
sage: D.has_edge(0,1,None)
True

>>> from sage.all import *
>>> D = sage.graphs.base.sparse_graph.SparseGraphBackend(Integer(9))
>>> D.add_edges([(Integer(0),Integer(1)), (Integer(2),Integer(3)), (Integer(4),Integer(5)), (Integer(5),Integer(6))], False)
>>> D.has_edge(Integer(0),Integer(1),None)
True
multiple_edges(new)[source]#

Get/set whether or not self allows multiple edges.

INPUT:

  • new – boolean (to set) or None (to get)

EXAMPLES:

sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(9)
sage: G.multiple_edges(True)
sage: G.multiple_edges(None)
True
sage: G.multiple_edges(False)
sage: G.multiple_edges(None)
False
sage: G.add_edge(0,1,0,True)
sage: G.add_edge(0,1,0,True)
sage: list(G.iterator_out_edges(range(9), True))
[(0, 1, 0)]

>>> from sage.all import *
>>> G = sage.graphs.base.sparse_graph.SparseGraphBackend(Integer(9))
>>> G.multiple_edges(True)
>>> G.multiple_edges(None)
True
>>> G.multiple_edges(False)
>>> G.multiple_edges(None)
False
>>> G.add_edge(Integer(0),Integer(1),Integer(0),True)
>>> G.add_edge(Integer(0),Integer(1),Integer(0),True)
>>> list(G.iterator_out_edges(range(Integer(9)), True))
[(0, 1, 0)]
set_edge_label(u, v, l, directed)[source]#

Label the edge (u,v) by l.

INPUT:

  • u, v – the vertices of the edge

  • l – the edge label

  • directed – if False, also set (v,u) with label l

EXAMPLES:

sage: G = sage.graphs.base.sparse_graph.SparseGraphBackend(9)
sage: G.add_edge(1,2,None,True)
sage: G.set_edge_label(1,2,'a',True)
sage: list(G.iterator_out_edges(range(9), True))
[(1, 2, 'a')]

>>> from sage.all import *
>>> G = sage.graphs.base.sparse_graph.SparseGraphBackend(Integer(9))
>>> G.add_edge(Integer(1),Integer(2),None,True)
>>> G.set_edge_label(Integer(1),Integer(2),'a',True)
>>> list(G.iterator_out_edges(range(Integer(9)), True))
[(1, 2, 'a')]

Note that it fails silently if there is no edge there:

sage: G.set_edge_label(2,1,'b',True)
sage: list(G.iterator_out_edges(range(9), True))
[(1, 2, 'a')]

>>> from sage.all import *
>>> G.set_edge_label(Integer(2),Integer(1),'b',True)
>>> list(G.iterator_out_edges(range(Integer(9)), True))
[(1, 2, 'a')]