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 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
36 digraph structure. (The library also provides other digraph types,
37 see \ref sec_graph_structures "later".)
39 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
41 "ListDigraph::Arc". You can add new items to the graph using the member
42 functions \ref ListDigraph::addNode() "addNode()" and
43 \ref ListDigraph::addArc() "addArc()", like this:
47 ListDigraph::Node a = g.addNode();
48 ListDigraph::Node b = g.addNode();
49 ListDigraph::Node c = g.addNode();
50 ListDigraph::Node d = g.addNode();
58 Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
61 ListDigraph::Arc arc = g.addArc(a,c);
64 \note Using ListDigraph, you can also remove nodes or arcs with the
65 \ref ListDigraph::erase() "erase()" function. Moreover, this class provides
66 several other operations, see its \ref ListDigraph "documentation" for more
68 However, not all graph structures support the addition and deletion
69 of graph items (see \ref sec_graph_concepts).
71 Two important member functions of the directed graphs are
72 \ref concepts::Digraph::source() "source()"
73 and \ref concepts::Digraph::target() "target()".
74 They give back the two end nodes of an arc.
77 if (g.source(arc) == g.target(arc))
78 std::cout << "This is a loop arc" << std::endl;
81 Each graph item has a unique integer identifier, which can be obtained using
82 the \ref concepts::Digraph::id() "id()" function of the graph structure.
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;
89 \note In fact, the \c Node and \c Arc types are typically simple wrapper
90 classes for a single \c int value, which is the identifier of the item.
93 [SEC]sec_digraph_it[SEC] Iterators
95 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
97 code will count the number of nodes in a graph.
101 for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
103 std::cout << "Number of nodes: " << cnt << std::endl;
106 Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
107 is an iterator class that traverses the
108 nodes. You must give the graph to the constructor and the iterator will be set
109 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
111 be set to \ref INVALID.
113 \note \ref INVALID is a global constant, which converts to
114 and compares with each and every iterator in LEMON.
116 The iterators convert to the corresponding item types. For example,
117 to following code will add a full graph to the existing nodes.
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);
125 \note Contrary to the iterators in the C++ Standard Template Library (STL),
126 LEMON iterators are convertible to the corresponding
127 item types without having to use \c %operator*(). This is not confusing,
128 since the program context always indicates whether we refer to the iterator
129 or to the graph item (they do not have conflicting functionalities).
131 The graph items are also ordered by the 'less than' operator (with respect to
132 their integer identifiers). For example, this code will add only one of the
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);
141 \warning The order in which the iterators visit the items is
142 undefined. The only thing you may assume that they will list the items
143 in the same order until the graph is not changed.
145 Similarly, \ref concepts::Digraph::ArcIt "ListDigraph::ArcIt"
146 lists the arcs. Its usage is the same as of
147 \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt".
151 for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
153 std::cout << "Number of arcs: " << cnt << std::endl;
156 Finally, you can also list the arcs starting from or arriving at a
158 \ref concepts::Digraph::OutArcIt "ListDigraph::OutArcIt"
160 \ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
161 Their usage is the same, but you must also give the node to the constructor.
165 for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a)
167 std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl;
171 [SEC]sec_digraph_maps[SEC] Maps
173 The concept of "maps" is another fundamental part of LEMON. They allow assigning
174 values of any type to the nodes or arcs of a graph. The standard maps
175 provided by the graph structures have a couple of nice properties.
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.
187 \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).
190 So, if you want to assign \c int values to each node, you have to allocate a
191 \ref concepts::Digraph::NodeMap "NodeMap<int>".
194 ListDigraph::NodeMap<int> map(g);
197 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.
203 map[c] = map[a] + map[b];
206 Any kind of data can be assigned to the graph items.
209 ListDigraph::NodeMap<std::string> label(g);
214 For a more complex example, let us create a map that assigns a unique
215 integer number to each node.
218 ListDigraph::NodeMap<int> id(g);
220 for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
224 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
226 of outgoing arcs for each node in a map.
229 ListDigraph::NodeMap<int> out_deg(g, 0);
231 for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
232 out_deg[g.source(a)]++;
235 \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
237 map will be initialized with the default constructor of the