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.