Changeset 37:c8be1109221b in lemon-tutorial

Timestamp:

02/20/10 21:54:52 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Improve and extend basics page

Files:

• basics.dox (modified) (11 diffs)
• toc.txt (modified) (1 diff)

basics.dox

@@ -32 +32 @@
 [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
@@ -44 +60 @@
 
 \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);
+  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
 
@@ -59 +72 @@
 
 \code
-  ListDigraph::Arc arc = g.addArc(a,c);
+  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
 
@@ -72 +92 @@
 \ref concepts::Digraph::source() "source()"
 and \ref concepts::Digraph::target() "target()".
-They give back the two end nodes of an arc.
-
-\code
-  if (g.source(arc) == g.target(arc))
+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 unique integer identifier, which can be obtained using
-the \ref concepts::Digraph::id() "id()" function of the graph structure.
+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
@@ -94 +116 @@
 
 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
+the graph structures provide several \e iterators. For example, the following
 code will count the number of nodes in a graph.
 
@@ -104 +126 @@
 \endcode
 
-Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
-is an iterator class that traverses the
-nodes. You must give the graph to the constructor and the iterator will be set
+\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.
-
-\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.
+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
@@ -163 +199 @@
 \code
   int cnt = 0;
-  for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a)
+  for (ListDigraph::OutArcIt a(g, x); a != INVALID; ++a)
     cnt++;
-  std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl;
-\endcode
+  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.
 
 
@@ -184 +225 @@
   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 acces to the elements instead of O(log n).
+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
@@ -199 +245 @@
 
 \code
-  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;
+  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)
-    id[n] = cnt++;
+    label[n] = ch++;
 \endcode
 
@@ -228 +275 @@
 \code
   ListDigraph::NodeMap<int> out_deg(g, 0);
-
   for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
     out_deg[g.source(a)]++;
@@ -238 +284 @@
 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]
 */

toc.txt

@@ -7 +7 @@
 ** sec_digraph_it
 ** sec_digraph_maps
+** sec_naming_conv
 *_sec_algorithms
 **_sec_alg_graph_search