alpar@21: /* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@21:  *
alpar@21:  * This file is a part of LEMON, a generic C++ optimization library.
alpar@21:  *
kpeter@32:  * Copyright (C) 2003-2010
alpar@21:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@21:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@21:  *
alpar@21:  * Permission to use, modify and distribute this software is granted
alpar@21:  * provided that this copyright notice appears in all copies. For
alpar@21:  * precise terms see the accompanying LICENSE file.
alpar@21:  *
alpar@21:  * This software is provided "AS IS" with no warranty of any kind,
alpar@21:  * express or implied, and with no claim as to its suitability for any
alpar@21:  * purpose.
alpar@21:  *
alpar@21:  */
alpar@21: 
alpar@21: namespace lemon {
alpar@21: /**
kpeter@26: [PAGE]sec_basics[PAGE] Basic Concepts
alpar@21: 
kpeter@27: Throughout the tutorial we are working with the \ref lemon namespace.
kpeter@27: To save a lot of typing, we assume that a
alpar@21: 
alpar@21: \code
alpar@21: using namespace lemon;
alpar@21: \endcode
alpar@21: 
alpar@21: directive is added to the code at the beginning.
alpar@21: 
kpeter@26: [SEC]sec_digraphs[SEC] Directed Graphs
alpar@21: 
kpeter@37: The core features of LEMON are the data structures, algorithms and auxiliary
kpeter@37: tools that make it possible to represent graphs and working with them easily
kpeter@37: and efficiently.
kpeter@27: This section tells you how to work with a directed graph (\e digraph,
kpeter@28: for short) in LEMON. Here we use \ref ListDigraph, the most versatile
kpeter@28: digraph structure. (The library also provides other digraph types,
kpeter@28: see \ref sec_graph_structures "later".)
alpar@21: 
kpeter@37: For using \ref ListDigraph, you must include the header file
kpeter@37: \ref list_graph.h like this:
kpeter@37: 
kpeter@37: \code
kpeter@37: #include <lemon/list_graph.h>
kpeter@37: \endcode
kpeter@37: 
kpeter@37: The default constructor of the class creates an empty digraph.
kpeter@37: 
kpeter@37: \code
kpeter@37:   ListDigraph g;
kpeter@37: \endcode
kpeter@37: 
kpeter@27: The nodes and the arcs of a graph are identified by two data types called
kpeter@27: \ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc
kpeter@27: "ListDigraph::Arc". You can add new items to the graph using the member
kpeter@27: functions \ref ListDigraph::addNode() "addNode()" and
kpeter@27: \ref ListDigraph::addArc() "addArc()", like this:
alpar@21: 
alpar@21: \code
kpeter@37:   ListDigraph::Node x = g.addNode();
kpeter@37:   ListDigraph::Node y = g.addNode();
kpeter@37:   ListDigraph::Node z = g.addNode();
alpar@21: 
kpeter@37:   g.addArc(x,y);
kpeter@37:   g.addArc(y,z);
kpeter@37:   g.addArc(z,x);
alpar@21: \endcode
alpar@21: 
alpar@21: Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
alpar@21: 
alpar@21: \code
kpeter@37:   ListDigraph::Arc arc = g.addArc(x,z);
kpeter@37: \endcode
kpeter@37: 
kpeter@37: Parallel and loop arcs are also supported.
kpeter@37: 
kpeter@37: \code
kpeter@37:   ListDigraph::Arc parallel = g.addArc(x,y);
kpeter@37:   ListDigraph::Arc loop = g.addArc(x,x);
alpar@21: \endcode
alpar@21: 
kpeter@27: \note Using ListDigraph, you can also remove nodes or arcs with the
kpeter@28: \ref ListDigraph::erase() "erase()" function. Moreover, this class provides
kpeter@28: several other operations, see its \ref ListDigraph "documentation" for more
kpeter@28: information.
kpeter@27: However, not all graph structures support the addition and deletion
kpeter@28: of graph items (see \ref sec_graph_concepts).
alpar@21: 
kpeter@27: Two important member functions of the directed graphs are
alpar@21: \ref concepts::Digraph::source() "source()"
alpar@21: and \ref concepts::Digraph::target() "target()".
kpeter@37: They give back the two end nodes of an arc (as \c Node objects).
alpar@21: 
alpar@21: \code
kpeter@37:   if (g.source(loop) == g.target(loop))
alpar@21:     std::cout << "This is a loop arc" << std::endl;
alpar@21: \endcode
alpar@21: 
kpeter@37: Each graph item has a non-negative integer identifier, which can be obtained
kpeter@37: using the \ref concepts::Digraph::id() "id()" function of the graph structure.
kpeter@37: These identifiers are unique with respect to a certain item type in a graph,
kpeter@37: but a node and an arc may have the same id.
kpeter@27: 
kpeter@27: \code
kpeter@27:   std::cout << "Arc " << g.id(arc) << " goes from node "
kpeter@27:     << g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl;
kpeter@27: \endcode
kpeter@27: 
kpeter@27: \note In fact, the \c Node and \c Arc types are typically simple wrapper
kpeter@27: classes for a single \c int value, which is the identifier of the item.
kpeter@27: 
kpeter@26: 
kpeter@26: [SEC]sec_digraph_it[SEC] Iterators
alpar@21: 
kpeter@27: Let us assume you want to list the elements of the graph. For this purpose,
kpeter@37: the graph structures provide several \e iterators. For example, the following
kpeter@27: code will count the number of nodes in a graph.
alpar@21: 
alpar@21: \code
alpar@21:   int cnt = 0;
kpeter@27:   for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
alpar@21:     cnt++;
alpar@21:   std::cout << "Number of nodes: " << cnt << std::endl;
alpar@21: \endcode
alpar@21: 
kpeter@37: \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
kpeter@37: is an iterator class that lists the nodes.
kpeter@37: The name of an iterator type starts with a name that refers to
kpeter@37: the iterated objects and ends with 'It'.
kpeter@37: 
kpeter@37: Using \ref concepts::Digraph::NodeIt "NodeIt", you must give
kpeter@37: the graph object to the constructor and the iterator will be set
alpar@21: to the first node. The next node is obtained by the prefix ++
kpeter@27: operator. If there are no more nodes in the graph, the iterator will
kpeter@37: be set to \ref INVALID, which is exploited in the stop condition of
kpeter@37: the loop.
alpar@21: 
kpeter@37: \note \ref INVALID is a constant in the \ref lemon namespace, which converts to
kpeter@37: and compares with each and every iterator and graph item type.
kpeter@37: Thus, you can even assign \ref INVALID to a \c Node or \c Arc object.
alpar@21: 
kpeter@37: The iterators convert to the corresponding item types.
kpeter@37: For example, the identifiers of the nodes can be printed like this.
kpeter@37: 
kpeter@37: \code
kpeter@37:   for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
kpeter@37:     std::cout << g.id(n) << std::endl;
kpeter@37: \endcode
kpeter@37: 
kpeter@37: As an other example, the following code adds a full graph to the
kpeter@37: existing nodes.
alpar@21: 
alpar@21: \code
kpeter@27:   for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
kpeter@27:     for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
kpeter@27:       if (u != v) g.addArc(u, v);
alpar@21: \endcode
alpar@21: 
kpeter@27: \note Contrary to the iterators in the C++ Standard Template Library (STL),
kpeter@27: LEMON iterators are convertible to the corresponding
kpeter@32: item types without having to use \c %operator*(). This is not confusing,
kpeter@32: since the program context always indicates whether we refer to the iterator
kpeter@32: or to the graph item (they do not have conflicting functionalities).
kpeter@27: 
kpeter@27: The graph items are also ordered by the 'less than' operator (with respect to
kpeter@27: their integer identifiers). For example, this code will add only one of the
kpeter@27: opposite arcs.
alpar@21: 
alpar@21: \code
kpeter@27:   for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
kpeter@27:     for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
kpeter@27:       if (u < v) g.addArc(u, v);
alpar@21: \endcode
alpar@21: 
kpeter@27: \warning The order in which the iterators visit the items is
alpar@21: undefined. The only thing you may assume that they will list the items
alpar@21: in the same order until the graph is not changed.
alpar@21: 
alpar@21: Similarly, \ref concepts::Digraph::ArcIt "ListDigraph::ArcIt"
alpar@21: lists the arcs. Its usage is the same as of
alpar@21: \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt".
alpar@21: 
alpar@21: \code
alpar@21:   int cnt = 0;
kpeter@27:   for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
alpar@21:     cnt++;
alpar@21:   std::cout << "Number of arcs: " << cnt << std::endl;
alpar@21: \endcode
alpar@21: 
alpar@21: Finally, you can also list the arcs starting from or arriving at a
kpeter@32: certain node with
alpar@21: \ref concepts::Digraph::OutArcIt "ListDigraph::OutArcIt"
alpar@21: and
alpar@21: \ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
kpeter@27: Their usage is the same, but you must also give the node to the constructor.
alpar@21: 
alpar@21: \code
alpar@21:   int cnt = 0;
kpeter@37:   for (ListDigraph::OutArcIt a(g, x); a != INVALID; ++a)
alpar@21:     cnt++;
kpeter@37:   std::cout << "Number of arcs leaving the node 'x': " << cnt << std::endl;
alpar@21: \endcode
alpar@21: 
kpeter@37: \note LEMON provides functions for counting the nodes and arcs of a digraph:
kpeter@37: \ref countNodes(), \ref countArcs(), \ref countInArcs(), \ref countOutArcs().
kpeter@37: Using them is not just simpler than the above loops, but they could be much
kpeter@37: faster, since several graph types support constant time item counting.
kpeter@37: 
kpeter@26: 
kpeter@26: [SEC]sec_digraph_maps[SEC] Maps
alpar@21: 
kpeter@27: The concept of "maps" is another fundamental part of LEMON. They allow assigning
kpeter@27: values of any type to the nodes or arcs of a graph. The standard maps
alpar@21: provided by the graph structures have a couple of nice properties.
alpar@21: 
kpeter@27: - \e Fast. Accessing (reading/writing) the values is as fast as a
kpeter@27:   simple vector reading/writing.
alpar@21: - \e Dynamic. Whenever you need, you
alpar@21:   can allocate new maps in your code, just as a local variable. So when you
alpar@21:   leave its scope, it will be de-allocated automatically.
alpar@21: - \e Automatic. If you add new nodes or arcs to the graph, the storage of the
alpar@21:   existing maps will automatically expanded and the new slots will be
alpar@21:   initialized. On the removal of an item, the corresponding values in the maps
alpar@21:   are properly destructed.
kpeter@37:   
kpeter@37: By principle, the graph classes represent only the pure structure of
kpeter@37: the graph (i.e. the nodes and arcs and their connections).
kpeter@37: All data that are assigned to the items of the graph (e.g. node labels,
kpeter@37: arc costs or capacities) must be stored separately using maps.
alpar@21: 
kpeter@27: \note These maps must not be confused with \c std::map, since they provide
kpeter@37: O(1) time access to the elements instead of O(log n).
kpeter@27: 
alpar@21: So, if you want to assign \c int values to each node, you have to allocate a
kpeter@27: \ref concepts::Digraph::NodeMap "NodeMap<int>".
alpar@21: 
alpar@21: \code
alpar@21:   ListDigraph::NodeMap<int> map(g);
alpar@21: \endcode
alpar@21: 
alpar@21: As you see, the graph you want to assign a map is given to the
alpar@21: constructor. Then you can access its element as if it were a vector.
alpar@21: 
alpar@21: \code
kpeter@37:   map[x] = 2;
kpeter@37:   map[y] = 3;
kpeter@37:   map[z] = map[x] + map[y];
alpar@21: \endcode
alpar@21: 
kpeter@37: Any kind of data can be assigned to the graph items (assuming that the type
kpeter@37: has a default constructor).
kpeter@27: 
kpeter@27: \code
kpeter@37:   ListDigraph::NodeMap<std::string> name(g);
kpeter@37:   name[x] = "Node A";
kpeter@37:   name[y] = "Node B";
kpeter@27: \endcode
kpeter@27: 
kpeter@37: As a more complex example, let us create a map that assigns \c char labels
kpeter@37: to the nodes.
alpar@21: 
alpar@21: \code
kpeter@37:   ListDigraph::NodeMap<char> label(g);
kpeter@37:   char ch = 'A';
kpeter@27:   for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
kpeter@37:     label[n] = ch++;
alpar@21: \endcode
alpar@21: 
kpeter@27: When you create a map, you can also give an initial value of the elements
kpeter@27: as a second parameter. For example, the following code puts the number
kpeter@27: of outgoing arcs for each node in a map.
alpar@21: 
alpar@21: \code
kpeter@27:   ListDigraph::NodeMap<int> out_deg(g, 0);
kpeter@27:   for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
alpar@21:     out_deg[g.source(a)]++;
alpar@21: \endcode
alpar@21: 
kpeter@27: \warning The initial value will apply to the currently existing items only. If
alpar@21: you add new nodes/arcs to the graph, then the corresponding values in the
alpar@21: map will be initialized with the default constructor of the
alpar@21: type.
alpar@21: 
kpeter@37: 
kpeter@37: [SEC]sec_naming_conv[SEC] Naming Conventions
kpeter@37: 
kpeter@37: In LEMON, there are some naming conventions you might already notice
kpeter@37: in the above examples.
kpeter@37: 
kpeter@37: The name of a source file is written lowercase and the words are separated with
kpeter@37: underscores (e.g. \ref list_graph.h). All header files are located in the
kpeter@37: \c %lemon subdirectory, so you can include them like this.
kpeter@37: 
kpeter@37: \code
kpeter@37: #include <lemon/header_file.h>
kpeter@37: \endcode
kpeter@37: 
kpeter@37: The name of a class or any type looks like the following
kpeter@37: (e.g. \ref ListDigraph, \ref concepts::Digraph::Node "Node",
kpeter@37: \ref concepts::Digraph::NodeIt "NodeIt" etc.).
kpeter@37: 
kpeter@37: \code
kpeter@37: AllWordsCapitalizedWithoutUnderscores
kpeter@37: \endcode
kpeter@37: 
kpeter@37: The name of a function looks like the following
kpeter@37: (e.g. \ref concepts::Digraph::source() "source()",
kpeter@37: \ref concepts::Digraph::source() "target()",
kpeter@37: \ref countNodes(), \ref countArcs() etc.).
kpeter@37: 
kpeter@37: \code
kpeter@37: firstWordLowerCaseRestCapitalizedWithoutUnderscores
kpeter@37: \endcode
kpeter@37: 
kpeter@37: The names of constants and macros look like the following
kpeter@37: (e.g. \ref INVALID).
kpeter@37: 
kpeter@37: \code
kpeter@37: ALL_UPPER_CASE_WITH_UNDERSCORES
kpeter@37: \endcode
kpeter@37: 
kpeter@37: For more details, see \ref coding_style.
kpeter@37: 
alpar@21: [TRAILER]
alpar@21: */
alpar@21: }