Changeset 911:89a4fbb99cad in lemon-0.x
- Timestamp:
- 09/28/04 09:00:58 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1222
- Files:
-
- 11 edited
-
doc/graphs.dox (modified) (2 diffs)
-
src/hugo/bfs.h (modified) (2 diffs)
-
src/hugo/dfs.h (modified) (2 diffs)
-
src/hugo/dijkstra.h (modified) (1 diff)
-
src/hugo/fib_heap.h (modified) (6 diffs)
-
src/hugo/graph_wrapper.h (modified) (1 diff)
-
src/hugo/list_graph.h (modified) (1 diff)
-
src/hugo/maps.h (modified) (2 diffs)
-
src/hugo/preflow.h (modified) (6 diffs)
-
src/hugo/skeletons/graph.h (modified) (5 diffs)
-
src/hugo/skeletons/sym_graph.h (modified) (8 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/graphs.dox
r880 r911 29 29 The implemented graph structures are the following. 30 30 \li \ref hugo::ListGraph "ListGraph" is the most versatile graph class. It meets 31 the hugo::skeleton::ErasableGraph "ErasableGraph" concept31 the \ref hugo::skeleton::ErasableGraph "ErasableGraph" concept 32 32 and it also have some convenience features. 33 33 \li \ref hugo::SmartGraph "SmartGraph" is a more memory … … 46 46 are shared by the edge pairs. 47 47 \li \ref hugo::FullGraph "FullGraph" 48 implements a full graph. It is a \ref ConstGraph, so you cannot48 implements a full graph. It is a \ref hugo::skeleton::StaticGraph, so you cannot 49 49 change the number of nodes once it is constructed. It is extremely memory 50 50 efficient: it uses constant amount of memory independently from the number of -
src/hugo/bfs.h
r906 r911 50 50 ///The type of the underlying graph. 51 51 typedef GR Graph; 52 /// .52 ///\e 53 53 typedef typename Graph::Node Node; 54 /// .54 ///\e 55 55 typedef typename Graph::NodeIt NodeIt; 56 /// .56 ///\e 57 57 typedef typename Graph::Edge Edge; 58 /// .58 ///\e 59 59 typedef typename Graph::OutEdgeIt OutEdgeIt; 60 60 … … 109 109 110 110 ///\param _G the graph the algorithm will run on. 111 /// 111 112 Bfs(const Graph& _G) : 112 113 G(&_G), -
src/hugo/dfs.h
r906 r911 49 49 ///The type of the underlying graph. 50 50 typedef GR Graph; 51 /// .51 ///\e 52 52 typedef typename Graph::Node Node; 53 /// .53 ///\e 54 54 typedef typename Graph::NodeIt NodeIt; 55 /// .55 ///\e 56 56 typedef typename Graph::Edge Edge; 57 /// .57 ///\e 58 58 typedef typename Graph::OutEdgeIt OutEdgeIt; 59 59 … … 108 108 109 109 ///\param _G the graph the algorithm will run on. 110 /// 110 111 Dfs(const Graph& _G) : 111 112 G(&_G), -
src/hugo/dijkstra.h
r906 r911 72 72 ///The type of the underlying graph. 73 73 typedef GR Graph; 74 /// .74 ///\e 75 75 typedef typename Graph::Node Node; 76 /// .76 ///\e 77 77 typedef typename Graph::NodeIt NodeIt; 78 /// .78 ///\e 79 79 typedef typename Graph::Edge Edge; 80 /// .80 ///\e 81 81 typedef typename Graph::OutEdgeIt OutEdgeIt; 82 82 -
src/hugo/fib_heap.h
r906 r911 36 36 ///is a data structure for storing items with specified values called \e 37 37 ///priorities in such a way that finding the item with minimum priority is 38 ///efficient. \ refCompare specifies the ordering of the priorities. In a heap38 ///efficient. \c Compare specifies the ordering of the priorities. In a heap 39 39 ///one can change the priority of an item, add or erase an item, etc. 40 40 /// … … 118 118 void push (Item const item, PrioType const value); 119 119 120 ///Returns the item with minimum priority relative to \ refCompare.121 122 /** 123 This method returns the item with minimum priority relative to \ ref120 ///Returns the item with minimum priority relative to \c Compare. 121 122 /** 123 This method returns the item with minimum priority relative to \c 124 124 Compare. 125 125 \pre The heap must be nonempty. … … 127 127 Item top() const { return container[minimum].name; } 128 128 129 ///Returns the minimum priority relative to \ refCompare.130 131 /** 132 It returns the minimum priority relative to \ refCompare.129 ///Returns the minimum priority relative to \c Compare. 130 131 /** 132 It returns the minimum priority relative to \c Compare. 133 133 \pre The heap must be nonempty. 134 134 */ … … 156 156 157 157 158 ///Deletes the item with minimum priority relative to \ refCompare.159 160 /** 161 This method deletes the item with minimum priority relative to \ ref158 ///Deletes the item with minimum priority relative to \c Compare. 159 160 /** 161 This method deletes the item with minimum priority relative to \c 162 162 Compare from the heap. 163 163 \pre The heap must be non-empty. … … 178 178 This method decreases the priority of \c item to \c value. 179 179 \pre \c item must be stored in the heap with priority at least \c 180 value relative to \ refCompare.180 value relative to \c Compare. 181 181 */ 182 182 void decrease (Item item, PrioType const value); … … 188 188 there is no precondition on the priority of \c item, this 189 189 method should be used only if it is indeed necessary to increase 190 (relative to \ refCompare) the priority of \c item, because this190 (relative to \c Compare) the priority of \c item, because this 191 191 method is inefficient. 192 192 */ -
src/hugo/graph_wrapper.h
r910 r911 606 606 /// bidirected graph made from a directed one. 607 607 /// 608 /// A wrapper for composing a subgraph of a 609 /// bidirected graph made from a directed one. 610 /// 608 611 ///\warning Graph wrappers are in even more experimental state than the other 609 612 ///parts of the lib. Use them at you own risk. -
src/hugo/list_graph.h
r909 r911 422 422 ///of oppositely directed edges. 423 423 ///There is a new edge map type called 424 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"424 ///\ref hugo::SymListGraph::SymEdgeMap "SymEdgeMap" 425 425 ///that complements this 426 426 ///feature by 427 427 ///storing shared values for the edge pairs. The usual 428 ///\ref Graph::EdgeMap "EdgeMap"428 ///\ref hugo::skeleton::StaticGraph::EdgeMap "EdgeMap" 429 429 ///can be used 430 430 ///as well. 431 431 /// 432 432 ///The oppositely directed edge can also be obtained easily 433 ///using \ref opposite.433 ///using \ref hugo::SymListGraph::opposite() "opposite()" member function. 434 434 /// 435 435 ///Here erase(Edge) deletes a pair of edges. -
src/hugo/maps.h
r906 r911 36 36 { 37 37 public: 38 /// .38 ///\e 39 39 typedef K KeyType; 40 /// .40 ///\e 41 41 typedef T ValueType; 42 42 }; … … 75 75 /// (More exactly it will be default constructed.) 76 76 ConstMap() {} 77 /// .77 ///\e 78 78 79 79 /// \param _v The initial value of the map. 80 /// 80 81 ConstMap(const T &_v) : v(_v) {} 81 82 -
src/hugo/preflow.h
r906 r911 45 45 ///setFlow. 46 46 /// 47 ///After running \ref phase1() or \ref preflow(), the actual flow 47 ///After running \ref hugo::Preflow::phase1() "phase1()" 48 ///or \ref hugo::Preflow::run() "run()", the actual flow 48 49 ///value can be obtained by calling \ref flowValue(). The minimum 49 50 ///value cut can be written into a <tt>bool</tt> node map by … … 97 98 ///- \c PRE_FLOW: any preflow, i.e. the sum of the in-flows is at 98 99 ///least the sum of the out-flows in every node except the \e source. 99 ///- \c NO_FLOW: indicates an unspecified edge map. \ref flow will be 100 ///set to the constant zero flow in the beginning of the algorithm in this case. 100 ///- \c NO_FLOW: indicates an unspecified edge map. \c flow will be 101 ///set to the constant zero flow in the beginning of 102 ///the algorithm in this case. 101 103 /// 102 104 enum FlowEnum{ … … 195 197 ///minimum value cut can already be computed, though a maximum flow 196 198 ///is not yet obtained. So after calling this method \ref flowValue 197 ///and \ref actMinCutgives proper results.198 ///\warning \ref minCut , \ref minMinCut and \ref maxMinCutdo not199 ///give minimum value cuts unless calling \ref phase2 .199 ///and \ref MinCut() gives proper results. 200 ///\warning \ref minCut(), \ref minMinCut() and \ref maxMinCut() do not 201 ///give minimum value cuts unless calling \ref phase2(). 200 202 void phase1() 201 203 { … … 350 352 351 353 /// Returns the value of the maximum flow by returning the excess 352 /// of the target node \ reft. This value equals to the value of354 /// of the target node \c t. This value equals to the value of 353 355 /// the maximum flow already after running \ref phase1. 354 356 Num flowValue() const { … … 363 365 ///phase1 and \ref phase2. It is much faster after 364 366 ///\ref phase1. \pre M should be a bool-valued node-map. \pre 365 ///If \ref min cut is called after \ref phase2then M should367 ///If \ref minCut() is called after \ref phase2() then M should 366 368 ///be initialized to false. 367 369 template<typename _CutMap> … … 426 428 ///which is inclusionwise maximum. It is computed by processing a 427 429 ///backward bfs from the target node \c t in the residual graph. 428 ///\pre \ref phase2() or preflow() should already be run.430 ///\pre \ref phase2() or run() should already be run. 429 431 template<typename _CutMap> 430 432 void maxMinCut(_CutMap& M) const { -
src/hugo/skeletons/graph.h
r906 r911 93 93 /// Inequality operator 94 94 95 /// \sa \refoperator==(Node n)95 /// \sa operator==(Node n) 96 96 /// 97 97 bool operator!=(Node) const { return true; } … … 181 181 /// Inequality operator 182 182 183 /// \sa \refoperator==(Node n)183 /// \sa operator==(Node n) 184 184 /// 185 185 bool operator!=(Edge) const { return true; } … … 383 383 int id(const Edge&) const { return 0; } 384 384 385 /// .385 ///\e 386 386 387 387 ///\todo Should it be in the concept? 388 388 /// 389 389 int nodeNum() const { return 0; } 390 /// .390 ///\e 391 391 392 392 ///\todo Should it be in the concept? … … 406 406 public: 407 407 408 /// .408 ///\e 409 409 NodeMap(const StaticGraph&) { } 410 /// .410 ///\e 411 411 NodeMap(const StaticGraph&, T) { } 412 412 … … 430 430 public: 431 431 432 /// .432 ///\e 433 433 EdgeMap(const StaticGraph&) { } 434 /// .434 ///\e 435 435 EdgeMap(const StaticGraph&, T) { } 436 436 -
src/hugo/skeletons/sym_graph.h
r909 r911 46 46 /// feature, the documentation of a real symmetric graph imlementation 47 47 /// like @ref SymListGraph or 48 /// @ref SymSmartGraph will just refer to this structure.48 /// @ref hugo::SymSmartGraph will just refer to this structure. 49 49 class StaticSymGraph 50 50 { … … 94 94 /// Inequality operator 95 95 96 /// \sa \refoperator==(Node n)96 /// \sa operator==(Node n) 97 97 /// 98 98 bool operator!=(Node) const { return true; } … … 182 182 /// Inequality operator 183 183 184 /// \sa \refoperator==(Node n)184 /// \sa operator==(Node n) 185 185 /// 186 186 bool operator!=(SymEdge) const { return true; } … … 224 224 /// Inequality operator 225 225 226 /// \sa \refoperator==(Node n)226 /// \sa operator==(Node n) 227 227 /// 228 228 bool operator!=(Edge) const { return true; } … … 490 490 int id(const SymEdge&) const { return 0; } 491 491 492 /// .492 ///\e 493 493 494 494 ///\todo Should it be in the concept? 495 495 /// 496 496 int nodeNum() const { return 0; } 497 /// .497 ///\e 498 498 499 499 ///\todo Should it be in the concept? … … 525 525 public: 526 526 527 /// .527 ///\e 528 528 NodeMap(const StaticSymGraph&) { } 529 /// .529 ///\e 530 530 NodeMap(const StaticSymGraph&, T) { } 531 531 … … 549 549 public: 550 550 551 /// .551 ///\e 552 552 EdgeMap(const StaticSymGraph&) { } 553 /// .553 ///\e 554 554 EdgeMap(const StaticSymGraph&, T) { } 555 555 … … 573 573 public: 574 574 575 /// .575 ///\e 576 576 SymEdgeMap(const StaticSymGraph&) { } 577 /// .577 ///\e 578 578 SymEdgeMap(const StaticSymGraph&, T) { } 579 579
Note: See TracChangeset
for help on using the changeset viewer.
