![]() |
pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
|
#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 |
#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().
Definition at line 190 of file tsplib.c.
Referenced by find_tsp_solution().
#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().
Definition at line 164 of file tsplib.c.
Referenced by annealing().
#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().
|
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().
Definition at line 383 of file tsplib.c.
References tspstruct::iorder, MOD, and tspstruct::n.
Referenced by annealing().
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 |
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().
Definition at line 369 of file tsplib.c.
References a, b, D, tspstruct::dist, DTYPE, tspstruct::iorder, MOD, and tspstruct::n.
Referenced by annealing().
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 |
|
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 |
|
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().
|
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().
|
static |
Definition at line 116 of file tsplib.c.
Referenced by initRand(), and Rand().
|
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().