Changeset 27:b453a59230c8 in lemontutorial
 Timestamp:
 02/14/10 22:19:50 (14 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

basics.dox
r26 r27 21 21 [PAGE]sec_basics[PAGE] Basic Concepts 22 22 23 Throughout the documentwe are working with the \ref lemon namespace.24 To save a lot of typing we assume that a23 Throughout the tutorial we are working with the \ref lemon namespace. 24 To save a lot of typing, we assume that a 25 25 26 26 \code … … 32 32 [SEC]sec_digraphs[SEC] Directed Graphs 33 33 34 This section tells you how to work with a directed graph. We use ListDigraph, 35 the most versatile graph structure. 36 37 The nodes and the arcs of a graph are identified by two datatypes called 38 ListDigraph::Node and ListDigraph::Arc. You can add new components the graph 39 by the \ref ListDigraph::addNode() "addNode()" and the 40 \ref ListDigraph::addArc() "addArc()" member functions, like this: 34 This section tells you how to work with a directed graph (\e digraph, 35 for short) in LEMON. 36 The library provides various digraph structures for both general and special 37 purposes. Here we use \c ListDigraph, the most versatile digraph type. 38 39 The nodes and the arcs of a graph are identified by two data types called 40 \ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc 41 "ListDigraph::Arc". You can add new items to the graph using the member 42 functions \ref ListDigraph::addNode() "addNode()" and 43 \ref ListDigraph::addArc() "addArc()", like this: 41 44 42 45 \code … … 56 59 57 60 \code 58 ListDigraph::Arc diag = g.addArc(a,c); 59 \endcode 60 61 \note You can also remove nodes or arcs with the 62 \ref ListDigraph::erase() "erase()", but this operation may not be available 63 with all graph structures. 64 65 Two other important member functions are 61 ListDigraph::Arc arc = g.addArc(a,c); 62 \endcode 63 64 \note Using ListDigraph, you can also remove nodes or arcs with the 65 \ref ListDigraph::erase() "erase()" function. 66 However, not all graph structures support the addition and deletion 67 of graph items. 68 69 Two important member functions of the directed graphs are 66 70 \ref concepts::Digraph::source() "source()" 67 71 and \ref concepts::Digraph::target() "target()". 68 They give s back the to end nodes of andarc.69 70 \code 71 if (g.source(e)==g.target(e))72 They give back the two end nodes of an arc. 73 74 \code 75 if (g.source(arc) == g.target(arc)) 72 76 std::cout << "This is a loop arc" << std::endl; 73 77 \endcode 74 78 79 Each graph item has a unique integer identifier, which can be obtained using 80 the \ref concepts::Digraph::id() "id()" function of the graph structure. 81 82 \code 83 std::cout << "Arc " << g.id(arc) << " goes from node " 84 << g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl; 85 \endcode 86 87 \note In fact, the \c Node and \c Arc types are typically simple wrapper 88 classes for a single \c int value, which is the identifier of the item. 89 75 90 76 91 [SEC]sec_digraph_it[SEC] Iterators 77 92 78 Now assume you want to list the elements of the graph. For this purpose the 79 the graph s provides several iterators. For example for following code will80 co undthe number of nodes in a graph.81 82 \code 83 int cnt = 0; 84 for (ListDigraph::NodeIt n(g); n!=INVALID; ++n)93 Let us assume you want to list the elements of the graph. For this purpose, 94 the graph structures provide several iterators. For example, the following 95 code will count the number of nodes in a graph. 96 97 \code 98 int cnt = 0; 99 for (ListDigraph::NodeIt n(g); n != INVALID; ++n) 85 100 cnt++; 86 101 std::cout << "Number of nodes: " << cnt << std::endl; … … 88 103 89 104 Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt" 90 is an iterator class that lists the91 nodes. You must give the graph to the constructor and itwill be set105 is an iterator class that traverses the 106 nodes. You must give the graph to the constructor and the iterator will be set 92 107 to the first node. The next node is obtained by the prefix ++ 93 operator. If there isno more nodes in the graph, the iterator will108 operator. If there are no more nodes in the graph, the iterator will 94 109 be set to \ref INVALID. 95 110 96 \note \ref INVALID is a global constant in lemon and itconverts to97 and compares with each and every iterator sin LEMON.98 99 The iterators convert s to the corresponding descriptor types. For example111 \note \ref INVALID is a global constant, which converts to 112 and compares with each and every iterator in LEMON. 113 114 The iterators convert to the corresponding item types. For example, 100 115 to following code will add a full graph to the existing nodes. 101 116 102 117 \code 103 for(ListDigraph::NodeIt u(g); u!=INVALID; ++u) 104 for(ListDigraph::NodeIt v(g); v!=INVALID; ++v) 105 if(u!=v) g.addArc(u,v); 106 \endcode 107 108 The items are also ordered by the 'less than' operator. For example this 109 code will add only one of the opposite arcs. 110 111 \code 112 for(ListDigraph::NodeIt u(g); u!=INVALID; ++u) 113 for(ListDigraph::NodeIt v(g); v!=INVALID; ++v) 114 if(u<v) g.addArc(u,v); 115 \endcode 116 117 \warning There order in which the iterator visits the items is 118 for (ListDigraph::NodeIt u(g); u != INVALID; ++u) 119 for (ListDigraph::NodeIt v(g); v != INVALID; ++v) 120 if (u != v) g.addArc(u, v); 121 \endcode 122 123 \note Contrary to the iterators in the C++ Standard Template Library (STL), 124 LEMON iterators are convertible to the corresponding 125 item types without having to use \c %operator*(). This is not confusing, since the 126 program context always indicates whether we refer to the iterator or to the graph 127 item (they do not have conflicting functionalities). 128 129 The graph items are also ordered by the 'less than' operator (with respect to 130 their integer identifiers). For example, this code will add only one of the 131 opposite arcs. 132 133 \code 134 for (ListDigraph::NodeIt u(g); u != INVALID; ++u) 135 for (ListDigraph::NodeIt v(g); v != INVALID; ++v) 136 if (u < v) g.addArc(u, v); 137 \endcode 138 139 \warning The order in which the iterators visit the items is 118 140 undefined. The only thing you may assume that they will list the items 119 141 in the same order until the graph is not changed. … … 125 147 \code 126 148 int cnt = 0; 127 for (ListDigraph::ArcIt a(g); a!=INVALID; ++a)149 for (ListDigraph::ArcIt a(g); a != INVALID; ++a) 128 150 cnt++; 129 151 std::cout << "Number of arcs: " << cnt << std::endl; … … 135 157 and 136 158 \ref concepts::Digraph::InArcIt "ListDigraph::InArcIt". 137 Their usage arethe same, but you must also give the node to the constructor.138 139 \code 140 int cnt = 0; 141 for (ListDigraph::OutArcIt a(g,start); a!=INVALID; ++a)159 Their usage is the same, but you must also give the node to the constructor. 160 161 \code 162 int cnt = 0; 163 for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a) 142 164 cnt++; 143 165 std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl; … … 147 169 [SEC]sec_digraph_maps[SEC] Maps 148 170 149 The concept of " Maps" is another fundamental part of LEMON. They allow assigning150 values of any type to the nodes or arcs of a graph. The defaultmaps171 The concept of "maps" is another fundamental part of LEMON. They allow assigning 172 values of any type to the nodes or arcs of a graph. The standard maps 151 173 provided by the graph structures have a couple of nice properties. 152 174 153  \e Fast. Accessing (reading/writing) the values areas fast as a154 simple vector reading/writing 175  \e Fast. Accessing (reading/writing) the values is as fast as a 176 simple vector reading/writing. 155 177  \e Dynamic. Whenever you need, you 156 178 can allocate new maps in your code, just as a local variable. So when you … … 161 183 are properly destructed. 162 184 185 \note These maps must not be confused with \c std::map, since they provide 186 O(1) time acces to the elements instead of O(log n). 187 163 188 So, if you want to assign \c int values to each node, you have to allocate a 164 \ref concepts::Digraph::Node 189 \ref concepts::Digraph::NodeMap "NodeMap<int>". 165 190 166 191 \code … … 172 197 173 198 \code 174 map[a]=2; 175 map[b]=3; 176 map[c]=map[a]+map[b]; 177 \endcode 178 179 As a more complex example, let's create a map that assigns a unique 199 map[a] = 2; 200 map[b] = 3; 201 map[c] = map[a] + map[b]; 202 \endcode 203 204 Any kind of data can be assigned to the graph items. 205 206 \code 207 ListDigraph::NodeMap<std::string> label(g); 208 label[a] = "Node A"; 209 label[b] = "Node B"; 210 \endcode 211 212 For a more complex example, let us create a map that assigns a unique 180 213 integer number to each node. 181 214 182 215 \code 183 216 ListDigraph::NodeMap<int> id(g); 184 int cnt =0;185 for (ListDigraph::NodeIt n(g); n!=INVALID; ++n, ++cnt)186 id[n] =cnt;187 \endcode 188 189 You can also give an initial value of the elements as a second parameter. 190 191 For example the following code puts the number of outgoing edgesin a map.192 193 \code 194 ListDigraph::NodeMap<int> out_deg(g, 0);195 196 for (ListDigraph::ArcIt a(g); a!=INVALID; ++a)217 int cnt = 0; 218 for (ListDigraph::NodeIt n(g); n != INVALID; ++n) 219 id[n] = cnt++; 220 \endcode 221 222 When you create a map, you can also give an initial value of the elements 223 as a second parameter. For example, the following code puts the number 224 of outgoing arcs for each node in a map. 225 226 \code 227 ListDigraph::NodeMap<int> out_deg(g, 0); 228 229 for (ListDigraph::ArcIt a(g); a != INVALID; ++a) 197 230 out_deg[g.source(a)]++; 198 231 \endcode 199 232 200 \warning The initial value will apply to the existing items only. If233 \warning The initial value will apply to the currently existing items only. If 201 234 you add new nodes/arcs to the graph, then the corresponding values in the 202 235 map will be initialized with the default constructor of the
Note: See TracChangeset
for help on using the changeset viewer.