COIN-OR::LEMON - Graph Library

source: lemon-tutorial/basics.dox @ 32:ef12f83752f6

Last change on this file since 32:ef12f83752f6 was 32:ef12f83752f6, checked in by Peter Kovacs <kpeter@…>, 9 years ago

Happy New Year + unify files

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