marci@510: // -*- c++ -*- marci@510: #include marci@510: #include marci@510: #include marci@510: #include marci@510: marci@510: #include marci@510: //#include marci@510: //#include marci@510: #include marci@510: #include marci@510: #include marci@510: #include marci@510: #include marci@510: #include marci@510: marci@510: using namespace hugo; marci@510: marci@510: // template marci@510: // class MaxMatching : public MaxFlow, marci@510: // stGraphWrapper:: EdgeMapWrapper, stGraphWrapper::EdgeMapWrapper > { marci@510: // typedef MaxFlow, marci@510: // stGraphWrapper::EdgeMapWrapper, marci@510: // stGraphWrapper::EdgeMapWrapper > marci@510: // Parent; marci@510: // protected: marci@510: // stGraphWrapper gw; marci@510: // stGraphWrapper::EdgeMapWrapper cap; marci@510: // stGraphWrapper::EdgeMapWrapper flow; marci@510: // //graph* g; marci@510: // //EdgeCap* edge_cap; marci@510: // //EdgeFlow* edge_flow; marci@510: // public: marci@510: // MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, marci@510: // EdgeFlow& _edge_flow, NodeFlow& _node_flow) : marci@510: // MaxFlow(), gw(_g), marci@510: // cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) { marci@510: // Parent::set(gw, cap, flow); marci@510: // } marci@510: // }; marci@510: marci@510: template marci@510: class MaxMatching { marci@510: protected: marci@510: // EdgeCap* edge_cap; marci@510: // NodeCap* node_cap; marci@510: // EdgeFlow* edge_flow; marci@510: // NodeFlow* node_flow; marci@510: typedef stGraphWrapper stGW; marci@510: stGW stgw; marci@510: typedef typename stGW::template EdgeMapWrapper CapMap; marci@510: CapMap cap; marci@512: NodeFlow* node_flow; marci@510: typedef typename stGW::template EdgeMapWrapper FlowMap; marci@510: FlowMap flow; marci@510: MaxFlow mf; marci@510: //graph* g; marci@510: //EdgeCap* edge_cap; marci@510: //EdgeFlow* edge_flow; marci@510: public: marci@510: MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, marci@510: EdgeFlow& _edge_flow, NodeFlow& _node_flow) : marci@510: stgw(_g), marci@512: cap(_edge_cap, _node_cap), marci@512: node_flow(0), marci@512: flow(_edge_flow, _node_flow), marci@510: mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } marci@512: MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, marci@512: EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) : marci@512: stgw(_g), marci@512: cap(_edge_cap, _node_cap), marci@512: node_flow(new NodeFlow(_g)), marci@512: flow(_edge_flow, *node_flow), marci@512: mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } marci@512: ~MaxMatching() { if (node_flow) delete node_flow; } marci@510: void run() { mf.run(); } marci@510: int matchingValue() { return mf.flowValue(); } marci@510: }; marci@510: marci@510: /** marci@510: * Inicializalja a veletlenszamgeneratort. marci@510: * Figyelem, ez nem jo igazi random szamokhoz, marci@510: * erre ne bizzad a titkaidat! marci@510: */ marci@510: void random_init() marci@510: { marci@510: unsigned int seed = getpid(); marci@510: seed |= seed << 15; marci@510: seed ^= time(0); marci@510: marci@510: srand(seed); marci@510: } marci@510: marci@510: /** marci@510: * Egy veletlen int-et ad vissza 0 es m-1 kozott. marci@510: */ marci@510: int random(int m) marci@510: { marci@510: return int( double(m) * rand() / (RAND_MAX + 1.0) ); marci@510: } marci@510: marci@510: int main() { marci@510: //typedef UndirListGraph Graph; marci@510: typedef BipartiteGraph Graph; marci@510: marci@510: typedef Graph::Node Node; marci@510: typedef Graph::NodeIt NodeIt; marci@510: typedef Graph::Edge Edge; marci@510: typedef Graph::EdgeIt EdgeIt; marci@510: typedef Graph::OutEdgeIt OutEdgeIt; marci@510: marci@510: Graph g; marci@510: marci@510: std::vector s_nodes; marci@510: std::vector t_nodes; marci@510: marci@510: int a; marci@510: std::cout << "number of nodes in the first color class="; marci@510: std::cin >> a; marci@510: int b; marci@510: std::cout << "number of nodes in the second color class="; marci@510: std::cin >> b; marci@510: int m; marci@510: std::cout << "number of edges="; marci@510: std::cin >> m; marci@510: marci@510: std::cout << "Generatig a random bipartite graph..." << std::endl; marci@510: for (int i=0; i stGW; marci@510: stGW stgw(g); marci@510: ConstMap const1map(1); marci@510: marci@510: Timer ts; marci@510: ts.reset(); marci@510: stGW::EdgeMap flow(stgw); marci@510: MaxFlow, stGW::EdgeMap > marci@510: max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); marci@510: max_flow_test.run(); marci@510: // while (max_flow_test.augmentOnShortestPath()) { } marci@510: // typedef ListGraph MutableGraph; marci@510: // while (max_flow_test.augmentOnBlockingFlow1()) { marci@510: // while (max_flow_test.augmentOnBlockingFlow2()) { marci@510: // std::cout << max_flow_test.flowValue() << std::endl; marci@510: // } marci@510: std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; marci@510: std::cout << "elapsed time: " << ts << std::endl; marci@512: // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { marci@512: // if (flow[e]) std::cout << e << std::endl; marci@512: // } marci@510: std::cout << std::endl; marci@510: marci@510: typedef ConstMap EdgeCap; marci@510: EdgeCap ge1(1); marci@510: typedef ConstMap NodeCap; marci@510: NodeCap gn1(1); marci@510: typedef Graph::EdgeMap EdgeFlow; marci@510: EdgeFlow gef(g); //0 marci@510: typedef Graph::NodeMap NodeFlow; marci@510: NodeFlow gnf(g); //0 marci@510: marci@510: typedef stGraphWrapper::EdgeMapWrapper CapMap; marci@510: typedef stGraphWrapper::EdgeMapWrapper FlowMap; marci@510: CapMap cm(ge1, gn1); marci@510: FlowMap fm(gef, gnf); marci@510: marci@510: //Timer ts; marci@510: ts.reset(); marci@510: //stGW::EdgeMap flow(stgw); marci@510: MaxFlow marci@510: max_flow_test1(stgw, stgw.S_NODE, stgw.T_NODE, cm, fm); marci@510: max_flow_test1.run(); marci@510: // while (max_flow_test.augmentOnShortestPath()) { } marci@510: // typedef ListGraph MutableGraph; marci@510: // while (max_flow_test.augmentOnBlockingFlow1()) { marci@510: // while (max_flow_test.augmentOnBlockingFlow2()) { marci@510: // std::cout << max_flow_test.flowValue() << std::endl; marci@510: // } marci@510: std::cout << "max flow value: " << max_flow_test1.flowValue() << std::endl; marci@510: std::cout << "elapsed time: " << ts << std::endl; marci@510: // FOR_EACH_LOC(Graph::EdgeIt, e, g) { marci@510: // if (gef[e]) std::cout << e << std::endl; marci@510: // } marci@510: std::cout << std::endl; marci@510: marci@510: ts.reset(); marci@510: FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); marci@510: FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); marci@510: MaxMatching, ConstMap, marci@510: Graph::EdgeMap, Graph::NodeMap > marci@510: matching_test(g, ge1, gn1, gef, gnf); marci@510: matching_test.run(); marci@510: marci@510: std::cout << "max flow value: " << matching_test.matchingValue() << std::endl; marci@510: std::cout << "elapsed time: " << ts << std::endl; marci@510: // FOR_EACH_LOC(Graph::EdgeIt, e, g) { marci@510: // if (gef[e]) std::cout << e << std::endl; marci@510: // } marci@510: std::cout << std::endl; marci@512: marci@512: ts.reset(); marci@512: FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); marci@512: //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); marci@512: MaxMatching, ConstMap, marci@512: Graph::EdgeMap, Graph::NodeMap > marci@512: matching_test_1(g, ge1, gn1, gef/*, gnf*/); marci@512: matching_test_1.run(); marci@512: marci@512: std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl; marci@512: std::cout << "elapsed time: " << ts << std::endl; marci@512: // FOR_EACH_LOC(Graph::EdgeIt, e, g) { marci@512: // if (gef[e]) std::cout << e << std::endl; marci@512: // } marci@512: std::cout << std::endl; marci@512: marci@510: return 0; marci@510: }