29 |
29 |
30 directive is added to the code at the beginning. |
30 directive is added to the code at the beginning. |
31 |
31 |
32 [SEC]sec_digraphs[SEC] Directed Graphs |
32 [SEC]sec_digraphs[SEC] Directed Graphs |
33 |
33 |
|
34 The core features of LEMON are the data structures, algorithms and auxiliary |
|
35 tools that make it possible to represent graphs and working with them easily |
|
36 and efficiently. |
34 This section tells you how to work with a directed graph (\e digraph, |
37 This section tells you how to work with a directed graph (\e digraph, |
35 for short) in LEMON. Here we use \ref ListDigraph, the most versatile |
38 for short) in LEMON. Here we use \ref ListDigraph, the most versatile |
36 digraph structure. (The library also provides other digraph types, |
39 digraph structure. (The library also provides other digraph types, |
37 see \ref sec_graph_structures "later".) |
40 see \ref sec_graph_structures "later".) |
|
41 |
|
42 For using \ref ListDigraph, you must include the header file |
|
43 \ref list_graph.h like this: |
|
44 |
|
45 \code |
|
46 #include <lemon/list_graph.h> |
|
47 \endcode |
|
48 |
|
49 The default constructor of the class creates an empty digraph. |
|
50 |
|
51 \code |
|
52 ListDigraph g; |
|
53 \endcode |
38 |
54 |
39 The nodes and the arcs of a graph are identified by two data types called |
55 The nodes and the arcs of a graph are identified by two data types called |
40 \ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc |
56 \ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc |
41 "ListDigraph::Arc". You can add new items to the graph using the member |
57 "ListDigraph::Arc". You can add new items to the graph using the member |
42 functions \ref ListDigraph::addNode() "addNode()" and |
58 functions \ref ListDigraph::addNode() "addNode()" and |
43 \ref ListDigraph::addArc() "addArc()", like this: |
59 \ref ListDigraph::addArc() "addArc()", like this: |
44 |
60 |
45 \code |
61 \code |
46 ListDigraph g; |
62 ListDigraph::Node x = g.addNode(); |
47 ListDigraph::Node a = g.addNode(); |
63 ListDigraph::Node y = g.addNode(); |
48 ListDigraph::Node b = g.addNode(); |
64 ListDigraph::Node z = g.addNode(); |
49 ListDigraph::Node c = g.addNode(); |
65 |
50 ListDigraph::Node d = g.addNode(); |
66 g.addArc(x,y); |
51 |
67 g.addArc(y,z); |
52 g.addArc(a,b); |
68 g.addArc(z,x); |
53 g.addArc(b,c); |
|
54 g.addArc(c,d); |
|
55 g.addArc(d,a); |
|
56 \endcode |
69 \endcode |
57 |
70 |
58 Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc: |
71 Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc: |
59 |
72 |
60 \code |
73 \code |
61 ListDigraph::Arc arc = g.addArc(a,c); |
74 ListDigraph::Arc arc = g.addArc(x,z); |
|
75 \endcode |
|
76 |
|
77 Parallel and loop arcs are also supported. |
|
78 |
|
79 \code |
|
80 ListDigraph::Arc parallel = g.addArc(x,y); |
|
81 ListDigraph::Arc loop = g.addArc(x,x); |
62 \endcode |
82 \endcode |
63 |
83 |
64 \note Using ListDigraph, you can also remove nodes or arcs with the |
84 \note Using ListDigraph, you can also remove nodes or arcs with the |
65 \ref ListDigraph::erase() "erase()" function. Moreover, this class provides |
85 \ref ListDigraph::erase() "erase()" function. Moreover, this class provides |
66 several other operations, see its \ref ListDigraph "documentation" for more |
86 several other operations, see its \ref ListDigraph "documentation" for more |
69 of graph items (see \ref sec_graph_concepts). |
89 of graph items (see \ref sec_graph_concepts). |
70 |
90 |
71 Two important member functions of the directed graphs are |
91 Two important member functions of the directed graphs are |
72 \ref concepts::Digraph::source() "source()" |
92 \ref concepts::Digraph::source() "source()" |
73 and \ref concepts::Digraph::target() "target()". |
93 and \ref concepts::Digraph::target() "target()". |
74 They give back the two end nodes of an arc. |
94 They give back the two end nodes of an arc (as \c Node objects). |
75 |
95 |
76 \code |
96 \code |
77 if (g.source(arc) == g.target(arc)) |
97 if (g.source(loop) == g.target(loop)) |
78 std::cout << "This is a loop arc" << std::endl; |
98 std::cout << "This is a loop arc" << std::endl; |
79 \endcode |
99 \endcode |
80 |
100 |
81 Each graph item has a unique integer identifier, which can be obtained using |
101 Each graph item has a non-negative integer identifier, which can be obtained |
82 the \ref concepts::Digraph::id() "id()" function of the graph structure. |
102 using the \ref concepts::Digraph::id() "id()" function of the graph structure. |
|
103 These identifiers are unique with respect to a certain item type in a graph, |
|
104 but a node and an arc may have the same id. |
83 |
105 |
84 \code |
106 \code |
85 std::cout << "Arc " << g.id(arc) << " goes from node " |
107 std::cout << "Arc " << g.id(arc) << " goes from node " |
86 << g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl; |
108 << g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl; |
87 \endcode |
109 \endcode |
91 |
113 |
92 |
114 |
93 [SEC]sec_digraph_it[SEC] Iterators |
115 [SEC]sec_digraph_it[SEC] Iterators |
94 |
116 |
95 Let us assume you want to list the elements of the graph. For this purpose, |
117 Let us assume you want to list the elements of the graph. For this purpose, |
96 the graph structures provide several iterators. For example, the following |
118 the graph structures provide several \e iterators. For example, the following |
97 code will count the number of nodes in a graph. |
119 code will count the number of nodes in a graph. |
98 |
120 |
99 \code |
121 \code |
100 int cnt = 0; |
122 int cnt = 0; |
101 for (ListDigraph::NodeIt n(g); n != INVALID; ++n) |
123 for (ListDigraph::NodeIt n(g); n != INVALID; ++n) |
102 cnt++; |
124 cnt++; |
103 std::cout << "Number of nodes: " << cnt << std::endl; |
125 std::cout << "Number of nodes: " << cnt << std::endl; |
104 \endcode |
126 \endcode |
105 |
127 |
106 Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt" |
128 \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt" |
107 is an iterator class that traverses the |
129 is an iterator class that lists the nodes. |
108 nodes. You must give the graph to the constructor and the iterator will be set |
130 The name of an iterator type starts with a name that refers to |
|
131 the iterated objects and ends with 'It'. |
|
132 |
|
133 Using \ref concepts::Digraph::NodeIt "NodeIt", you must give |
|
134 the graph object to the constructor and the iterator will be set |
109 to the first node. The next node is obtained by the prefix ++ |
135 to the first node. The next node is obtained by the prefix ++ |
110 operator. If there are no more nodes in the graph, the iterator will |
136 operator. If there are no more nodes in the graph, the iterator will |
111 be set to \ref INVALID. |
137 be set to \ref INVALID, which is exploited in the stop condition of |
112 |
138 the loop. |
113 \note \ref INVALID is a global constant, which converts to |
139 |
114 and compares with each and every iterator in LEMON. |
140 \note \ref INVALID is a constant in the \ref lemon namespace, which converts to |
115 |
141 and compares with each and every iterator and graph item type. |
116 The iterators convert to the corresponding item types. For example, |
142 Thus, you can even assign \ref INVALID to a \c Node or \c Arc object. |
117 to following code will add a full graph to the existing nodes. |
143 |
|
144 The iterators convert to the corresponding item types. |
|
145 For example, the identifiers of the nodes can be printed like this. |
|
146 |
|
147 \code |
|
148 for (ListDigraph::NodeIt n(g); n != INVALID; ++n) |
|
149 std::cout << g.id(n) << std::endl; |
|
150 \endcode |
|
151 |
|
152 As an other example, the following code adds a full graph to the |
|
153 existing nodes. |
118 |
154 |
119 \code |
155 \code |
120 for (ListDigraph::NodeIt u(g); u != INVALID; ++u) |
156 for (ListDigraph::NodeIt u(g); u != INVALID; ++u) |
121 for (ListDigraph::NodeIt v(g); v != INVALID; ++v) |
157 for (ListDigraph::NodeIt v(g); v != INVALID; ++v) |
122 if (u != v) g.addArc(u, v); |
158 if (u != v) g.addArc(u, v); |
160 \ref concepts::Digraph::InArcIt "ListDigraph::InArcIt". |
196 \ref concepts::Digraph::InArcIt "ListDigraph::InArcIt". |
161 Their usage is the same, but you must also give the node to the constructor. |
197 Their usage is the same, but you must also give the node to the constructor. |
162 |
198 |
163 \code |
199 \code |
164 int cnt = 0; |
200 int cnt = 0; |
165 for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a) |
201 for (ListDigraph::OutArcIt a(g, x); a != INVALID; ++a) |
166 cnt++; |
202 cnt++; |
167 std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl; |
203 std::cout << "Number of arcs leaving the node 'x': " << cnt << std::endl; |
168 \endcode |
204 \endcode |
|
205 |
|
206 \note LEMON provides functions for counting the nodes and arcs of a digraph: |
|
207 \ref countNodes(), \ref countArcs(), \ref countInArcs(), \ref countOutArcs(). |
|
208 Using them is not just simpler than the above loops, but they could be much |
|
209 faster, since several graph types support constant time item counting. |
169 |
210 |
170 |
211 |
171 [SEC]sec_digraph_maps[SEC] Maps |
212 [SEC]sec_digraph_maps[SEC] Maps |
172 |
213 |
173 The concept of "maps" is another fundamental part of LEMON. They allow assigning |
214 The concept of "maps" is another fundamental part of LEMON. They allow assigning |
181 leave its scope, it will be de-allocated automatically. |
222 leave its scope, it will be de-allocated automatically. |
182 - \e Automatic. If you add new nodes or arcs to the graph, the storage of the |
223 - \e Automatic. If you add new nodes or arcs to the graph, the storage of the |
183 existing maps will automatically expanded and the new slots will be |
224 existing maps will automatically expanded and the new slots will be |
184 initialized. On the removal of an item, the corresponding values in the maps |
225 initialized. On the removal of an item, the corresponding values in the maps |
185 are properly destructed. |
226 are properly destructed. |
|
227 |
|
228 By principle, the graph classes represent only the pure structure of |
|
229 the graph (i.e. the nodes and arcs and their connections). |
|
230 All data that are assigned to the items of the graph (e.g. node labels, |
|
231 arc costs or capacities) must be stored separately using maps. |
186 |
232 |
187 \note These maps must not be confused with \c std::map, since they provide |
233 \note These maps must not be confused with \c std::map, since they provide |
188 O(1) time acces to the elements instead of O(log n). |
234 O(1) time access to the elements instead of O(log n). |
189 |
235 |
190 So, if you want to assign \c int values to each node, you have to allocate a |
236 So, if you want to assign \c int values to each node, you have to allocate a |
191 \ref concepts::Digraph::NodeMap "NodeMap<int>". |
237 \ref concepts::Digraph::NodeMap "NodeMap<int>". |
192 |
238 |
193 \code |
239 \code |
196 |
242 |
197 As you see, the graph you want to assign a map is given to the |
243 As you see, the graph you want to assign a map is given to the |
198 constructor. Then you can access its element as if it were a vector. |
244 constructor. Then you can access its element as if it were a vector. |
199 |
245 |
200 \code |
246 \code |
201 map[a] = 2; |
247 map[x] = 2; |
202 map[b] = 3; |
248 map[y] = 3; |
203 map[c] = map[a] + map[b]; |
249 map[z] = map[x] + map[y]; |
204 \endcode |
250 \endcode |
205 |
251 |
206 Any kind of data can be assigned to the graph items. |
252 Any kind of data can be assigned to the graph items (assuming that the type |
207 |
253 has a default constructor). |
208 \code |
254 |
209 ListDigraph::NodeMap<std::string> label(g); |
255 \code |
210 label[a] = "Node A"; |
256 ListDigraph::NodeMap<std::string> name(g); |
211 label[b] = "Node B"; |
257 name[x] = "Node A"; |
212 \endcode |
258 name[y] = "Node B"; |
213 |
259 \endcode |
214 For a more complex example, let us create a map that assigns a unique |
260 |
215 integer number to each node. |
261 As a more complex example, let us create a map that assigns \c char labels |
216 |
262 to the nodes. |
217 \code |
263 |
218 ListDigraph::NodeMap<int> id(g); |
264 \code |
219 int cnt = 0; |
265 ListDigraph::NodeMap<char> label(g); |
|
266 char ch = 'A'; |
220 for (ListDigraph::NodeIt n(g); n != INVALID; ++n) |
267 for (ListDigraph::NodeIt n(g); n != INVALID; ++n) |
221 id[n] = cnt++; |
268 label[n] = ch++; |
222 \endcode |
269 \endcode |
223 |
270 |
224 When you create a map, you can also give an initial value of the elements |
271 When you create a map, you can also give an initial value of the elements |
225 as a second parameter. For example, the following code puts the number |
272 as a second parameter. For example, the following code puts the number |
226 of outgoing arcs for each node in a map. |
273 of outgoing arcs for each node in a map. |
227 |
274 |
228 \code |
275 \code |
229 ListDigraph::NodeMap<int> out_deg(g, 0); |
276 ListDigraph::NodeMap<int> out_deg(g, 0); |
230 |
|
231 for (ListDigraph::ArcIt a(g); a != INVALID; ++a) |
277 for (ListDigraph::ArcIt a(g); a != INVALID; ++a) |
232 out_deg[g.source(a)]++; |
278 out_deg[g.source(a)]++; |
233 \endcode |
279 \endcode |
234 |
280 |
235 \warning The initial value will apply to the currently existing items only. If |
281 \warning The initial value will apply to the currently existing items only. If |
236 you add new nodes/arcs to the graph, then the corresponding values in the |
282 you add new nodes/arcs to the graph, then the corresponding values in the |
237 map will be initialized with the default constructor of the |
283 map will be initialized with the default constructor of the |
238 type. |
284 type. |
239 |
285 |
|
286 |
|
287 [SEC]sec_naming_conv[SEC] Naming Conventions |
|
288 |
|
289 In LEMON, there are some naming conventions you might already notice |
|
290 in the above examples. |
|
291 |
|
292 The name of a source file is written lowercase and the words are separated with |
|
293 underscores (e.g. \ref list_graph.h). All header files are located in the |
|
294 \c %lemon subdirectory, so you can include them like this. |
|
295 |
|
296 \code |
|
297 #include <lemon/header_file.h> |
|
298 \endcode |
|
299 |
|
300 The name of a class or any type looks like the following |
|
301 (e.g. \ref ListDigraph, \ref concepts::Digraph::Node "Node", |
|
302 \ref concepts::Digraph::NodeIt "NodeIt" etc.). |
|
303 |
|
304 \code |
|
305 AllWordsCapitalizedWithoutUnderscores |
|
306 \endcode |
|
307 |
|
308 The name of a function looks like the following |
|
309 (e.g. \ref concepts::Digraph::source() "source()", |
|
310 \ref concepts::Digraph::source() "target()", |
|
311 \ref countNodes(), \ref countArcs() etc.). |
|
312 |
|
313 \code |
|
314 firstWordLowerCaseRestCapitalizedWithoutUnderscores |
|
315 \endcode |
|
316 |
|
317 The names of constants and macros look like the following |
|
318 (e.g. \ref INVALID). |
|
319 |
|
320 \code |
|
321 ALL_UPPER_CASE_WITH_UNDERSCORES |
|
322 \endcode |
|
323 |
|
324 For more details, see \ref coding_style. |
|
325 |
240 [TRAILER] |
326 [TRAILER] |
241 */ |
327 */ |
242 } |
328 } |