1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/basics.dox Mon Mar 23 09:29:58 2009 +0000
1.3 @@ -0,0 +1,205 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +namespace lemon {
1.23 +/**
1.24 +[PAGE]basics[PAGE] Basic Concepts
1.25 +
1.26 +Throughout the document we are working with the \ref lemon namespace.
1.27 +To save a lot of typing we assume that a
1.28 +
1.29 +\code
1.30 +using namespace lemon;
1.31 +\endcode
1.32 +
1.33 +directive is added to the code at the beginning.
1.34 +
1.35 +[SEC]digraphs[SEC] Directed Graphs
1.36 +
1.37 +This section tells you how to work with a directed graph. We use ListDigraph,
1.38 +the most versatile graph structure.
1.39 +
1.40 +The nodes and the arcs of a graph are identified by two datatypes called
1.41 +ListDigraph::Node and ListDigraph::Arc. You can add new components the graph
1.42 +by the \ref ListDigraph::addNode() "addNode()" and the
1.43 +\ref ListDigraph::addArc() "addArc()" member functions, like this:
1.44 +
1.45 +\code
1.46 + ListDigraph g;
1.47 + ListDigraph::Node a = g.addNode();
1.48 + ListDigraph::Node b = g.addNode();
1.49 + ListDigraph::Node c = g.addNode();
1.50 + ListDigraph::Node d = g.addNode();
1.51 +
1.52 + g.addArc(a,b);
1.53 + g.addArc(b,c);
1.54 + g.addArc(c,d);
1.55 + g.addArc(d,a);
1.56 +\endcode
1.57 +
1.58 +Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
1.59 +
1.60 +\code
1.61 + ListDigraph::Arc diag = g.addArc(a,c);
1.62 +\endcode
1.63 +
1.64 +\note You can also remove nodes or arcs with the
1.65 +\ref ListDigraph::erase() "erase()", but this operation may not be available
1.66 +with all graph structures.
1.67 +
1.68 +Two other important member functions are
1.69 +\ref concepts::Digraph::source() "source()"
1.70 +and \ref concepts::Digraph::target() "target()".
1.71 +They gives back the to end nodes of and arc.
1.72 +
1.73 +\code
1.74 + if(g.source(e)==g.target(e))
1.75 + std::cout << "This is a loop arc" << std::endl;
1.76 +\endcode
1.77 +
1.78 +[SEC]digraphs_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 +
1.84 +\code
1.85 + int cnt = 0;
1.86 + for(ListDigraph::NodeIt n(g); n!=INVALID; ++n)
1.87 + cnt++;
1.88 + std::cout << "Number of nodes: " << cnt << std::endl;
1.89 +\endcode
1.90 +
1.91 +Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
1.92 +is an iterator class that lists the
1.93 +nodes. You must give the graph to the constructor and it will be set
1.94 +to the first node. The next node is obtained by the prefix ++
1.95 +operator. If there is no more nodes in the graph, the iterator will
1.96 +be set to \ref INVALID.
1.97 +
1.98 +\note \ref INVALID is a global constant in lemon and it converts to
1.99 +and compares with each and every iterators in LEMON.
1.100 +
1.101 +The iterators converts to the corresponding descriptor types. For example
1.102 +to following code will add a full graph to the existing nodes.
1.103 +
1.104 +\code
1.105 + for(ListDigraph::NodeIt u(g); u!=INVALID; ++u)
1.106 + for(ListDigraph::NodeIt v(g); v!=INVALID; ++v)
1.107 + if(u!=v) g.addArc(u,v);
1.108 +\endcode
1.109 +
1.110 +The items are also ordered by the 'less than' operator. For example this
1.111 +code will add only one of the opposite arcs.
1.112 +
1.113 +\code
1.114 + for(ListDigraph::NodeIt u(g); u!=INVALID; ++u)
1.115 + for(ListDigraph::NodeIt v(g); v!=INVALID; ++v)
1.116 + if(u<v) g.addArc(u,v);
1.117 +\endcode
1.118 +
1.119 +\warning There order in which the iterator visits the items is
1.120 +undefined. The only thing you may assume that they will list the items
1.121 +in the same order until the graph is not changed.
1.122 +
1.123 +Similarly, \ref concepts::Digraph::ArcIt "ListDigraph::ArcIt"
1.124 +lists the arcs. Its usage is the same as of
1.125 +\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt".
1.126 +
1.127 +\code
1.128 + int cnt = 0;
1.129 + for(ListDigraph::ArcIt a(g); a!=INVALID; ++a)
1.130 + cnt++;
1.131 + std::cout << "Number of arcs: " << cnt << std::endl;
1.132 +\endcode
1.133 +
1.134 +Finally, you can also list the arcs starting from or arriving at a
1.135 +certain node with
1.136 +\ref concepts::Digraph::OutArcIt "ListDigraph::OutArcIt"
1.137 +and
1.138 +\ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
1.139 +Their usage are the same, but you must also give the node to the constructor.
1.140 +
1.141 +\code
1.142 + int cnt = 0;
1.143 + for(ListDigraph::OutArcIt a(g,start); a!=INVALID; ++a)
1.144 + cnt++;
1.145 + std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl;
1.146 +\endcode
1.147 +
1.148 +[SEC]maps[SEC] Maps
1.149 +
1.150 +The concept of "Maps" is another fundamental part of LEMON. They allow assigning
1.151 +values of any type to the nodes or arcs of a graph. The default maps
1.152 +provided by the graph structures have a couple of nice properties.
1.153 +
1.154 +- \e Fast. Accessing (reading/writing) the values are as fast as a
1.155 + simple vector reading/writing
1.156 +- \e Dynamic. Whenever you need, you
1.157 + can allocate new maps in your code, just as a local variable. So when you
1.158 + leave its scope, it will be de-allocated automatically.
1.159 +- \e Automatic. If you add new nodes or arcs to the graph, the storage of the
1.160 + existing maps will automatically expanded and the new slots will be
1.161 + initialized. On the removal of an item, the corresponding values in the maps
1.162 + are properly destructed.
1.163 +
1.164 +So, if you want to assign \c int values to each node, you have to allocate a
1.165 +\ref concepts::Digraph::Node Map "NodeMap<int>".
1.166 +
1.167 +\code
1.168 + ListDigraph::NodeMap<int> map(g);
1.169 +\endcode
1.170 +
1.171 +As you see, the graph you want to assign a map is given to the
1.172 +constructor. Then you can access its element as if it were a vector.
1.173 +
1.174 +\code
1.175 + map[a]=2;
1.176 + map[b]=3;
1.177 + map[c]=map[a]+map[b];
1.178 +\endcode
1.179 +
1.180 +As a more complex example, let's create a map that assigns a unique
1.181 +integer number to each node.
1.182 +
1.183 +\code
1.184 + ListDigraph::NodeMap<int> id(g);
1.185 + int cnt=0;
1.186 + for(ListDigraph::NodeIt n(g); n!=INVALID; ++n, ++cnt)
1.187 + id[n]=cnt;
1.188 +\endcode
1.189 +
1.190 +You can also give an initial value of the elements as a second parameter.
1.191 +
1.192 +For example the following code puts the number of outgoing edges in a map.
1.193 +
1.194 +\code
1.195 + ListDigraph::NodeMap<int> out_deg(g,0);
1.196 +
1.197 + for(ListDigraph::ArcIt a(g); a!=INVALID; ++a)
1.198 + out_deg[g.source(a)]++;
1.199 +\endcode
1.200 +
1.201 +\warning The initial value will apply to the existing items only. If
1.202 +you add new nodes/arcs to the graph, then the corresponding values in the
1.203 +map will be initialized with the default constructor of the
1.204 +type.
1.205 +
1.206 +[TRAILER]
1.207 +*/
1.208 +}
2.1 --- a/toc.txt Mon Feb 02 11:08:14 2009 +0100
2.2 +++ b/toc.txt Mon Mar 23 09:29:58 2009 +0000
2.3 @@ -2,6 +2,10 @@
2.4 ** intro_lemon
2.5 ** intro_tutorial
2.6 * hello_lemon
2.7 +* basics
2.8 +** digraphs
2.9 +*** digraphs_it
2.10 +*** maps
2.11 *_digraph_build
2.12 *_digraph_iterate
2.13 *_standard_maps