Changeset 559:82a8f2bc5758 in lemon0.x for src/work/marci/max_bipartite_matching.h
 Timestamp:
 05/06/04 19:45:12 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@732
 File:

 1 copied
Legend:
 Unmodified
 Added
 Removed

src/work/marci/max_bipartite_matching.h
r558 r559 1 1 // * c++ * 2 #include <iostream> 3 #include <fstream> 4 #include <vector> 2 #ifndef HUGO_MAX_BIPARTITE_MATCHING_H 3 #define HUGO_MAX_BIPARTITE_MATCHING_H 5 4 6 #include <list_graph.h> 7 //#include <smart_graph.h> 8 //#include <dimacs.h> 9 #include <hugo/time_measure.h> 10 #include <for_each_macros.h> 11 #include <bfs_iterator.h> 5 //#include <for_each_macros.h> 12 6 #include <bipartite_graph_wrapper.h> 13 #include <hugo/maps.h>7 //#include <hugo/maps.h> 14 8 #include <max_flow.h> 15 #include <graph_gen.h>16 9 17 using namespace hugo; 10 namespace hugo { 18 11 19 // template <typename Graph, typename EdgeCap, typename NodeCap,20 // typename EdgeFlow, typename NodeFlow>21 // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>,22 // stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {23 // typedef MaxFlow<stGraphWrapper<Graph>,24 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,25 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >26 // Parent;27 // protected:28 // stGraphWrapper<Graph> gw;29 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap;30 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow;31 // //graph* g;32 // //EdgeCap* edge_cap;33 // //EdgeFlow* edge_flow;34 // public:35 // MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,36 // EdgeFlow& _edge_flow, NodeFlow& _node_flow) :37 // MaxFlow(), gw(_g),38 // cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) {39 // Parent::set(gw, cap, flow);40 // }41 // };12 // template <typename Graph, typename EdgeCap, typename NodeCap, 13 // typename EdgeFlow, typename NodeFlow> 14 // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>, 15 // stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > { 16 // typedef MaxFlow<stGraphWrapper<Graph>, 17 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>, 18 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > 19 // Parent; 20 // protected: 21 // stGraphWrapper<Graph> gw; 22 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap; 23 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow; 24 // //graph* g; 25 // //EdgeCap* edge_cap; 26 // //EdgeFlow* edge_flow; 27 // public: 28 // MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, 29 // EdgeFlow& _edge_flow, NodeFlow& _node_flow) : 30 // MaxFlow(), gw(_g), 31 // cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) { 32 // Parent::set(gw, cap, flow); 33 // } 34 // }; 42 35 43 template <typename Graph, typename EdgeCap, typename NodeCap, 44 typename EdgeFlow, typename NodeFlow> 45 class MaxMatching { 46 protected: 47 // EdgeCap* edge_cap; 48 // NodeCap* node_cap; 49 // EdgeFlow* edge_flow; 50 // NodeFlow* node_flow; 51 typedef stGraphWrapper<Graph> stGW; 52 stGW stgw; 53 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; 54 CapMap cap; 55 NodeFlow* node_flow; 56 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; 57 FlowMap flow; 58 MaxFlow<stGW, int, CapMap, FlowMap> mf; 59 //graph* g; 60 //EdgeCap* edge_cap; 61 //EdgeFlow* edge_flow; 62 public: 63 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, 64 EdgeFlow& _edge_flow, NodeFlow& _node_flow) : 65 stgw(_g), 66 cap(_edge_cap, _node_cap), 67 node_flow(0), 68 flow(_edge_flow, _node_flow), 69 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } 70 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, 71 EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) : 72 stgw(_g), 73 cap(_edge_cap, _node_cap), 74 node_flow(new NodeFlow(_g)), 75 flow(_edge_flow, *node_flow), 76 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } 77 ~MaxMatching() { if (node_flow) delete node_flow; } 78 void run() { mf.run(); } 79 int matchingValue() { return mf.flowValue(); } 80 }; 36 /// A bipartite matching class. 37 /// This class reduces the matching problem to a flow problem and 38 /// a preflow is used on a wrapper. Such a generic approach means that 39 /// matchings, bmatchings an capacitated bmatchings can be handled in 40 /// a similar way. Due to the efficiency of the preflow algorithm, an 41 /// efficient matching framework is obtained. 42 template <typename Graph, typename EdgeCap, typename NodeCap, 43 typename EdgeFlow, typename NodeFlow> 44 class MaxMatching { 45 protected: 46 // EdgeCap* edge_cap; 47 // NodeCap* node_cap; 48 // EdgeFlow* edge_flow; 49 // NodeFlow* node_flow; 50 typedef stGraphWrapper<Graph> stGW; 51 stGW stgw; 52 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; 53 CapMap cap; 54 NodeFlow* node_flow; 55 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; 56 FlowMap flow; 57 MaxFlow<stGW, int, CapMap, FlowMap> mf; 58 //graph* g; 59 //EdgeCap* edge_cap; 60 //EdgeFlow* edge_flow; 61 public: 62 /// For capacitated bmatchings, edgecaoacities and nodecapacities 63 /// have to be given. After running \c run the matching is is given 64 /// back in the edgemap \c _edge_flow and \c _node_map can be used 65 /// to obtain saturation information about nodes. 66 ///\bug Note that the values in _edge_flow and _node_flow have 67 /// to form a flow. 68 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, 69 EdgeFlow& _edge_flow, NodeFlow& _node_flow) : 70 stgw(_g), 71 cap(_edge_cap, _node_cap), 72 node_flow(0), 73 flow(_edge_flow, _node_flow), 74 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } 75 /// If the saturation information of nodes is not needed that the use of 76 /// this constructor is more comfortable. 77 ///\bug Note that the values in _edge_flow and _node_flow have 78 /// to form a flow. 79 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, 80 EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) : 81 stgw(_g), 82 cap(_edge_cap, _node_cap), 83 node_flow(new NodeFlow(_g)), 84 flow(_edge_flow, *node_flow), 85 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } 86 /// The class have a nontrivial destructor. 87 ~MaxMatching() { if (node_flow) delete node_flow; } 88 /// run computes the max matching. 89 void run() { mf.run(); } 90 /// The matching value after running \c run. 91 int matchingValue() { return mf.flowValue(); } 92 }; 81 93 94 } //namespace hugo 82 95 83 int main() { 84 //typedef UndirListGraph Graph; 85 typedef BipartiteGraph<ListGraph> Graph; 86 87 typedef Graph::Node Node; 88 typedef Graph::NodeIt NodeIt; 89 typedef Graph::Edge Edge; 90 typedef Graph::EdgeIt EdgeIt; 91 typedef Graph::OutEdgeIt OutEdgeIt; 92 93 Graph g; 94 95 int a; 96 std::cout << "number of nodes in the first color class="; 97 std::cin >> a; 98 int b; 99 std::cout << "number of nodes in the second color class="; 100 std::cin >> b; 101 int m; 102 std::cout << "number of edges="; 103 std::cin >> m; 104 105 std::cout << "Generatig a random bipartite graph..." << std::endl; 106 random_init(); 107 randomBipartiteGraph(g, a, b, m); 108 109 // std::cout << "Edges of the bipartite graph:" << std::endl; 110 // FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " "; 111 // std::cout << std::endl; 112 113 // std::cout << "Nodes:" << std::endl; 114 // FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " "; 115 // std::cout << std::endl; 116 // std::cout << "Nodes in T:" << std::endl; 117 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " "; 118 // std::cout << std::endl; 119 // std::cout << "Nodes in S:" << std::endl; 120 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " "; 121 // std::cout << std::endl; 122 123 // std::cout << "Erasing the first node..." << std::endl; 124 // NodeIt n; 125 // g.first(n); 126 // g.erase(n); 127 // std::cout << "Nodes of the bipartite graph:" << std::endl; 128 // FOR_EACH_GLOB(n, g) std::cout << n << " "; 129 // std::cout << std::endl; 130 131 // std::cout << "Nodes in T:" << std::endl; 132 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " "; 133 // std::cout << std::endl; 134 // std::cout << "Nodes in S:" << std::endl; 135 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " "; 136 // std::cout << std::endl; 137 138 typedef stGraphWrapper<Graph> stGW; 139 stGW stgw(g); 140 ConstMap<stGW::Edge, int> const1map(1); 141 142 Timer ts; 143 ts.reset(); 144 stGW::EdgeMap<int> flow(stgw); 145 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 146 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); 147 max_flow_test.run(); 148 // while (max_flow_test.augmentOnShortestPath()) { } 149 // typedef ListGraph MutableGraph; 150 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 151 // while (max_flow_test.augmentOnBlockingFlow2()) { 152 // std::cout << max_flow_test.flowValue() << std::endl; 153 // } 154 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; 155 std::cout << "elapsed time: " << ts << std::endl; 156 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 157 // if (flow[e]) std::cout << e << std::endl; 158 // } 159 std::cout << std::endl; 160 161 typedef ConstMap<Graph::Edge, int> EdgeCap; 162 EdgeCap ge1(1); 163 typedef ConstMap<Graph::Node, int> NodeCap; 164 NodeCap gn1(1); 165 typedef Graph::EdgeMap<int> EdgeFlow; 166 EdgeFlow gef(g); //0 167 typedef Graph::NodeMap<int> NodeFlow; 168 NodeFlow gnf(g); //0 169 170 typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> CapMap; 171 typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; 172 CapMap cm(ge1, gn1); 173 FlowMap fm(gef, gnf); 174 175 //Timer ts; 176 ts.reset(); 177 //stGW::EdgeMap<int> flow(stgw); 178 MaxFlow<stGW, int, CapMap, FlowMap> 179 max_flow_test1(stgw, stgw.S_NODE, stgw.T_NODE, cm, fm); 180 max_flow_test1.run(); 181 // while (max_flow_test.augmentOnShortestPath()) { } 182 // typedef ListGraph MutableGraph; 183 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 184 // while (max_flow_test.augmentOnBlockingFlow2()) { 185 // std::cout << max_flow_test.flowValue() << std::endl; 186 // } 187 std::cout << "max flow value: " << max_flow_test1.flowValue() << std::endl; 188 std::cout << "elapsed time: " << ts << std::endl; 189 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 190 // if (gef[e]) std::cout << e << std::endl; 191 // } 192 std::cout << std::endl; 193 194 ts.reset(); 195 FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); 196 FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); 197 MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>, 198 Graph::EdgeMap<int>, Graph::NodeMap<int> > 199 matching_test(g, ge1, gn1, gef, gnf); 200 matching_test.run(); 201 202 std::cout << "max flow value: " << matching_test.matchingValue() << std::endl; 203 std::cout << "elapsed time: " << ts << std::endl; 204 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 205 // if (gef[e]) std::cout << e << std::endl; 206 // } 207 std::cout << std::endl; 208 209 ts.reset(); 210 FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); 211 //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); 212 MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>, 213 Graph::EdgeMap<int>, Graph::NodeMap<int> > 214 matching_test_1(g, ge1, gn1, gef/*, gnf*/); 215 matching_test_1.run(); 216 217 std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl; 218 std::cout << "elapsed time: " << ts << std::endl; 219 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 220 // if (gef[e]) std::cout << e << std::endl; 221 // } 222 std::cout << std::endl; 223 224 return 0; 225 } 96 #endif //HUGO_MAX_BIPARTITE_MATCHING_H
Note: See TracChangeset
for help on using the changeset viewer.