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 |