generator.h

Go to the documentation of this file.

//
// This program can be freely used in an academic environment
// ONLY for research purposes, subject to the following restrictions:
//
// 1. The origin of this software must not be misrepresented; you must not
//    claim that you wrote the original software. If you use this software
//    an acknowledgment in the product documentation is required.
// 2. Altered source versions must be plainly marked as such, and must not be
//    misrepresented as being the original software.
// 3. This notice may not be removed or altered from any source distribution.
//
// Any other use is strictly prohibited by the author, without an explicit
// permission.
//
// Note that this program uses the LEDA library, which is NOT free. For more
// details visit Algorithmic Solutions at http://www.algorithmic-solutions.com/
//
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// ! Any commercial use of this software is strictly !
// ! prohibited without explicit permission by the   !
// ! author.                                         !
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//
// This software is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
//
// Copyright (C) 2004-2010 Dimitris Michail <michail@hua.gr>
 // end of group generator

#ifndef LEP_GENERATOR_H
#define LEP_GENERATOR_H

#include <LEP/mosp/config.h>
#include <set>
#include <list>
#include <vector>
#include <map>

#ifdef LEDA_GE_V5
#include <LEDA/graph/graph.h>
#include <LEDA/core/random_source.h>
#include <LEDA/system/assert.h>
#include <LEDA/graph/node_map.h>
#include <LEDA/graph/edge_map.h>
#include <LEDA/core/list.h>
#include <LEDA/core/array.h>
#else
#include <LEDA/graph.h>
#include <LEDA/random_source.h>
#include <LEDA/std/assert.h>
#include <LEDA/node_map.h>
#include <LEDA/edge_map.h>
#include <LEDA/list.h>
#include <LEDA/array.h>
#endif

namespace mosp
{


    class StructuredInstanceGenerator
    {
        public:

            StructuredInstanceGenerator(int apps, int posts, int seed = default_seed);

            virtual ~StructuredInstanceGenerator(); 

            void GenerateGML( std::ostream& o );

            void GenerateGraph( leda::graph& G, 
                    leda::list<leda::node>& A, 
                    leda::list<leda::node>& B,
                    leda::node_map<int>& capacity,
                    leda::edge_map<int>& rank
                    );

            int NumPosts() const { return numPosts; }

            int NumApplicants() const { return numApplicants; }

        protected:
            static const int default_seed = 13;

            int numApplicants;
            int numPosts;

            int seedUsed;
            leda::random_source randomSource;  // random source
            leda::random_source randomSourceI; // random source in integer mode

            std::map<int, leda::node> ApplicantToNode;
            std::map<int, leda::node> PostToNode;

            void InitializeGraph( leda::graph& G,
                    leda::list<leda::node>& A, 
                    leda::list<leda::node>& B,
                    leda::node_map<int>& capacity,
                    leda::edge_map<int>& rank );

        private:
            virtual void GenerateEdges( leda::graph& G, 
                    leda::list<leda::node>& A,
                    leda::list<leda::node>& B,
                    leda::node_map<int>& capacity,
                    leda::edge_map<int>& rank ) = 0;

    };

    class VSExponentialInstanceGenerator : public StructuredInstanceGenerator
    {
        public:
            VSExponentialInstanceGenerator( int apps, int posts, double Density, double lambda ) : 
                StructuredInstanceGenerator( apps, posts ), EdgeProbability( Density ), Lambda( lambda )
            {
                assert( EdgeProbability >= 0.0 && EdgeProbability <= 1.0 );
            }

            VSExponentialInstanceGenerator( int apps, int posts, double Density, double lambda, int seed ) : 
                StructuredInstanceGenerator( apps, posts, seed ), EdgeProbability( Density ), Lambda( lambda )
            {
                assert( EdgeProbability >= 0.0 && EdgeProbability <= 1.0 );
            }

            ~VSExponentialInstanceGenerator()
            {
            }

        private:

            virtual void GenerateEdges( leda::graph& G, 
                    leda::list<leda::node>& A,
                    leda::list<leda::node>& B,
                    leda::node_map<int>& capacity,
                    leda::edge_map<int>& rank );

            // probability of an edge beeing there
            const double EdgeProbability;
            const double Lambda;

            // private implementation
            bool notIncreaseRank( int j );
    };

    class FSExponentialInstanceGenerator : public StructuredInstanceGenerator
    {
        public:
            FSExponentialInstanceGenerator( int apps, int posts, double lambda ) : 
                StructuredInstanceGenerator( apps, posts ), Lambda( lambda )
            {
            }

            FSExponentialInstanceGenerator( int apps, int posts, double lambda, int seed ) : 
                StructuredInstanceGenerator( apps, posts, seed ), Lambda( lambda )
            {
            }

            ~FSExponentialInstanceGenerator()
            {
            }

        private:

            virtual void GenerateEdges( leda::graph& G, 
                    leda::list<leda::node>& A,
                    leda::list<leda::node>& B,
                    leda::node_map<int>& capacity,
                    leda::edge_map<int>& rank );

            const double Lambda;

            // private implementation
            typedef std::set<int> Cluster;
            typedef std::list< Cluster > Clustering;

            Clustering PartitionPosts( int n );
            Clustering::const_iterator ChooseCluster( const Clustering& c );

            // private implementation
            bool notIncreaseRank( int j );
    };



    class HighlyCorrelatedInstanceGenerator : public StructuredInstanceGenerator
    {
        public:
            HighlyCorrelatedInstanceGenerator( int apps, int posts, double Density, double TieProp, int capacity ) 
                : StructuredInstanceGenerator( apps, posts ), EdgeProbability( Density ), 
                  TieProbability( TieProp ), Capacity(capacity)
            {
                assert( EdgeProbability >= 0.0 && EdgeProbability <= 1.0 );
                assert( TieProbability >= 0.0 && TieProbability <= 1.0 );
                assert( Capacity >= 1 );
            }

            HighlyCorrelatedInstanceGenerator( int apps, int posts, double Density, double TieProp, int capacity, int seed ) 
                : StructuredInstanceGenerator( apps, posts, seed ), EdgeProbability( Density ), 
                  TieProbability( TieProp ), Capacity( capacity )
            {
                assert( EdgeProbability >= 0.0 && EdgeProbability <= 1.0 );
                assert( TieProbability >= 0.0 && TieProbability <= 1.0 );
                assert( Capacity >= 1 );
            }

            ~HighlyCorrelatedInstanceGenerator()
            {
            }

        private:

            virtual void GenerateEdges( leda::graph& G, 
                    leda::list<leda::node>& A,
                    leda::list<leda::node>& B,
                    leda::node_map<int>& capacity,
                    leda::edge_map<int>& rank );


            // probability of an edge beeing there
            const double EdgeProbability;
            // probability of an edge beeing tied to its predecessor
            const double TieProbability;

            // fixed posts capacity
            int Capacity;

            // get a random subset from the set {0,1,...,n-1}
            void GetRandomSubset( int n, int k, leda::array<int>& a );   
    };


    class RegionalInstanceGenerator : public StructuredInstanceGenerator
    {
        public:
            RegionalInstanceGenerator( int apps, int posts, int capacity, int regions, double lambda ) 
                : StructuredInstanceGenerator( apps, posts ), 
                  Capacity(capacity), Regions(regions), Lambda(lambda) 
            {
                assert( Capacity >= 1 );
                assert( Regions >= 1 );
                assert( Lambda > 0.0 );
            }

            RegionalInstanceGenerator( int apps, int posts, int capacity, int regions, double lambda, int seed ) 
                : StructuredInstanceGenerator( apps, posts, seed ), 
                  Capacity(capacity), Regions(regions), Lambda(lambda) 
            {
                assert( Capacity >= 1 );
                assert( Regions >= 1 );
                assert( Lambda > 0.0 );
            }

            ~RegionalInstanceGenerator()
            {
            }

        private:

            // private implementation
            typedef std::set<int> Cluster;
            typedef std::vector< Cluster > Region;

            bool notIncreaseRank( int j );
            void CreateRegion( Region& R, int& remainingPosts, int postsPerRegion, int& firstPostNumber );
            void CreateRegions( std::vector<Region>& R, int regions, int posts  );
            int  ChooseRegion( std::vector<Region>& R );


            virtual void GenerateEdges( leda::graph& G, 
                    leda::list<leda::node>& A,
                    leda::list<leda::node>& B,
                    leda::node_map<int>& capacity,
                    leda::edge_map<int>& rank );


            // private
            const int Capacity;
            const int Regions;
            const double Lambda;
    };

}

#endif  // LEP_GENERATOR_H

/* ex: set ts=4 sw=4 sts=4 et: */