# Overview of (di)graph data structures#

This module contains no code, and describes Sage’s data structures for graphs
and digraphs. They can be used directly at Cython/C level, or through the
`Graph`

and `DiGraph`

classes (except one)

## Data structures#

Four data structures are natively available for (di)graphs in Sage:

`sparse_graph`

(default) – for sparse (di)graphs, with a \(\log(n)\) edge test, and easy enumeration of neighbors. It is the most general-purpose data structure, though it can have a high memory cost in practice.Supports: Addition/removal of edges/vertices, multiple edges, edge labels and loops.

`dense_graph`

– for dense (di)graphs, with a \(O(1)\) edge test, and slow enumeration of neighbors.Supports: addition/removal of edges/vertices, and loops.

Does not support: multiple edges and edge labels.

`static_sparse_graph`

– for sparse (di)graphs and very intensive computations (at C-level). It is faster than`sparse_graph`

in practice and*much*lighter in memory.Supports: multiple edges, edge labels and loops

Does not support: addition/removal of edges/vertices.

`static_dense_graph`

– for dense (di)graphs and very intensive computations (at C-level). It is mostly a wrapper over bitsets.Supports: addition/removal of edges/vertices, and loops.

Does not support: multiple edges and edge labels.

For more information, see the data structures’ respective pages.

## The backends#

The `Graph`

and `DiGraph`

objects delegate the storage of vertices
and edges to other objects: the `graph backends`

:

```
sage: Graph()._backend
<sage.graphs.base.sparse_graph.SparseGraphBackend object at ...>
```

```
>>> from sage.all import *
>>> Graph()._backend
<sage.graphs.base.sparse_graph.SparseGraphBackend object at ...>
```

A (di)graph backend is a simpler (di)graph class having only the most elementary methods (e.g.: add/remove vertices/edges). Its vertices can be arbitrary hashable objects.

The only backend available in Sage is
`CGraphBackend`

.

## CGraph and CGraphBackend#

`CGraphBackend`

is the backend of all native
data structures that can be used by `Graph`

and `DiGraph`

. It is
extended by:

While a `CGraphBackend`

deals with arbitrary
(hashable) vertices, it contains a `._cg`

attribute of type
`CGraph`

which only deals with integer
vertices.

The `CGraph`

data structures available in Sage
are:

See the `c_graph`

module for more information.