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

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


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.