Fast dense graphs

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

Usage Introduction

Sage

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

Python

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

Dense graphs are initialized as follows:

Sage

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

Python

>>> 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

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]

Python

>>> 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

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

Python

>>> 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

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

Python

>>> 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

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

Python

>>> 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

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

Python

>>> 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

sage: T.has_arc(1, 0)
False

Python

>>> 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

Bases: CGraph

Compiled dense graphs.

Sage

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

Python

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

Dense graphs are initialized as follows:

Sage

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

Python

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

INPUT:

• nverts – nonnegative integer; the number of vertices

• extra_vertices – nonnegative 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

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

Python

>>> 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)

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

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

Python

>>> 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

Bases: CGraphBackend

Backend for Sage graphs using DenseGraphs.

Sage

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

Python

>>> 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

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

Python

>>> 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

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

Python

>>> 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)

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

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

Python

>>> 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)

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

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

Python

>>> 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)

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

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

Python

>>> 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)

Get/set whether or not self allows multiple edges.

INPUT:

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

EXAMPLES:

Sage

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

Python

>>> 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)

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

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

Python

>>> 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