basics.dox
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 28 Feb 2010 19:38:57 +0100
changeset 53 0f695eac7e07
parent 32 ef12f83752f6
permissions -rw-r--r--
Show demo files in the menu
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
 *
kpeter@32
     5
 * Copyright (C) 2003-2010
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
kpeter@27
    23
Throughout the tutorial we are working with the \ref lemon namespace.
kpeter@27
    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
kpeter@37
    34
The core features of LEMON are the data structures, algorithms and auxiliary
kpeter@37
    35
tools that make it possible to represent graphs and working with them easily
kpeter@37
    36
and efficiently.
kpeter@27
    37
This section tells you how to work with a directed graph (\e digraph,
kpeter@28
    38
for short) in LEMON. Here we use \ref ListDigraph, the most versatile
kpeter@28
    39
digraph structure. (The library also provides other digraph types,
kpeter@28
    40
see \ref sec_graph_structures "later".)
alpar@21
    41
kpeter@37
    42
For using \ref ListDigraph, you must include the header file
kpeter@37
    43
\ref list_graph.h like this:
kpeter@37
    44
kpeter@37
    45
\code
kpeter@37
    46
#include <lemon/list_graph.h>
kpeter@37
    47
\endcode
kpeter@37
    48
kpeter@37
    49
The default constructor of the class creates an empty digraph.
kpeter@37
    50
kpeter@37
    51
\code
kpeter@37
    52
  ListDigraph g;
kpeter@37
    53
\endcode
kpeter@37
    54
kpeter@27
    55
The nodes and the arcs of a graph are identified by two data types called
kpeter@27
    56
\ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc
kpeter@27
    57
"ListDigraph::Arc". You can add new items to the graph using the member
kpeter@27
    58
functions \ref ListDigraph::addNode() "addNode()" and
kpeter@27
    59
\ref ListDigraph::addArc() "addArc()", like this:
alpar@21
    60
alpar@21
    61
\code
kpeter@37
    62
  ListDigraph::Node x = g.addNode();
kpeter@37
    63
  ListDigraph::Node y = g.addNode();
kpeter@37
    64
  ListDigraph::Node z = g.addNode();
alpar@21
    65
kpeter@37
    66
  g.addArc(x,y);
kpeter@37
    67
  g.addArc(y,z);
kpeter@37
    68
  g.addArc(z,x);
alpar@21
    69
\endcode
alpar@21
    70
alpar@21
    71
Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
alpar@21
    72
alpar@21
    73
\code
kpeter@37
    74
  ListDigraph::Arc arc = g.addArc(x,z);
kpeter@37
    75
\endcode
kpeter@37
    76
kpeter@37
    77
Parallel and loop arcs are also supported.
kpeter@37
    78
kpeter@37
    79
\code
kpeter@37
    80
  ListDigraph::Arc parallel = g.addArc(x,y);
kpeter@37
    81
  ListDigraph::Arc loop = g.addArc(x,x);
alpar@21
    82
\endcode
alpar@21
    83
kpeter@27
    84
\note Using ListDigraph, you can also remove nodes or arcs with the
kpeter@28
    85
\ref ListDigraph::erase() "erase()" function. Moreover, this class provides
kpeter@28
    86
several other operations, see its \ref ListDigraph "documentation" for more
kpeter@28
    87
information.
kpeter@27
    88
However, not all graph structures support the addition and deletion
kpeter@28
    89
of graph items (see \ref sec_graph_concepts).
alpar@21
    90
kpeter@27
    91
Two important member functions of the directed graphs are
alpar@21
    92
\ref concepts::Digraph::source() "source()"
alpar@21
    93
and \ref concepts::Digraph::target() "target()".
kpeter@37
    94
They give back the two end nodes of an arc (as \c Node objects).
alpar@21
    95
alpar@21
    96
\code
kpeter@37
    97
  if (g.source(loop) == g.target(loop))
alpar@21
    98
    std::cout << "This is a loop arc" << std::endl;
alpar@21
    99
\endcode
alpar@21
   100
kpeter@37
   101
Each graph item has a non-negative integer identifier, which can be obtained
kpeter@37
   102
using the \ref concepts::Digraph::id() "id()" function of the graph structure.
kpeter@37
   103
These identifiers are unique with respect to a certain item type in a graph,
kpeter@37
   104
but a node and an arc may have the same id.
kpeter@27
   105
kpeter@27
   106
\code
kpeter@27
   107
  std::cout << "Arc " << g.id(arc) << " goes from node "
kpeter@27
   108
    << g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl;
kpeter@27
   109
\endcode
kpeter@27
   110
kpeter@27
   111
\note In fact, the \c Node and \c Arc types are typically simple wrapper
kpeter@27
   112
classes for a single \c int value, which is the identifier of the item.
kpeter@27
   113
kpeter@26
   114
kpeter@26
   115
[SEC]sec_digraph_it[SEC] Iterators
alpar@21
   116
kpeter@27
   117
Let us assume you want to list the elements of the graph. For this purpose,
kpeter@37
   118
the graph structures provide several \e iterators. For example, the following
kpeter@27
   119
code will count the number of nodes in a graph.
alpar@21
   120
alpar@21
   121
\code
alpar@21
   122
  int cnt = 0;
kpeter@27
   123
  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
alpar@21
   124
    cnt++;
alpar@21
   125
  std::cout << "Number of nodes: " << cnt << std::endl;
alpar@21
   126
\endcode
alpar@21
   127
kpeter@37
   128
\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
kpeter@37
   129
is an iterator class that lists the nodes.
kpeter@37
   130
The name of an iterator type starts with a name that refers to
kpeter@37
   131
the iterated objects and ends with 'It'.
kpeter@37
   132
kpeter@37
   133
Using \ref concepts::Digraph::NodeIt "NodeIt", you must give
kpeter@37
   134
the graph object to the constructor and the iterator will be set
alpar@21
   135
to the first node. The next node is obtained by the prefix ++
kpeter@27
   136
operator. If there are no more nodes in the graph, the iterator will
kpeter@37
   137
be set to \ref INVALID, which is exploited in the stop condition of
kpeter@37
   138
the loop.
alpar@21
   139
kpeter@37
   140
\note \ref INVALID is a constant in the \ref lemon namespace, which converts to
kpeter@37
   141
and compares with each and every iterator and graph item type.
kpeter@37
   142
Thus, you can even assign \ref INVALID to a \c Node or \c Arc object.
alpar@21
   143
kpeter@37
   144
The iterators convert to the corresponding item types.
kpeter@37
   145
For example, the identifiers of the nodes can be printed like this.
kpeter@37
   146
kpeter@37
   147
\code
kpeter@37
   148
  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
kpeter@37
   149
    std::cout << g.id(n) << std::endl;
kpeter@37
   150
\endcode
kpeter@37
   151
kpeter@37
   152
As an other example, the following code adds a full graph to the
kpeter@37
   153
existing nodes.
alpar@21
   154
alpar@21
   155
\code
kpeter@27
   156
  for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
kpeter@27
   157
    for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
kpeter@27
   158
      if (u != v) g.addArc(u, v);
alpar@21
   159
\endcode
alpar@21
   160
kpeter@27
   161
\note Contrary to the iterators in the C++ Standard Template Library (STL),
kpeter@27
   162
LEMON iterators are convertible to the corresponding
kpeter@32
   163
item types without having to use \c %operator*(). This is not confusing,
kpeter@32
   164
since the program context always indicates whether we refer to the iterator
kpeter@32
   165
or to the graph item (they do not have conflicting functionalities).
kpeter@27
   166
kpeter@27
   167
The graph items are also ordered by the 'less than' operator (with respect to
kpeter@27
   168
their integer identifiers). For example, this code will add only one of the
kpeter@27
   169
opposite arcs.
alpar@21
   170
alpar@21
   171
\code
kpeter@27
   172
  for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
kpeter@27
   173
    for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
kpeter@27
   174
      if (u < v) g.addArc(u, v);
alpar@21
   175
\endcode
alpar@21
   176
kpeter@27
   177
\warning The order in which the iterators visit the items is
alpar@21
   178
undefined. The only thing you may assume that they will list the items
alpar@21
   179
in the same order until the graph is not changed.
alpar@21
   180
alpar@21
   181
Similarly, \ref concepts::Digraph::ArcIt "ListDigraph::ArcIt"
alpar@21
   182
lists the arcs. Its usage is the same as of
alpar@21
   183
\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt".
alpar@21
   184
alpar@21
   185
\code
alpar@21
   186
  int cnt = 0;
kpeter@27
   187
  for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
alpar@21
   188
    cnt++;
alpar@21
   189
  std::cout << "Number of arcs: " << cnt << std::endl;
alpar@21
   190
\endcode
alpar@21
   191
alpar@21
   192
Finally, you can also list the arcs starting from or arriving at a
kpeter@32
   193
certain node with
alpar@21
   194
\ref concepts::Digraph::OutArcIt "ListDigraph::OutArcIt"
alpar@21
   195
and
alpar@21
   196
\ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
kpeter@27
   197
Their usage is the same, but you must also give the node to the constructor.
alpar@21
   198
alpar@21
   199
\code
alpar@21
   200
  int cnt = 0;
kpeter@37
   201
  for (ListDigraph::OutArcIt a(g, x); a != INVALID; ++a)
alpar@21
   202
    cnt++;
kpeter@37
   203
  std::cout << "Number of arcs leaving the node 'x': " << cnt << std::endl;
alpar@21
   204
\endcode
alpar@21
   205
kpeter@37
   206
\note LEMON provides functions for counting the nodes and arcs of a digraph:
kpeter@37
   207
\ref countNodes(), \ref countArcs(), \ref countInArcs(), \ref countOutArcs().
kpeter@37
   208
Using them is not just simpler than the above loops, but they could be much
kpeter@37
   209
faster, since several graph types support constant time item counting.
kpeter@37
   210
kpeter@26
   211
kpeter@26
   212
[SEC]sec_digraph_maps[SEC] Maps
alpar@21
   213
kpeter@27
   214
The concept of "maps" is another fundamental part of LEMON. They allow assigning
kpeter@27
   215
values of any type to the nodes or arcs of a graph. The standard maps
alpar@21
   216
provided by the graph structures have a couple of nice properties.
alpar@21
   217
kpeter@27
   218
- \e Fast. Accessing (reading/writing) the values is as fast as a
kpeter@27
   219
  simple vector reading/writing.
alpar@21
   220
- \e Dynamic. Whenever you need, you
alpar@21
   221
  can allocate new maps in your code, just as a local variable. So when you
alpar@21
   222
  leave its scope, it will be de-allocated automatically.
alpar@21
   223
- \e Automatic. If you add new nodes or arcs to the graph, the storage of the
alpar@21
   224
  existing maps will automatically expanded and the new slots will be
alpar@21
   225
  initialized. On the removal of an item, the corresponding values in the maps
alpar@21
   226
  are properly destructed.
kpeter@37
   227
  
kpeter@37
   228
By principle, the graph classes represent only the pure structure of
kpeter@37
   229
the graph (i.e. the nodes and arcs and their connections).
kpeter@37
   230
All data that are assigned to the items of the graph (e.g. node labels,
kpeter@37
   231
arc costs or capacities) must be stored separately using maps.
alpar@21
   232
kpeter@27
   233
\note These maps must not be confused with \c std::map, since they provide
kpeter@37
   234
O(1) time access to the elements instead of O(log n).
kpeter@27
   235
alpar@21
   236
So, if you want to assign \c int values to each node, you have to allocate a
kpeter@27
   237
\ref concepts::Digraph::NodeMap "NodeMap<int>".
alpar@21
   238
alpar@21
   239
\code
alpar@21
   240
  ListDigraph::NodeMap<int> map(g);
alpar@21
   241
\endcode
alpar@21
   242
alpar@21
   243
As you see, the graph you want to assign a map is given to the
alpar@21
   244
constructor. Then you can access its element as if it were a vector.
alpar@21
   245
alpar@21
   246
\code
kpeter@37
   247
  map[x] = 2;
kpeter@37
   248
  map[y] = 3;
kpeter@37
   249
  map[z] = map[x] + map[y];
alpar@21
   250
\endcode
alpar@21
   251
kpeter@37
   252
Any kind of data can be assigned to the graph items (assuming that the type
kpeter@37
   253
has a default constructor).
kpeter@27
   254
kpeter@27
   255
\code
kpeter@37
   256
  ListDigraph::NodeMap<std::string> name(g);
kpeter@37
   257
  name[x] = "Node A";
kpeter@37
   258
  name[y] = "Node B";
kpeter@27
   259
\endcode
kpeter@27
   260
kpeter@37
   261
As a more complex example, let us create a map that assigns \c char labels
kpeter@37
   262
to the nodes.
alpar@21
   263
alpar@21
   264
\code
kpeter@37
   265
  ListDigraph::NodeMap<char> label(g);
kpeter@37
   266
  char ch = 'A';
kpeter@27
   267
  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
kpeter@37
   268
    label[n] = ch++;
alpar@21
   269
\endcode
alpar@21
   270
kpeter@27
   271
When you create a map, you can also give an initial value of the elements
kpeter@27
   272
as a second parameter. For example, the following code puts the number
kpeter@27
   273
of outgoing arcs for each node in a map.
alpar@21
   274
alpar@21
   275
\code
kpeter@27
   276
  ListDigraph::NodeMap<int> out_deg(g, 0);
kpeter@27
   277
  for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
alpar@21
   278
    out_deg[g.source(a)]++;
alpar@21
   279
\endcode
alpar@21
   280
kpeter@27
   281
\warning The initial value will apply to the currently existing items only. If
alpar@21
   282
you add new nodes/arcs to the graph, then the corresponding values in the
alpar@21
   283
map will be initialized with the default constructor of the
alpar@21
   284
type.
alpar@21
   285
kpeter@37
   286
kpeter@37
   287
[SEC]sec_naming_conv[SEC] Naming Conventions
kpeter@37
   288
kpeter@37
   289
In LEMON, there are some naming conventions you might already notice
kpeter@37
   290
in the above examples.
kpeter@37
   291
kpeter@37
   292
The name of a source file is written lowercase and the words are separated with
kpeter@37
   293
underscores (e.g. \ref list_graph.h). All header files are located in the
kpeter@37
   294
\c %lemon subdirectory, so you can include them like this.
kpeter@37
   295
kpeter@37
   296
\code
kpeter@37
   297
#include <lemon/header_file.h>
kpeter@37
   298
\endcode
kpeter@37
   299
kpeter@37
   300
The name of a class or any type looks like the following
kpeter@37
   301
(e.g. \ref ListDigraph, \ref concepts::Digraph::Node "Node",
kpeter@37
   302
\ref concepts::Digraph::NodeIt "NodeIt" etc.).
kpeter@37
   303
kpeter@37
   304
\code
kpeter@37
   305
AllWordsCapitalizedWithoutUnderscores
kpeter@37
   306
\endcode
kpeter@37
   307
kpeter@37
   308
The name of a function looks like the following
kpeter@37
   309
(e.g. \ref concepts::Digraph::source() "source()",
kpeter@37
   310
\ref concepts::Digraph::source() "target()",
kpeter@37
   311
\ref countNodes(), \ref countArcs() etc.).
kpeter@37
   312
kpeter@37
   313
\code
kpeter@37
   314
firstWordLowerCaseRestCapitalizedWithoutUnderscores
kpeter@37
   315
\endcode
kpeter@37
   316
kpeter@37
   317
The names of constants and macros look like the following
kpeter@37
   318
(e.g. \ref INVALID).
kpeter@37
   319
kpeter@37
   320
\code
kpeter@37
   321
ALL_UPPER_CASE_WITH_UNDERSCORES
kpeter@37
   322
\endcode
kpeter@37
   323
kpeter@37
   324
For more details, see \ref coding_style.
kpeter@37
   325
alpar@21
   326
[TRAILER]
alpar@21
   327
*/
alpar@21
   328
}