pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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,
 
)    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,
 
)    ((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 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 
)
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().

Variable Documentation

int arr[55]
static

Definition at line 116 of file tsplib.c.

Referenced by initRand(), and Rand().