9 The primary data structures of LEMON are the graph classes. They all |
9 The primary data structures of LEMON are the graph classes. They all |
10 provide a node list - edge list interface, i.e. they have |
10 provide a node list - edge list interface, i.e. they have |
11 functionalities to list the nodes and the edges of the graph as well |
11 functionalities to list the nodes and the edges of the graph as well |
12 as incoming and outgoing edges of a given node. |
12 as incoming and outgoing edges of a given node. |
13 |
13 |
14 Each graph should meet the \ref lemon::concept::Graph "Graph" concept. |
14 Each graph should meet the \ref lemon::concepts::Graph "Graph" concept. |
15 This concept does not make it possible to change the graph (i.e. it is |
15 This concept does not make it possible to change the graph (i.e. it is |
16 not possible to add or delete edges or nodes). Most of the graph |
16 not possible to add or delete edges or nodes). Most of the graph |
17 algorithms will run on these graphs. |
17 algorithms will run on these graphs. |
18 |
18 |
19 |
19 |
20 In case of graphs meeting the full feature |
20 In case of graphs meeting the full feature |
21 \ref lemon::concept::ErasableGraph "ErasableGraph" |
21 \ref lemon::concepts::ErasableGraph "ErasableGraph" |
22 concept |
22 concept |
23 you can also erase individual edges and nodes in arbitrary order. |
23 you can also erase individual edges and nodes in arbitrary order. |
24 |
24 |
25 The implemented graph structures are the following. |
25 The implemented graph structures are the following. |
26 \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets |
26 \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets |
27 the \ref lemon::concept::ErasableGraph "ErasableGraph" concept |
27 the \ref lemon::concepts::ErasableGraph "ErasableGraph" concept |
28 and it also has some convenient extra features. |
28 and it also has some convenient extra features. |
29 \li \ref lemon::SmartGraph "SmartGraph" is a more memory |
29 \li \ref lemon::SmartGraph "SmartGraph" is a more memory |
30 efficient version of \ref lemon::ListGraph "ListGraph". The |
30 efficient version of \ref lemon::ListGraph "ListGraph". The |
31 price of this is that it only meets the |
31 price of this is that it only meets the |
32 \ref lemon::concept::ExtendableGraph "ExtendableGraph" concept, |
32 \ref lemon::concepts::ExtendableGraph "ExtendableGraph" concept, |
33 so you cannot delete individual edges or nodes. |
33 so you cannot delete individual edges or nodes. |
34 \li \ref lemon::FullGraph "FullGraph" |
34 \li \ref lemon::FullGraph "FullGraph" |
35 implements a complete graph. It is a |
35 implements a complete graph. It is a |
36 \ref lemon::concept::Graph "Graph", so you cannot |
36 \ref lemon::concepts::Graph "Graph", so you cannot |
37 change the number of nodes once it is constructed. It is extremely memory |
37 change the number of nodes once it is constructed. It is extremely memory |
38 efficient: it uses constant amount of memory independently from the number of |
38 efficient: it uses constant amount of memory independently from the number of |
39 the nodes of the graph. Of course, the size of the \ref maps-page "NodeMap"'s and |
39 the nodes of the graph. Of course, the size of the \ref maps-page "NodeMap"'s and |
40 \ref maps-page "EdgeMap"'s will depend on the number of nodes. |
40 \ref maps-page "EdgeMap"'s will depend on the number of nodes. |
41 |
41 |