Some modifications and another testfile.
2 #ifndef HUGO_MAX_BIPARTITE_MATCHING_H
3 #define HUGO_MAX_BIPARTITE_MATCHING_H
5 //#include <for_each_macros.h>
6 #include <bipartite_graph_wrapper.h>
7 //#include <hugo/maps.h>
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> >
21 // stGraphWrapper<Graph> gw;
22 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap;
23 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow;
25 // //EdgeCap* edge_cap;
26 // //EdgeFlow* edge_flow;
28 // MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
29 // EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
31 // cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) {
32 // Parent::set(gw, cap, flow);
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, b-matchings an capacitated b-matchings 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>
48 // EdgeFlow* edge_flow;
49 // NodeFlow* node_flow;
50 typedef stGraphWrapper<Graph> stGW;
52 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
55 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
57 MaxFlow<stGW, int, CapMap, FlowMap> mf;
60 //EdgeFlow* edge_flow;
62 /// For capacitated b-matchings, edge-caoacities and node-capacities
63 /// have to be given. After running \c run the matching is is given
64 /// back in the edge-map \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
68 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
69 EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
71 cap(_edge_cap, _node_cap),
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
79 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
80 EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) :
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(); }
96 #endif //HUGO_MAX_BIPARTITE_MATCHING_H