tsplib.c File Reference

#include <postgres.h>
#include <string.h>
#include <math.h>
#include "./tsp.h"
#include "../../common/src/debug_macro.h"

Go to the source code of this file.

Classes
struct	tspstruct

Macros
#define	COOLING   0.9 /* to lower down T(< 1) */
#define	D(x, y)   dist[(x)*n+y]
#define	DQ()   arc[--l]
#define	EMPTY   (l == 0)
#define	FINAL_T   0.1
#define	IMPROVED_PATH_PER_T   60*n
#define	MAX(a, b)   ((a) > (b)?(a) : (b))
#define	MIN(a, b)   ((a) < (b)?(a) : (b))
#define	MOD(i, n)   ((i) %(n) >= 0 ?(i) %(n) :(i) %(n) +(n))
#define	NQ(x)   arc[l++] = x
#define	PRANDMAX   1000000000
#define	RANDOM   Rand
#define	RREAL   ((double)Rand()/PRANDMAX)
#define	sqr(x)   ((x)*(x))
#define	T_INIT   100
#define	TRIES_PER_T   500*n
#define	unifRand(n)   (Rand()%n)
#define	VISITED(x)   jorder[x]

Typedefs
typedef int	Path [3]
typedef struct tspstruct	TSP

Functions
static void	annealing (TSP *tsp)
static void	doReverse (TSP *tsp, Path p)
static void	doThreeWay (TSP *tsp, Path p)
int	find_tsp_solution (int num, double *cost, int *ids, int start, int end, double *total_len, char *err_msg)
static int	findEulerianPath (TSP *tsp)
static double	getReverseCost (TSP *tsp, Path p)
static double	getThreeWayCost (TSP *tsp, Path p)
static void	initRand (int seed)
static double	pathLength (TSP *tsp)
static int	Rand (void)
static void	reverse (int num, int *ids)

Variables
static int	a
static int	arr [55]
static int	b

Macro Definition Documentation

#define COOLING   0.9 /* to lower down T(< 1) */

Definition at line 104 of file tsplib.c.

Referenced by annealing().

#define D	(		x,
			y
	)		dist[(x)*n+y]

Definition at line 187 of file tsplib.c.

Referenced by findEulerianPath(), getReverseCost(), getThreeWayCost(), and pathLength().

#define DQ

(

)

arc[--l]

Referenced by findEulerianPath().

#define EMPTY   (l == 0)

Referenced by findEulerianPath().

#define FINAL_T   0.1

Definition at line 103 of file tsplib.c.

Referenced by annealing().

#define IMPROVED_PATH_PER_T   60*n

Definition at line 106 of file tsplib.c.

Referenced by annealing().

#define MAX	(		a,
			b
	)		((a) > (b)?(a) : (b))

Definition at line 190 of file tsplib.c.

Referenced by find_tsp_solution().

#define MIN	(		a,
			b
	)		((a) < (b)?(a) : (b))

Definition at line 189 of file tsplib.c.

#define MOD	(		i,
			n
	)		((i) %(n) >= 0 ?(i) %(n) :(i) %(n) +(n))

Definition at line 186 of file tsplib.c.

Referenced by annealing(), doReverse(), doThreeWay(), getReverseCost(), and getThreeWayCost().

#define NQ

(

x

)

arc[l++] = x

Referenced by findEulerianPath().

#define PRANDMAX   1000000000

Definition at line 113 of file tsplib.c.

Referenced by initRand(), and Rand().

#define RANDOM   Rand

Definition at line 165 of file tsplib.c.

Referenced by annealing().

#define RREAL   ((double)Rand()/PRANDMAX)

Definition at line 164 of file tsplib.c.

Referenced by annealing().

#define sqr

(

x

)

((x)*(x))

Definition at line 191 of file tsplib.c.

#define T_INIT   100

Definition at line 102 of file tsplib.c.

Referenced by annealing().

#define TRIES_PER_T   500*n

Definition at line 105 of file tsplib.c.

Referenced by annealing().

#define unifRand

(

n

)

(Rand()%n)

Definition at line 166 of file tsplib.c.

Referenced by annealing().

#define VISITED

(

x

)

jorder[x]

Referenced by findEulerianPath().

Typedef Documentation

typedef int Path[3]

Definition at line 173 of file tsplib.c.

typedef struct tspstruct TSP

Function Documentation

static void annealing ( TSP *  tsp )

static

Definition at line 401 of file tsplib.c.

References tspstruct::bestlen, tspstruct::border, COOLING, doReverse(), doThreeWay(), DTYPE, FINAL_T, getReverseCost(), getThreeWayCost(), IMPROVED_PATH_PER_T, tspstruct::iorder, MOD, tspstruct::n, pathLength(), PGR_DBG, RANDOM, RREAL, T_INIT, TRIES_PER_T, and unifRand.

Referenced by find_tsp_solution().

static void doReverse ( TSP *  tsp, Path  p  )

static

Definition at line 383 of file tsplib.c.

References tspstruct::iorder, MOD, and tspstruct::n.

Referenced by annealing().

static void doThreeWay ( TSP *  tsp, Path  p  )

static

Definition at line 331 of file tsplib.c.

References a, b, tspstruct::iorder, tspstruct::jorder, MOD, and tspstruct::n.

Referenced by annealing().

int find_tsp_solution	(	int	num,
		double *	cost,
		int *	ids,
		int	start,
		int	end,
		double *	total_len,
		char *	err_msg
	)

Definition at line 467 of file tsplib.c.

References annealing(), tspstruct::bestlen, tspstruct::border, tspstruct::dist, DTYPE, findEulerianPath(), initRand(), tspstruct::iorder, tspstruct::jorder, MAX, tspstruct::maxd, tspstruct::n, pathLength(), PGR_DBG, and reverse().

Referenced by solve_tsp().

static int findEulerianPath ( TSP *  tsp )

static

Definition at line 198 of file tsplib.c.

References a, D, tspstruct::dist, DQ, DTYPE, EMPTY, tspstruct::iorder, tspstruct::jorder, tspstruct::maxd, tspstruct::n, NQ, and VISITED.

Referenced by find_tsp_solution().

static double getReverseCost ( TSP *  tsp, Path  p  )

static

Definition at line 369 of file tsplib.c.

References a, b, D, tspstruct::dist, DTYPE, tspstruct::iorder, MOD, and tspstruct::n.

Referenced by annealing().

static double getThreeWayCost ( TSP *  tsp, Path  p  )

static

Definition at line 313 of file tsplib.c.

References a, b, D, tspstruct::dist, DTYPE, tspstruct::iorder, MOD, and tspstruct::n.

Referenced by annealing().

static void initRand ( int  seed )

static

Definition at line 122 of file tsplib.c.

References a, arr, b, PRANDMAX, and Rand().

Referenced by find_tsp_solution().

static double pathLength ( TSP *  tsp )

static

Definition at line 289 of file tsplib.c.

References D, tspstruct::dist, DTYPE, tspstruct::iorder, and tspstruct::n.

Referenced by annealing(), and find_tsp_solution().

static int Rand ( void  )

static

Definition at line 146 of file tsplib.c.

References a, arr, b, and PRANDMAX.

Referenced by initRand().

static void reverse ( int  num, int *  ids  )

static

Definition at line 457 of file tsplib.c.

Referenced by pgrouting::vrp::Optimize::decrease_truck(), do_pgr_eucledianTSP(), do_pgr_tsp(), find_tsp_solution(), pgrouting::vrp::Optimize::inter_swap(), pgrouting::vrp::Optimize::move_duration_based(), pgrouting::vrp::Optimize::move_wait_time_based(), and pgrouting::tsp::Tour::reverse().

Variable Documentation

int a

static

Definition at line 114 of file tsplib.c.

Referenced by check_points(), do_pgr_many_to_many_withPoints(), do_pgr_many_to_one_withPoints(), do_pgr_one_to_many_withPoints(), doThreeWay(), findEulerianPath(), pgrouting::tsp::TSP< MATRIX >::getDeltaReverse(), pgrouting::tsp::TSP< MATRIX >::getDeltaSwap(), getReverseCost(), getThreeWayCost(), initRand(), and Rand().

int arr[55]

static

Definition at line 116 of file tsplib.c.

Referenced by initRand(), and Rand().

int b

static

Definition at line 115 of file tsplib.c.

Referenced by check_points(), do_pgr_many_to_many_withPoints(), do_pgr_many_to_one_withPoints(), do_pgr_one_to_many_withPoints(), doThreeWay(), pgrouting::tsp::TSP< MATRIX >::getDeltaReverse(), pgrouting::tsp::TSP< MATRIX >::getDeltaSwap(), getReverseCost(), getThreeWayCost(), initRand(), Pgr_allpairs< G >::inf_plus< T >::operator()(), and Rand().