Fast dense graphs#

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

Usage Introduction#

sage: from sage.graphs.base.dense_graph import DenseGraph

>>> from sage.all import *
>>> from sage.graphs.base.dense_graph import DenseGraph

Dense graphs are initialized as follows:

sage: D = DenseGraph(nverts=10, extra_vertices=10)

>>> from sage.all import *
>>> D = DenseGraph(nverts=Integer(10), extra_vertices=Integer(10))

This example initializes a dense 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: D.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: D.add_vertex(9)
9
sage: D.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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

But 10 is not, until we add it:

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

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

You can begin working right away as follows:

sage: D.add_arc(0, 1)
sage: D.add_arc(1, 2)
sage: D.add_arc(1, 0)
sage: D.has_arc(7, 3)
False
sage: D.has_arc(0, 1)
True
sage: D.in_neighbors(1)
[0]
sage: D.out_neighbors(1)
[0, 2]
sage: D.del_all_arcs(0, 1)
sage: D.has_arc(0, 1)
False
sage: D.has_arc(1, 2)
True
sage: D.del_vertex(7)
sage: D.has_arc(7, 3)
False

>>> from sage.all import *
>>> D.add_arc(Integer(0), Integer(1))
>>> D.add_arc(Integer(1), Integer(2))
>>> D.add_arc(Integer(1), Integer(0))
>>> D.has_arc(Integer(7), Integer(3))
False
>>> D.has_arc(Integer(0), Integer(1))
True
>>> D.in_neighbors(Integer(1))
[0]
>>> D.out_neighbors(Integer(1))
[0, 2]
>>> D.del_all_arcs(Integer(0), Integer(1))
>>> D.has_arc(Integer(0), Integer(1))
False
>>> D.has_arc(Integer(1), Integer(2))
True
>>> D.del_vertex(Integer(7))
>>> D.has_arc(Integer(7), Integer(3))
False

Dense graphs do not support multiple or labeled edges.

sage: T = DenseGraph(nverts=3, extra_vertices=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 = DenseGraph(nverts=Integer(3), extra_vertices=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

sage: for _ in range(10): D.add_arc(5, 4)
sage: D.has_arc(5,4 )
True

>>> from sage.all import *
>>> for _ in range(Integer(10)): D.add_arc(Integer(5), Integer(4))
>>> D.has_arc(Integer(5),Integer(4) )
True

Dense 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

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 DenseGraph 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 binary_matrix_t edges

Note

As the edges are stored as the adjacency matrix of the graph, enumerating the edges of the graph has complexity \(O(n^2)\) and enumerating the neighbors of a vertex has complexity \(O(n)\) (where \(n\) in the size of the bitset active_vertices). So, the class DenseGraph should be used for graphs such that the number of edges is close to the square of the number of vertices.

class sage.graphs.base.dense_graph.DenseGraph[source]#

Bases: CGraph

Compiled dense graphs.

sage: from sage.graphs.base.dense_graph import DenseGraph

>>> from sage.all import *
>>> from sage.graphs.base.dense_graph import DenseGraph

Dense graphs are initialized as follows:

sage: D = DenseGraph(nverts=10, extra_vertices=10)

>>> from sage.all import *
>>> D = DenseGraph(nverts=Integer(10), extra_vertices=Integer(10))

INPUT:

  • nverts – non-negative integer; the number of vertices

  • extra_vertices – non-negative integer (default: 10); how many extra vertices to allocate

  • verts – list (default: None); optional list of vertices to add

  • arcs – list (default: None); optional list of arcs to add

  • directed – boolean (default: None); whether the graph is directed

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.

complement()[source]#

Replace the graph with its complement

Note

Assumes that the graph has no loop.

EXAMPLES:

sage: from sage.graphs.base.dense_graph import DenseGraph
sage: G = DenseGraph(5)
sage: G.add_arc(0, 1)
sage: G.has_arc(0, 1)
True
sage: G.complement()
sage: G.has_arc(0, 1)
False

>>> from sage.all import *
>>> from sage.graphs.base.dense_graph import DenseGraph
>>> G = DenseGraph(Integer(5))
>>> G.add_arc(Integer(0), Integer(1))
>>> G.has_arc(Integer(0), Integer(1))
True
>>> G.complement()
>>> G.has_arc(Integer(0), Integer(1))
False
realloc(total_verts)[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.dense_graph import DenseGraph
sage: D = DenseGraph(nverts=4, extra_vertices=4)
sage: D.current_allocation()
8
sage: D.add_vertex(6)
6
sage: D.current_allocation()
8
sage: D.add_vertex(10)
10
sage: D.current_allocation()
16
sage: D.add_vertex(40)
Traceback (most recent call last):
...
RuntimeError: requested vertex is past twice the allocated range: use realloc
sage: D.realloc(50)
sage: D.add_vertex(40)
40
sage: D.current_allocation()
50
sage: D.realloc(30)
-1
sage: D.current_allocation()
50
sage: D.del_vertex(40)
sage: D.realloc(30)
sage: D.current_allocation()
30

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

Bases: CGraphBackend

Backend for Sage graphs using DenseGraphs.

sage: from sage.graphs.base.dense_graph import DenseGraphBackend

>>> from sage.all import *
>>> from sage.graphs.base.dense_graph import DenseGraphBackend

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

sage: G = Graph(30, sparse=False)
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=False)
>>> 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 DenseGraphs themselves. This is because DenseGraphs (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.dense_graph import DenseGraph
sage: DG = DenseGraph(30)
sage: DG.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.dense_graph import DenseGraph
>>> DG = DenseGraph(Integer(30))
>>> DG.add_vertex((Integer(0), Integer(1), Integer(2)))
Traceback (most recent call last):
...
TypeError: an integer is required
add_edges(edges, directed, remove_loops=False)[source]#

Add edges from a list.

INPUT:

  • edges – an iterable of edges to be added; each edge can either be

    of the form (u, v) or (u, v, l)

  • directed – if False, adds (v, u) as well as (u, v)

  • remove_loops – if True, remove loops

EXAMPLES:

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

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

Return the edge label for (u, v).

Always None, since dense graphs do not support edge labels.

INPUT:

  • u, v – the vertices of the edge

EXAMPLES:

sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(9)
sage: D.add_edges([(0, 1), (2, 3, 7), (4, 5), (5, 6)], False)
sage: list(D.iterator_edges(range(9), True))
[(0, 1, None),
 (2, 3, None),
 (4, 5, None),
 (5, 6, None)]
sage: D.del_edge(0, 1, None, True)
sage: list(D.iterator_out_edges(range(9), True))
[(1, 0, None),
 (2, 3, None),
 (3, 2, None),
 (4, 5, None),
 (5, 4, None),
 (5, 6, None),
 (6, 5, None)]
sage: D.get_edge_label(2, 3)
sage: D.get_edge_label(2, 4)
Traceback (most recent call last):
...
LookupError: (2, 4) is not an edge of the graph

>>> from sage.all import *
>>> D = sage.graphs.base.dense_graph.DenseGraphBackend(Integer(9))
>>> D.add_edges([(Integer(0), Integer(1)), (Integer(2), Integer(3), Integer(7)), (Integer(4), Integer(5)), (Integer(5), Integer(6))], False)
>>> list(D.iterator_edges(range(Integer(9)), True))
[(0, 1, None),
 (2, 3, None),
 (4, 5, None),
 (5, 6, None)]
>>> D.del_edge(Integer(0), Integer(1), None, True)
>>> list(D.iterator_out_edges(range(Integer(9)), True))
[(1, 0, None),
 (2, 3, None),
 (3, 2, None),
 (4, 5, None),
 (5, 4, None),
 (5, 6, None),
 (6, 5, None)]
>>> D.get_edge_label(Integer(2), Integer(3))
>>> D.get_edge_label(Integer(2), Integer(4))
Traceback (most recent call last):
...
LookupError: (2, 4) is not an edge of the graph
has_edge(u, v, l)[source]#

Check whether this graph has edge (u, v).

Note

The input l is for consistency with other backends.

INPUT:

  • u, v – the vertices of the edge

  • l – the edge label (ignored)

EXAMPLES:

sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(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.dense_graph.DenseGraphBackend(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: import sage.graphs.base.dense_graph
sage: G = sage.graphs.base.dense_graph.DenseGraphBackend(9)
sage: G.multiple_edges(True)
Traceback (most recent call last):
...
NotImplementedError: dense graphs do not support multiple edges
sage: G.multiple_edges(None)
False

>>> from sage.all import *
>>> import sage.graphs.base.dense_graph
>>> G = sage.graphs.base.dense_graph.DenseGraphBackend(Integer(9))
>>> G.multiple_edges(True)
Traceback (most recent call last):
...
NotImplementedError: dense graphs do not support multiple edges
>>> G.multiple_edges(None)
False
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: import sage.graphs.base.dense_graph
sage: G = sage.graphs.base.dense_graph.DenseGraphBackend(9)
sage: G.set_edge_label(1, 2, 'a', True)
Traceback (most recent call last):
...
NotImplementedError: dense graphs do not support edge labels

>>> from sage.all import *
>>> import sage.graphs.base.dense_graph
>>> G = sage.graphs.base.dense_graph.DenseGraphBackend(Integer(9))
>>> G.set_edge_label(Integer(1), Integer(2), 'a', True)
Traceback (most recent call last):
...
NotImplementedError: dense graphs do not support edge labels