Changeset 37:c8be1109221b in lemontutorial for basics.dox
 Timestamp:
 02/20/10 21:54:52 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

basics.dox
r32 r37 32 32 [SEC]sec_digraphs[SEC] Directed Graphs 33 33 34 The core features of LEMON are the data structures, algorithms and auxiliary 35 tools that make it possible to represent graphs and working with them easily 36 and efficiently. 34 37 This section tells you how to work with a directed graph (\e digraph, 35 38 for short) in LEMON. Here we use \ref ListDigraph, the most versatile 36 39 digraph structure. (The library also provides other digraph types, 37 40 see \ref sec_graph_structures "later".) 41 42 For using \ref ListDigraph, you must include the header file 43 \ref list_graph.h like this: 44 45 \code 46 #include <lemon/list_graph.h> 47 \endcode 48 49 The default constructor of the class creates an empty digraph. 50 51 \code 52 ListDigraph g; 53 \endcode 38 54 39 55 The nodes and the arcs of a graph are identified by two data types called … … 44 60 45 61 \code 46 ListDigraph g; 47 ListDigraph::Node a = g.addNode(); 48 ListDigraph::Node b = g.addNode(); 49 ListDigraph::Node c = g.addNode(); 50 ListDigraph::Node d = g.addNode(); 51 52 g.addArc(a,b); 53 g.addArc(b,c); 54 g.addArc(c,d); 55 g.addArc(d,a); 62 ListDigraph::Node x = g.addNode(); 63 ListDigraph::Node y = g.addNode(); 64 ListDigraph::Node z = g.addNode(); 65 66 g.addArc(x,y); 67 g.addArc(y,z); 68 g.addArc(z,x); 56 69 \endcode 57 70 … … 59 72 60 73 \code 61 ListDigraph::Arc arc = g.addArc(a,c); 74 ListDigraph::Arc arc = g.addArc(x,z); 75 \endcode 76 77 Parallel and loop arcs are also supported. 78 79 \code 80 ListDigraph::Arc parallel = g.addArc(x,y); 81 ListDigraph::Arc loop = g.addArc(x,x); 62 82 \endcode 63 83 … … 72 92 \ref concepts::Digraph::source() "source()" 73 93 and \ref concepts::Digraph::target() "target()". 74 They give back the two end nodes of an arc .75 76 \code 77 if (g.source( arc) == g.target(arc))94 They give back the two end nodes of an arc (as \c Node objects). 95 96 \code 97 if (g.source(loop) == g.target(loop)) 78 98 std::cout << "This is a loop arc" << std::endl; 79 99 \endcode 80 100 81 Each graph item has a unique integer identifier, which can be obtained using 82 the \ref concepts::Digraph::id() "id()" function of the graph structure. 101 Each graph item has a nonnegative integer identifier, which can be obtained 102 using the \ref concepts::Digraph::id() "id()" function of the graph structure. 103 These identifiers are unique with respect to a certain item type in a graph, 104 but a node and an arc may have the same id. 83 105 84 106 \code … … 94 116 95 117 Let us assume you want to list the elements of the graph. For this purpose, 96 the graph structures provide several iterators. For example, the following118 the graph structures provide several \e iterators. For example, the following 97 119 code will count the number of nodes in a graph. 98 120 … … 104 126 \endcode 105 127 106 Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt" 107 is an iterator class that traverses the 108 nodes. You must give the graph to the constructor and the iterator will be set 128 \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt" 129 is an iterator class that lists the nodes. 130 The name of an iterator type starts with a name that refers to 131 the iterated objects and ends with 'It'. 132 133 Using \ref concepts::Digraph::NodeIt "NodeIt", you must give 134 the graph object to the constructor and the iterator will be set 109 135 to the first node. The next node is obtained by the prefix ++ 110 136 operator. If there are no more nodes in the graph, the iterator will 111 be set to \ref INVALID. 112 113 \note \ref INVALID is a global constant, which converts to 114 and compares with each and every iterator in LEMON. 115 116 The iterators convert to the corresponding item types. For example, 117 to following code will add a full graph to the existing nodes. 137 be set to \ref INVALID, which is exploited in the stop condition of 138 the loop. 139 140 \note \ref INVALID is a constant in the \ref lemon namespace, which converts to 141 and compares with each and every iterator and graph item type. 142 Thus, you can even assign \ref INVALID to a \c Node or \c Arc object. 143 144 The iterators convert to the corresponding item types. 145 For example, the identifiers of the nodes can be printed like this. 146 147 \code 148 for (ListDigraph::NodeIt n(g); n != INVALID; ++n) 149 std::cout << g.id(n) << std::endl; 150 \endcode 151 152 As an other example, the following code adds a full graph to the 153 existing nodes. 118 154 119 155 \code … … 163 199 \code 164 200 int cnt = 0; 165 for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a)201 for (ListDigraph::OutArcIt a(g, x); a != INVALID; ++a) 166 202 cnt++; 167 std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl; 168 \endcode 203 std::cout << "Number of arcs leaving the node 'x': " << cnt << std::endl; 204 \endcode 205 206 \note LEMON provides functions for counting the nodes and arcs of a digraph: 207 \ref countNodes(), \ref countArcs(), \ref countInArcs(), \ref countOutArcs(). 208 Using them is not just simpler than the above loops, but they could be much 209 faster, since several graph types support constant time item counting. 169 210 170 211 … … 184 225 initialized. On the removal of an item, the corresponding values in the maps 185 226 are properly destructed. 227 228 By principle, the graph classes represent only the pure structure of 229 the graph (i.e. the nodes and arcs and their connections). 230 All data that are assigned to the items of the graph (e.g. node labels, 231 arc costs or capacities) must be stored separately using maps. 186 232 187 233 \note These maps must not be confused with \c std::map, since they provide 188 O(1) time acces to the elements instead of O(log n).234 O(1) time access to the elements instead of O(log n). 189 235 190 236 So, if you want to assign \c int values to each node, you have to allocate a … … 199 245 200 246 \code 201 map[a] = 2; 202 map[b] = 3; 203 map[c] = map[a] + map[b]; 204 \endcode 205 206 Any kind of data can be assigned to the graph items. 207 208 \code 209 ListDigraph::NodeMap<std::string> label(g); 210 label[a] = "Node A"; 211 label[b] = "Node B"; 212 \endcode 213 214 For a more complex example, let us create a map that assigns a unique 215 integer number to each node. 216 217 \code 218 ListDigraph::NodeMap<int> id(g); 219 int cnt = 0; 247 map[x] = 2; 248 map[y] = 3; 249 map[z] = map[x] + map[y]; 250 \endcode 251 252 Any kind of data can be assigned to the graph items (assuming that the type 253 has a default constructor). 254 255 \code 256 ListDigraph::NodeMap<std::string> name(g); 257 name[x] = "Node A"; 258 name[y] = "Node B"; 259 \endcode 260 261 As a more complex example, let us create a map that assigns \c char labels 262 to the nodes. 263 264 \code 265 ListDigraph::NodeMap<char> label(g); 266 char ch = 'A'; 220 267 for (ListDigraph::NodeIt n(g); n != INVALID; ++n) 221 id[n] = cnt++;268 label[n] = ch++; 222 269 \endcode 223 270 … … 228 275 \code 229 276 ListDigraph::NodeMap<int> out_deg(g, 0); 230 231 277 for (ListDigraph::ArcIt a(g); a != INVALID; ++a) 232 278 out_deg[g.source(a)]++; … … 238 284 type. 239 285 286 287 [SEC]sec_naming_conv[SEC] Naming Conventions 288 289 In LEMON, there are some naming conventions you might already notice 290 in the above examples. 291 292 The name of a source file is written lowercase and the words are separated with 293 underscores (e.g. \ref list_graph.h). All header files are located in the 294 \c %lemon subdirectory, so you can include them like this. 295 296 \code 297 #include <lemon/header_file.h> 298 \endcode 299 300 The name of a class or any type looks like the following 301 (e.g. \ref ListDigraph, \ref concepts::Digraph::Node "Node", 302 \ref concepts::Digraph::NodeIt "NodeIt" etc.). 303 304 \code 305 AllWordsCapitalizedWithoutUnderscores 306 \endcode 307 308 The name of a function looks like the following 309 (e.g. \ref concepts::Digraph::source() "source()", 310 \ref concepts::Digraph::source() "target()", 311 \ref countNodes(), \ref countArcs() etc.). 312 313 \code 314 firstWordLowerCaseRestCapitalizedWithoutUnderscores 315 \endcode 316 317 The names of constants and macros look like the following 318 (e.g. \ref INVALID). 319 320 \code 321 ALL_UPPER_CASE_WITH_UNDERSCORES 322 \endcode 323 324 For more details, see \ref coding_style. 325 240 326 [TRAILER] 241 327 */
Note: See TracChangeset
for help on using the changeset viewer.