/* -*- 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

 The core features of LEMON are the data structures, algorithms and auxiliary

 tools that make it possible to represent graphs and working with them easily

 and efficiently.

 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".)

 For using \ref ListDigraph, you must include the header file

 \ref list_graph.h like this:

 \code

 #include <lemon/list_graph.h>

 \endcode

 The default constructor of the class creates an empty digraph.

 \code

   ListDigraph g;

 \endcode

 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::Node x = g.addNode();

   ListDigraph::Node y = g.addNode();

   ListDigraph::Node z = g.addNode();

   g.addArc(x,y);

   g.addArc(y,z);

   g.addArc(z,x);

 \endcode

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

 \code

   ListDigraph::Arc arc = g.addArc(x,z);

 \endcode

 Parallel and loop arcs are also supported.

 \code

   ListDigraph::Arc parallel = g.addArc(x,y);

   ListDigraph::Arc loop = g.addArc(x,x);

 \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 (as \c Node objects).

 \code

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

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

 \endcode

 Each graph item has a non-negative integer identifier, which can be obtained

 using the \ref concepts::Digraph::id() "id()" function of the graph structure.

 These identifiers are unique with respect to a certain item type in a graph,

 but a node and an arc may have the same id.

 \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 \e 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

 \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"

 is an iterator class that lists the nodes.

 The name of an iterator type starts with a name that refers to

 the iterated objects and ends with 'It'.

 Using \ref concepts::Digraph::NodeIt "NodeIt", you must give

 the graph object 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, which is exploited in the stop condition of

 the loop.

 \note \ref INVALID is a constant in the \ref lemon namespace, which converts to

 and compares with each and every iterator and graph item type.

 Thus, you can even assign \ref INVALID to a \c Node or \c Arc object.

 The iterators convert to the corresponding item types.

 For example, the identifiers of the nodes can be printed like this.

 \code

   for (ListDigraph::NodeIt n(g); n != INVALID; ++n)

     std::cout << g.id(n) << std::endl;

 \endcode

 As an other example, the following code adds 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, x); a != INVALID; ++a)

     cnt++;

   std::cout << "Number of arcs leaving the node 'x': " << cnt << std::endl;

 \endcode

 \note LEMON provides functions for counting the nodes and arcs of a digraph:

 \ref countNodes(), \ref countArcs(), \ref countInArcs(), \ref countOutArcs().

 Using them is not just simpler than the above loops, but they could be much

 faster, since several graph types support constant time item counting.

 [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.

 By principle, the graph classes represent only the pure structure of

 the graph (i.e. the nodes and arcs and their connections).

 All data that are assigned to the items of the graph (e.g. node labels,

 arc costs or capacities) must be stored separately using maps.

 \note These maps must not be confused with \c std::map, since they provide

 O(1) time access 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[x] = 2;

   map[y] = 3;

   map[z] = map[x] + map[y];

 \endcode

 Any kind of data can be assigned to the graph items (assuming that the type

 has a default constructor).

 \code

   ListDigraph::NodeMap<std::string> name(g);

   name[x] = "Node A";

   name[y] = "Node B";

 \endcode

 As a more complex example, let us create a map that assigns \c char labels

 to the nodes.

 \code

   ListDigraph::NodeMap<char> label(g);

   char ch = 'A';

   for (ListDigraph::NodeIt n(g); n != INVALID; ++n)

     label[n] = ch++;

 \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.

 [SEC]sec_naming_conv[SEC] Naming Conventions

 In LEMON, there are some naming conventions you might already notice

 in the above examples.

 The name of a source file is written lowercase and the words are separated with

 underscores (e.g. \ref list_graph.h). All header files are located in the

 \c %lemon subdirectory, so you can include them like this.

 \code

 #include <lemon/header_file.h>

 \endcode

 The name of a class or any type looks like the following

 (e.g. \ref ListDigraph, \ref concepts::Digraph::Node "Node",

 \ref concepts::Digraph::NodeIt "NodeIt" etc.).

 \code

 AllWordsCapitalizedWithoutUnderscores

 \endcode

 The name of a function looks like the following

 (e.g. \ref concepts::Digraph::source() "source()",

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

 \ref countNodes(), \ref countArcs() etc.).

 \code

 firstWordLowerCaseRestCapitalizedWithoutUnderscores

 \endcode

 The names of constants and macros look like the following

 (e.g. \ref INVALID).

 \code

 ALL_UPPER_CASE_WITH_UNDERSCORES

 \endcode

 For more details, see \ref coding_style.

 [TRAILER]

 */

 }