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@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@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
alpar@21:   ListDigraph g;
alpar@21:   ListDigraph::Node a = g.addNode();
alpar@21:   ListDigraph::Node b = g.addNode();
alpar@21:   ListDigraph::Node c = g.addNode();
alpar@21:   ListDigraph::Node d = g.addNode();
alpar@21: 
alpar@21:   g.addArc(a,b);
alpar@21:   g.addArc(b,c);
alpar@21:   g.addArc(c,d);
alpar@21:   g.addArc(d,a);
alpar@21: \endcode
alpar@21: 
alpar@21: Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
alpar@21: 
alpar@21: \code
kpeter@27:   ListDigraph::Arc arc = g.addArc(a,c);
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@27: They give back the two end nodes of an arc.
alpar@21: 
alpar@21: \code
kpeter@27:   if (g.source(arc) == g.target(arc))
alpar@21:     std::cout << "This is a loop arc" << std::endl;
alpar@21: \endcode
alpar@21: 
kpeter@27: Each graph item has a unique integer identifier, which can be obtained using
kpeter@27: the \ref concepts::Digraph::id() "id()" function of the graph structure.
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@27: the graph structures provide several 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: 
alpar@21: Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
kpeter@27: is an iterator class that traverses the
kpeter@27: nodes. You must give the graph 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
alpar@21: be set to \ref INVALID.
alpar@21: 
kpeter@27: \note \ref INVALID is a global constant, which converts to
kpeter@27: and compares with each and every iterator in LEMON.
alpar@21: 
kpeter@27: The iterators convert to the corresponding item types. For example,
alpar@21: to following code will add a full graph to the 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@27:   for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a)
alpar@21:     cnt++;
alpar@21:   std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl;
alpar@21: \endcode
alpar@21: 
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.
alpar@21: 
kpeter@27: \note These maps must not be confused with \c std::map, since they provide
kpeter@27: O(1) time acces 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@27:   map[a] = 2;
kpeter@27:   map[b] = 3;
kpeter@27:   map[c] = map[a] + map[b];
alpar@21: \endcode
alpar@21: 
kpeter@27: Any kind of data can be assigned to the graph items.
kpeter@27: 
kpeter@27: \code
kpeter@27:   ListDigraph::NodeMap<std::string> label(g);
kpeter@27:   label[a] = "Node A";
kpeter@27:   label[b] = "Node B";
kpeter@27: \endcode
kpeter@27: 
kpeter@27: For a more complex example, let us create a map that assigns a unique
alpar@21: integer number to each node.
alpar@21: 
alpar@21: \code
alpar@21:   ListDigraph::NodeMap<int> id(g);
kpeter@27:   int cnt = 0;
kpeter@27:   for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
kpeter@27:     id[n] = cnt++;
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);
alpar@21: 
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: 
alpar@21: [TRAILER]
alpar@21: */
alpar@21: }