Changeset 2084:59769591eb60 in lemon0.x for lemon/bpugraph_adaptor.h
 Timestamp:
 05/15/06 11:49:51 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2749
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bpugraph_adaptor.h
r2040 r2084 410 410 /// 411 411 /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's 412 /// anodeset will be the original graph's bnodeset and the adaptor's 413 /// bnodeset will be the original graph's anodeset. 412 /// anodeset will be the original graph's bnodeset and the adaptor's 413 /// bnodeset will be the original graph's anodeset. 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 anodeset size and bnodeset size. 422 /// We always made graphs with 10000 nodes and 20000 edges and we 423 /// computed the maximum cardinality matching with the HopcroftKarp 424 /// algorithm. 425 /// 426 /// The next diagram shows the running time of the tests. If the anodeset 427 /// is smaller than the bnodeset 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 441 template <typename _BpUGraph> 415 442 class SwapBpUGraphAdaptor … … 426 453 public: 427 454 455 /// \brief Construct a swapped graph. 456 /// 457 /// Construct a swapped graph. 428 458 explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); } 429 459
Note: See TracChangeset
for help on using the changeset viewer.