COIN-OR::LEMON - Graph Library

Changeset 2084:59769591eb60 in lemon-0.x for lemon/bpugraph_adaptor.h


Ignore:
Timestamp:
05/15/06 11:49:51 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2749
Message:

Documentation improvements

Rearrangements:

IO modules
Algorithms

New documentation:

SwapBpUGraphAdaptor

Demos:

strongly_connected_orientation.cc

Benchmarks:

swap_bipartite_bench.cc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bpugraph_adaptor.h

    r2040 r2084  
    410410  ///
    411411  /// 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
    413   /// b-nodeset will be the original graph's a-nodeset.
     412  /// anode-set will be the original graph's bnode-set and the adaptor's
     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
    414441  template <typename _BpUGraph>
    415442  class SwapBpUGraphAdaptor
     
    426453  public:
    427454
     455    /// \brief Construct a swapped graph.
     456    ///
     457    /// Construct a swapped graph.
    428458    explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
    429459
Note: See TracChangeset for help on using the changeset viewer.