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