lemon-tutorial: comparison basics.dox

equal deleted inserted replaced

-:e8800e69e6b7
+:8fe2bd6f4d1d
 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 g;
+ListDigraph::Node x = g.addNode();
-ListDigraph::Node a = g.addNode();
+ListDigraph::Node y = g.addNode();
-ListDigraph::Node b = g.addNode();
+ListDigraph::Node z = g.addNode();
-ListDigraph::Node c = g.addNode();
-ListDigraph::Node d = g.addNode();
+g.addArc(x,y);
+g.addArc(y,z);
-g.addArc(a,b);
+g.addArc(z,x);
-g.addArc(b,c);
-g.addArc(c,d);
-g.addArc(d,a);
 \endcode
 Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
 \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
 \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
 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.
+They give back the two end nodes of an arc (as \c Node objects).
 \code
-if (g.source(arc) == g.target(arc))
+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
+Each graph item has a non-negative integer identifier, which can be obtained
-the \ref concepts::Digraph::id() "id()" function of the graph structure.
+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
 [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 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.
 \code
 int cnt = 0;
 for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
 cnt++;
 std::cout << "Number of nodes: " << cnt << std::endl;
 \endcode
-Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
+\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
-is an iterator class that traverses the
+is an iterator class that lists the nodes.
-nodes. You must give the graph to the constructor and the iterator will be set
+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.
+be set to \ref INVALID, which is exploited in the stop condition of
+the loop.
-\note \ref INVALID is a global constant, which converts to
-and compares with each and every iterator in LEMON.
+\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.
-The iterators convert to the corresponding item types. For example,
+Thus, you can even assign \ref INVALID to a \c Node or \c Arc object.
-to following code will add a full graph to the existing nodes.
+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);
 \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, 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;
+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
 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 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
 \ref concepts::Digraph::NodeMap "NodeMap<int>".
 \code
 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[a] = 2;
+map[x] = 2;
-map[b] = 3;
+map[y] = 3;
-map[c] = map[a] + map[b];
+map[z] = map[x] + map[y];
 \endcode
-Any kind of data can be assigned to the graph items.
+Any kind of data can be assigned to the graph items (assuming that the type
+has a default constructor).
-\code
-ListDigraph::NodeMap<std::string> label(g);
+\code
-label[a] = "Node A";
+ListDigraph::NodeMap<std::string> name(g);
-label[b] = "Node B";
+name[x] = "Node A";
-\endcode
+name[y] = "Node B";
+\endcode
-For a more complex example, let us create a map that assigns a unique
-integer number to each node.
+As a more complex example, let us create a map that assigns \c char labels
+to the nodes.
-\code
-ListDigraph::NodeMap<int> id(g);
+\code
-int cnt = 0;
+ListDigraph::NodeMap<char> label(g);
+char ch = 'A';
 for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
-id[n] = cnt++;
+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]
 */
 }

changeset 53	0f695eac7e07
parent 32	ef12f83752f6