SwapBpUGraphAdaptor< _BpUGraph > Class Template Reference
[Adaptor Classes for Graphs]

---

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.

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

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

#include <lemon/bpugraph_adaptor.h>

Inheritance diagram for SwapBpUGraphAdaptor< _BpUGraph >:

[legend]

List of all members.

Public Member Functions
	SwapBpUGraphAdaptor (Graph &_graph)

---

Constructor & Destructor Documentation

SwapBpUGraphAdaptor

(

Graph &

_graph

)

[inline, explicit]

Construct a swapped graph.