Changes in / [206:4e22275a2b52:207:574b963d0275] in lemon-1.1
- Files:
-
- 1 added
- 1 deleted
- 14 edited
Legend:
- Unmodified
- Added
- Removed
-
demo/arg_parser_demo.cc
r137 r204 30 30 int main(int argc, const char **argv) 31 31 { 32 ArgParser ap(argc,argv); 32 // Initialize the argument parser 33 ArgParser ap(argc, argv); 33 34 int i; 34 35 std::string s; 35 double d; 36 bool b,sil; 37 bool g1,g2,g3; 38 ap.refOption("n", "An integer input.", i, true) 39 .refOption("val", "A double input.", d) 40 .doubleOption("val2", "A double input.", d) 41 .synonym("vals","val") 42 .refOption("name", "A string input.", s) 43 .refOption("f", "A switch.", b) 44 .refOption("nohelp", "", sil) 45 .refOption("gra","Choice A",g1) 46 .refOption("grb","Choice B",g2) 47 .refOption("grc","Choice C",g3) 48 .optionGroup("gr","gra") 49 .optionGroup("gr","grb") 50 .optionGroup("gr","grc") 51 .mandatoryGroup("gr") 52 .onlyOneGroup("gr") 53 .other("infile","The input file.") 36 double d = 1.0; 37 bool b, nh; 38 bool g1, g2, g3; 39 40 // Add a mandatory integer option with storage reference 41 ap.refOption("n", "An integer input.", i, true); 42 // Add a double option with storage reference (the default value is 1.0) 43 ap.refOption("val", "A double input.", d); 44 // Add a double option without storage reference (the default value is 3.14) 45 ap.doubleOption("val2", "A double input.", 3.14); 46 // Set synonym for -val option 47 ap.synonym("vals", "val"); 48 // Add a string option 49 ap.refOption("name", "A string input.", s); 50 // Add bool options 51 ap.refOption("f", "A switch.", b) 52 .refOption("nohelp", "", nh) 53 .refOption("gra", "Choice A", g1) 54 .refOption("grb", "Choice B", g2) 55 .refOption("grc", "Choice C", g3); 56 // Bundle -gr* options into a group 57 ap.optionGroup("gr", "gra") 58 .optionGroup("gr", "grb") 59 .optionGroup("gr", "grc"); 60 // Set the group mandatory 61 ap.mandatoryGroup("gr"); 62 // Set the options of the group exclusive (only one option can be given) 63 ap.onlyOneGroup("gr"); 64 // Add non-parsed arguments (e.g. input files) 65 ap.other("infile", "The input file.") 54 66 .other("..."); 55 67 68 // Perform the parsing process 69 // (in case of any error it terminates the program) 56 70 ap.parse(); 57 71 72 // Check each option if it has been given and print its value 58 73 std::cout << "Parameters of '" << ap.commandName() << "':\n"; 59 74 60 if(ap.given("n"))std::cout << " Value of -n: " << i << std::endl;75 std::cout << " Value of -n: " << i << std::endl; 61 76 if(ap.given("val")) std::cout << " Value of -val: " << d << std::endl; 77 if(ap.given("val2")) { 78 d = ap["val2"]; 79 std::cout << " Value of -val2: " << d << std::endl; 80 } 62 81 if(ap.given("name")) std::cout << " Value of -name: " << s << std::endl; 63 82 if(ap.given("f")) std::cout << " -f is given\n"; 64 if(ap.given("nohelp")) std::cout << " Value of -nohelp: " << sil<< std::endl;83 if(ap.given("nohelp")) std::cout << " Value of -nohelp: " << nh << std::endl; 65 84 if(ap.given("gra")) std::cout << " -gra is given\n"; 66 85 if(ap.given("grb")) std::cout << " -grb is given\n"; 67 86 if(ap.given("grc")) std::cout << " -grc is given\n"; 68 87 69 88 switch(ap.files().size()) { 70 89 case 0: … … 81 100 std::cout << " '" << ap.files()[i] << "'\n"; 82 101 102 return 0; 83 103 } -
demo/lgf_demo.cc
r164 r193 21 21 ///\brief Demonstrating graph input and output 22 22 /// 23 /// This program gives an example of how to load a directed graph from24 /// an \ref lgf-format "LGF" file with the \ref lemon::DigraphReader25 /// "DigraphReader" class.23 /// This program gives an example of how to read and write a digraph 24 /// and additional maps from/to a stream or a file using the 25 /// \ref lgf-format "LGF" format. 26 26 /// 27 27 /// The \c "digraph.lgf" file: 28 28 /// \include digraph.lgf 29 29 /// 30 /// And the program which reads it: 30 /// And the program which reads it and prints the digraph to the 31 /// standard output: 31 32 /// \include lgf_demo.cc 32 33 … … 35 36 #include <lemon/lgf_reader.h> 36 37 #include <lemon/lgf_writer.h> 37 #include <lemon/random.h>38 39 38 40 39 using namespace lemon; … … 44 43 SmartDigraph::ArcMap<int> cap(g); 45 44 SmartDigraph::Node s, t; 45 46 try { 47 digraphReader("digraph.lgf", g). // read the directed graph into g 48 arcMap("capacity", cap). // read the 'capacity' arc map into cap 49 node("source", s). // read 'source' node to s 50 node("target", t). // read 'target' node to t 51 run(); 52 } catch (DataFormatError& error) { // check if there was any error 53 std::cerr << "Error: " << error.what() << std::endl; 54 return -1; 55 } 46 56 47 digraphReader("digraph.lgf", g). // read the directeg graph into g 48 arcMap("capacity", cap). // read the 'capacity' arc map into cap 49 node("source", s). // read 'source' node to s 50 node("target", t). // read 'target' node to t 51 run(); 52 53 std::cout << "Digraph read from 'digraph.lgf'" << std::endl; 57 std::cout << "A digraph is read from 'digraph.lgf'." << std::endl; 54 58 std::cout << "Number of nodes: " << countNodes(g) << std::endl; 55 59 std::cout << "Number of arcs: " << countArcs(g) << std::endl; -
doc/groups.dox
r156 r192 476 476 @defgroup lemon_io Lemon Input-Output 477 477 @ingroup io_group 478 \brief Reading and writing LEMON format 479 480 This group describes methods for reading and writing LEMON format. 481 You can find more about this format on the \ref graph-io-page "Graph Input-Output" 482 tutorial pages. 478 \brief Reading and writing \ref lgf-format "Lemon Graph Format". 479 480 This group describes methods for reading and writing \ref lgf-format "Lemon Graph Format". 483 481 */ 484 482 -
doc/lgf.dox
r162 r201 47 47 48 48 The \c \@nodes section describes a set of nodes and associated 49 maps. The first is a header line, it columns are the names of the49 maps. The first is a header line, its columns are the names of the 50 50 maps appearing in the following lines. 51 51 One of the maps must be called \c … … 65 65 66 66 The \c \@arcs section is very similar to the \c \@nodes section, 67 it again starts with a header line describing the names of the arc,67 it again starts with a header line describing the names of the maps, 68 68 but the \c "label" map is not obligatory here. The following lines 69 69 describe the arcs. The first two tokens of each line are … … 79 79 \endcode 80 80 81 The \c \@edges is just a synonym of \c \@arcs. 81 The \c \@edges is just a synonym of \c \@arcs. The @arcs section can 82 also store the edge set of an undirected graph. In such case there is 83 a conventional method for store arc maps in the file, if two columns 84 has the same caption with \c '+' and \c '-' prefix, then these columns 85 can be regarded as the values of an arc map. 82 86 83 87 The \c \@attributes section contains key-value pairs, each line 84 consists of two tokens, an attribute name, and then an attribute value. 88 consists of two tokens, an attribute name, and then an attribute 89 value. The value of the attribute could be also a label value of a 90 node or an edge, or even an edge label prefixed with \c '+' or \c '-', 91 which regards to the forward or backward directed arc of the 92 corresponding edge. 85 93 86 94 \code -
lemon/Makefile.am
r166 r195 33 33 lemon/kruskal.h \ 34 34 lemon/lgf_reader.h \ 35 lemon/lgf_writer.h \ 35 36 lemon/list_graph.h \ 36 37 lemon/maps.h \ … … 60 61 lemon/concepts/digraph.h \ 61 62 lemon/concepts/graph.h \ 63 lemon/concepts/graph_components.h \ 62 64 lemon/concepts/heap.h \ 63 65 lemon/concepts/maps.h \ 64 lemon/concepts/path.h \ 65 lemon/concepts/graph_components.h 66 lemon/concepts/path.h -
lemon/arg_parser.h
r108 r204 119 119 public: 120 120 121 /// \e121 ///Constructor 122 122 ArgParser(int argc, const char **argv); 123 123 124 124 ~ArgParser(); 125 125 126 ///\name Options 127 /// 128 129 ///@{ 130 126 131 ///Add a new integer type option 127 132 133 ///Add a new integer type option. 128 134 ///\param name The name of the option. The leading '-' must be omitted. 129 135 ///\param help A help string. … … 136 142 ///Add a new floating point type option 137 143 144 ///Add a new floating point type option. 138 145 ///\param name The name of the option. The leading '-' must be omitted. 139 146 ///\param help A help string. … … 146 153 ///Add a new bool type option 147 154 155 ///Add a new bool type option. 148 156 ///\param name The name of the option. The leading '-' must be omitted. 149 157 ///\param help A help string. … … 157 165 ///Add a new string type option 158 166 167 ///Add a new string type option. 159 168 ///\param name The name of the option. The leading '-' must be omitted. 160 169 ///\param help A help string. … … 165 174 std::string value="", bool obl=false); 166 175 167 ///\name Options with external storage 176 ///Give help string for non-parsed arguments. 177 178 ///With this function you can give help string for non-parsed arguments. 179 ///The parameter \c name will be printed in the short usage line, while 180 ///\c help gives a more detailed description. 181 ArgParser &other(const std::string &name, 182 const std::string &help=""); 183 184 ///@} 185 186 ///\name Options with External Storage 168 187 ///Using this functions, the value of the option will be directly written 169 188 ///into a variable once the option appears in the command line. … … 173 192 ///Add a new integer type option with a storage reference 174 193 194 ///Add a new integer type option with a storage reference. 175 195 ///\param name The name of the option. The leading '-' must be omitted. 176 196 ///\param help A help string. … … 183 203 ///Add a new floating type option with a storage reference 184 204 205 ///Add a new floating type option with a storage reference. 185 206 ///\param name The name of the option. The leading '-' must be omitted. 186 207 ///\param help A help string. … … 193 214 ///Add a new bool type option with a storage reference 194 215 216 ///Add a new bool type option with a storage reference. 195 217 ///\param name The name of the option. The leading '-' must be omitted. 196 218 ///\param help A help string. … … 204 226 ///Add a new string type option with a storage reference 205 227 228 ///Add a new string type option with a storage reference. 206 229 ///\param name The name of the option. The leading '-' must be omitted. 207 230 ///\param help A help string. … … 219 242 ///@{ 220 243 221 ///B oundle some options into a group244 ///Bundle some options into a group 222 245 223 246 /// You can group some option by calling this function repeatedly for each … … 231 254 232 255 ///If you call this function for a group, than at most one of them can be 233 ///given at the same time 256 ///given at the same time. 234 257 ArgParser &onlyOneGroup(const std::string &group); 235 258 … … 248 271 249 272 ///@} 250 251 ///Give help string for non-parsed arguments.252 253 ///With this function you can give help string for non-parsed arguments.254 ///The parameter \c name will be printed in the short usage line, while255 ///\c help gives a more detailed description.256 ArgParser &other(const std::string &name,257 const std::string &help="");258 259 ///Give back the non-option type arguments.260 261 ///Give back a reference to a vector consisting of the program arguments262 ///not starting with a '-' character.263 std::vector<std::string> &files() { return _file_args; }264 265 ///Give back the command name (the 0th argument)266 const std::string &commandName() { return _command_name; }267 273 268 274 void show(std::ostream &os,Opts::iterator i); … … 287 293 } 288 294 295 ///Give back the command name (the 0th argument) 296 const std::string &commandName() { return _command_name; } 297 289 298 ///Check if an opion has been given to the command. 290 299 bool given(std::string op) … … 361 370 return RefType(*this, n); 362 371 } 372 373 ///Give back the non-option type arguments. 374 375 ///Give back a reference to a vector consisting of the program arguments 376 ///not starting with a '-' character. 377 std::vector<std::string> &files() { return _file_args; } 363 378 364 379 }; 365 380 } 366 381 367 368 369 #endif // LEMON_MAIN_PARAMS 382 #endif // LEMON_ARG_PARSER -
lemon/concepts/heap.h
r113 r203 182 182 Item item; 183 183 Prio prio; 184 State state;185 184 item=Item(); 186 185 prio=Prio(); 187 186 ignore_unused_variable_warning(item); 188 187 ignore_unused_variable_warning(prio); 189 ignore_unused_variable_warning(state);190 188 191 189 OwnItem own_item; … … 204 202 205 203 int s = heap.size(); 204 ignore_unused_variable_warning(s); 206 205 bool e = heap.empty(); 206 ignore_unused_variable_warning(e); 207 207 208 208 prio = heap.prio(); … … 228 228 heap.clear(); 229 229 230 state = heap.state(item); 231 heap.state(item, state); 232 state = heap.state(own_item); 230 own_state = heap.state(own_item); 233 231 heap.state(own_item, own_state); 234 232 235 state = _Heap::PRE_HEAP;236 state = _Heap::IN_HEAP;237 state = _Heap::POST_HEAP;238 233 own_state = _Heap::PRE_HEAP; 239 234 own_state = _Heap::IN_HEAP; -
lemon/graph_utils.h
r169 r199 603 603 for (typename From::ArcIt it(from); it != INVALID; ++it) { 604 604 arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)], 605 605 nodeRefMap[from.target(it)]); 606 606 } 607 607 } … … 629 629 } 630 630 for (typename From::EdgeIt it(from); it != INVALID; ++it) { 631 edgeRefMap[it] = to.add Arc(nodeRefMap[from.source(it)],632 nodeRefMap[from.target(it)]);631 edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)], 632 nodeRefMap[from.v(it)]); 633 633 } 634 634 } … … 926 926 927 927 Value operator[](const Key& key) const { 928 bool forward = 929 (_from.direction(key) == 930 (_node_ref[_from.source(key)] == _to.source(_edge_ref[key]))); 928 bool forward = _from.u(key) != _from.v(key) ? 929 _node_ref[_from.source(key)] == 930 _to.source(_to.direct(_edge_ref[key], true)) : 931 _from.direction(key); 931 932 return _to.direct(_edge_ref[key], forward); 932 933 } -
lemon/kruskal.h
r167 r194 33 33 ///\ingroup spantree 34 34 ///\file 35 ///\brief Kruskal's algorithm to compute a minimum cost tree35 ///\brief Kruskal's algorithm to compute a minimum cost spanning tree 36 36 /// 37 ///Kruskal's algorithm to compute a minimum cost tree.37 ///Kruskal's algorithm to compute a minimum cost spanning tree. 38 38 /// 39 39 … … 252 252 /// \ingroup spantree 253 253 /// 254 /// \brief Kruskal's algorithm to find a minimum cost tree of a graph. 255 /// 256 /// This function runs Kruskal's algorithm to find a minimum cost tree. 254 /// \brief Kruskal algorithm to find a minimum cost spanning tree of 255 /// a graph. 256 /// 257 /// This function runs Kruskal's algorithm to find a minimum cost 258 /// spanning tree. 257 259 /// Due to some C++ hacking, it accepts various input and output types. 258 260 /// … … 263 265 /// undirected by disregarding the direction of the arcs. 264 266 /// 265 /// \param in This object is used to describe the arc costs. It can be one266 /// of the following choices.267 /// \param in This object is used to describe the arc/edge costs. 268 /// It can be one of the following choices. 267 269 /// - An STL compatible 'Forward Container' with 268 /// <tt>std::pair<GR:: Edge,X></tt> or269 /// <tt>std::pair<GR:: Arc,X></tt> as its <tt>value_type</tt>, where270 /// \c X is the type of the costs. The pairs indicates the arcs 270 /// <tt>std::pair<GR::Arc,X></tt> or 271 /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where 272 /// \c X is the type of the costs. The pairs indicates the arcs/edges 271 273 /// along with the assigned cost. <em>They must be in a 272 274 /// cost-ascending order.</em> 273 /// - Any readable Arc map. The values of the map indicate the arc costs. 274 /// 275 /// \retval out Here we also have a choise. 276 /// - It can be a writable \c bool arc map. After running the 277 /// algorithm this will contain the found minimum cost spanning 278 /// tree: the value of an arc will be set to \c true if it belongs 275 /// - Any readable arc/edge map. The values of the map indicate the 276 /// arc/edge costs. 277 /// 278 /// \retval out Here we also have a choice. 279 /// - It can be a writable \c bool arc/edge map. After running the 280 /// algorithm it will contain the found minimum cost spanning 281 /// tree: the value of an arc/edge will be set to \c true if it belongs 279 282 /// to the tree, otherwise it will be set to \c false. The value of 280 /// each arc will be set exactly once.283 /// each arc/edge will be set exactly once. 281 284 /// - It can also be an iteraror of an STL Container with 282 /// <tt>GR:: Edge</tt> or <tt>GR::Arc</tt> as its285 /// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its 283 286 /// <tt>value_type</tt>. The algorithm copies the elements of the 284 287 /// found tree into this sequence. For example, if we know that the … … 291 294 /// Or if we don't know in advance the size of the tree, we can 292 295 /// write this. 293 ///\code std::vector<Arc> tree; 296 ///\code 297 /// std::vector<Arc> tree; 294 298 /// kruskal(g,cost,std::back_inserter(tree)); 295 299 ///\endcode 296 300 /// 297 /// \return The total cost of the found tree.298 /// 299 /// \warning If kruskal runs on an be consistent of using the same301 /// \return The total cost of the found spanning tree. 302 /// 303 /// \warning If Kruskal runs on an be consistent of using the same 300 304 /// Arc type for input and output. 301 305 /// -
lemon/lgf_reader.h
r190 r201 19 19 ///\ingroup lemon_io 20 20 ///\file 21 ///\brief Lemon Graph Formatreader.21 ///\brief \ref lgf-format "Lemon Graph Format" reader. 22 22 23 23 … … 196 196 }; 197 197 198 bool isWhiteSpace(char c) {198 inline bool isWhiteSpace(char c) { 199 199 return c == ' ' || c == '\t' || c == '\v' || 200 200 c == '\n' || c == '\r' || c == '\f'; 201 201 } 202 202 203 bool isOct(char c) {203 inline bool isOct(char c) { 204 204 return '0' <= c && c <='7'; 205 205 } 206 206 207 in t valueOct(char c) {207 inline int valueOct(char c) { 208 208 LEMON_ASSERT(isOct(c), "The character is not octal."); 209 209 return c - '0'; 210 210 } 211 211 212 bool isHex(char c) {212 inline bool isHex(char c) { 213 213 return ('0' <= c && c <= '9') || 214 214 ('a' <= c && c <= 'z') || … … 216 216 } 217 217 218 in t valueHex(char c) {218 inline int valueHex(char c) { 219 219 LEMON_ASSERT(isHex(c), "The character is not hexadecimal."); 220 220 if ('0' <= c && c <= '9') return c - '0'; … … 223 223 } 224 224 225 bool isIdentifierFirstChar(char c) {225 inline bool isIdentifierFirstChar(char c) { 226 226 return ('a' <= c && c <= 'z') || 227 227 ('A' <= c && c <= 'Z') || c == '_'; 228 228 } 229 229 230 bool isIdentifierChar(char c) {230 inline bool isIdentifierChar(char c) { 231 231 return isIdentifierFirstChar(c) || 232 232 ('0' <= c && c <= '9'); 233 233 } 234 234 235 char readEscape(std::istream& is) {235 inline char readEscape(std::istream& is) { 236 236 char c; 237 237 if (!is.get(c)) … … 285 285 } 286 286 287 std::istream& readToken(std::istream& is, std::string& str) {287 inline std::istream& readToken(std::istream& is, std::string& str) { 288 288 std::ostringstream os; 289 289 … … 401 401 /// \ingroup lemon_io 402 402 /// 403 /// \brief LGFreader for directed graphs403 /// \brief \ref lgf-format "LGF" reader for directed graphs 404 404 /// 405 405 /// This utility reads an \ref lgf-format "LGF" file. … … 411 411 /// with the \c nodeMap() or \c arcMap() members. An optional 412 412 /// converter parameter can also be added as a standard functor 413 /// converting from std::string to the value type of the map. If it413 /// converting from \c std::string to the value type of the map. If it 414 414 /// is set, it will determine how the tokens in the file should be 415 /// is converted to the map's value type. If the functor is not set,415 /// converted to the value type of the map. If the functor is not set, 416 416 /// then a default conversion will be used. One map can be read into 417 417 /// multiple map objects at the same time. The \c attribute(), \c … … 420 420 /// 421 421 ///\code 422 /// 423 /// 424 /// 425 /// 426 /// 427 /// 428 /// 422 /// DigraphReader<Digraph>(std::cin, digraph). 423 /// nodeMap("coordinates", coord_map). 424 /// arcMap("capacity", cap_map). 425 /// node("source", src). 426 /// node("target", trg). 427 /// attribute("caption", caption). 428 /// run(); 429 429 ///\endcode 430 430 /// … … 438 438 /// graph) during the reading, but instead the label map of the items 439 439 /// are given as a parameter of these functions. An 440 /// application of these function is multipass reading, which is441 /// important if two \ e\@arcs sections must be read from the442 /// file. In this example the first phase would read the node set and one440 /// application of these functions is multipass reading, which is 441 /// important if two \c \@arcs sections must be read from the 442 /// file. In this case the first phase would read the node set and one 443 443 /// of the arc sets, while the second phase would read the second arc 444 444 /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet). 445 445 /// The previously read label node map should be passed to the \c 446 446 /// useNodes() functions. Another application of multipass reading when 447 /// paths are given as a node map or an arc map. It is impossible read this in447 /// paths are given as a node map or an arc map. It is impossible to read this in 448 448 /// a single pass, because the arcs are not constructed when the node 449 449 /// maps are read. … … 736 736 /// Use previously constructed node set, and specify the node 737 737 /// label map and a functor which converts the label map values to 738 /// std::string.738 /// \c std::string. 739 739 template <typename Map, typename Converter> 740 740 DigraphReader& useNodes(const Map& map, … … 769 769 /// Use previously constructed arc set, and specify the arc 770 770 /// label map and a functor which converts the label map values to 771 /// std::string.771 /// \c std::string. 772 772 template <typename Map, typename Converter> 773 773 DigraphReader& useArcs(const Map& map, … … 785 785 /// 786 786 /// Omit the reading of the node section. This implies that each node 787 /// map reading rule will be aban oned, and the nodes of the graph787 /// map reading rule will be abandoned, and the nodes of the graph 788 788 /// will not be constructed, which usually cause that the arc set 789 /// could not be read due to lack of node name 790 /// resolving. Therefore, the \c skipArcs() should be used too, or 791 /// the useNodes() member function should be used to specify the 792 /// label of the nodes. 789 /// could not be read due to lack of node name resolving. 790 /// Therefore \c skipArcs() function should also be used, or 791 /// \c useNodes() should be used to specify the label of the nodes. 793 792 DigraphReader& skipNodes() { 794 793 LEMON_ASSERT(!_skip_nodes, "Skip nodes already set"); … … 800 799 /// 801 800 /// Omit the reading of the arc section. This implies that each arc 802 /// map reading rule will be aban oned, and the arcs of the graph801 /// map reading rule will be abandoned, and the arcs of the graph 803 802 /// will not be constructed. 804 803 DigraphReader& skipArcs() { … … 1176 1175 }; 1177 1176 1177 /// \brief Return a \ref DigraphReader class 1178 /// 1179 /// This function just returns a \ref DigraphReader class. 1178 1180 /// \relates DigraphReader 1179 1181 template <typename Digraph> … … 1183 1185 } 1184 1186 1187 /// \brief Return a \ref DigraphReader class 1188 /// 1189 /// This function just returns a \ref DigraphReader class. 1185 1190 /// \relates DigraphReader 1186 1191 template <typename Digraph> … … 1191 1196 } 1192 1197 1198 /// \brief Return a \ref DigraphReader class 1199 /// 1200 /// This function just returns a \ref DigraphReader class. 1193 1201 /// \relates DigraphReader 1194 1202 template <typename Digraph> … … 1212 1220 /// \ingroup lemon_io 1213 1221 /// 1214 /// \brief LGFreader for undirected graphs1222 /// \brief \ref lgf-format "LGF" reader for undirected graphs 1215 1223 /// 1216 1224 /// This utility reads an \ref lgf-format "LGF" file. 1225 /// 1226 /// It can be used almost the same way as \c DigraphReader. 1227 /// The only difference is that this class can handle edges and 1228 /// edge maps as well as arcs and arc maps. 1229 /// 1230 /// The columns in the \c \@edges (or \c \@arcs) section are the 1231 /// edge maps. However, if there are two maps with the same name 1232 /// prefixed with \c '+' and \c '-', then these can be read into an 1233 /// arc map. Similarly, an attribute can be read into an arc, if 1234 /// it's value is an edge label prefixed with \c '+' or \c '-'. 1217 1235 template <typename _Graph> 1218 1236 class GraphReader { … … 1263 1281 /// \brief Constructor 1264 1282 /// 1265 /// Construct a undirected graph reader, which reads from the given1283 /// Construct an undirected graph reader, which reads from the given 1266 1284 /// input stream. 1267 1285 GraphReader(std::istream& is, Graph& graph) … … 1272 1290 /// \brief Constructor 1273 1291 /// 1274 /// Construct a undirected graph reader, which reads from the given1292 /// Construct an undirected graph reader, which reads from the given 1275 1293 /// file. 1276 1294 GraphReader(const std::string& fn, Graph& graph) … … 1281 1299 /// \brief Constructor 1282 1300 /// 1283 /// Construct a undirected graph reader, which reads from the given1301 /// Construct an undirected graph reader, which reads from the given 1284 1302 /// file. 1285 1303 GraphReader(const char* fn, Graph& graph) … … 1498 1516 /// \brief Set \c \@nodes section to be read 1499 1517 /// 1500 /// Set \c \@nodes section to be read 1518 /// Set \c \@nodes section to be read. 1501 1519 GraphReader& nodes(const std::string& caption) { 1502 1520 _nodes_caption = caption; … … 1506 1524 /// \brief Set \c \@edges section to be read 1507 1525 /// 1508 /// Set \c \@edges section to be read 1526 /// Set \c \@edges section to be read. 1509 1527 GraphReader& edges(const std::string& caption) { 1510 1528 _edges_caption = caption; … … 1514 1532 /// \brief Set \c \@attributes section to be read 1515 1533 /// 1516 /// Set \c \@attributes section to be read 1534 /// Set \c \@attributes section to be read. 1517 1535 GraphReader& attributes(const std::string& caption) { 1518 1536 _attributes_caption = caption; … … 1545 1563 /// Use previously constructed node set, and specify the node 1546 1564 /// label map and a functor which converts the label map values to 1547 /// std::string.1565 /// \c std::string. 1548 1566 template <typename Map, typename Converter> 1549 1567 GraphReader& useNodes(const Map& map, … … 1578 1596 /// Use previously constructed edge set, and specify the edge 1579 1597 /// label map and a functor which converts the label map values to 1580 /// std::string.1598 /// \c std::string. 1581 1599 template <typename Map, typename Converter> 1582 1600 GraphReader& useEdges(const Map& map, … … 1591 1609 } 1592 1610 1593 /// \brief Skip sthe reading of node section1611 /// \brief Skip the reading of node section 1594 1612 /// 1595 1613 /// Omit the reading of the node section. This implies that each node 1596 /// map reading rule will be aban oned, and the nodes of the graph1614 /// map reading rule will be abandoned, and the nodes of the graph 1597 1615 /// will not be constructed, which usually cause that the edge set 1598 1616 /// could not be read due to lack of node name 1599 /// resolving. Therefore, the \c skipEdges() should be used too, or1600 /// the useNodes() member function should be used to specify the1601 /// label of the nodes.1617 /// could not be read due to lack of node name resolving. 1618 /// Therefore \c skipEdges() function should also be used, or 1619 /// \c useNodes() should be used to specify the label of the nodes. 1602 1620 GraphReader& skipNodes() { 1603 1621 LEMON_ASSERT(!_skip_nodes, "Skip nodes already set"); … … 1606 1624 } 1607 1625 1608 /// \brief Skip sthe reading of edge section1626 /// \brief Skip the reading of edge section 1609 1627 /// 1610 1628 /// Omit the reading of the edge section. This implies that each edge 1611 /// map reading rule will be aban oned, and the edges of the graph1629 /// map reading rule will be abandoned, and the edges of the graph 1612 1630 /// will not be constructed. 1613 1631 GraphReader& skipEdges() { … … 1983 2001 }; 1984 2002 2003 /// \brief Return a \ref GraphReader class 2004 /// 2005 /// This function just returns a \ref GraphReader class. 1985 2006 /// \relates GraphReader 1986 2007 template <typename Graph> … … 1990 2011 } 1991 2012 2013 /// \brief Return a \ref GraphReader class 2014 /// 2015 /// This function just returns a \ref GraphReader class. 1992 2016 /// \relates GraphReader 1993 2017 template <typename Graph> … … 1998 2022 } 1999 2023 2024 /// \brief Return a \ref GraphReader class 2025 /// 2026 /// This function just returns a \ref GraphReader class. 2000 2027 /// \relates GraphReader 2001 2028 template <typename Graph> … … 2011 2038 SectionReader sectionReader(const char* fn); 2012 2039 2040 /// \ingroup lemon_io 2041 /// 2013 2042 /// \brief Section reader class 2014 2043 /// 2015 /// In the \ e LGF file extra sections can be placed, which contain2016 /// any data in arbitrary format. Such sections can be read with2017 /// this class. A reading rule can be added with two different2018 /// functions, with the \c sectionLines() function a functor can2019 /// process the section line-by-line. While with the \c2044 /// In the \ref lgf-format "LGF" file extra sections can be placed, 2045 /// which contain any data in arbitrary format. Such sections can be 2046 /// read with this class. A reading rule can be added to the class 2047 /// with two different functions. With the \c sectionLines() function a 2048 /// functor can process the section line-by-line, while with the \c 2020 2049 /// sectionStream() member the section can be read from an input 2021 2050 /// stream. … … 2106 2135 ///\endcode 2107 2136 /// 2108 /// The functor is implemented as a nstruct:2137 /// The functor is implemented as a struct: 2109 2138 ///\code 2110 2139 /// struct NumberSection { … … 2124 2153 template <typename Functor> 2125 2154 SectionReader& sectionLines(const std::string& type, Functor functor) { 2126 LEMON_ASSERT(!type.empty(), "Type is notempty.");2155 LEMON_ASSERT(!type.empty(), "Type is empty."); 2127 2156 LEMON_ASSERT(_sections.find(type) == _sections.end(), 2128 2157 "Multiple reading of section."); … … 2136 2165 /// 2137 2166 /// The first parameter is the type of the section, the second is 2138 /// a functor, which takes an \c std::istream& and an int&2167 /// a functor, which takes an \c std::istream& and an \c int& 2139 2168 /// parameter, the latter regard to the line number of stream. The 2140 2169 /// functor can read the input while the section go on, and the … … 2142 2171 template <typename Functor> 2143 2172 SectionReader& sectionStream(const std::string& type, Functor functor) { 2144 LEMON_ASSERT(!type.empty(), "Type is notempty.");2173 LEMON_ASSERT(!type.empty(), "Type is empty."); 2145 2174 LEMON_ASSERT(_sections.find(type) == _sections.end(), 2146 2175 "Multiple reading of section."); … … 2187 2216 /// \brief Start the batch processing 2188 2217 /// 2189 /// This function starts the batch processing 2218 /// This function starts the batch processing. 2190 2219 void run() { 2191 2220 … … 2240 2269 }; 2241 2270 2271 /// \brief Return a \ref SectionReader class 2272 /// 2273 /// This function just returns a \ref SectionReader class. 2242 2274 /// \relates SectionReader 2243 2275 inline SectionReader sectionReader(std::istream& is) { … … 2246 2278 } 2247 2279 2280 /// \brief Return a \ref SectionReader class 2281 /// 2282 /// This function just returns a \ref SectionReader class. 2248 2283 /// \relates SectionReader 2249 2284 inline SectionReader sectionReader(const std::string& fn) { … … 2252 2287 } 2253 2288 2289 /// \brief Return a \ref SectionReader class 2290 /// 2291 /// This function just returns a \ref SectionReader class. 2254 2292 /// \relates SectionReader 2255 2293 inline SectionReader sectionReader(const char* fn) { … … 2270 2308 /// reading the graph. 2271 2309 /// 2272 ///\code LgfContents contents("graph.lgf"); 2310 ///\code 2311 /// LgfContents contents("graph.lgf"); 2273 2312 /// contents.run(); 2274 2313 /// 2275 /// // does it contain any node section and arc section2314 /// // Does it contain any node section and arc section? 2276 2315 /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) { 2277 /// std::cerr << "Failure, cannot find graph " << std::endl;2316 /// std::cerr << "Failure, cannot find graph." << std::endl; 2278 2317 /// return -1; 2279 2318 /// } 2280 /// std::cout << "The name of the default node section 2319 /// std::cout << "The name of the default node section: " 2281 2320 /// << contents.nodeSection(0) << std::endl; 2282 /// std::cout << "The number of the arc maps 2321 /// std::cout << "The number of the arc maps: " 2283 2322 /// << contents.arcMaps(0).size() << std::endl; 2284 /// std::cout << "The name of second arc map 2323 /// std::cout << "The name of second arc map: " 2285 2324 /// << contents.arcMaps(0)[1] << std::endl; 2286 2325 ///\endcode … … 2353 2392 } 2354 2393 2355 /// \brief Returns the section name at the given position.2356 /// 2357 /// Returns the section name at the given position.2394 /// \brief Returns the node section name at the given position. 2395 /// 2396 /// Returns the node section name at the given position. 2358 2397 const std::string& nodeSection(int i) const { 2359 2398 return _node_sections[i]; … … 2380 2419 } 2381 2420 2382 /// \brief Returns the section name at the given position.2383 /// 2384 /// Returns the section name at the given position.2421 /// \brief Returns the arc/edge section name at the given position. 2422 /// 2423 /// Returns the arc/edge section name at the given position. 2385 2424 /// \note It is synonym of \c edgeSection(). 2386 2425 const std::string& arcSection(int i) const { … … 2437 2476 } 2438 2477 2439 /// \brief Returns the section name at the given position.2440 /// 2441 /// Returns the section name at the given position.2478 /// \brief Returns the attribute section name at the given position. 2479 /// 2480 /// Returns the attribute section name at the given position. 2442 2481 const std::string& attributeSectionNames(int i) const { 2443 2482 return _attribute_sections[i]; … … 2530 2569 /// @{ 2531 2570 2532 /// \brief Start the reading2533 /// 2534 /// This function starts the reading 2571 /// \brief Starts the reading 2572 /// 2573 /// This function starts the reading. 2535 2574 void run() { 2536 2575 -
lemon/lgf_writer.h
r190 r201 19 19 ///\ingroup lemon_io 20 20 ///\file 21 ///\brief Lemon Graph Formatwriter.21 ///\brief \ref lgf-format "Lemon Graph Format" writer. 22 22 23 23 … … 226 226 }; 227 227 228 bool isWhiteSpace(char c) {228 inline bool isWhiteSpace(char c) { 229 229 return c == ' ' || c == '\t' || c == '\v' || 230 230 c == '\n' || c == '\r' || c == '\f'; 231 231 } 232 232 233 bool isEscaped(char c) {233 inline bool isEscaped(char c) { 234 234 return c == '\\' || c == '\"' || c == '\'' || 235 235 c == '\a' || c == '\b'; 236 236 } 237 237 238 static void writeEscape(std::ostream& os, char c) {238 inline static void writeEscape(std::ostream& os, char c) { 239 239 switch (c) { 240 240 case '\\': … … 277 277 } 278 278 279 bool requireEscape(const std::string& str) {279 inline bool requireEscape(const std::string& str) { 280 280 if (str.empty() || str[0] == '@') return true; 281 281 std::istringstream is(str); … … 289 289 } 290 290 291 std::ostream& writeToken(std::ostream& os, const std::string& str) {291 inline std::ostream& writeToken(std::ostream& os, const std::string& str) { 292 292 293 293 if (requireEscape(str)) { … … 323 323 /// \ingroup lemon_io 324 324 /// 325 /// \brief LGFwriter for directed graphs325 /// \brief \ref lgf-format "LGF" writer for directed graphs 326 326 /// 327 327 /// This utility writes an \ref lgf-format "LGF" file. … … 333 333 /// with the \c nodeMap() or \c arcMap() members. An optional 334 334 /// converter parameter can also be added as a standard functor 335 /// converting from the value type of the map to std::string. If it336 /// is set, it will determine how the map's value typeis written to335 /// converting from the value type of the map to \c std::string. If it 336 /// is set, it will determine how the value type of the map is written to 337 337 /// the output stream. If the functor is not set, then a default 338 338 /// conversion will be used. The \c attribute(), \c node() and \c … … 340 340 /// 341 341 ///\code 342 /// 343 /// 344 /// 345 /// 346 /// 347 /// 348 /// 349 /// 350 /// 342 /// DigraphWriter<Digraph>(std::cout, digraph). 343 /// nodeMap("coordinates", coord_map). 344 /// nodeMap("size", size). 345 /// nodeMap("title", title). 346 /// arcMap("capacity", cap_map). 347 /// node("source", src). 348 /// node("target", trg). 349 /// attribute("caption", caption). 350 /// run(); 351 351 ///\endcode 352 352 /// … … 487 487 /// @{ 488 488 489 /// \brief Node map reading rule490 /// 491 /// Add a node map reading rule to the writer.489 /// \brief Node map writing rule 490 /// 491 /// Add a node map writing rule to the writer. 492 492 template <typename Map> 493 493 DigraphWriter& nodeMap(const std::string& caption, const Map& map) { … … 587 587 } 588 588 589 /// \name Se lect section by name589 /// \name Section captions 590 590 /// @{ 591 591 592 /// \brief Set \c \@nodes section to be read593 /// 594 /// Set \c \@nodes section to be read592 /// \brief Add an additional caption to the \c \@nodes section 593 /// 594 /// Add an additional caption to the \c \@nodes section. 595 595 DigraphWriter& nodes(const std::string& caption) { 596 596 _nodes_caption = caption; … … 598 598 } 599 599 600 /// \brief Set \c \@arcs section to be read601 /// 602 /// Set \c \@arcs section to be read600 /// \brief Add an additional caption to the \c \@arcs section 601 /// 602 /// Add an additional caption to the \c \@arcs section. 603 603 DigraphWriter& arcs(const std::string& caption) { 604 604 _arcs_caption = caption; … … 606 606 } 607 607 608 /// \brief Set \c \@attributes section to be read609 /// 610 /// Set \c \@attributes section to be read608 /// \brief Add an additional caption to the \c \@attributes section 609 /// 610 /// Add an additional caption to the \c \@attributes section. 611 611 DigraphWriter& attributes(const std::string& caption) { 612 612 _attributes_caption = caption; … … 619 619 /// \brief Skip writing the node set 620 620 /// 621 /// The \c \@nodes section will be notwritten to the stream.621 /// The \c \@nodes section will not be written to the stream. 622 622 DigraphWriter& skipNodes() { 623 623 LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member"); … … 628 628 /// \brief Skip writing arc set 629 629 /// 630 /// The \c \@arcs section will be notwritten to the stream.630 /// The \c \@arcs section will not be written to the stream. 631 631 DigraphWriter& skipArcs() { 632 632 LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member"); … … 836 836 /// \brief Start the batch processing 837 837 /// 838 /// This function starts the batch processing 838 /// This function starts the batch processing. 839 839 void run() { 840 840 if (!_skip_nodes) { … … 851 851 } 852 852 853 /// \brief Give sback the stream of the writer854 /// 855 /// Give s back the stream of the writer853 /// \brief Give back the stream of the writer 854 /// 855 /// Give back the stream of the writer. 856 856 std::ostream& ostream() { 857 857 return *_os; … … 861 861 }; 862 862 863 /// \brief Return a \ref DigraphWriter class 864 /// 865 /// This function just returns a \ref DigraphWriter class. 863 866 /// \relates DigraphWriter 864 867 template <typename Digraph> … … 869 872 } 870 873 874 /// \brief Return a \ref DigraphWriter class 875 /// 876 /// This function just returns a \ref DigraphWriter class. 871 877 /// \relates DigraphWriter 872 878 template <typename Digraph> … … 877 883 } 878 884 885 /// \brief Return a \ref DigraphWriter class 886 /// 887 /// This function just returns a \ref DigraphWriter class. 879 888 /// \relates DigraphWriter 880 889 template <typename Digraph> … … 899 908 /// \ingroup lemon_io 900 909 /// 901 /// \brief LGFwriter for directed graphs910 /// \brief \ref lgf-format "LGF" writer for directed graphs 902 911 /// 903 912 /// This utility writes an \ref lgf-format "LGF" file. 913 /// 914 /// It can be used almost the same way as \c DigraphWriter. 915 /// The only difference is that this class can handle edges and 916 /// edge maps as well as arcs and arc maps. 917 /// 918 /// The arc maps are written into the file as two columns, the 919 /// caption of the columns are the name of the map prefixed with \c 920 /// '+' and \c '-'. The arcs are written into the \c \@attributes 921 /// section as a \c '+' or a \c '-' prefix (depends on the direction 922 /// of the arc) and the label of corresponding edge. 904 923 template <typename _Graph> 905 924 class GraphWriter { … … 1024 1043 /// @{ 1025 1044 1026 /// \brief Node map reading rule1027 /// 1028 /// Add a node map reading rule to the writer.1045 /// \brief Node map writing rule 1046 /// 1047 /// Add a node map writing rule to the writer. 1029 1048 template <typename Map> 1030 1049 GraphWriter& nodeMap(const std::string& caption, const Map& map) { … … 1170 1189 } 1171 1190 1172 /// \name Se lect section by name1191 /// \name Section captions 1173 1192 /// @{ 1174 1193 1175 /// \brief Set \c \@nodes section to be read1176 /// 1177 /// Set \c \@nodes section to be read1194 /// \brief Add an additional caption to the \c \@nodes section 1195 /// 1196 /// Add an additional caption to the \c \@nodes section. 1178 1197 GraphWriter& nodes(const std::string& caption) { 1179 1198 _nodes_caption = caption; … … 1181 1200 } 1182 1201 1183 /// \brief Set \c \@edges section to be read1184 /// 1185 /// Set \c \@edges section to be read1202 /// \brief Add an additional caption to the \c \@arcs section 1203 /// 1204 /// Add an additional caption to the \c \@arcs section. 1186 1205 GraphWriter& edges(const std::string& caption) { 1187 1206 _edges_caption = caption; … … 1189 1208 } 1190 1209 1191 /// \brief Set \c \@attributes section to be read1192 /// 1193 /// Set \c \@attributes section to be read1210 /// \brief Add an additional caption to the \c \@attributes section 1211 /// 1212 /// Add an additional caption to the \c \@attributes section. 1194 1213 GraphWriter& attributes(const std::string& caption) { 1195 1214 _attributes_caption = caption; … … 1202 1221 /// \brief Skip writing the node set 1203 1222 /// 1204 /// The \c \@nodes section will be notwritten to the stream.1223 /// The \c \@nodes section will not be written to the stream. 1205 1224 GraphWriter& skipNodes() { 1206 1225 LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member"); … … 1211 1230 /// \brief Skip writing edge set 1212 1231 /// 1213 /// The \c \@edges section will be notwritten to the stream.1232 /// The \c \@edges section will not be written to the stream. 1214 1233 GraphWriter& skipEdges() { 1215 1234 LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member"); … … 1419 1438 /// \brief Start the batch processing 1420 1439 /// 1421 /// This function starts the batch processing 1440 /// This function starts the batch processing. 1422 1441 void run() { 1423 1442 if (!_skip_nodes) { … … 1434 1453 } 1435 1454 1436 /// \brief Give sback the stream of the writer1437 /// 1438 /// Give sback the stream of the writer1455 /// \brief Give back the stream of the writer 1456 /// 1457 /// Give back the stream of the writer 1439 1458 std::ostream& ostream() { 1440 1459 return *_os; … … 1444 1463 }; 1445 1464 1465 /// \brief Return a \ref GraphWriter class 1466 /// 1467 /// This function just returns a \ref GraphWriter class. 1446 1468 /// \relates GraphWriter 1447 1469 template <typename Graph> … … 1451 1473 } 1452 1474 1475 /// \brief Return a \ref GraphWriter class 1476 /// 1477 /// This function just returns a \ref GraphWriter class. 1453 1478 /// \relates GraphWriter 1454 1479 template <typename Graph> … … 1458 1483 } 1459 1484 1485 /// \brief Return a \ref GraphWriter class 1486 /// 1487 /// This function just returns a \ref GraphWriter class. 1460 1488 /// \relates GraphWriter 1461 1489 template <typename Graph> -
test/CMakeLists.txt
r171 r203 11 11 dim_test 12 12 error_test 13 graph_copy_test 13 14 graph_test 14 15 graph_utils_test 16 heap_test 15 17 kruskal_test 16 18 maps_test -
test/Makefile.am
r171 r203 4 4 noinst_HEADERS += \ 5 5 test/graph_test.h \ 6 test/heap_test.h \7 6 test/graph_maps_test.h \ 8 7 test/test_tools.h … … 16 15 test/dim_test \ 17 16 test/error_test \ 17 test/graph_copy_test \ 18 18 test/graph_test \ 19 19 test/graph_utils_test \ 20 test/heap_test \ 20 21 test/kruskal_test \ 21 22 test/maps_test \ … … 37 38 test_dim_test_SOURCES = test/dim_test.cc 38 39 test_error_test_SOURCES = test/error_test.cc 40 test_graph_copy_test_SOURCES = test/graph_copy_test.cc 39 41 test_graph_test_SOURCES = test/graph_test.cc 40 42 test_graph_utils_test_SOURCES = test/graph_utils_test.cc 41 #test_heap_test_SOURCES = test/heap_test.cc43 test_heap_test_SOURCES = test/heap_test.cc 42 44 test_kruskal_test_SOURCES = test/kruskal_test.cc 43 45 test_maps_test_SOURCES = test/maps_test.cc -
test/heap_test.cc
r171 r203 25 25 #include <lemon/concepts/heap.h> 26 26 27 #include <lemon/ list_graph.h>27 #include <lemon/smart_graph.h> 28 28 29 #include <lemon/digraph_reader.h> 29 #include <lemon/lgf_reader.h> 30 #include <lemon/dijkstra.h> 31 #include <lemon/maps.h> 30 32 31 33 #include <lemon/bin_heap.h> 32 #include <lemon/fib_heap.h>33 #include <lemon/radix_heap.h>34 #include <lemon/bucket_heap.h>35 34 36 35 #include "test_tools.h" 37 36 38 #include "heap_test.h"39 40 #include <lemon/time_measure.h>41 42 37 using namespace lemon; 43 38 using namespace lemon::concepts; 39 40 typedef ListDigraph Digraph; 41 DIGRAPH_TYPEDEFS(Digraph); 42 43 char test_lgf[] = 44 "@nodes\n" 45 "label\n" 46 "0\n" 47 "1\n" 48 "2\n" 49 "3\n" 50 "4\n" 51 "5\n" 52 "6\n" 53 "7\n" 54 "8\n" 55 "9\n" 56 "@arcs\n" 57 " label capacity\n" 58 "0 5 0 94\n" 59 "3 9 1 11\n" 60 "8 7 2 83\n" 61 "1 2 3 94\n" 62 "5 7 4 35\n" 63 "7 4 5 84\n" 64 "9 5 6 38\n" 65 "0 4 7 96\n" 66 "6 7 8 6\n" 67 "3 1 9 27\n" 68 "5 2 10 77\n" 69 "5 6 11 69\n" 70 "6 5 12 41\n" 71 "4 6 13 70\n" 72 "3 2 14 45\n" 73 "7 9 15 93\n" 74 "5 9 16 50\n" 75 "9 0 17 94\n" 76 "9 6 18 67\n" 77 "0 9 19 86\n" 78 "@attributes\n" 79 "source 3\n"; 80 81 int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26, 1, 9, 4, 34}; 82 int test_inc[] = {20, 28, 34, 16, 0, 46, 44, 0, 42, 32, 14, 8, 6, 37}; 83 84 int test_len = sizeof(test_seq) / sizeof(test_seq[0]); 85 86 template <typename Heap> 87 void heapSortTest() { 88 RangeMap<int> map(test_len, -1); 89 90 Heap heap(map); 91 92 std::vector<int> v(test_len); 93 94 for (int i = 0; i < test_len; ++i) { 95 v[i] = test_seq[i]; 96 heap.push(i, v[i]); 97 } 98 std::sort(v.begin(), v.end()); 99 for (int i = 0; i < test_len; ++i) { 100 check(v[i] == heap.prio() ,"Wrong order in heap sort."); 101 heap.pop(); 102 } 103 } 104 105 template <typename Heap> 106 void heapIncreaseTest() { 107 RangeMap<int> map(test_len, -1); 108 109 Heap heap(map); 110 111 std::vector<int> v(test_len); 112 113 for (int i = 0; i < test_len; ++i) { 114 v[i] = test_seq[i]; 115 heap.push(i, v[i]); 116 } 117 for (int i = 0; i < test_len; ++i) { 118 v[i] += test_inc[i]; 119 heap.increase(i, v[i]); 120 } 121 std::sort(v.begin(), v.end()); 122 for (int i = 0; i < test_len; ++i) { 123 check(v[i] == heap.prio() ,"Wrong order in heap increase test."); 124 heap.pop(); 125 } 126 } 127 128 129 130 template <typename Heap> 131 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, 132 Node source) { 133 134 typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>:: 135 Create dijkstra(digraph, length); 136 137 dijkstra.run(source); 138 139 for(ArcIt a(digraph); a != INVALID; ++a) { 140 Node s = digraph.source(a); 141 Node t = digraph.target(a); 142 if (dijkstra.reached(s)) { 143 check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a], 144 "Error in a shortest path tree!"); 145 } 146 } 147 148 for(NodeIt n(digraph); n != INVALID; ++n) { 149 if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) { 150 Arc a = dijkstra.predArc(n); 151 Node s = digraph.source(a); 152 check( dijkstra.dist(n) - dijkstra.dist(s) == length[a], 153 "Error in a shortest path tree!"); 154 } 155 } 156 157 } 44 158 45 159 int main() { … … 47 161 typedef int Item; 48 162 typedef int Prio; 49 typedef IntIntMap ItemIntMap; 163 typedef RangeMap<int> ItemIntMap; 164 165 Digraph digraph; 166 IntArcMap length(digraph); 167 Node source; 50 168 51 typedef ListDigraph Digraph; 52 53 typedef Digraph::Arc Arc; 54 typedef Digraph::Node Node; 55 typedef Digraph::ArcIt ArcIt; 56 typedef Digraph::NodeIt NodeIt; 57 typedef Digraph::ArcMap<int> LengthMap; 58 59 Digraph digraph; 60 LengthMap length(digraph); 61 Node start; 62 63 /// \todo create own test digraph 64 65 std::string f_name; 66 if( getenv("srcdir") ) 67 f_name = std::string(getenv("srcdir")); 68 else f_name = "."; 69 f_name += "/test/dijkstra_test.lgf"; 70 71 std::ifstream input(f_name.c_str()); 72 check(input, "Input file '" << f_name << "' not found."); 73 DigraphReader<Digraph>(input, digraph). 74 readArcMap("capacity", length). 75 readNode("source", start). 169 std::istringstream input(test_lgf); 170 digraphReader(input, digraph). 171 arcMap("capacity", length). 172 node("source", source). 76 173 run(); 77 174 78 175 { 79 std::cout << "Checking Bin Heap" << std::endl;80 81 176 typedef BinHeap<Prio, ItemIntMap> IntHeap; 82 177 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 83 heapSortTest<IntHeap>( 100);84 heapIncreaseTest<IntHeap>( 100);178 heapSortTest<IntHeap>(); 179 heapIncreaseTest<IntHeap>(); 85 180 86 typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap; 87 checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>(); 88 Timer timer; 89 dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start); 90 std::cout << timer << std::endl; 91 } 92 { 93 std::cout << "Checking Fib Heap" << std::endl; 94 95 typedef FibHeap<Prio, ItemIntMap> IntHeap; 96 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 97 heapSortTest<IntHeap>(100); 98 heapIncreaseTest<IntHeap>(100); 99 100 typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap; 101 checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>(); 102 Timer timer; 103 dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start); 104 std::cout << timer << std::endl; 105 } 106 { 107 std::cout << "Checking Radix Heap" << std::endl; 108 109 typedef RadixHeap<ItemIntMap> IntHeap; 110 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 111 heapSortTest<IntHeap>(100); 112 heapIncreaseTest<IntHeap>(100); 113 114 typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap; 115 checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>(); 116 Timer timer; 117 dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start); 118 std::cout << timer << std::endl; 119 } 120 121 { 122 std::cout << "Checking Bucket Heap" << std::endl; 123 124 typedef BucketHeap<ItemIntMap> IntHeap; 125 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 126 heapSortTest<IntHeap>(100); 127 heapIncreaseTest<IntHeap>(100); 128 129 typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap; 130 checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>(); 131 Timer timer; 132 dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start); 133 std::cout << timer << std::endl; 181 typedef BinHeap<Prio, IntNodeMap > NodeHeap; 182 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 183 dijkstraHeapTest<NodeHeap>(digraph, length, source); 134 184 } 135 185
Note: See TracChangeset
for help on using the changeset viewer.