Changeset 27:b453a59230c8 in lemon-tutorial

Timestamp:

02/14/10 22:19:50 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Rework and extend the section of basic concepts

File:

• basics.dox (modified) (9 diffs)

basics.dox

@@ -21 +21 @@
 [PAGE]sec_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
+Throughout the tutorial we are working with the \ref lemon namespace.
+To save a lot of typing, we assume that a
 
 \code
@@ -32 +32 @@
 [SEC]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:
+This section tells you how to work with a directed graph (\e digraph,
+for short) in LEMON.
+The library provides various digraph structures for both general and special
+purposes. Here we use \c ListDigraph, the most versatile digraph type.
+
+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
@@ -56 +59 @@
 
 \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
+  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.
+However, not all graph structures support the addition and deletion
+of graph items.
+
+Two important member functions of the directed graphs 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))
+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
 
-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)
+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;
@@ -88 +103 @@
 
 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
+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 is no more nodes in the graph, the iterator will
+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 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
+\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
-
-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
+  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.
@@ -125 +147 @@
 \code
   int cnt = 0;
-  for(ListDigraph::ArcIt a(g); a!=INVALID; ++a)
+  for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
     cnt++;
   std::cout << "Number of arcs: " << cnt << std::endl;
@@ -135 +157 @@
 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)
+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;
@@ -147 +169 @@
 [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 default 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 are as fast as a
-  simple vector reading/writing
+- \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
@@ -161 +183 @@
   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::Node Map "NodeMap<int>".
+\ref concepts::Digraph::NodeMap "NodeMap<int>".
 
 \code
@@ -172 +197 @@
 
 \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
+  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, ++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)
+  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 existing items only. If
+\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