An variable size "exponential" instance generator. More...

#include <generator.h>

Inheritance diagram for mosp::VSExponentialInstanceGenerator:

Collaboration diagram for mosp::VSExponentialInstanceGenerator:

Public Member Functions
	VSExponentialInstanceGenerator (int apps, int posts, double Density, double lambda)
	Create a new generator. More...

	VSExponentialInstanceGenerator (int apps, int posts, double Density, double lambda, int seed)
	Create a new generator. More...

void	GenerateGML (std::ostream &o)
	Generate a random structured instance in GML format. More...

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)
	Generate a random structured instance. More...

int	NumPosts () const

int	NumApplicants () const

Detailed Description

An variable size "exponential" instance generator.

The variable size random instance generator, while very similar to the fixed size generator , tries to capture a slightly different situation. Let $p_1, p_2, \ldots, p_m$ be a strict total order, as in the previous generator. We again partition the posts into clusters of exponentially increasing size. Now, however, clusters are similar but different for each applicant.

The generator has the following parameters: (a) number of applicants $n$ and posts $m$ , (b) instance density parameter $d$ , and (c) parameter $\lambda$ controlling the distribution of posts into clusters. We construct the preference list of an applicant $a \in A$ as follows. Our goal is to add an edge from $a$ to the first $m \cdot d$ posts. We initially add edge $(a, p_1)$ with rank 1. When adding edge $(a, p_i)$ we decide the rank based on the parameter $\lambda$ . We choose with probability $\frac{1}{e^{\lambda i}}$ whether to increase the rank by one or use the same rank as edge $(a, p_{i-1})$ .

Constructor & Destructor Documentation

mosp::VSExponentialInstanceGenerator::VSExponentialInstanceGenerator	(	int	apps,
		int	posts,
		double	Density,
		double	lambda
	)

inline

Create a new generator.

Parameters

apps	Number of applicants .
posts	Number of posts .
Density	Density parameter .
lambda	Parameter $\lambda$ .

mosp::VSExponentialInstanceGenerator::VSExponentialInstanceGenerator	(	int	apps,
		int	posts,
		double	Density,
		double	lambda,
		int	seed
	)

inline

Create a new generator.

Parameters

apps	Number of applicants .
posts	Number of posts .
Density	Density parameter .
lambda	Parameter $\lambda$
seed	A seed for the random number generator

Member Function Documentation

void mosp::StructuredInstanceGenerator::GenerateGML ( std::ostream & o )

inherited

Generate a random structured instance in GML format.

Parameters

o	Output the GML graph in this stream

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

inherited

Generate a random structured instance.

Parameters

G	The graph to return
A	The list of applicants
B	The list of posts
capacity	The node capacities
rank	The edge ranks

int mosp::StructuredInstanceGenerator::NumApplicants ( ) const

inlineinherited

Number of applicants that the resulting instance will have.

int mosp::StructuredInstanceGenerator::NumPosts ( ) const

inlineinherited

Number of posts that the resulting instance will have.

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation