1 /*! |
1 /*! |
2 |
2 |
3 \page graphs Graphs |
3 \page graphs Graphs |
|
4 |
|
5 \todo Write a new Graphs page. I think it should be contain the Graph, |
|
6 UGraph and BpUGraph concept. It should be describe the iterators and |
|
7 the basic functions and the differences of the implementations. |
4 |
8 |
5 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 |
6 provide a node list - edge list interface, i.e. they have |
10 provide a node list - edge list interface, i.e. they have |
7 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 |
8 as incoming and outgoing edges of a given node. |
12 as incoming and outgoing edges of a given node. |
9 |
13 |
|
14 Each graph should meet the \ref lemon::concept::Graph "Graph" concept. |
|
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 |
|
17 algorithms will run on these graphs. |
10 |
18 |
11 Each graph should meet the |
|
12 \ref lemon::concept::StaticGraph "StaticGraph" concept. |
|
13 This concept does not |
|
14 make it possible to change the graph (i.e. it is not possible to add |
|
15 or delete edges or nodes). Most of the graph algorithms will run on |
|
16 these graphs. |
|
17 |
|
18 The graphs meeting the |
|
19 \ref lemon::concept::ExtendableGraph "ExtendableGraph" |
|
20 concept allow node and |
|
21 edge addition. You can also "clear" such a graph (i.e. erase all edges and nodes ). |
|
22 |
19 |
23 In case of graphs meeting the full feature |
20 In case of graphs meeting the full feature |
24 \ref lemon::concept::ErasableGraph "ErasableGraph" |
21 \ref lemon::concept::ErasableGraph "ErasableGraph" |
25 concept |
22 concept |
26 you can also erase individual edges and nodes in arbitrary order. |
23 you can also erase individual edges and nodes in arbitrary order. |
34 price of this is that it only meets the |
31 price of this is that it only meets the |
35 \ref lemon::concept::ExtendableGraph "ExtendableGraph" concept, |
32 \ref lemon::concept::ExtendableGraph "ExtendableGraph" concept, |
36 so you cannot delete individual edges or nodes. |
33 so you cannot delete individual edges or nodes. |
37 \li \ref lemon::FullGraph "FullGraph" |
34 \li \ref lemon::FullGraph "FullGraph" |
38 implements a complete graph. It is a |
35 implements a complete graph. It is a |
39 \ref lemon::concept::StaticGraph "StaticGraph", so you cannot |
36 \ref lemon::concept::Graph "Graph", so you cannot |
40 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 |
41 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 |
42 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 |
43 \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. |
44 |
41 |