# 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]
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.has_arc(7, 3)
False
sage: D.has_arc(0, 1)
True
sage: D.in_neighbors(1)

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.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.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
6
sage: D.current_allocation()
8
10
sage: D.current_allocation()
16
Traceback (most recent call last):
...
RuntimeError: requested vertex is past twice the allocated range: use realloc
sage: D.realloc(50)
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)
Traceback (most recent call last):
...
TypeError: an integer is required
```

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