Changeset - r967:38213abd2911
« 964:141f9c
968:b89e46 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Small doc fixes and improvements (#359)
0 4 0
default
4 files changed with 22 insertions and 23 deletions:
LICENSE
1
1
doc/groups.dox
9
17
lemon/arg_parser.h
10
3
lemon/hartmann_orlin_mmc.h
2
2
↑ Collapse diff ↑
LICENSE
Show white space 6 line context
1 1 
LEMON code without an explicit copyright notice is covered by the following
2 2 
copyright/license.
3 3 

			




	4
	
	
		
Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi


			




	
	4
	
		
Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi


			




	5
	5
	
		
Kutatocsoport (Egervary Combinatorial Optimization Research Group,


			




	6
	6
	
		
EGRES).


			




	7
	7
	
		

			




        

    

    

    

        

            

                

                    doc/groups.dox
                

                

                  
                  
                  
                  Show white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -263,14 +263,6 @@


			




	263
	263
	
		
*/


			




	264
	264
	
		

			




	265
	265
	
		
/**


			




	266
	
	
		
@defgroup matrices Matrices


			




	267
	
	
		
@ingroup datas


			




	268
	
	
		
\brief Two dimensional data storages implemented in LEMON.


			




	269
	
	
		

			




	270
	
	
		
This group contains two dimensional data storages implemented in LEMON.


			




	271
	
	
		
*/


			




	272
	
	
		

			




	273
	
	
		
/**


			




	274
	266
	
		
@defgroup auxdat Auxiliary Data Structures


			




	275
	267
	
		
@ingroup datas


			




	276
	268
	
		
\brief Auxiliary data structures implemented in LEMON.


			




	...
	...
	
		
@@ -472,19 +464,19 @@


			




	472
	464
	
		
function.


			




	473
	465
	
		

			




	474
	466
	
		
LEMON contains three algorithms for solving the minimum mean cycle problem:


			




	475
	
	
		
- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,


			




	
	467
	
		
- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,


			




	476
	468
	
		
  \ref dasdan98minmeancycle.


			




	477
	
	
		
- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved


			




	
	469
	
		
- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved


			




	478
	470
	
		
  version of Karp's algorithm \ref dasdan98minmeancycle.


			




	479
	
	
		
- \ref Howard "Howard"'s policy iteration algorithm


			




	
	471
	
		
- \ref HowardMmc Howard's policy iteration algorithm


			




	480
	472
	
		
  \ref dasdan98minmeancycle.


			




	481
	473
	
		

			




	482
	
	
		
In practice, the Howard algorithm proved to be by far the most efficient


			




	483
	
	
		
one, though the best known theoretical bound on its running time is


			




	484
	
	
		
exponential.


			




	485
	
	
		
Both Karp and HartmannOrlin algorithms run in time O(ne) and use space


			




	486
	
	
		
O(n<sup>2</sup>+e), but the latter one is typically faster due to the


			




	487
	
	
		
applied early termination scheme.


			




	
	474
	
		
In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the


			




	
	475
	
		
most efficient one, though the best known theoretical bound on its running


			




	
	476
	
		
time is exponential.


			




	
	477
	
		
Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms


			




	
	478
	
		
run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is


			




	
	479
	
		
typically faster due to the applied early termination scheme.


			




	488
	480
	
		
*/


			




	489
	481
	
		

			




	490
	482
	
		
/**

			




        

    

    

    

        

            

                

                    lemon/arg_parser.h
                

                

                  
                  
                  
                  Show white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -35,12 +35,19 @@


			




	35
	35
	
		
namespace lemon {


			




	36
	36
	
		

			




	37
	37
	
		
  ///Exception used by ArgParser


			




	
	38
	
		

			




	
	39
	
		
  ///Exception used by ArgParser.


			




	
	40
	
		
  ///


			




	38
	41
	
		
  class ArgParserException : public Exception {


			




	39
	42
	
		
  public:


			




	
	43
	
		
    /// Reasons for failure


			




	
	44
	
		

			




	
	45
	
		
    /// Reasons for failure.


			




	
	46
	
		
    ///


			




	40
	47
	
		
    enum Reason {


			




	41
	
	
		
      HELP,         /// <tt>--help</tt> option was given


			




	42
	
	
		
      UNKNOWN_OPT,  /// Unknown option was given


			




	43
	
	
		
      INVALID_OPT   /// Invalid combination of options


			




	
	48
	
		
      HELP,         ///< <tt>--help</tt> option was given.


			




	
	49
	
		
      UNKNOWN_OPT,  ///< Unknown option was given.


			




	
	50
	
		
      INVALID_OPT   ///< Invalid combination of options.


			




	44
	51
	
		
    };


			




	45
	52
	
		

			




	46
	53
	
		
  private:

			




        

    

    

    

        

            

                

                    lemon/hartmann_orlin_mmc.h
                

                

                  
                  
                  
                  Show white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -38,7 +38,7 @@


			




	38
	38
	
		
  /// Default traits class of HartmannOrlinMmc class.


			




	39
	39
	
		
  /// \tparam GR The type of the digraph.


			




	40
	40
	
		
  /// \tparam CM The type of the cost map.


			




	41
	
	
		
  /// It must conform to the \ref concepts::Rea_data "Rea_data" concept.


			




	
	41
	
		
  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.


			




	42
	42
	
		
#ifdef DOXYGEN


			




	43
	43
	
		
  template <typename GR, typename CM>


			




	44
	44
	
		
#else


			




	...
	...
	
		
@@ -99,7 +99,7 @@


			




	99
	99
	
		
  /// This class implements the Hartmann-Orlin algorithm for finding


			




	100
	100
	
		
  /// a directed cycle of minimum mean cost in a digraph


			




	101
	101
	
		
  /// \ref amo93networkflows, \ref dasdan98minmeancycle.


			




	102
	
	
		
  /// It is an improved version of \ref Karp "Karp"'s original algorithm,


			




	
	102
	
		
  /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,


			




	103
	103
	
		
  /// it applies an efficient early termination scheme.


			




	104
	104
	
		
  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).


			




	105
	105
	
		
  ///


			




        

    






    
    



    


    

     
    
0 comments (0 inline)