Changeset 1587:8f1c317ebeb4 in lemon-0.x
- Timestamp:
- 07/26/05 15:15:13 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2091
- Files:
-
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
demo/graph_to_eps_demo.cc
r1573 r1587 21 21 /// This demo program shows examples how to use the function \ref 22 22 /// graphToEps(). It takes no input but simply creates six 23 /// <tt>.eps</tt> files demonstrating how to draw directed/undirected 24 /// graphs, how to handle parallel egdes, how to change the properties 25 /// (like color, shape, size, title etc.) of nodes and edges 26 /// individually using appropriate \ref maps-page "graphmaps". 23 /// <tt>.eps</tt> files demonstrating the capability of \ref 24 /// graphToEps(), and showing how to draw directed/undirected graphs, 25 /// how to handle parallel egdes, how to change the properties (like 26 /// color, shape, size, title etc.) of nodes and edges individually 27 /// using appropriate \ref maps-page "graphmapfactory". 27 28 28 29 #include <cmath> -
doc/groups.dox
r1582 r1587 165 165 */ 166 166 167 /* *167 /* --- Unused group 168 168 @defgroup experimental Experimental Structures and Algorithms 169 169 This group contains some Experimental structures and algorithms. -
lemon/bits/alteration_notifier.h
r1435 r1587 21 21 #include <algorithm> 22 22 23 ///\ingroup graphmap s23 ///\ingroup graphmapfactory 24 24 ///\file 25 25 ///\brief Observer registry for graph alteration observers. … … 27 27 namespace lemon { 28 28 29 /// \addtogroup graphmap s29 /// \addtogroup graphmapfactory 30 30 /// @{ 31 31 -
lemon/bits/array_map.h
r1435 r1587 21 21 #include <lemon/bits/map_iterator.h> 22 22 23 ///\ingroup graphmap s23 ///\ingroup graphmapfactory 24 24 ///\file 25 25 ///\brief Graph maps that construates and destruates … … 29 29 30 30 31 /// \addtogroup graphmap s31 /// \addtogroup graphmapfactory 32 32 /// @{ 33 33 -
lemon/bits/default_map.h
r1435 r1587 22 22 #include <lemon/bits/vector_map.h> 23 23 24 ///\ingroup graphmap s24 ///\ingroup graphmapfactory 25 25 ///\file 26 26 ///\brief Graph maps that construct and destruct … … 29 29 namespace lemon { 30 30 31 /// \addtogroup graphmap s31 /// \addtogroup graphmapfactory 32 32 /// @{ 33 33 -
lemon/bits/map_iterator.h
r1435 r1587 23 23 #include <lemon/graph_utils.h> 24 24 25 ///\ingroup graphmap s25 ///\ingroup graphmapfactory 26 26 ///\file 27 27 ///\brief Iterators on the maps. … … 29 29 namespace lemon { 30 30 31 /// \addtogroup graphmap s31 /// \addtogroup graphmapfactory 32 32 /// @{ 33 33 -
lemon/bits/vector_map.h
r1435 r1587 25 25 #include <lemon/bits/alteration_notifier.h> 26 26 27 ///\ingroup graphmap s27 ///\ingroup graphmapfactory 28 28 ///\file 29 29 ///\brief Vector based graph maps. … … 31 31 namespace lemon { 32 32 33 /// \addtogroup graphmap s33 /// \addtogroup graphmapfactory 34 34 /// @{ 35 35 -
lemon/max_matching.h
r1435 r1587 98 98 ///2*number of nodes), and a heuristical Edmonds' algorithm with a 99 99 ///heuristic of postponing shrinks for dense graphs. 100 inline void run(); 100 void run() { 101 if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) { 102 greedyMatching(); 103 runEdmonds(0); 104 } else runEdmonds(1); 105 } 106 101 107 102 108 ///Runs Edmonds' algorithm. … … 105 111 ///Edmonds' algorithm with a heuristic of postponing shrinks, 106 112 ///giving a faster algorithm for dense graphs. 107 void runEdmonds( int heur ); 113 void runEdmonds( int heur = 1 ) { 114 115 for(NodeIt v(g); v!=INVALID; ++v) 116 position.set(v,C); 117 118 typename Graph::template NodeMap<Node> ear(g,INVALID); 119 //undefined for the base nodes of the blossoms (i.e. for the 120 //representative elements of UFE blossom) and for the nodes in C 121 122 typename UFE::MapType blossom_base(g); 123 UFE blossom(blossom_base); 124 typename UFE::MapType tree_base(g); 125 UFE tree(tree_base); 126 //If these UFE's would be members of the class then also 127 //blossom_base and tree_base should be a member. 128 129 for(NodeIt v(g); v!=INVALID; ++v) { 130 if ( position[v]==C && _mate[v]==INVALID ) { 131 blossom.insert(v); 132 tree.insert(v); 133 position.set(v,D); 134 if ( heur == 1 ) lateShrink( v, ear, blossom, tree ); 135 else normShrink( v, ear, blossom, tree ); 136 } 137 } 138 } 139 108 140 109 141 ///Finds a greedy matching starting from the actual matching. … … 111 143 ///Starting form the actual matching stored, it finds a maximal 112 144 ///greedy matching. 113 void greedyMatching(); 145 void greedyMatching() { 146 for(NodeIt v(g); v!=INVALID; ++v) 147 if ( _mate[v]==INVALID ) { 148 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) { 149 Node y=g.runningNode(e); 150 if ( _mate[y]==INVALID && y!=v ) { 151 _mate.set(v,y); 152 _mate.set(y,v); 153 break; 154 } 155 } 156 } 157 } 114 158 115 159 ///Returns the size of the actual matching stored. … … 117 161 ///Returns the size of the actual matching stored. After \ref 118 162 ///run() it returns the size of a maximum matching in the graph. 119 int size() const; 163 int size() const { 164 int s=0; 165 for(NodeIt v(g); v!=INVALID; ++v) { 166 if ( _mate[v]!=INVALID ) { 167 ++s; 168 } 169 } 170 return s/2; 171 } 172 120 173 121 174 ///Resets the actual matching to the empty matching. … … 123 176 ///Resets the actual matching to the empty matching. 124 177 /// 125 void resetMatching(); 178 void resetMatching() { 179 for(NodeIt v(g); v!=INVALID; ++v) 180 _mate.set(v,INVALID); 181 } 126 182 127 183 ///Returns the mate of a node in the actual matching. … … 285 341 286 342 template <typename Graph> 287 void MaxMatching<Graph>::run() {288 if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {289 greedyMatching();290 runEdmonds(0);291 } else runEdmonds(1);292 }293 294 295 template <typename Graph>296 void MaxMatching<Graph>::runEdmonds( int heur=1 ) {297 298 for(NodeIt v(g); v!=INVALID; ++v)299 position.set(v,C);300 301 typename Graph::template NodeMap<Node> ear(g,INVALID);302 //undefined for the base nodes of the blossoms (i.e. for the303 //representative elements of UFE blossom) and for the nodes in C304 305 typename UFE::MapType blossom_base(g);306 UFE blossom(blossom_base);307 typename UFE::MapType tree_base(g);308 UFE tree(tree_base);309 //If these UFE's would be members of the class then also310 //blossom_base and tree_base should be a member.311 312 for(NodeIt v(g); v!=INVALID; ++v) {313 if ( position[v]==C && _mate[v]==INVALID ) {314 blossom.insert(v);315 tree.insert(v);316 position.set(v,D);317 if ( heur == 1 ) lateShrink( v, ear, blossom, tree );318 else normShrink( v, ear, blossom, tree );319 }320 }321 }322 323 324 template <typename Graph>325 343 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear, 326 344 UFE& blossom, UFE& tree) { … … 458 476 } 459 477 } 460 }461 462 template <typename Graph>463 void MaxMatching<Graph>::greedyMatching() {464 for(NodeIt v(g); v!=INVALID; ++v)465 if ( _mate[v]==INVALID ) {466 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {467 Node y=g.runningNode(e);468 if ( _mate[y]==INVALID && y!=v ) {469 _mate.set(v,y);470 _mate.set(y,v);471 break;472 }473 }474 }475 }476 477 template <typename Graph>478 int MaxMatching<Graph>::size() const {479 int s=0;480 for(NodeIt v(g); v!=INVALID; ++v) {481 if ( _mate[v]!=INVALID ) {482 ++s;483 }484 }485 return s/2;486 }487 488 template <typename Graph>489 void MaxMatching<Graph>::resetMatching() {490 for(NodeIt v(g); v!=INVALID; ++v)491 _mate.set(v,INVALID);492 478 } 493 479
Note: See TracChangeset
for help on using the changeset viewer.