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

Timestamp:

05/15/06 11:49:51 (18 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:

• lemon/bpugraph_adaptor.h (modified) (2 diffs)

lemon/bpugraph_adaptor.h

@@ -410 +410 @@
   ///
   /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
-  /// a-nodeset will be the original graph's b-nodeset and the adaptor's
-  /// b-nodeset will be the original graph's a-nodeset. 
+  /// 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. 
+  ///
+  /// \image html swap_test.png
+  /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth
+  /// 
+  /// The next part shows how can we swap the two nodeset:
+  ///
+  ///\code
+  /// typedef SwapBpUGraphAdaptor<BpUGraph> SBpUGraph;
+  /// SBpUGraph sbpugraph(bpugraph);
+  /// MaxBipartiteMatching<SBpUGraph> sbpumatch(sbpugraph);
+  ///\endcode
   template <typename _BpUGraph>
   class SwapBpUGraphAdaptor 
@@ -426 +453 @@
   public:
 
+    /// \brief Construct a swapped graph.
+    ///
+    /// Construct a swapped graph.
     explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }