equal
deleted
inserted
replaced
14 #include <iter_map.h> |
14 #include <iter_map.h> |
15 #include <hugo/graph_wrapper.h> |
15 #include <hugo/graph_wrapper.h> |
16 |
16 |
17 namespace hugo { |
17 namespace hugo { |
18 |
18 |
|
19 /// \brief A wrapper for composing a bipartite graph from a graph |
|
20 /// and from a node-map showing for any node which color class it belongs to. |
|
21 /// |
19 /// A wrapper for composing a bipartite graph. |
22 /// A wrapper for composing a bipartite graph. |
20 /// \c _graph have to be a reference to a graph of type \c Graph |
23 /// \c _graph have to be a reference to a graph of type \c Graph |
21 /// and \c _s_false_t_true_map is an \c IterableBoolMap |
24 /// and \c _s_false_t_true_map is an \c IterableBoolMap |
22 /// reference containing the elements for the |
25 /// reference containing the elements for the |
23 /// color classes S and T. \c _graph is to be referred to an undirected |
26 /// color classes S and T. \c _graph is to be referred to an undirected |
24 /// graph or a directed graph with edges oriented from S to T. |
27 /// graph or a directed graph with edges oriented from S to T. |
25 /// |
28 /// |
26 ///\author Marton Makai |
29 /// \author Marton Makai |
27 template<typename Graph> |
30 template<typename Graph> |
28 class BipartiteGraphWrapper : public GraphWrapper<Graph> { |
31 class BipartiteGraphWrapper : public GraphWrapper<Graph> { |
29 protected: |
32 protected: |
30 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
33 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
31 SFalseTTrueMap; |
34 SFalseTTrueMap; |
174 } |
177 } |
175 Node bNode(const InEdgeIt& e) const { |
178 Node bNode(const InEdgeIt& e) const { |
176 return Node(this->graph->bNode(e.e)); |
179 return Node(this->graph->bNode(e.e)); |
177 } |
180 } |
178 |
181 |
|
182 /// Returns true iff \c n is in S. |
179 bool inSClass(const Node& n) const { |
183 bool inSClass(const Node& n) const { |
180 return !(*(this->s_false_t_true_map))[n]; |
184 return !(*(this->s_false_t_true_map))[n]; |
181 } |
185 } |
|
186 |
|
187 /// Returns true iff \c n is in T. |
182 bool inTClass(const Node& n) const { |
188 bool inTClass(const Node& n) const { |
183 return (*(this->s_false_t_true_map))[n]; |
189 return (*(this->s_false_t_true_map))[n]; |
184 } |
190 } |
185 }; |
191 }; |
186 |
192 |
188 template<typename G> |
194 template<typename G> |
189 const bool BipartiteGraphWrapper<G>::S_CLASS=false; |
195 const bool BipartiteGraphWrapper<G>::S_CLASS=false; |
190 template<typename G> |
196 template<typename G> |
191 const bool BipartiteGraphWrapper<G>::T_CLASS=true; |
197 const bool BipartiteGraphWrapper<G>::T_CLASS=true; |
192 |
198 |
193 |
199 /// \brief A bipartite graph template class |
194 |
200 /// |
195 |
201 /// This class composes a bipartite graph over a directed or undirected |
196 |
202 /// graph structure of type \c Graph. |
197 |
203 /// \c _graph have to be a reference to a graph of type \c Graph |
198 |
204 /// and \c _s_false_t_true_map is an \c IterableBoolMap |
199 |
205 /// reference containing the elements for the |
200 |
206 /// color classes S and T. \c _graph is to be referred to an undirected |
201 |
207 /// graph or a directed graph with edges oriented from S to T. |
202 |
208 /// |
203 |
209 ///\bug experimental. Do not use this while the bipartitemap augmentation |
204 ///\bug Do not use this while the bipartitemap augmentation |
|
205 /// does not work well. |
210 /// does not work well. |
206 template<typename Graph> |
211 template<typename Graph> |
207 class BipartiteGraph : public BipartiteGraphWrapper<Graph> { |
212 class BipartiteGraph : public BipartiteGraphWrapper<Graph> { |
208 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
213 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
209 SFalseTTrueMap; |
214 SFalseTTrueMap; |
268 // os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << |
273 // os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << |
269 // " node: " << i.n << ")"; |
274 // " node: " << i.n << ")"; |
270 // return os; |
275 // return os; |
271 // } |
276 // } |
272 |
277 |
273 /// experimentral, do not try it. |
278 /// \brief A wrapper for adding extra nodes s and t to a bipartite graph |
274 /// It eats a bipartite graph, oriented from S to T. |
279 /// and edges from s to each node of S and form each node of T to t. |
275 /// Such one can be made e.g. by the above wrapper. |
280 /// |
|
281 /// A wrapper for adding extra nodes s and t to a bipartite graph |
|
282 /// and edges from s to each node of S and form each node of T to t. |
|
283 /// This class is very useful to reduce some matching or more |
|
284 /// generally, capacitataed b-matching problem to a flow problem. |
|
285 /// According to the bipartite graph concepts the bipartite |
|
286 /// graph have to be oriented from S to T. |
276 /// |
287 /// |
277 ///\author Marton Makai |
288 /// \author Marton Makai |
278 template<typename Graph> |
289 template<typename Graph> |
279 class stGraphWrapper : public GraphWrapper<Graph> { |
290 class stGraphWrapper : public GraphWrapper<Graph> { |
280 public: |
291 public: |
281 class Node; |
292 class Node; |
282 friend class Node; |
293 friend class Node; |