1.1 --- a/lemon/max_matching.h Mon Jul 25 11:17:23 2005 +0000
1.2 +++ b/lemon/max_matching.h Tue Jul 26 13:15:13 2005 +0000
1.3 @@ -97,32 +97,88 @@
1.4 ///Runs Edmonds' algorithm for sparse graphs (number of edges <
1.5 ///2*number of nodes), and a heuristical Edmonds' algorithm with a
1.6 ///heuristic of postponing shrinks for dense graphs.
1.7 - inline void run();
1.8 + void run() {
1.9 + if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {
1.10 + greedyMatching();
1.11 + runEdmonds(0);
1.12 + } else runEdmonds(1);
1.13 + }
1.14 +
1.15
1.16 ///Runs Edmonds' algorithm.
1.17
1.18 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs
1.19 ///Edmonds' algorithm with a heuristic of postponing shrinks,
1.20 ///giving a faster algorithm for dense graphs.
1.21 - void runEdmonds( int heur );
1.22 + void runEdmonds( int heur = 1 ) {
1.23 +
1.24 + for(NodeIt v(g); v!=INVALID; ++v)
1.25 + position.set(v,C);
1.26 +
1.27 + typename Graph::template NodeMap<Node> ear(g,INVALID);
1.28 + //undefined for the base nodes of the blossoms (i.e. for the
1.29 + //representative elements of UFE blossom) and for the nodes in C
1.30 +
1.31 + typename UFE::MapType blossom_base(g);
1.32 + UFE blossom(blossom_base);
1.33 + typename UFE::MapType tree_base(g);
1.34 + UFE tree(tree_base);
1.35 + //If these UFE's would be members of the class then also
1.36 + //blossom_base and tree_base should be a member.
1.37 +
1.38 + for(NodeIt v(g); v!=INVALID; ++v) {
1.39 + if ( position[v]==C && _mate[v]==INVALID ) {
1.40 + blossom.insert(v);
1.41 + tree.insert(v);
1.42 + position.set(v,D);
1.43 + if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
1.44 + else normShrink( v, ear, blossom, tree );
1.45 + }
1.46 + }
1.47 + }
1.48 +
1.49
1.50 ///Finds a greedy matching starting from the actual matching.
1.51
1.52 ///Starting form the actual matching stored, it finds a maximal
1.53 ///greedy matching.
1.54 - void greedyMatching();
1.55 + void greedyMatching() {
1.56 + for(NodeIt v(g); v!=INVALID; ++v)
1.57 + if ( _mate[v]==INVALID ) {
1.58 + for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
1.59 + Node y=g.runningNode(e);
1.60 + if ( _mate[y]==INVALID && y!=v ) {
1.61 + _mate.set(v,y);
1.62 + _mate.set(y,v);
1.63 + break;
1.64 + }
1.65 + }
1.66 + }
1.67 + }
1.68
1.69 ///Returns the size of the actual matching stored.
1.70
1.71 ///Returns the size of the actual matching stored. After \ref
1.72 ///run() it returns the size of a maximum matching in the graph.
1.73 - int size() const;
1.74 + int size() const {
1.75 + int s=0;
1.76 + for(NodeIt v(g); v!=INVALID; ++v) {
1.77 + if ( _mate[v]!=INVALID ) {
1.78 + ++s;
1.79 + }
1.80 + }
1.81 + return s/2;
1.82 + }
1.83 +
1.84
1.85 ///Resets the actual matching to the empty matching.
1.86
1.87 ///Resets the actual matching to the empty matching.
1.88 ///
1.89 - void resetMatching();
1.90 + void resetMatching() {
1.91 + for(NodeIt v(g); v!=INVALID; ++v)
1.92 + _mate.set(v,INVALID);
1.93 + }
1.94
1.95 ///Returns the mate of a node in the actual matching.
1.96
1.97 @@ -284,44 +340,6 @@
1.98
1.99
1.100 template <typename Graph>
1.101 - void MaxMatching<Graph>::run() {
1.102 - if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {
1.103 - greedyMatching();
1.104 - runEdmonds(0);
1.105 - } else runEdmonds(1);
1.106 - }
1.107 -
1.108 -
1.109 - template <typename Graph>
1.110 - void MaxMatching<Graph>::runEdmonds( int heur=1 ) {
1.111 -
1.112 - for(NodeIt v(g); v!=INVALID; ++v)
1.113 - position.set(v,C);
1.114 -
1.115 - typename Graph::template NodeMap<Node> ear(g,INVALID);
1.116 - //undefined for the base nodes of the blossoms (i.e. for the
1.117 - //representative elements of UFE blossom) and for the nodes in C
1.118 -
1.119 - typename UFE::MapType blossom_base(g);
1.120 - UFE blossom(blossom_base);
1.121 - typename UFE::MapType tree_base(g);
1.122 - UFE tree(tree_base);
1.123 - //If these UFE's would be members of the class then also
1.124 - //blossom_base and tree_base should be a member.
1.125 -
1.126 - for(NodeIt v(g); v!=INVALID; ++v) {
1.127 - if ( position[v]==C && _mate[v]==INVALID ) {
1.128 - blossom.insert(v);
1.129 - tree.insert(v);
1.130 - position.set(v,D);
1.131 - if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
1.132 - else normShrink( v, ear, blossom, tree );
1.133 - }
1.134 - }
1.135 - }
1.136 -
1.137 -
1.138 - template <typename Graph>
1.139 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
1.140 UFE& blossom, UFE& tree) {
1.141
1.142 @@ -460,38 +478,6 @@
1.143 }
1.144
1.145 template <typename Graph>
1.146 - void MaxMatching<Graph>::greedyMatching() {
1.147 - for(NodeIt v(g); v!=INVALID; ++v)
1.148 - if ( _mate[v]==INVALID ) {
1.149 - for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
1.150 - Node y=g.runningNode(e);
1.151 - if ( _mate[y]==INVALID && y!=v ) {
1.152 - _mate.set(v,y);
1.153 - _mate.set(y,v);
1.154 - break;
1.155 - }
1.156 - }
1.157 - }
1.158 - }
1.159 -
1.160 - template <typename Graph>
1.161 - int MaxMatching<Graph>::size() const {
1.162 - int s=0;
1.163 - for(NodeIt v(g); v!=INVALID; ++v) {
1.164 - if ( _mate[v]!=INVALID ) {
1.165 - ++s;
1.166 - }
1.167 - }
1.168 - return s/2;
1.169 - }
1.170 -
1.171 - template <typename Graph>
1.172 - void MaxMatching<Graph>::resetMatching() {
1.173 - for(NodeIt v(g); v!=INVALID; ++v)
1.174 - _mate.set(v,INVALID);
1.175 - }
1.176 -
1.177 - template <typename Graph>
1.178 bool MaxMatching<Graph>::noShrinkStep(Node x,
1.179 typename Graph::template
1.180 NodeMap<Node>& ear,