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.