diff -r d426dca0aaf7 -r bfd6c14e2975 src/work/marci/bipartite_graph_wrapper.h --- a/src/work/marci/bipartite_graph_wrapper.h Fri May 14 15:33:52 2004 +0000 +++ b/src/work/marci/bipartite_graph_wrapper.h Fri May 14 18:08:29 2004 +0000 @@ -16,6 +16,9 @@ namespace hugo { + /// \brief A wrapper for composing a bipartite graph from a graph + /// and from a node-map showing for any node which color class it belongs to. + /// /// A wrapper for composing a bipartite graph. /// \c _graph have to be a reference to a graph of type \c Graph /// and \c _s_false_t_true_map is an \c IterableBoolMap @@ -23,7 +26,7 @@ /// color classes S and T. \c _graph is to be referred to an undirected /// graph or a directed graph with edges oriented from S to T. /// - ///\author Marton Makai + /// \author Marton Makai template class BipartiteGraphWrapper : public GraphWrapper { protected: @@ -176,9 +179,12 @@ return Node(this->graph->bNode(e.e)); } + /// Returns true iff \c n is in S. bool inSClass(const Node& n) const { return !(*(this->s_false_t_true_map))[n]; } + + /// Returns true iff \c n is in T. bool inTClass(const Node& n) const { return (*(this->s_false_t_true_map))[n]; } @@ -190,18 +196,17 @@ template const bool BipartiteGraphWrapper::T_CLASS=true; - - - - - - - - - - - - ///\bug Do not use this while the bipartitemap augmentation + /// \brief A bipartite graph template class + /// + /// This class composes a bipartite graph over a directed or undirected + /// graph structure of type \c Graph. + /// \c _graph have to be a reference to a graph of type \c Graph + /// and \c _s_false_t_true_map is an \c IterableBoolMap + /// reference containing the elements for the + /// color classes S and T. \c _graph is to be referred to an undirected + /// graph or a directed graph with edges oriented from S to T. + /// + ///\bug experimental. Do not use this while the bipartitemap augmentation /// does not work well. template class BipartiteGraph : public BipartiteGraphWrapper { @@ -270,11 +275,17 @@ // return os; // } - /// experimentral, do not try it. - /// It eats a bipartite graph, oriented from S to T. - /// Such one can be made e.g. by the above wrapper. + /// \brief A wrapper for adding extra nodes s and t to a bipartite graph + /// and edges from s to each node of S and form each node of T to t. + /// + /// A wrapper for adding extra nodes s and t to a bipartite graph + /// and edges from s to each node of S and form each node of T to t. + /// This class is very useful to reduce some matching or more + /// generally, capacitataed b-matching problem to a flow problem. + /// According to the bipartite graph concepts the bipartite + /// graph have to be oriented from S to T. /// - ///\author Marton Makai + /// \author Marton Makai template class stGraphWrapper : public GraphWrapper { public: