/* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  * Copyright (C) 2003-2009

  * 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]basics[PAGE] Basic Concepts

 Throughout the document 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]digraphs[SEC] Directed Graphs

 This section tells you how to work with a directed graph. We use ListDigraph,

 the most versatile graph structure.

 The nodes and the arcs of a graph are identified by two datatypes called

 ListDigraph::Node and ListDigraph::Arc. You can add new components the graph

 by the \ref ListDigraph::addNode() "addNode()" and the

 \ref ListDigraph::addArc() "addArc()" member functions, 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 diag = g.addArc(a,c);

 \endcode

 \note You can also remove nodes or arcs with the

 \ref ListDigraph::erase() "erase()", but this operation may not be available

 with all graph structures.

 Two other important member functions are

 \ref concepts::Digraph::source() "source()"

 and \ref concepts::Digraph::target() "target()".

 They gives back the to end nodes of and arc.

 \code

   if(g.source(e)==g.target(e))

     std::cout << "This is a loop arc" << std::endl;

 \endcode

 [SEC]digraphs_it[SEC] Iterators

 Now assume you want to list the elements of the graph. For this purpose the

 the graphs provides several iterators. For example for following code will

 cound 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 lists the

 nodes. You must give the graph to the constructor and it will be set

 to the first node. The next node is obtained by the prefix ++

 operator.  If there is no more nodes in the graph, the iterator will

 be set to \ref INVALID.

 \note \ref INVALID is a global constant in lemon and it converts to

 and compares with each and every iterators in LEMON.

 The iterators converts to the corresponding descriptor 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

 The items are also ordered by the 'less than' operator. 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 There order in which the iterator visits 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 are 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]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 default maps

 provided by the graph structures have a couple of nice properties.

 - \e Fast. Accessing (reading/writing) the values are 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.

 So, if you want to assign \c int values to each node, you have to allocate a

 \ref concepts::Digraph::Node Map "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

 As a more complex example, let's 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, ++cnt)

     id[n]=cnt;

 \endcode

 You can also give an initial value of the elements as a second parameter.

 For example the following code puts the number of outgoing edges 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 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]

 */

 }