COIN-OR::LEMON - Graph Library

source: lemon-tutorial/basics.dox @ 27:b453a59230c8

Last change on this file since 27:b453a59230c8 was 27:b453a59230c8, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Rework and extend the section of basic concepts

File size: 7.7 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-2009
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
34This section tells you how to work with a directed graph (\e digraph,
35for short) in LEMON.
36The library provides various digraph structures for both general and special
37purposes. Here we use \c ListDigraph, the most versatile digraph type.
38
39The 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
41"ListDigraph::Arc". You can add new items to the graph using the member
42functions \ref ListDigraph::addNode() "addNode()" and
43\ref ListDigraph::addArc() "addArc()", like this:
44
45\code
46  ListDigraph g;
47  ListDigraph::Node a = g.addNode();
48  ListDigraph::Node b = g.addNode();
49  ListDigraph::Node c = g.addNode();
50  ListDigraph::Node d = g.addNode();
51
52  g.addArc(a,b);
53  g.addArc(b,c);
54  g.addArc(c,d);
55  g.addArc(d,a);
56\endcode
57
58Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
59
60\code
61  ListDigraph::Arc arc = g.addArc(a,c);
62\endcode
63
64\note Using ListDigraph, you can also remove nodes or arcs with the
65\ref ListDigraph::erase() "erase()" function.
66However, not all graph structures support the addition and deletion
67of graph items.
68
69Two important member functions of the directed graphs are
70\ref concepts::Digraph::source() "source()"
71and \ref concepts::Digraph::target() "target()".
72They give back the two end nodes of an arc.
73
74\code
75  if (g.source(arc) == g.target(arc))
76    std::cout << "This is a loop arc" << std::endl;
77\endcode
78
79Each graph item has a unique integer identifier, which can be obtained using
80the \ref concepts::Digraph::id() "id()" function of the graph structure.
81
82\code
83  std::cout << "Arc " << g.id(arc) << " goes from node "
84    << g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl;
85\endcode
86
87\note In fact, the \c Node and \c Arc types are typically simple wrapper
88classes for a single \c int value, which is the identifier of the item.
89
90
91[SEC]sec_digraph_it[SEC] Iterators
92
93Let us assume you want to list the elements of the graph. For this purpose,
94the graph structures provide several iterators. For example, the following
95code will count the number of nodes in a graph.
96
97\code
98  int cnt = 0;
99  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
100    cnt++;
101  std::cout << "Number of nodes: " << cnt << std::endl;
102\endcode
103
104Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
105is an iterator class that traverses the
106nodes. You must give the graph to the constructor and the iterator will be set
107to the first node. The next node is obtained by the prefix ++
108operator. If there are no more nodes in the graph, the iterator will
109be set to \ref INVALID.
110
111\note \ref INVALID is a global constant, which converts to
112and compares with each and every iterator in LEMON.
113
114The iterators convert to the corresponding item types. For example,
115to following code will add a full graph to the existing nodes.
116
117\code
118  for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
119    for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
120      if (u != v) g.addArc(u, v);
121\endcode
122
123\note Contrary to the iterators in the C++ Standard Template Library (STL),
124LEMON iterators are convertible to the corresponding
125item types without having to use \c %operator*(). This is not confusing, since the
126program context always indicates whether we refer to the iterator or to the graph
127item (they do not have conflicting functionalities).
128
129The graph items are also ordered by the 'less than' operator (with respect to
130their integer identifiers). For example, this code will add only one of the
131opposite arcs.
132
133\code
134  for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
135    for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
136      if (u < v) g.addArc(u, v);
137\endcode
138
139\warning The order in which the iterators visit the items is
140undefined. The only thing you may assume that they will list the items
141in the same order until the graph is not changed.
142
143Similarly, \ref concepts::Digraph::ArcIt "ListDigraph::ArcIt"
144lists the arcs. Its usage is the same as of
145\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt".
146
147\code
148  int cnt = 0;
149  for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
150    cnt++;
151  std::cout << "Number of arcs: " << cnt << std::endl;
152\endcode
153
154Finally, you can also list the arcs starting from or arriving at a
155certain node with
156\ref concepts::Digraph::OutArcIt "ListDigraph::OutArcIt"
157and
158\ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
159Their usage is the same, but you must also give the node to the constructor.
160
161\code
162  int cnt = 0;
163  for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a)
164    cnt++;
165  std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl;
166\endcode
167
168
169[SEC]sec_digraph_maps[SEC] Maps
170
171The concept of "maps" is another fundamental part of LEMON. They allow assigning
172values of any type to the nodes or arcs of a graph. The standard maps
173provided by the graph structures have a couple of nice properties.
174
175- \e Fast. Accessing (reading/writing) the values is as fast as a
176  simple vector reading/writing.
177- \e Dynamic. Whenever you need, you
178  can allocate new maps in your code, just as a local variable. So when you
179  leave its scope, it will be de-allocated automatically.
180- \e Automatic. If you add new nodes or arcs to the graph, the storage of the
181  existing maps will automatically expanded and the new slots will be
182  initialized. On the removal of an item, the corresponding values in the maps
183  are properly destructed.
184
185\note These maps must not be confused with \c std::map, since they provide
186O(1) time acces to the elements instead of O(log n).
187
188So, if you want to assign \c int values to each node, you have to allocate a
189\ref concepts::Digraph::NodeMap "NodeMap<int>".
190
191\code
192  ListDigraph::NodeMap<int> map(g);
193\endcode
194
195As you see, the graph you want to assign a map is given to the
196constructor. Then you can access its element as if it were a vector.
197
198\code
199  map[a] = 2;
200  map[b] = 3;
201  map[c] = map[a] + map[b];
202\endcode
203
204Any kind of data can be assigned to the graph items.
205
206\code
207  ListDigraph::NodeMap<std::string> label(g);
208  label[a] = "Node A";
209  label[b] = "Node B";
210\endcode
211
212For a more complex example, let us create a map that assigns a unique
213integer number to each node.
214
215\code
216  ListDigraph::NodeMap<int> id(g);
217  int cnt = 0;
218  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
219    id[n] = cnt++;
220\endcode
221
222When you create a map, you can also give an initial value of the elements
223as a second parameter. For example, the following code puts the number
224of outgoing arcs for each node in a map.
225
226\code
227  ListDigraph::NodeMap<int> out_deg(g, 0);
228
229  for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
230    out_deg[g.source(a)]++;
231\endcode
232
233\warning The initial value will apply to the currently existing items only. If
234you add new nodes/arcs to the graph, then the corresponding values in the
235map will be initialized with the default constructor of the
236type.
237
238[TRAILER]
239*/
240}
Note: See TracBrowser for help on using the repository browser.