Renamed simann_test.cc to simann_demo.cc.
2 #ifndef LEMON_MAX_BIPARTITE_MATCHING_H
3 #define LEMON_MAX_BIPARTITE_MATCHING_H
7 /// \brief Maximum bipartite matchings, b-matchings and
8 /// capacitated b-matchings.
10 /// This file contains a class for bipartite maximum matching, b-matchings
11 /// and capacitated b-matching computations.
13 // /// \author Marton Makai
15 //#include <for_each_macros.h>
16 #include <bipartite_graph_wrapper.h>
17 //#include <lemon/maps.h>
18 #include <lemon/max_flow.h>
22 // template <typename Graph, typename EdgeCap, typename NodeCap,
23 // typename EdgeFlow, typename NodeFlow>
24 // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>,
25 // stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {
26 // typedef MaxFlow<stGraphWrapper<Graph>,
27 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,
28 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >
31 // stGraphWrapper<Graph> gw;
32 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap;
33 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow;
35 // //EdgeCap* edge_cap;
36 // //EdgeFlow* edge_flow;
38 // MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
39 // EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
41 // cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) {
42 // Parent::set(gw, cap, flow);
46 /// \brief A bipartite matching class.
48 /// This class reduces the matching problem to a flow problem and
49 /// a preflow is used on a wrapper. Such a generic approach means that
50 /// matchings, b-matchings an capacitated b-matchings can be handled in
51 /// a similar way. Due to the efficiency of the preflow algorithm, an
52 /// efficient matching framework is obtained.
54 template <typename Graph, typename EdgeCap, typename NodeCap,
55 typename EdgeFlow, typename NodeFlow>
56 class MaxBipartiteMatching {
60 // EdgeFlow* edge_flow;
61 // NodeFlow* node_flow;
62 typedef stBipartiteGraphWrapper<Graph> stGW;
64 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
67 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
69 typedef MaxFlow<stGW, int, CapMap, FlowMap> MaxFlow;
73 //EdgeFlow* edge_flow;
78 GEN_MATCHING_WITH_GOOD_NODE_FLOW,
81 /// For capacitated b-matchings, edge-caoacities and node-capacities
82 /// have to be given. After running \c run the matching is is given
83 /// back in the edge-map \c _edge_flow and \c _node_map can be used
84 /// to obtain saturation information about nodes.
85 ///\bug Note that the values in _edge_flow and _node_flow have
87 MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
88 EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
90 cap(_edge_cap, _node_cap),
92 flow(_edge_flow, _node_flow),
93 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
94 /// If the saturation information of nodes is not needed that the use of
95 /// this constructor is more comfortable.
96 ///\bug Note that the values in _edge_flow and _node_flow have
98 MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
99 EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) :
101 cap(_edge_cap, _node_cap),
102 node_flow(new NodeFlow(_g)),
103 flow(_edge_flow, *node_flow),
104 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
105 /// The class have a nontrivial destructor.
106 ~MaxBipartiteMatching() { if (node_flow) delete node_flow; }
107 /// run computes the max matching.
108 void run(MatchingEnum me=ZERO_MATCHING) {
111 mf.run(MaxFlow::ZERO_FLOW);
115 typename stGW::OutEdgeIt e;
116 for (stgw.first(e, stgw.S_NODE); stgw.valid(e); stgw.next(e))
120 typename stGW::InEdgeIt e;
121 for (stgw.first(e, stgw.T_NODE); stgw.valid(e); stgw.next(e))
124 mf.run(MaxFlow::PRE_FLOW);
126 case GEN_MATCHING_WITH_GOOD_NODE_FLOW:
127 mf.run(MaxFlow::GEN_FLOW);
130 mf.run(MaxFlow::NO_FLOW);
134 /// The matching value after running \c run.
135 int matchingValue() const { return mf.flowValue(); }
140 #endif //LEMON_MAX_BIPARTITE_MATCHING_H