COIN-OR::LEMON - Graph Library

source: lemon-tutorial/basics.dox @ 21:e4bd4ee05e3f

Last change on this file since 21:e4bd4ee05e3f was 21:e4bd4ee05e3f, checked in by Alpar Juttner <alpar@…>, 12 years ago

Basic graph operation + intro to the default maps

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