Fix a type in Secion LP. Thanks for Jacint
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
21 [PAGE]sec_basics[PAGE] Basic Concepts
23 Throughout the tutorial we are working with the \ref lemon namespace.
24 To save a lot of typing, we assume that a
27 using namespace lemon;
30 directive is added to the code at the beginning.
32 [SEC]sec_digraphs[SEC] Directed Graphs
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
37 This section tells you how to work with a directed graph (\e digraph,
38 for short) in LEMON. Here we use \ref ListDigraph, the most versatile
39 digraph structure. (The library also provides other digraph types,
40 see \ref sec_graph_structures "later".)
42 For using \ref ListDigraph, you must include the header file
43 \ref list_graph.h like this:
46 #include <lemon/list_graph.h>
49 The default constructor of the class creates an empty digraph.
55 The 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
58 functions \ref ListDigraph::addNode() "addNode()" and
59 \ref ListDigraph::addArc() "addArc()", like this:
62 ListDigraph::Node x = g.addNode();
63 ListDigraph::Node y = g.addNode();
64 ListDigraph::Node z = g.addNode();
71 Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
74 ListDigraph::Arc arc = g.addArc(x,z);
77 Parallel and loop arcs are also supported.
80 ListDigraph::Arc parallel = g.addArc(x,y);
81 ListDigraph::Arc loop = g.addArc(x,x);
84 \note Using ListDigraph, you can also remove nodes or arcs with the
85 \ref ListDigraph::erase() "erase()" function. Moreover, this class provides
86 several other operations, see its \ref ListDigraph "documentation" for more
88 However, not all graph structures support the addition and deletion
89 of graph items (see \ref sec_graph_concepts).
91 Two important member functions of the directed graphs are
92 \ref concepts::Digraph::source() "source()"
93 and \ref concepts::Digraph::target() "target()".
94 They give back the two end nodes of an arc (as \c Node objects).
97 if (g.source(loop) == g.target(loop))
98 std::cout << "This is a loop arc" << std::endl;
101 Each graph item has a non-negative integer identifier, which can be obtained
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.
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;
111 \note In fact, the \c Node and \c Arc types are typically simple wrapper
112 classes for a single \c int value, which is the identifier of the item.
115 [SEC]sec_digraph_it[SEC] Iterators
117 Let us assume you want to list the elements of the graph. For this purpose,
118 the graph structures provide several \e iterators. For example, the following
119 code will count the number of nodes in a graph.
123 for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
125 std::cout << "Number of nodes: " << cnt << std::endl;
128 \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
129 is an iterator class that lists the nodes.
130 The name of an iterator type starts with a name that refers to
131 the iterated objects and ends with 'It'.
133 Using \ref concepts::Digraph::NodeIt "NodeIt", you must give
134 the graph object to the constructor and the iterator will be set
135 to the first node. The next node is obtained by the prefix ++
136 operator. If there are no more nodes in the graph, the iterator will
137 be set to \ref INVALID, which is exploited in the stop condition of
140 \note \ref INVALID is a constant in the \ref lemon namespace, which converts to
141 and compares with each and every iterator and graph item type.
142 Thus, you can even assign \ref INVALID to a \c Node or \c Arc object.
144 The iterators convert to the corresponding item types.
145 For example, the identifiers of the nodes can be printed like this.
148 for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
149 std::cout << g.id(n) << std::endl;
152 As an other example, the following code adds a full graph to the
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);
161 \note Contrary to the iterators in the C++ Standard Template Library (STL),
162 LEMON iterators are convertible to the corresponding
163 item types without having to use \c %operator*(). This is not confusing,
164 since the program context always indicates whether we refer to the iterator
165 or to the graph item (they do not have conflicting functionalities).
167 The graph items are also ordered by the 'less than' operator (with respect to
168 their integer identifiers). For example, this code will add only one of the
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);
177 \warning The order in which the iterators visit the items is
178 undefined. The only thing you may assume that they will list the items
179 in the same order until the graph is not changed.
181 Similarly, \ref concepts::Digraph::ArcIt "ListDigraph::ArcIt"
182 lists the arcs. Its usage is the same as of
183 \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt".
187 for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
189 std::cout << "Number of arcs: " << cnt << std::endl;
192 Finally, you can also list the arcs starting from or arriving at a
194 \ref concepts::Digraph::OutArcIt "ListDigraph::OutArcIt"
196 \ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
197 Their usage is the same, but you must also give the node to the constructor.
201 for (ListDigraph::OutArcIt a(g, x); a != INVALID; ++a)
203 std::cout << "Number of arcs leaving the node 'x': " << cnt << std::endl;
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.
212 [SEC]sec_digraph_maps[SEC] Maps
214 The concept of "maps" is another fundamental part of LEMON. They allow assigning
215 values of any type to the nodes or arcs of a graph. The standard maps
216 provided by the graph structures have a couple of nice properties.
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.
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.
233 \note These maps must not be confused with \c std::map, since they provide
234 O(1) time access to the elements instead of O(log n).
236 So, if you want to assign \c int values to each node, you have to allocate a
237 \ref concepts::Digraph::NodeMap "NodeMap<int>".
240 ListDigraph::NodeMap<int> map(g);
243 As you see, the graph you want to assign a map is given to the
244 constructor. Then you can access its element as if it were a vector.
249 map[z] = map[x] + map[y];
252 Any kind of data can be assigned to the graph items (assuming that the type
253 has a default constructor).
256 ListDigraph::NodeMap<std::string> name(g);
261 As a more complex example, let us create a map that assigns \c char labels
265 ListDigraph::NodeMap<char> label(g);
267 for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
271 When you create a map, you can also give an initial value of the elements
272 as a second parameter. For example, the following code puts the number
273 of outgoing arcs for each node in a map.
276 ListDigraph::NodeMap<int> out_deg(g, 0);
277 for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
278 out_deg[g.source(a)]++;
281 \warning The initial value will apply to the currently existing items only. If
282 you add new nodes/arcs to the graph, then the corresponding values in the
283 map will be initialized with the default constructor of the
287 [SEC]sec_naming_conv[SEC] Naming Conventions
289 In LEMON, there are some naming conventions you might already notice
290 in the above examples.
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.
297 #include <lemon/header_file.h>
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.).
305 AllWordsCapitalizedWithoutUnderscores
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.).
314 firstWordLowerCaseRestCapitalizedWithoutUnderscores
317 The names of constants and macros look like the following
321 ALL_UPPER_CASE_WITH_UNDERSCORES
324 For more details, see \ref coding_style.