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

Dense graphs are initialized as follows:

sage: D = DenseGraph(nverts=10, extra_vertices=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]

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]

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

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
sage: for _ in range(10): D.add_arc(5, 4)
sage: D.has_arc(5,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

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
class sage.graphs.base.dense_graph.DenseGraph#

Bases: CGraph

Compiled dense graphs.

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

Dense graphs are initialized as follows:

sage: D = DenseGraph(nverts=10, extra_vertices=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()#

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
realloc(total_verts)#

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
class sage.graphs.base.dense_graph.DenseGraphBackend#

Bases: CGraphBackend

Backend for Sage graphs using DenseGraphs.

sage: 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)]

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
add_edges(edges, directed, remove_loops=False)#

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)]
get_edge_label(u, v)#

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
has_edge(u, v, l)#

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
multiple_edges(new)#

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
set_edge_label(u, v, l, directed)#

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