Changeset 2084:59769591eb60 in lemon-0.x for lemon
- Timestamp:
- 05/15/06 11:49:51 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2749
- Location:
- lemon
- Files:
-
- 12 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bpugraph_adaptor.h
r2040 r2084 410 410 /// 411 411 /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's 412 /// a-nodeset will be the original graph's b-nodeset and the adaptor's 413 /// b-nodeset will be the original graph's a-nodeset. 412 /// anode-set will be the original graph's bnode-set and the adaptor's 413 /// bnode-set will be the original graph's anode-set. 414 /// 415 /// As example look at an algorithm what can be sped up with the 416 /// swap bipartite undirected graph adaptor. If we want to find the 417 /// maximum matching in the bipartite graph then it will be not changed 418 /// if we swap the two nodesets. But the algorithm use the two nodeset 419 /// different way. If we swap the nodesets it provides different 420 /// running time. We run a test on random bipartite graphs with 421 /// different rate of the anode-set size and bnode-set size. 422 /// We always made graphs with 10000 nodes and 20000 edges and we 423 /// computed the maximum cardinality matching with the Hopcroft-Karp 424 /// algorithm. 425 /// 426 /// The next diagram shows the running time of the tests. If the anode-set 427 /// is smaller than the bnode-set the running time is better than with 428 /// the swapped graph. Other conclusion is that the running time 429 /// is greater when the two nodesets size are nearly equal. 430 /// 431 /// \image html swap_test.png 432 /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth 433 /// 434 /// The next part shows how can we swap the two nodeset: 435 /// 436 ///\code 437 /// typedef SwapBpUGraphAdaptor<BpUGraph> SBpUGraph; 438 /// SBpUGraph sbpugraph(bpugraph); 439 /// MaxBipartiteMatching<SBpUGraph> sbpumatch(sbpugraph); 440 ///\endcode 414 441 template <typename _BpUGraph> 415 442 class SwapBpUGraphAdaptor … … 426 453 public: 427 454 455 /// \brief Construct a swapped graph. 456 /// 457 /// Construct a swapped graph. 428 458 explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); } 429 459 -
lemon/eps.h
r2008 r2084 27 27 #include<lemon/xy.h> 28 28 29 ///\ingroup io_group29 ///\ingroup eps_io 30 30 ///\file 31 31 ///\brief Simple tool to create \c .eps files … … 35 35 namespace lemon { 36 36 37 ///\ingroup io_group37 ///\ingroup eps_io 38 38 ///\brief A simple tool to create \c .eps files 39 39 /// -
lemon/graph_adaptor.h
r2081 r2084 265 265 /// implements the graph obtained from \c g by 266 266 /// reversing the orientation of its edges. 267 /// 268 /// A good example of using RevGraphAdaptor is to decide that the 269 /// directed graph is wheter strongly connected or not. If from one 270 /// node each node is reachable and from each node is reachable this 271 /// node then and just then the graph is strongly connected. Instead of 272 /// this condition we use a little bit different. From one node each node 273 /// ahould be reachable in the graph and in the reversed graph. Now this 274 /// condition can be checked with the Dfs algorithm class and the 275 /// RevGraphAdaptor algorithm class. 276 /// 277 /// And look at the code: 278 /// 279 ///\code 280 /// bool stronglyConnected(const Graph& graph) { 281 /// if (NodeIt(graph) == INVALID) return true; 282 /// Dfs<Graph> dfs(graph); 283 /// dfs.run(NodeIt(graph)); 284 /// for (NodeIt it(graph); it != INVALID; ++it) { 285 /// if (!dfs.reached(it)) { 286 /// return false; 287 /// } 288 /// } 289 /// typedef RevGraphAdaptor<const Graph> RGraph; 290 /// RGraph rgraph(graph); 291 /// DfsVisit<RGraph> rdfs(rgraph); 292 /// rdfs.run(NodeIt(graph)); 293 /// for (NodeIt it(graph); it != INVALID; ++it) { 294 /// if (!rdfs.reached(it)) { 295 /// return false; 296 /// } 297 /// } 298 /// return true; 299 /// } 300 ///\endcode 267 301 template<typename _Graph> 268 302 class RevGraphAdaptor : … … 2388 2422 /// 2389 2423 /// The second solution contains just 3 disjoint paths while the first 4. 2390 /// The full code can be found in the \ref disjoint_paths .cc demo file.2424 /// The full code can be found in the \ref disjoint_paths_demo.cc demo file. 2391 2425 /// 2392 2426 /// This graph adaptor is fully conform to the … … 2588 2622 }; 2589 2623 2624 /// \brief Just gives back a split graph adaptor 2625 /// 2626 /// Just gives back a split graph adaptor 2627 template<typename Graph> 2628 SplitGraphAdaptor<Graph> 2629 splitGraphAdaptor(const Graph& graph) { 2630 return SplitGraphAdaptor<Graph>(graph); 2631 } 2632 2590 2633 2591 2634 } //namespace lemon -
lemon/graph_reader.h
r2037 r2084 17 17 */ 18 18 19 ///\ingroup io_group19 ///\ingroup lemon_io 20 20 ///\file 21 21 ///\brief Lemon Graph Format reader. … … 31 31 namespace lemon { 32 32 33 /// \addtogroup io_group33 /// \addtogroup lemon_io 34 34 /// @{ 35 35 -
lemon/graph_to_eps.h
r2028 r2084 42 42 43 43 44 ///\ingroup io_group44 ///\ingroup eps_io 45 45 ///\file 46 46 ///\brief Simple graph drawer … … 1043 1043 ///Generates an EPS file from a graph 1044 1044 1045 ///\ingroup io_group1045 ///\ingroup eps_io 1046 1046 ///Generates an EPS file from a graph. 1047 1047 ///\param g is a reference to the graph to be printed … … 1072 1072 ///Generates an EPS file from a graph 1073 1073 1074 ///\ingroup io_group1074 ///\ingroup eps_io 1075 1075 ///This function does the same as 1076 1076 ///\ref graphToEps(G &g,std::ostream& os) … … 1088 1088 ///Generates an EPS file from a graph 1089 1089 1090 ///\ingroup io_group1090 ///\ingroup eps_io 1091 1091 ///This function does the same as 1092 1092 ///\ref graphToEps(G &g,std::ostream& os) -
lemon/kruskal.h
r1993 r2084 25 25 #include <lemon/bits/utility.h> 26 26 #include <lemon/bits/traits.h> 27 28 /**29 @defgroup spantree Minimum Cost Spanning Tree Algorithms30 @ingroup galgs31 \brief This group containes the algorithms for finding a minimum cost spanning32 tree in a graph33 34 This group containes the algorithms for finding a minimum cost spanning35 tree in a graph36 */37 27 38 28 ///\ingroup spantree -
lemon/lemon_reader.h
r2016 r2084 17 17 */ 18 18 19 ///\ingroup io_group19 ///\ingroup lemon_io 20 20 ///\file 21 21 ///\brief Lemon Format reader. … … 457 457 } 458 458 459 /// \ingroup io_group459 /// \ingroup lemon_io 460 460 /// \brief Lemon Format reader class. 461 461 /// … … 524 524 char_type* eptr() { return _eptr; } 525 525 526 int blen() { return _eptr - _base; }527 528 void setb(char_type* buf, int len) {526 int_type blen() { return _eptr - _base; } 527 528 void setb(char_type* buf, int_type len) { 529 529 _base = buf; 530 530 _eptr = buf + len; … … 582 582 } 583 583 584 virtual int underflow() {584 virtual int_type underflow() { 585 585 char c; 586 586 if (_is.read(&c, 1)) { … … 613 613 } 614 614 615 virtual int sync() {615 virtual int_type sync() { 616 616 return EOF; 617 617 } -
lemon/lemon_writer.h
r2016 r2084 17 17 */ 18 18 19 ///\ingroup io_group19 ///\ingroup lemon_io 20 20 ///\file 21 21 ///\brief Lemon Format writer. … … 258 258 } 259 259 260 /// \ingroup io_group260 /// \ingroup lemon_io 261 261 /// \brief Lemon Format writer class. 262 262 /// … … 311 311 virtual std::string header() = 0; 312 312 313 /// \brief 313 /// \brief Writer function of the section. 314 314 /// 315 315 /// Write the content of the section. 316 316 virtual void write(std::ostream& os) = 0; 317 318 /// \brief Gives back true when the section should be written. 319 /// 320 /// Gives back true when the section should be written. 321 virtual bool valid() { return true; } 317 322 }; 318 323 … … 356 361 SectionWriters::iterator it; 357 362 for (it = writers.begin(); it != writers.end(); ++it) { 358 *os << (*it)->header() << std::endl; 359 (*it)->write(*os); 363 if ((*it)->valid()) { 364 *os << (*it)->header() << std::endl; 365 (*it)->write(*os); 366 } 360 367 } 361 368 *os << "@end" << std::endl; … … 465 472 virtual void write(std::ostream& os) { 466 473 for (int i = 0; i < (int)writers.size(); ++i) { 467 if (writers[i].first == "label" || (writers[i].first == "id" && labelMap == 0)) {474 if (writers[i].first == "label") { 468 475 labelMap = writers[i].second; 469 476 forceLabelMap = false; … … 637 644 } 638 645 for (int i = 0; i < (int)writers.size(); ++i) { 639 if (writers[i].first == "label" || (writers[i].first == "id" && labelMap == 0)) {646 if (writers[i].first == "label") { 640 647 labelMap = writers[i].second; 641 648 forceLabelMap = false; … … 1009 1016 } 1010 1017 } 1018 1019 /// \brief Gives back true when the section should be written. 1020 /// 1021 /// Gives back true when the section should be written. 1022 virtual bool valid() { return !writers.empty(); } 1011 1023 1012 1024 private: … … 1088 1100 } 1089 1101 } 1102 1103 /// \brief Gives back true when the section should be written. 1104 /// 1105 /// Gives back true when the section should be written. 1106 virtual bool valid() { return !writers.empty(); } 1090 1107 1091 1108 private: … … 1190 1207 } 1191 1208 } 1209 1210 /// \brief Gives back true when the section should be written. 1211 /// 1212 /// Gives back true when the section should be written. 1213 virtual bool valid() { 1214 return !uEdgeWriters.empty() || !edgeWriters.empty(); 1215 } 1192 1216 1193 1217 private: … … 1289 1313 } 1290 1314 1315 /// \brief Gives back true when the section should be written. 1316 /// 1317 /// Gives back true when the section should be written. 1318 virtual bool valid() { return !writers.empty(); } 1319 1291 1320 private: 1292 1321 std::string name; -
lemon/matrix_maps.h
r2072 r2084 48 48 49 49 50 /// \brief Constructor of the row map 51 /// 52 /// Constructor of the row map. 50 53 MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _row) 51 54 : matrix(_matrix), row(_row) {} … … 92 95 93 96 97 /// \brief Constructor of the row map 98 /// 99 /// Constructor of the row map. 94 100 ConstMatrixRowMap(const MatrixMap& _matrix, 95 101 typename MatrixMap::FirstKey _row) … … 109 115 }; 110 116 117 /// \ingroup matrices 118 /// 111 119 /// \brief Gives back a row view of the matrix map 112 120 /// 113 /// \ingroup matrices114 121 /// Gives back a row view of the matrix map. 115 122 /// 123 /// \sa MatrixRowMap 124 /// \sa ConstMatrixRowMap 116 125 template <typename MatrixMap> 117 126 MatrixRowMap<MatrixMap> matrixRowMap(MatrixMap& matrixMap, … … 138 147 typedef typename MatrixMap::Value Value; 139 148 149 /// \brief Constructor of the column map 150 /// 151 /// Constructor of the column map. 140 152 MatrixColMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _col) 141 153 : matrix(_matrix), col(_col) {} … … 181 193 typedef typename MatrixMap::Value Value; 182 194 195 /// \brief Constructor of the column map 196 /// 197 /// Constructor of the column map. 183 198 ConstMatrixColMap(const MatrixMap& _matrix, 184 199 typename MatrixMap::SecondKey _col) … … 198 213 }; 199 214 215 /// \ingroup matrices 216 /// 200 217 /// \brief Gives back a column view of the matrix map 201 218 /// 202 /// \ingroup matrices203 219 /// Gives back a column view of the matrix map. 204 220 /// 221 /// \sa MatrixColMap 222 /// \sa ConstMatrixColMap 205 223 template <typename MatrixMap> 206 224 MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap, -
lemon/path.h
r2045 r2084 17 17 */ 18 18 19 /**20 @defgroup paths Path Structures21 @ingroup datas22 \brief Path structures implemented in LEMON.23 24 LEMON provides flexible data structures25 to work with paths.26 27 All of them have the same interface, especially they can be built or extended28 using a standard Builder subclass. This make is easy to have e.g. the Dijkstra29 algorithm to store its result in any kind of path structure.30 31 \sa lemon::concept::Path32 33 */34 19 35 20 ///\ingroup paths -
lemon/radix_sort.h
r2042 r2084 20 20 #define RADIX_SORT_H 21 21 22 /// \ingroup aux dat22 /// \ingroup auxalg 23 23 /// \file 24 24 /// \brief Radix sort … … 195 195 } 196 196 197 /// \ingroup aux dat197 /// \ingroup auxalg 198 198 /// 199 199 /// \brief Sorts the stl compatible range into ascending order. … … 412 412 } 413 413 414 /// \ingroup aux dat414 /// \ingroup auxalg 415 415 /// 416 416 /// \brief Sorts stable the stl compatible range into ascending order. -
lemon/ugraph_adaptor.h
r2069 r2084 39 39 namespace lemon { 40 40 41 /// \ingroup graph_adaptors42 ///43 41 /// \brief Base type for the Graph Adaptors 44 42 /// … … 234 232 235 233 /// \ingroup graph_adaptors 234 /// 235 /// \brief Trivial undirected graph adaptor 236 /// 237 /// This class is an adaptor which does not change the adapted undirected 238 /// graph. It can be used only to test the undirected graph adaptors. 236 239 template <typename _UGraph> 237 240 class UGraphAdaptor … … 349 352 } 350 353 351 /// \e352 354 /// \brief Hide the given node in the graph. 355 /// 353 356 /// This function hides \c n in the graph, i.e. the iteration 354 357 /// jumps over it. This is done by simply setting the value of \c n … … 356 359 void hide(const Node& n) const { node_filter_map->set(n, false); } 357 360 358 /// \e359 361 /// \brief Hide the given undirected edge in the graph. 362 /// 360 363 /// This function hides \c e in the graph, i.e. the iteration 361 364 /// jumps over it. This is done by simply setting the value of \c e 362 /// to be false in the corresponding edge-map.365 /// to be false in the corresponding uedge-map. 363 366 void hide(const UEdge& e) const { uedge_filter_map->set(e, false); } 364 367 365 /// \e366 368 /// \brief Unhide the given node in the graph. 369 /// 367 370 /// The value of \c n is set to be true in the node-map which stores 368 371 /// hide information. If \c n was hidden previuosly, then it is shown … … 370 373 void unHide(const Node& n) const { node_filter_map->set(n, true); } 371 374 372 /// \e373 374 /// The value of \c e is set to be true in the edge-map which stores375 /// \brief Hide the given undirected edge in the graph. 376 /// 377 /// The value of \c e is set to be true in the uedge-map which stores 375 378 /// hide information. If \c e was hidden previuosly, then it is shown 376 379 /// again 377 380 void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); } 378 381 382 /// \brief Returns true if \c n is hidden. 383 /// 379 384 /// Returns true if \c n is hidden. 380 381 ///\e382 ///383 385 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } 384 386 385 /// Returns true if \c n is hidden. 386 387 ///\e 388 /// 387 /// \brief Returns true if \c e is hidden. 388 /// 389 /// Returns true if \c e is hidden. 389 390 bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; } 390 391 … … 578 579 } 579 580 580 /// \e581 581 /// \brief Hide the given node in the graph. 582 /// 582 583 /// This function hides \c n in the graph, i.e. the iteration 583 584 /// jumps over it. This is done by simply setting the value of \c n … … 585 586 void hide(const Node& n) const { node_filter_map->set(n, false); } 586 587 587 /// \e588 588 /// \brief Hide the given undirected edge in the graph. 589 /// 589 590 /// This function hides \c e in the graph, i.e. the iteration 590 591 /// jumps over it. This is done by simply setting the value of \c e 591 /// to be false in the corresponding edge-map.592 /// to be false in the corresponding uedge-map. 592 593 void hide(const UEdge& e) const { uedge_filter_map->set(e, false); } 593 594 594 /// \e595 595 /// \brief Unhide the given node in the graph. 596 /// 596 597 /// The value of \c n is set to be true in the node-map which stores 597 598 /// hide information. If \c n was hidden previuosly, then it is shown … … 599 600 void unHide(const Node& n) const { node_filter_map->set(n, true); } 600 601 601 /// \e602 603 /// The value of \c e is set to be true in the edge-map which stores602 /// \brief Hide the given undirected edge in the graph. 603 /// 604 /// The value of \c e is set to be true in the uedge-map which stores 604 605 /// hide information. If \c e was hidden previuosly, then it is shown 605 606 /// again 606 607 void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); } 607 608 609 /// \brief Returns true if \c n is hidden. 610 /// 608 611 /// Returns true if \c n is hidden. 609 610 ///\e611 ///612 612 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } 613 613 614 /// Returns true if \c n is hidden. 615 616 ///\e 617 /// 614 /// \brief Returns true if \c e is hidden. 615 /// 616 /// Returns true if \c e is hidden. 618 617 bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; } 619 618 … … 734 733 /// node-filter. 735 734 /// 736 /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to737 /// \c Graph::Node that is why \c g.id(n) can be applied.738 ///739 735 template<typename _UGraph, typename NodeFilterMap, 740 736 typename UEdgeFilterMap, bool checked = true>
Note: See TracChangeset
for help on using the changeset viewer.