3 \page graphs How to use graphs |
3 \page graphs How to use graphs |
4 |
4 |
5 The primary data structures of LEMON are the graph classes. They all |
5 The primary data structures of LEMON are the graph classes. They all |
6 provide a node list - edge list interface, i.e. they have |
6 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 |
7 functionalities to list the nodes and the edges of the graph as well |
8 as in incoming and outgoing edges of a given node. |
8 as incoming and outgoing edges of a given node. |
9 |
9 |
10 |
10 |
11 Each graph should meet the |
11 Each graph should meet the |
12 \ref lemon::concept::StaticGraph "StaticGraph" concept. |
12 \ref lemon::concept::StaticGraph "StaticGraph" concept. |
13 This concept does not |
13 This concept does not |
14 makes it possible to change the graph (i.e. it is not possible to add |
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 |
15 or delete edges or nodes). Most of the graph algorithms will run on |
16 these graphs. |
16 these graphs. |
17 |
17 |
18 The graphs meeting the |
18 The graphs meeting the |
19 \ref lemon::concept::ExtendableGraph "ExtendableGraph" |
19 \ref lemon::concept::ExtendableGraph "ExtendableGraph" |
20 concept allow node and |
20 concept allow node and |
21 edge addition. You can also "clear" (i.e. erase all edges and nodes) |
21 edge addition. You can also "clear" such a graph (i.e. erase all edges and nodes ). |
22 such a graph. |
|
23 |
22 |
24 In case of graphs meeting the full feature |
23 In case of graphs meeting the full feature |
25 \ref lemon::concept::ErasableGraph "ErasableGraph" |
24 \ref lemon::concept::ErasableGraph "ErasableGraph" |
26 concept |
25 concept |
27 you can also erase individual edges and node in arbitrary order. |
26 you can also erase individual edges and nodes in arbitrary order. |
28 |
27 |
29 The implemented graph structures are the following. |
28 The implemented graph structures are the following. |
30 \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets |
29 \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets |
31 the \ref lemon::concept::ErasableGraph "ErasableGraph" concept |
30 the \ref lemon::concept::ErasableGraph "ErasableGraph" concept |
32 and it also have some convenience features. |
31 and it also has some convenient extra features. |
33 \li \ref lemon::SmartGraph "SmartGraph" is a more memory |
32 \li \ref lemon::SmartGraph "SmartGraph" is a more memory |
34 efficient version of \ref lemon::ListGraph "ListGraph". The |
33 efficient version of \ref lemon::ListGraph "ListGraph". The |
35 price of it is that it only meets the |
34 price of this is that it only meets the |
36 \ref lemon::concept::ExtendableGraph "ExtendableGraph" concept, |
35 \ref lemon::concept::ExtendableGraph "ExtendableGraph" concept, |
37 so you cannot delete individual edges or nodes. |
36 so you cannot delete individual edges or nodes. |
38 \li \ref lemon::SymListGraph "SymListGraph" and |
37 \li \ref lemon::SymListGraph "SymListGraph" and |
39 \ref lemon::SymSmartGraph "SymSmartGraph" classes are very similar to |
38 \ref lemon::SymSmartGraph "SymSmartGraph" classes are very similar to |
40 \ref lemon::ListGraph "ListGraph" and \ref lemon::SmartGraph "SmartGraph". |
39 \ref lemon::ListGraph "ListGraph" and \ref lemon::SmartGraph "SmartGraph". |
43 They are linked together so it is possible to access the counterpart of an |
42 They are linked together so it is possible to access the counterpart of an |
44 edge. An even more important feature is that using these classes you can also |
43 edge. An even more important feature is that using these classes you can also |
45 attach data to the edges in such a way that the stored data |
44 attach data to the edges in such a way that the stored data |
46 are shared by the edge pairs. |
45 are shared by the edge pairs. |
47 \li \ref lemon::FullGraph "FullGraph" |
46 \li \ref lemon::FullGraph "FullGraph" |
48 implements a full graph. It is a \ref lemon::concept::StaticGraph, so you cannot |
47 implements a complete graph. It is a \ref lemon::concept::StaticGraph, so you cannot |
49 change the number of nodes once it is constructed. It is extremely memory |
48 change the number of nodes once it is constructed. It is extremely memory |
50 efficient: it uses constant amount of memory independently from the number of |
49 efficient: it uses constant amount of memory independently from the number of |
51 the nodes of the graph. Of course, the size of the \ref maps-page "NodeMap"'s and |
50 the nodes of the graph. Of course, the size of the \ref maps-page "NodeMap"'s and |
52 \ref maps-page "EdgeMap"'s will depend on the number of nodes. |
51 \ref maps-page "EdgeMap"'s will depend on the number of nodes. |
53 |
52 |
58 is possible to attach several \ref lemon::EdgeSet "EdgeSet"'s to a base graph. |
57 is possible to attach several \ref lemon::EdgeSet "EdgeSet"'s to a base graph. |
59 |
58 |
60 \todo Don't we need SmartNodeSet and SmartEdgeSet? |
59 \todo Don't we need SmartNodeSet and SmartEdgeSet? |
61 \todo Some cross-refs are wrong. |
60 \todo Some cross-refs are wrong. |
62 |
61 |
63 The graph structures itself can not store data attached |
62 The graph structures themselves can not store data attached |
64 to the edges and nodes. However they all provide |
63 to the edges and nodes. However they all provide |
65 \ref maps-page "map classes" |
64 \ref maps-page "map classes" |
66 to dynamically attach data the to graph components. |
65 to dynamically attach data the to graph components. |
67 |
66 |
68 The following program demonstrates the basic features of LEMON's graph |
67 The following program demonstrates the basic features of LEMON's graph |
98 for (NodeIt i(g); i!=INVALID; ++i) |
97 for (NodeIt i(g); i!=INVALID; ++i) |
99 for (NodeIt j(g); j!=INVALID; ++j) |
98 for (NodeIt j(g); j!=INVALID; ++j) |
100 if (i != j) g.addEdge(i, j); |
99 if (i != j) g.addEdge(i, j); |
101 \endcode |
100 \endcode |
102 |
101 |
103 After some convenience typedefs we create a graph and add three nodes to it. |
102 After some convenient typedefs we create a graph and add three nodes to it. |
104 Then we add edges to it to form a full graph. |
103 Then we add edges to it to form a complete graph. |
105 |
104 |
106 \code |
105 \code |
107 std::cout << "Nodes:"; |
106 std::cout << "Nodes:"; |
108 for (NodeIt i(g); i!=INVALID; ++i) |
107 for (NodeIt i(g); i!=INVALID; ++i) |
109 std::cout << " " << g.id(i); |
108 std::cout << " " << g.id(i); |
131 |
130 |
132 \code |
131 \code |
133 Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0) |
132 Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0) |
134 \endcode |
133 \endcode |
135 |
134 |
136 We can also iterate through all edges of the graph very similarly. The target and |
135 We can also iterate through all edges of the graph very similarly. The |
137 source member functions can be used to access the endpoints of an edge. |
136 \c target and |
|
137 \c source member functions can be used to access the endpoints of an edge. |
138 |
138 |
139 \code |
139 \code |
140 NodeIt first_node(g); |
140 NodeIt first_node(g); |
141 |
141 |
142 std::cout << "Out-edges of node " << g.id(first_node) << ":"; |
142 std::cout << "Out-edges of node " << g.id(first_node) << ":"; |
183 As we mentioned above, graphs are not containers rather |
183 As we mentioned above, graphs are not containers rather |
184 incidence structures which are iterable in many ways. LEMON introduces |
184 incidence structures which are iterable in many ways. LEMON introduces |
185 concepts that allow us to attach containers to graphs. These containers are |
185 concepts that allow us to attach containers to graphs. These containers are |
186 called maps. |
186 called maps. |
187 |
187 |
188 In the example above we create an EdgeMap which assigns an int value to all |
188 In the example above we create an EdgeMap which assigns an integer value to all |
189 edges of the graph. We use the set member function of the map to write values |
189 edges of the graph. We use the set member function of the map to write values |
190 into the map and the operator[] to retrieve them. |
190 into the map and the operator[] to retrieve them. |
191 |
191 |
192 Here we used the maps provided by the ListGraph class, but you can also write |
192 Here we used the maps provided by the ListGraph class, but you can also write |
193 your own maps. You can read more about using maps \ref maps-page "here". |
193 your own maps. You can read more about using maps \ref maps-page "here". |