lemon/bpugraph_adaptor.h
changeset 2121 09a07a851506
parent 2040 c7bd55c0d820
child 2231 06faf3f06d67
equal deleted inserted replaced
1:21c8b6d41911 2:865378fe8d59
   407   /// \ingroup graph_adaptors
   407   /// \ingroup graph_adaptors
   408   ///
   408   ///
   409   /// \brief Bipartite graph adaptor which swaps the two nodeset.
   409   /// \brief Bipartite graph adaptor which swaps the two nodeset.
   410   ///
   410   ///
   411   /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
   411   /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
   412   /// a-nodeset will be the original graph's b-nodeset and the adaptor's
   412   /// anode-set will be the original graph's bnode-set and the adaptor's
   413   /// b-nodeset will be the original graph's a-nodeset. 
   413   /// bnode-set will be the original graph's anode-set.
       
   414   ///
       
   415   /// As example look at an algorithm what can be sped up with the
       
   416   /// swap bipartite undirected graph adaptor. If we want to find the
       
   417   /// maximum matching in the bipartite graph then it will be not changed
       
   418   /// if we swap the two nodesets. But the algorithm use the two nodeset
       
   419   /// different way. If we swap the nodesets it provides different
       
   420   /// running time. We run a test on random bipartite graphs with
       
   421   /// different rate of the anode-set size and bnode-set size.
       
   422   /// We always made graphs with 10000 nodes and 20000 edges and we
       
   423   /// computed the maximum cardinality matching with the Hopcroft-Karp 
       
   424   /// algorithm.
       
   425   ///
       
   426   /// The next diagram shows the running time of the tests. If the anode-set
       
   427   /// is smaller than the bnode-set the running time is better than with 
       
   428   /// the swapped graph. Other conclusion is that the running time
       
   429   /// is greater when the two nodesets size are nearly equal. 
       
   430   ///
       
   431   /// \image html swap_test.png
       
   432   /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth
       
   433   /// 
       
   434   /// The next part shows how can we swap the two nodeset:
       
   435   ///
       
   436   ///\code
       
   437   /// typedef SwapBpUGraphAdaptor<BpUGraph> SBpUGraph;
       
   438   /// SBpUGraph sbpugraph(bpugraph);
       
   439   /// MaxBipartiteMatching<SBpUGraph> sbpumatch(sbpugraph);
       
   440   ///\endcode
   414   template <typename _BpUGraph>
   441   template <typename _BpUGraph>
   415   class SwapBpUGraphAdaptor 
   442   class SwapBpUGraphAdaptor 
   416     : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > { 
   443     : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > { 
   417   public:
   444   public:
   418 
   445 
   423   protected:
   450   protected:
   424     SwapBpUGraphAdaptor() : Parent() {}
   451     SwapBpUGraphAdaptor() : Parent() {}
   425 
   452 
   426   public:
   453   public:
   427 
   454 
       
   455     /// \brief Construct a swapped graph.
       
   456     ///
       
   457     /// Construct a swapped graph.
   428     explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
   458     explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
   429 
   459 
   430   };
   460   };
   431 
   461 
   432 
   462