source: lemon-tutorial/basics.dox @ 32:ef12f83752f6

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2010
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

namespace lemon {
/**
[PAGE]sec_basics[PAGE] Basic Concepts

Throughout the tutorial we are working with the \ref lemon namespace.
To save a lot of typing, we assume that a

\code
using namespace lemon;
\endcode

directive is added to the code at the beginning.

[SEC]sec_digraphs[SEC] Directed Graphs

This section tells you how to work with a directed graph (\e digraph,
for short) in LEMON. Here we use \ref ListDigraph, the most versatile
digraph structure. (The library also provides other digraph types,
see \ref sec_graph_structures "later".)

The nodes and the arcs of a graph are identified by two data types called
\ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc
"ListDigraph::Arc". You can add new items to the graph using the member
functions \ref ListDigraph::addNode() "addNode()" and
\ref ListDigraph::addArc() "addArc()", like this:

\code
  ListDigraph g;
  ListDigraph::Node a = g.addNode();
  ListDigraph::Node b = g.addNode();
  ListDigraph::Node c = g.addNode();
  ListDigraph::Node d = g.addNode();

  g.addArc(a,b);
  g.addArc(b,c);
  g.addArc(c,d);
  g.addArc(d,a);
\endcode

Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:

\code
  ListDigraph::Arc arc = g.addArc(a,c);
\endcode

\note Using ListDigraph, you can also remove nodes or arcs with the
\ref ListDigraph::erase() "erase()" function. Moreover, this class provides
several other operations, see its \ref ListDigraph "documentation" for more
information.
However, not all graph structures support the addition and deletion
of graph items (see \ref sec_graph_concepts).

Two important member functions of the directed graphs are
\ref concepts::Digraph::source() "source()"
and \ref concepts::Digraph::target() "target()".
They give back the two end nodes of an arc.

\code
  if (g.source(arc) == g.target(arc))
    std::cout << "This is a loop arc" << std::endl;
\endcode

Each graph item has a unique integer identifier, which can be obtained using
the \ref concepts::Digraph::id() "id()" function of the graph structure.

\code
  std::cout << "Arc " << g.id(arc) << " goes from node "
    << g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl;
\endcode

\note In fact, the \c Node and \c Arc types are typically simple wrapper
classes for a single \c int value, which is the identifier of the item.


[SEC]sec_digraph_it[SEC] Iterators

Let us assume you want to list the elements of the graph. For this purpose,
the graph structures provide several iterators. For example, the following
code will count the number of nodes in a graph.

\code
  int cnt = 0;
  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
    cnt++;
  std::cout << "Number of nodes: " << cnt << std::endl;
\endcode

Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
is an iterator class that traverses the
nodes. You must give the graph to the constructor and the iterator will be set
to the first node. The next node is obtained by the prefix ++
operator. If there are no more nodes in the graph, the iterator will
be set to \ref INVALID.

\note \ref INVALID is a global constant, which converts to
and compares with each and every iterator in LEMON.

The iterators convert to the corresponding item types. For example,
to following code will add a full graph to the existing nodes.

\code
  for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
    for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
      if (u != v) g.addArc(u, v);
\endcode

\note Contrary to the iterators in the C++ Standard Template Library (STL),
LEMON iterators are convertible to the corresponding
item types without having to use \c %operator*(). This is not confusing,
since the program context always indicates whether we refer to the iterator
or to the graph item (they do not have conflicting functionalities).

The graph items are also ordered by the 'less than' operator (with respect to
their integer identifiers). For example, this code will add only one of the
opposite arcs.

\code
  for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
    for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
      if (u < v) g.addArc(u, v);
\endcode

\warning The order in which the iterators visit the items is
undefined. The only thing you may assume that they will list the items
in the same order until the graph is not changed.

Similarly, \ref concepts::Digraph::ArcIt "ListDigraph::ArcIt"
lists the arcs. Its usage is the same as of
\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt".

\code
  int cnt = 0;
  for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
    cnt++;
  std::cout << "Number of arcs: " << cnt << std::endl;
\endcode

Finally, you can also list the arcs starting from or arriving at a
certain node with
\ref concepts::Digraph::OutArcIt "ListDigraph::OutArcIt"
and
\ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
Their usage is the same, but you must also give the node to the constructor.

\code
  int cnt = 0;
  for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a)
    cnt++;
  std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl;
\endcode


[SEC]sec_digraph_maps[SEC] Maps

The concept of "maps" is another fundamental part of LEMON. They allow assigning
values of any type to the nodes or arcs of a graph. The standard maps
provided by the graph structures have a couple of nice properties.

- \e Fast. Accessing (reading/writing) the values is as fast as a
  simple vector reading/writing.
- \e Dynamic. Whenever you need, you
  can allocate new maps in your code, just as a local variable. So when you
  leave its scope, it will be de-allocated automatically.
- \e Automatic. If you add new nodes or arcs to the graph, the storage of the
  existing maps will automatically expanded and the new slots will be
  initialized. On the removal of an item, the corresponding values in the maps
  are properly destructed.

\note These maps must not be confused with \c std::map, since they provide
O(1) time acces to the elements instead of O(log n).

So, if you want to assign \c int values to each node, you have to allocate a
\ref concepts::Digraph::NodeMap "NodeMap<int>".

\code
  ListDigraph::NodeMap<int> map(g);
\endcode

As you see, the graph you want to assign a map is given to the
constructor. Then you can access its element as if it were a vector.

\code
  map[a] = 2;
  map[b] = 3;
  map[c] = map[a] + map[b];
\endcode

Any kind of data can be assigned to the graph items.

\code
  ListDigraph::NodeMap<std::string> label(g);
  label[a] = "Node A";
  label[b] = "Node B";
\endcode

For a more complex example, let us create a map that assigns a unique
integer number to each node.

\code
  ListDigraph::NodeMap<int> id(g);
  int cnt = 0;
  for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
    id[n] = cnt++;
\endcode

When you create a map, you can also give an initial value of the elements
as a second parameter. For example, the following code puts the number
of outgoing arcs for each node in a map.

\code
  ListDigraph::NodeMap<int> out_deg(g, 0);

  for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
    out_deg[g.source(a)]++;
\endcode

\warning The initial value will apply to the currently existing items only. If
you add new nodes/arcs to the graph, then the corresponding values in the
map will be initialized with the default constructor of the
type.

[TRAILER]
*/
}