40 they all conform to the corresponding \ref graph_concepts "graph concept", |
40 they all conform to the corresponding \ref graph_concepts "graph concept", |
41 which defines the common part of the graph interfaces. |
41 which defines the common part of the graph interfaces. |
42 The \ref concepts::Digraph "Digraph concept" describes the common interface |
42 The \ref concepts::Digraph "Digraph concept" describes the common interface |
43 of directed graphs (without any sensible implementation), while |
43 of directed graphs (without any sensible implementation), while |
44 the \ref concepts::Graph "Graph concept" describes the undirected graphs. |
44 the \ref concepts::Graph "Graph concept" describes the undirected graphs. |
45 Any generic graph algorithm should only exploit the features of the |
45 A generic graph algorithm should only exploit the features of the |
46 corresponding graph concept. (It should compile with the |
46 corresponding graph concept so that it could be applied to any graph |
|
47 structure. (Such an algorithm should compile with the |
47 \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type, |
48 \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type, |
48 but it will not run properly, of course.) |
49 but it will not run properly, of course.) |
49 |
50 |
50 The graph %concepts define the member classes for the iterators and maps |
51 The graph %concepts define the member classes for the iterators and maps |
51 along with some useful basic functions for obtaining the identifiers of |
52 along with some useful basic functions for obtaining the identifiers of |
52 the items, the end nodes of the arcs (or edges) and their iterators, |
53 the items, the end nodes of the arcs (or edges) and their iterators, |
53 etc. |
54 etc. |
54 An actual graph implementation may have various additional functionalities |
55 An actual graph implementation may have various additional functionalities |
55 according to its purpose. |
56 according to its purpose. |
56 |
57 |
|
58 Another advantage of this design is that you can write your own graph classes, |
|
59 if you would like to. |
|
60 As long as they provide the interface defined in one of the graph concepts, |
|
61 all the LEMON algorithms and classes will work with them properly. |
|
62 |
57 |
63 |
58 [SEC]sec_digraph_types[SEC] Digraph Structures |
64 [SEC]sec_digraph_types[SEC] Digraph Structures |
59 |
65 |
60 The already used \ref ListDigraph class is the most versatile directed |
66 The already used \ref ListDigraph class is the most versatile directed |
61 graph structure. Apart from the general digraph functionalities, it |
67 graph structure. As its name suggests, it is based on linked lists, |
|
68 therefore iterating through its nodes and arcs is fast and it is quite |
|
69 flexible. Apart from the general digraph functionalities, it |
62 provides operations for adding and removing nodes and arcs, changing |
70 provides operations for adding and removing nodes and arcs, changing |
63 the source or target node of an arc, and contracting and splitting nodes |
71 the source or target node of an arc, and contracting and splitting nodes |
64 or arcs. |
72 or arcs. |
65 |
73 |
66 \ref SmartDigraph is another general digraph implementation, which is |
74 \ref SmartDigraph is another general digraph implementation, which is |
67 significantly more efficient (both in terms of space and time), but it |
75 significantly more efficient (both in terms of space and time), but it |
68 provides less functionality. For example, nodes and arcs cannot be |
76 provides less functionality. For example, nodes and arcs cannot be |
69 removed from it. |
77 removed from it. |
70 |
78 |
|
79 The \ref StaticDigraph structure is even more optimized for efficiency, |
|
80 but it is completely static. It requires less space in memory and |
|
81 provides faster item iteration than \ref ListDigraph and \ref |
|
82 SmartDigraph, especially using \ref concepts::Digraph::OutArcIt |
|
83 "OutArcIt" iterators, since its arcs are stored in an appropriate order. |
|
84 However, it only provides \ref StaticDigraph::build() "build()" and |
|
85 \ref \ref StaticDigraph::clear() "clear()" functions and does not |
|
86 support any other modification of the digraph. |
|
87 |
71 \ref FullDigraph is an efficient implementation of a directed full graph. |
88 \ref FullDigraph is an efficient implementation of a directed full graph. |
72 This structure is completely static, so you can neither add nor delete |
89 This structure is also completely static, so you can neither add nor delete |
73 arcs or nodes, and the class needs constant space in memory. |
90 arcs or nodes, moreover, the class needs constant space in memory. |
74 |
91 |
75 |
92 |
76 [SEC]sec_undir_graphs[SEC] Undirected Graphs |
93 [SEC]sec_undir_graphs[SEC] Undirected Graphs |
77 |
94 |
78 LEMON also provides undirected graph structures. For example, |
95 LEMON also provides undirected graph structures. For example, |