57 protected: |
57 protected: |
58 // EdgeCap* edge_cap; |
58 // EdgeCap* edge_cap; |
59 // NodeCap* node_cap; |
59 // NodeCap* node_cap; |
60 // EdgeFlow* edge_flow; |
60 // EdgeFlow* edge_flow; |
61 // NodeFlow* node_flow; |
61 // NodeFlow* node_flow; |
62 typedef stGraphWrapper<Graph> stGW; |
62 typedef stBipartiteGraphWrapper<Graph> stGW; |
63 stGW stgw; |
63 stGW stgw; |
64 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; |
64 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; |
65 CapMap cap; |
65 CapMap cap; |
66 NodeFlow* node_flow; |
66 NodeFlow* node_flow; |
67 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; |
67 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; |
68 FlowMap flow; |
68 FlowMap flow; |
69 MaxFlow<stGW, int, CapMap, FlowMap> mf; |
69 typedef MaxFlow<stGW, int, CapMap, FlowMap> MaxFlow; |
|
70 MaxFlow mf; |
70 //graph* g; |
71 //graph* g; |
71 //EdgeCap* edge_cap; |
72 //EdgeCap* edge_cap; |
72 //EdgeFlow* edge_flow; |
73 //EdgeFlow* edge_flow; |
73 public: |
74 public: |
|
75 enum MatchingEnum{ |
|
76 ZERO_MATCHING, |
|
77 GEN_MATCHING, |
|
78 GEN_MATCHING_WITH_GOOD_NODE_FLOW, |
|
79 NO_MATCHING |
|
80 }; |
74 /// For capacitated b-matchings, edge-caoacities and node-capacities |
81 /// For capacitated b-matchings, edge-caoacities and node-capacities |
75 /// have to be given. After running \c run the matching is is given |
82 /// have to be given. After running \c run the matching is is given |
76 /// back in the edge-map \c _edge_flow and \c _node_map can be used |
83 /// back in the edge-map \c _edge_flow and \c _node_map can be used |
77 /// to obtain saturation information about nodes. |
84 /// to obtain saturation information about nodes. |
78 ///\bug Note that the values in _edge_flow and _node_flow have |
85 ///\bug Note that the values in _edge_flow and _node_flow have |
96 flow(_edge_flow, *node_flow), |
103 flow(_edge_flow, *node_flow), |
97 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } |
104 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } |
98 /// The class have a nontrivial destructor. |
105 /// The class have a nontrivial destructor. |
99 ~MaxBipartiteMatching() { if (node_flow) delete node_flow; } |
106 ~MaxBipartiteMatching() { if (node_flow) delete node_flow; } |
100 /// run computes the max matching. |
107 /// run computes the max matching. |
101 void run() { mf.run(); } |
108 void run(MatchingEnum me=ZERO_MATCHING) { |
|
109 switch (me) { |
|
110 case ZERO_MATCHING: |
|
111 mf.run(MaxFlow::ZERO_FLOW); |
|
112 break; |
|
113 case GEN_MATCHING: |
|
114 { |
|
115 typename stGW::OutEdgeIt e; |
|
116 for (stgw.first(e, stgw.S_NODE); stgw.valid(e); stgw.next(e)) |
|
117 flow.set(e, cap[e]); |
|
118 } |
|
119 { |
|
120 typename stGW::InEdgeIt e; |
|
121 for (stgw.first(e, stgw.T_NODE); stgw.valid(e); stgw.next(e)) |
|
122 flow.set(e, 0); |
|
123 } |
|
124 mf.run(MaxFlow::PRE_FLOW); |
|
125 break; |
|
126 case GEN_MATCHING_WITH_GOOD_NODE_FLOW: |
|
127 mf.run(MaxFlow::GEN_FLOW); |
|
128 break; |
|
129 case NO_MATCHING: |
|
130 mf.run(MaxFlow::NO_FLOW); |
|
131 break; |
|
132 } |
|
133 } |
102 /// The matching value after running \c run. |
134 /// The matching value after running \c run. |
103 int matchingValue() { return mf.flowValue(); } |
135 int matchingValue() const { return mf.flowValue(); } |
104 }; |
136 }; |
105 |
137 |
106 } //namespace hugo |
138 } //namespace hugo |
107 |
139 |
108 #endif //HUGO_MAX_BIPARTITE_MATCHING_H |
140 #endif //HUGO_MAX_BIPARTITE_MATCHING_H |