SwapBpUGraphAdaptor Class Template Reference
[Adaptor Classes for Graphs]

#include <lemon/bpugraph_adaptor.h>

Inherits BpUGraphAdaptorExtender< lemon::SwapBpUGraphAdaptorBase< _BpUGraph > >.

Inheritance diagram for SwapBpUGraphAdaptor:

Inheritance graph
[legend]
List of all members.

Detailed Description

template<typename _BpUGraph>
class lemon::SwapBpUGraphAdaptor< _BpUGraph >

Bipartite graph adaptor which swaps the two nodeset. The adaptor's anode-set will be the original graph's bnode-set and the adaptor's bnode-set will be the original graph's anode-set.

As example look at an algorithm what can be sped up with the swap bipartite undirected graph adaptor. If we want to find the maximum matching in the bipartite graph then it will be not changed if we swap the two nodesets. But the algorithm use the two nodeset different way. If we swap the nodesets it provides different running time. We run a test on random bipartite graphs with different rate of the anode-set size and bnode-set size. We always made graphs with 10000 nodes and 20000 edges and we computed the maximum cardinality matching with the Hopcroft-Karp algorithm.

The next diagram shows the running time of the tests. If the anode-set is smaller than the bnode-set the running time is better than with the swapped graph. Other conclusion is that the running time is greater when the two nodesets size are nearly equal.

swap_test.png

The next part shows how can we swap the two nodeset:

      typedef SwapBpUGraphAdaptor<BpUGraph> SBpUGraph;
      SBpUGraph sbpugraph(bpugraph);
      MaxBipartiteMatching<SBpUGraph> sbpumatch(sbpugraph);


Public Member Functions

 SwapBpUGraphAdaptor (Graph &_graph)
 Construct a swapped graph.


Constructor & Destructor Documentation

SwapBpUGraphAdaptor ( Graph &  _graph  )  [inline, explicit]

Construct a swapped graph.


The documentation for this class was generated from the following file:
Generated on Tue Oct 31 09:49:51 2006 for LEMON by  doxygen 1.5.1