COIN-OR::LEMON - Graph Library

source: lemon-tutorial/basics.dox @ 26:a40eafb6066d

Last change on this file since 26:a40eafb6066d was 26:a40eafb6066d, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Distinguish section names from the doc groups

File size: 6.2 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 document 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. We use ListDigraph,
35the most versatile graph structure.
36
37The nodes and the arcs of a graph are identified by two datatypes called
38ListDigraph::Node and ListDigraph::Arc. You can add new components the graph
39by the \ref ListDigraph::addNode() "addNode()" and the
40\ref ListDigraph::addArc() "addArc()" member functions, like this:
41
42\code
43  ListDigraph g;
44  ListDigraph::Node a = g.addNode();
45  ListDigraph::Node b = g.addNode();
46  ListDigraph::Node c = g.addNode();
47  ListDigraph::Node d = g.addNode();
48
49  g.addArc(a,b);
50  g.addArc(b,c);
51  g.addArc(c,d);
52  g.addArc(d,a);
53\endcode
54
55Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
56
57\code
58  ListDigraph::Arc diag = g.addArc(a,c);
59\endcode
60
61\note You can also remove nodes or arcs with the
62\ref ListDigraph::erase() "erase()", but this operation may not be available
63with all graph structures.
64
65Two other important member functions are
66\ref concepts::Digraph::source() "source()"
67and \ref concepts::Digraph::target() "target()".
68They gives back the to end nodes of and arc.
69
70\code
71  if(g.source(e)==g.target(e))
72    std::cout << "This is a loop arc" << std::endl;
73\endcode
74
75
76[SEC]sec_digraph_it[SEC] Iterators
77
78Now assume you want to list the elements of the graph. For this purpose the
79the graphs provides several iterators. For example for following code will
80cound the number of nodes in a graph.
81
82\code
83  int cnt = 0;
84  for(ListDigraph::NodeIt n(g); n!=INVALID; ++n)
85    cnt++;
86  std::cout << "Number of nodes: " << cnt << std::endl;
87\endcode
88
89Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
90is an iterator class that lists the
91nodes. You must give the graph to the constructor and it will be set
92to the first node. The next node is obtained by the prefix ++
93operator.  If there is no more nodes in the graph, the iterator will
94be set to \ref INVALID.
95
96\note \ref INVALID is a global constant in lemon and it converts to
97and compares with each and every iterators in LEMON.
98
99The iterators converts to the corresponding descriptor types. For example
100to following code will add a full graph to the existing nodes.
101
102\code
103  for(ListDigraph::NodeIt u(g); u!=INVALID; ++u)
104    for(ListDigraph::NodeIt v(g); v!=INVALID; ++v)
105      if(u!=v) g.addArc(u,v);
106\endcode
107
108The items are also ordered by the 'less than' operator. For example this
109code will add only one of the opposite arcs.
110
111\code
112  for(ListDigraph::NodeIt u(g); u!=INVALID; ++u)
113    for(ListDigraph::NodeIt v(g); v!=INVALID; ++v)
114      if(u<v) g.addArc(u,v);
115\endcode
116
117\warning There order in which the iterator visits the items is
118undefined. The only thing you may assume that they will list the items
119in the same order until the graph is not changed.
120
121Similarly, \ref concepts::Digraph::ArcIt "ListDigraph::ArcIt"
122lists the arcs. Its usage is the same as of
123\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt".
124
125\code
126  int cnt = 0;
127  for(ListDigraph::ArcIt a(g); a!=INVALID; ++a)
128    cnt++;
129  std::cout << "Number of arcs: " << cnt << std::endl;
130\endcode
131
132Finally, you can also list the arcs starting from or arriving at a
133certain node with
134\ref concepts::Digraph::OutArcIt "ListDigraph::OutArcIt"
135and
136\ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
137Their usage are the same, but you must also give the node to the constructor.
138
139\code
140  int cnt = 0;
141  for(ListDigraph::OutArcIt a(g,start); a!=INVALID; ++a)
142    cnt++;
143  std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl;
144\endcode
145
146
147[SEC]sec_digraph_maps[SEC] Maps
148
149The concept of "Maps" is another fundamental part of LEMON. They allow assigning
150values of any type to the nodes or arcs of a graph. The default maps
151provided by the graph structures have a couple of nice properties.
152
153- \e Fast. Accessing (reading/writing) the values are as fast as a
154  simple vector reading/writing
155- \e Dynamic. Whenever you need, you
156  can allocate new maps in your code, just as a local variable. So when you
157  leave its scope, it will be de-allocated automatically.
158- \e Automatic. If you add new nodes or arcs to the graph, the storage of the
159  existing maps will automatically expanded and the new slots will be
160  initialized. On the removal of an item, the corresponding values in the maps
161  are properly destructed.
162
163So, if you want to assign \c int values to each node, you have to allocate a
164\ref concepts::Digraph::Node Map "NodeMap<int>".
165
166\code
167  ListDigraph::NodeMap<int> map(g);
168\endcode
169
170As you see, the graph you want to assign a map is given to the
171constructor. Then you can access its element as if it were a vector.
172
173\code
174  map[a]=2;
175  map[b]=3;
176  map[c]=map[a]+map[b];
177\endcode
178
179As a more complex example, let's create a map that assigns a unique
180integer number to each node.
181
182\code
183  ListDigraph::NodeMap<int> id(g);
184  int cnt=0;
185  for(ListDigraph::NodeIt n(g); n!=INVALID; ++n, ++cnt)
186    id[n]=cnt;
187\endcode
188
189You can also give an initial value of the elements as a second parameter.
190
191For example the following code puts the number of outgoing edges in a map.
192
193\code
194  ListDigraph::NodeMap<int> out_deg(g,0);
195
196  for(ListDigraph::ArcIt a(g); a!=INVALID; ++a)
197    out_deg[g.source(a)]++;
198\endcode
199
200\warning The initial value will apply to the existing items only. If
201you add new nodes/arcs to the graph, then the corresponding values in the
202map will be initialized with the default constructor of the
203type.
204
205[TRAILER]
206*/
207}
Note: See TracBrowser for help on using the repository browser.