Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

r""" 

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 

:class:`Graph` and :class:`DiGraph` classes (except one) 

 

Data structures 

--------------- 

 

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

 

- :mod:`~sage.graphs.base.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. 

 

- :mod:`~sage.graphs.base.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. 

 

- :mod:`~sage.graphs.base.static_sparse_graph` -- for sparse (di)graphs and very 

intensive computations (at C-level). It is faster than 

:mod:`~sage.graphs.base.sparse_graph` in practice and *much* lighter in 

memory. 

 

- Supports: multiple edges, edge labels and loops 

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

 

- :mod:`~sage.graphs.base.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 :class:`Graph` and :class:`DiGraph` objects delegate the storage of vertices 

and edges to other objects: the :mod:`graph backends 

<sage.graphs.base.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 

:class:`~sage.graphs.base.c_graph.CGraphBackend`. 

 

CGraph and CGraphBackend 

------------------------ 

 

:class:`~sage.graphs.base.c_graph.CGraphBackend` is the backend of all native 

data structures that can be used by :class:`Graph` and :class:`DiGraph`. It is 

extended by: 

 

- :class:`~sage.graphs.base.dense_graph.DenseGraphBackend` 

- :class:`~sage.graphs.base.sparse_graph.SparseGraphBackend` 

- :class:`~sage.graphs.base.static_sparse_backend.StaticSparseBackend` 

 

While a :class:`~sage.graphs.base.c_graph.CGraphBackend` deals with arbitrary 

(hashable) vertices, it contains a ``._cg`` attribute of type 

:class:`~sage.graphs.base.c_graph.CGraph` which only deals with integer 

vertices. 

 

The :class:`~sage.graphs.base.c_graph.CGraph` data structures available in Sage 

are: 

 

- :class:`~sage.graphs.base.dense_graph.DenseGraph` 

- :class:`~sage.graphs.base.sparse_graph.SparseGraph` 

- :class:`~sage.graphs.base.static_sparse_backend.StaticSparseCGraph` 

 

See the :mod:`~sage.graphs.base.c_graph` module for more information. 

"""