1.1 --- a/basics.dox Sun Feb 14 21:32:19 2010 +0100
1.2 +++ b/basics.dox Sun Feb 14 22:19:50 2010 +0100
1.3 @@ -20,8 +20,8 @@
1.4 /**
1.5 [PAGE]sec_basics[PAGE] Basic Concepts
1.6
1.7 -Throughout the document we are working with the \ref lemon namespace.
1.8 -To save a lot of typing we assume that a
1.9 +Throughout the tutorial we are working with the \ref lemon namespace.
1.10 +To save a lot of typing, we assume that a
1.11
1.12 \code
1.13 using namespace lemon;
1.14 @@ -31,13 +31,16 @@
1.15
1.16 [SEC]sec_digraphs[SEC] Directed Graphs
1.17
1.18 -This section tells you how to work with a directed graph. We use ListDigraph,
1.19 -the most versatile graph structure.
1.20 +This section tells you how to work with a directed graph (\e digraph,
1.21 +for short) in LEMON.
1.22 +The library provides various digraph structures for both general and special
1.23 +purposes. Here we use \c ListDigraph, the most versatile digraph type.
1.24
1.25 -The nodes and the arcs of a graph are identified by two datatypes called
1.26 -ListDigraph::Node and ListDigraph::Arc. You can add new components the graph
1.27 -by the \ref ListDigraph::addNode() "addNode()" and the
1.28 -\ref ListDigraph::addArc() "addArc()" member functions, like this:
1.29 +The nodes and the arcs of a graph are identified by two data types called
1.30 +\ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc
1.31 +"ListDigraph::Arc". You can add new items to the graph using the member
1.32 +functions \ref ListDigraph::addNode() "addNode()" and
1.33 +\ref ListDigraph::addArc() "addArc()", like this:
1.34
1.35 \code
1.36 ListDigraph g;
1.37 @@ -55,66 +58,85 @@
1.38 Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
1.39
1.40 \code
1.41 - ListDigraph::Arc diag = g.addArc(a,c);
1.42 + ListDigraph::Arc arc = g.addArc(a,c);
1.43 \endcode
1.44
1.45 -\note You can also remove nodes or arcs with the
1.46 -\ref ListDigraph::erase() "erase()", but this operation may not be available
1.47 -with all graph structures.
1.48 +\note Using ListDigraph, you can also remove nodes or arcs with the
1.49 +\ref ListDigraph::erase() "erase()" function.
1.50 +However, not all graph structures support the addition and deletion
1.51 +of graph items.
1.52
1.53 -Two other important member functions are
1.54 +Two important member functions of the directed graphs are
1.55 \ref concepts::Digraph::source() "source()"
1.56 and \ref concepts::Digraph::target() "target()".
1.57 -They gives back the to end nodes of and arc.
1.58 +They give back the two end nodes of an arc.
1.59
1.60 \code
1.61 - if(g.source(e)==g.target(e))
1.62 + if (g.source(arc) == g.target(arc))
1.63 std::cout << "This is a loop arc" << std::endl;
1.64 \endcode
1.65
1.66 +Each graph item has a unique integer identifier, which can be obtained using
1.67 +the \ref concepts::Digraph::id() "id()" function of the graph structure.
1.68 +
1.69 +\code
1.70 + std::cout << "Arc " << g.id(arc) << " goes from node "
1.71 + << g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl;
1.72 +\endcode
1.73 +
1.74 +\note In fact, the \c Node and \c Arc types are typically simple wrapper
1.75 +classes for a single \c int value, which is the identifier of the item.
1.76 +
1.77
1.78 [SEC]sec_digraph_it[SEC] Iterators
1.79
1.80 -Now assume you want to list the elements of the graph. For this purpose the
1.81 -the graphs provides several iterators. For example for following code will
1.82 -cound the number of nodes in a graph.
1.83 +Let us assume you want to list the elements of the graph. For this purpose,
1.84 +the graph structures provide several iterators. For example, the following
1.85 +code will count the number of nodes in a graph.
1.86
1.87 \code
1.88 int cnt = 0;
1.89 - for(ListDigraph::NodeIt n(g); n!=INVALID; ++n)
1.90 + for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
1.91 cnt++;
1.92 std::cout << "Number of nodes: " << cnt << std::endl;
1.93 \endcode
1.94
1.95 Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
1.96 -is an iterator class that lists the
1.97 -nodes. You must give the graph to the constructor and it will be set
1.98 +is an iterator class that traverses the
1.99 +nodes. You must give the graph to the constructor and the iterator will be set
1.100 to the first node. The next node is obtained by the prefix ++
1.101 -operator. If there is no more nodes in the graph, the iterator will
1.102 +operator. If there are no more nodes in the graph, the iterator will
1.103 be set to \ref INVALID.
1.104
1.105 -\note \ref INVALID is a global constant in lemon and it converts to
1.106 -and compares with each and every iterators in LEMON.
1.107 +\note \ref INVALID is a global constant, which converts to
1.108 +and compares with each and every iterator in LEMON.
1.109
1.110 -The iterators converts to the corresponding descriptor types. For example
1.111 +The iterators convert to the corresponding item types. For example,
1.112 to following code will add a full graph to the existing nodes.
1.113
1.114 \code
1.115 - for(ListDigraph::NodeIt u(g); u!=INVALID; ++u)
1.116 - for(ListDigraph::NodeIt v(g); v!=INVALID; ++v)
1.117 - if(u!=v) g.addArc(u,v);
1.118 + for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
1.119 + for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
1.120 + if (u != v) g.addArc(u, v);
1.121 \endcode
1.122
1.123 -The items are also ordered by the 'less than' operator. For example this
1.124 -code will add only one of the opposite arcs.
1.125 +\note Contrary to the iterators in the C++ Standard Template Library (STL),
1.126 +LEMON iterators are convertible to the corresponding
1.127 +item types without having to use \c %operator*(). This is not confusing, since the
1.128 +program context always indicates whether we refer to the iterator or to the graph
1.129 +item (they do not have conflicting functionalities).
1.130 +
1.131 +The graph items are also ordered by the 'less than' operator (with respect to
1.132 +their integer identifiers). For example, this code will add only one of the
1.133 +opposite arcs.
1.134
1.135 \code
1.136 - for(ListDigraph::NodeIt u(g); u!=INVALID; ++u)
1.137 - for(ListDigraph::NodeIt v(g); v!=INVALID; ++v)
1.138 - if(u<v) g.addArc(u,v);
1.139 + for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
1.140 + for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
1.141 + if (u < v) g.addArc(u, v);
1.142 \endcode
1.143
1.144 -\warning There order in which the iterator visits the items is
1.145 +\warning The order in which the iterators visit the items is
1.146 undefined. The only thing you may assume that they will list the items
1.147 in the same order until the graph is not changed.
1.148
1.149 @@ -124,7 +146,7 @@
1.150
1.151 \code
1.152 int cnt = 0;
1.153 - for(ListDigraph::ArcIt a(g); a!=INVALID; ++a)
1.154 + for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
1.155 cnt++;
1.156 std::cout << "Number of arcs: " << cnt << std::endl;
1.157 \endcode
1.158 @@ -134,11 +156,11 @@
1.159 \ref concepts::Digraph::OutArcIt "ListDigraph::OutArcIt"
1.160 and
1.161 \ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
1.162 -Their usage are the same, but you must also give the node to the constructor.
1.163 +Their usage is the same, but you must also give the node to the constructor.
1.164
1.165 \code
1.166 int cnt = 0;
1.167 - for(ListDigraph::OutArcIt a(g,start); a!=INVALID; ++a)
1.168 + for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a)
1.169 cnt++;
1.170 std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl;
1.171 \endcode
1.172 @@ -146,12 +168,12 @@
1.173
1.174 [SEC]sec_digraph_maps[SEC] Maps
1.175
1.176 -The concept of "Maps" is another fundamental part of LEMON. They allow assigning
1.177 -values of any type to the nodes or arcs of a graph. The default maps
1.178 +The concept of "maps" is another fundamental part of LEMON. They allow assigning
1.179 +values of any type to the nodes or arcs of a graph. The standard maps
1.180 provided by the graph structures have a couple of nice properties.
1.181
1.182 -- \e Fast. Accessing (reading/writing) the values are as fast as a
1.183 - simple vector reading/writing
1.184 +- \e Fast. Accessing (reading/writing) the values is as fast as a
1.185 + simple vector reading/writing.
1.186 - \e Dynamic. Whenever you need, you
1.187 can allocate new maps in your code, just as a local variable. So when you
1.188 leave its scope, it will be de-allocated automatically.
1.189 @@ -160,8 +182,11 @@
1.190 initialized. On the removal of an item, the corresponding values in the maps
1.191 are properly destructed.
1.192
1.193 +\note These maps must not be confused with \c std::map, since they provide
1.194 +O(1) time acces to the elements instead of O(log n).
1.195 +
1.196 So, if you want to assign \c int values to each node, you have to allocate a
1.197 -\ref concepts::Digraph::Node Map "NodeMap<int>".
1.198 +\ref concepts::Digraph::NodeMap "NodeMap<int>".
1.199
1.200 \code
1.201 ListDigraph::NodeMap<int> map(g);
1.202 @@ -171,33 +196,41 @@
1.203 constructor. Then you can access its element as if it were a vector.
1.204
1.205 \code
1.206 - map[a]=2;
1.207 - map[b]=3;
1.208 - map[c]=map[a]+map[b];
1.209 + map[a] = 2;
1.210 + map[b] = 3;
1.211 + map[c] = map[a] + map[b];
1.212 \endcode
1.213
1.214 -As a more complex example, let's create a map that assigns a unique
1.215 +Any kind of data can be assigned to the graph items.
1.216 +
1.217 +\code
1.218 + ListDigraph::NodeMap<std::string> label(g);
1.219 + label[a] = "Node A";
1.220 + label[b] = "Node B";
1.221 +\endcode
1.222 +
1.223 +For a more complex example, let us create a map that assigns a unique
1.224 integer number to each node.
1.225
1.226 \code
1.227 ListDigraph::NodeMap<int> id(g);
1.228 - int cnt=0;
1.229 - for(ListDigraph::NodeIt n(g); n!=INVALID; ++n, ++cnt)
1.230 - id[n]=cnt;
1.231 + int cnt = 0;
1.232 + for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
1.233 + id[n] = cnt++;
1.234 \endcode
1.235
1.236 -You can also give an initial value of the elements as a second parameter.
1.237 -
1.238 -For example the following code puts the number of outgoing edges in a map.
1.239 +When you create a map, you can also give an initial value of the elements
1.240 +as a second parameter. For example, the following code puts the number
1.241 +of outgoing arcs for each node in a map.
1.242
1.243 \code
1.244 - ListDigraph::NodeMap<int> out_deg(g,0);
1.245 + ListDigraph::NodeMap<int> out_deg(g, 0);
1.246
1.247 - for(ListDigraph::ArcIt a(g); a!=INVALID; ++a)
1.248 + for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
1.249 out_deg[g.source(a)]++;
1.250 \endcode
1.251
1.252 -\warning The initial value will apply to the existing items only. If
1.253 +\warning The initial value will apply to the currently existing items only. If
1.254 you add new nodes/arcs to the graph, then the corresponding values in the
1.255 map will be initialized with the default constructor of the
1.256 type.