COIN-OR::LEMON - Graph Library

source: lemon-tutorial/basics.dox @ 37:c8be1109221b

Last change on this file since 37:c8be1109221b was 37:c8be1109221b, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Improve and extend basics page

File size: 10.5 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19namespace lemon {
20/**
21[PAGE]sec_basics[PAGE] Basic Concepts
22
23Throughout the tutorial we are working with the \ref lemon namespace.
24To save a lot of typing, we assume that a
25
26\code
27using namespace lemon;
28\endcode
29
30directive is added to the code at the beginning.
31
32[SEC]sec_digraphs[SEC] Directed Graphs
33
34The core features of LEMON are the data structures, algorithms and auxiliary
35tools that make it possible to represent graphs and working with them easily
36and efficiently.
37This section tells you how to work with a directed graph (\e digraph,
38for short) in LEMON. Here we use \ref ListDigraph, the most versatile
39digraph structure. (The library also provides other digraph types,
40see \ref sec_graph_structures "later".)
41
42For 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
49The default constructor of the class creates an empty digraph.
50
51\code
52  ListDigraph g;
53\endcode
54
55The nodes and the arcs of a graph are identified by two data types called
56\ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc
57"ListDigraph::Arc". You can add new items to the graph using the member
58functions \ref ListDigraph::addNode() "addNode()" and
59\ref ListDigraph::addArc() "addArc()", like this:
60
61\code
62  ListDigraph::Node x = g.addNode();
63  ListDigraph::Node y = g.addNode();
64  ListDigraph::Node z = g.addNode();
65
66  g.addArc(x,y);
67  g.addArc(y,z);
68  g.addArc(z,x);
69\endcode
70
71Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
72
73\code
74  ListDigraph::Arc arc = g.addArc(x,z);
75\endcode
76
77Parallel 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);
82\endcode
83
84\note Using ListDigraph, you can also remove nodes or arcs with the
85\ref ListDigraph::erase() "erase()" function. Moreover, this class provides
86several other operations, see its \ref ListDigraph "documentation" for more
87information.
88However, not all graph structures support the addition and deletion
89of graph items (see \ref sec_graph_concepts).
90
91Two important member functions of the directed graphs are
92\ref concepts::Digraph::source() "source()"
93and \ref concepts::Digraph::target() "target()".
94They give back the two end nodes of an arc (as \c Node objects).
95
96\code
97  if (g.source(loop) == g.target(loop))
98    std::cout << "This is a loop arc" << std::endl;
99\endcode
100
101Each graph item has a non-negative integer identifier, which can be obtained
102using the \ref concepts::Digraph::id() "id()" function of the graph structure.
103These identifiers are unique with respect to a certain item type in a graph,
104but a node and an arc may have the same id.
105
106\code
107  std::cout << "Arc " << g.id(arc) << " goes from node "
108    << g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl;
109\endcode
110
111\note In fact, the \c Node and \c Arc types are typically simple wrapper
112classes for a single \c int value, which is the identifier of the item.
113
114
115[SEC]sec_digraph_it[SEC] Iterators
116
117Let us assume you want to list the elements of the graph. For this purpose,
118the graph structures provide several \e iterators. For example, the following
119code will count the number of nodes in a graph.
120
121\code
122  int cnt = 0;
123  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
124    cnt++;
125  std::cout << "Number of nodes: " << cnt << std::endl;
126\endcode
127
128\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
129is an iterator class that lists the nodes.
130The name of an iterator type starts with a name that refers to
131the iterated objects and ends with 'It'.
132
133Using \ref concepts::Digraph::NodeIt "NodeIt", you must give
134the graph object to the constructor and the iterator will be set
135to the first node. The next node is obtained by the prefix ++
136operator. If there are no more nodes in the graph, the iterator will
137be set to \ref INVALID, which is exploited in the stop condition of
138the loop.
139
140\note \ref INVALID is a constant in the \ref lemon namespace, which converts to
141and compares with each and every iterator and graph item type.
142Thus, you can even assign \ref INVALID to a \c Node or \c Arc object.
143
144The iterators convert to the corresponding item types.
145For 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
152As an other example, the following code adds a full graph to the
153existing nodes.
154
155\code
156  for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
157    for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
158      if (u != v) g.addArc(u, v);
159\endcode
160
161\note Contrary to the iterators in the C++ Standard Template Library (STL),
162LEMON iterators are convertible to the corresponding
163item types without having to use \c %operator*(). This is not confusing,
164since the program context always indicates whether we refer to the iterator
165or to the graph item (they do not have conflicting functionalities).
166
167The graph items are also ordered by the 'less than' operator (with respect to
168their integer identifiers). For example, this code will add only one of the
169opposite arcs.
170
171\code
172  for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
173    for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
174      if (u < v) g.addArc(u, v);
175\endcode
176
177\warning The order in which the iterators visit the items is
178undefined. The only thing you may assume that they will list the items
179in the same order until the graph is not changed.
180
181Similarly, \ref concepts::Digraph::ArcIt "ListDigraph::ArcIt"
182lists the arcs. Its usage is the same as of
183\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt".
184
185\code
186  int cnt = 0;
187  for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
188    cnt++;
189  std::cout << "Number of arcs: " << cnt << std::endl;
190\endcode
191
192Finally, you can also list the arcs starting from or arriving at a
193certain node with
194\ref concepts::Digraph::OutArcIt "ListDigraph::OutArcIt"
195and
196\ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
197Their usage is the same, but you must also give the node to the constructor.
198
199\code
200  int cnt = 0;
201  for (ListDigraph::OutArcIt a(g, x); a != INVALID; ++a)
202    cnt++;
203  std::cout << "Number of arcs leaving the node 'x': " << cnt << std::endl;
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().
208Using them is not just simpler than the above loops, but they could be much
209faster, since several graph types support constant time item counting.
210
211
212[SEC]sec_digraph_maps[SEC] Maps
213
214The concept of "maps" is another fundamental part of LEMON. They allow assigning
215values of any type to the nodes or arcs of a graph. The standard maps
216provided by the graph structures have a couple of nice properties.
217
218- \e Fast. Accessing (reading/writing) the values is as fast as a
219  simple vector reading/writing.
220- \e Dynamic. Whenever you need, you
221  can allocate new maps in your code, just as a local variable. So when you
222  leave its scope, it will be de-allocated automatically.
223- \e Automatic. If you add new nodes or arcs to the graph, the storage of the
224  existing maps will automatically expanded and the new slots will be
225  initialized. On the removal of an item, the corresponding values in the maps
226  are properly destructed.
227 
228By principle, the graph classes represent only the pure structure of
229the graph (i.e. the nodes and arcs and their connections).
230All data that are assigned to the items of the graph (e.g. node labels,
231arc costs or capacities) must be stored separately using maps.
232
233\note These maps must not be confused with \c std::map, since they provide
234O(1) time access to the elements instead of O(log n).
235
236So, if you want to assign \c int values to each node, you have to allocate a
237\ref concepts::Digraph::NodeMap "NodeMap<int>".
238
239\code
240  ListDigraph::NodeMap<int> map(g);
241\endcode
242
243As you see, the graph you want to assign a map is given to the
244constructor. Then you can access its element as if it were a vector.
245
246\code
247  map[x] = 2;
248  map[y] = 3;
249  map[z] = map[x] + map[y];
250\endcode
251
252Any kind of data can be assigned to the graph items (assuming that the type
253has a default constructor).
254
255\code
256  ListDigraph::NodeMap<std::string> name(g);
257  name[x] = "Node A";
258  name[y] = "Node B";
259\endcode
260
261As a more complex example, let us create a map that assigns \c char labels
262to the nodes.
263
264\code
265  ListDigraph::NodeMap<char> label(g);
266  char ch = 'A';
267  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
268    label[n] = ch++;
269\endcode
270
271When you create a map, you can also give an initial value of the elements
272as a second parameter. For example, the following code puts the number
273of outgoing arcs for each node in a map.
274
275\code
276  ListDigraph::NodeMap<int> out_deg(g, 0);
277  for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
278    out_deg[g.source(a)]++;
279\endcode
280
281\warning The initial value will apply to the currently existing items only. If
282you add new nodes/arcs to the graph, then the corresponding values in the
283map will be initialized with the default constructor of the
284type.
285
286
287[SEC]sec_naming_conv[SEC] Naming Conventions
288
289In LEMON, there are some naming conventions you might already notice
290in the above examples.
291
292The name of a source file is written lowercase and the words are separated with
293underscores (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
300The 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
305AllWordsCapitalizedWithoutUnderscores
306\endcode
307
308The 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
314firstWordLowerCaseRestCapitalizedWithoutUnderscores
315\endcode
316
317The names of constants and macros look like the following
318(e.g. \ref INVALID).
319
320\code
321ALL_UPPER_CASE_WITH_UNDERSCORES
322\endcode
323
324For more details, see \ref coding_style.
325
326[TRAILER]
327*/
328}
Note: See TracBrowser for help on using the repository browser.