| 1 |
/*===========================================================================*/ |
| 2 |
/* */ |
| 3 |
/* This file is part of a demonstration application for use with the */ |
| 4 |
/* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */ |
| 5 |
/* the Vehicle Routing Problem and the Traveling Salesman Problem. */ |
| 6 |
/* */ |
| 7 |
/* (c) Copyright 2000-2013 Ted Ralphs. All Rights Reserved. */ |
| 8 |
/* */ |
| 9 |
/* This application was developed by Ted Ralphs ([email protected]) */ |
| 10 |
/* */ |
| 11 |
/* This software is licensed under the Eclipse Public License. Please see */ |
| 12 |
/* accompanying file for terms. */ |
| 13 |
/* */ |
| 14 |
/*===========================================================================*/ |
| 15 |
|
| 16 |
#ifndef _NETWORK |
| 17 |
#define _NETWORK |
| 18 |
|
| 19 |
/* SYMPHONY include files */ |
| 20 |
#include "sym_proto.h" |
| 21 |
|
| 22 |
/* VRP include files */ |
| 23 |
#include "vrp_const.h" |
| 24 |
|
| 25 |
#define NOT_INTEGRAL -1 |
| 26 |
#define OTHER_END(cur_edge, v) \ |
| 27 |
(cur_edge->data->v0 == v) ? cur_edge->data->v1 : cur_edge->data->v0 |
| 28 |
|
| 29 |
/*-----------------------------------------------------------------------*\ |
| 30 |
| These are data tructures used in constructing the solution graph used | |
| 31 |
| by the cut generator to locate cuts. The graph is stored using | |
| 32 |
| adjacency lists | |
| 33 |
\*-----------------------------------------------------------------------*/ |
| 34 |
|
| 35 |
typedef struct EDGE{ |
| 36 |
int v0; |
| 37 |
int v1; |
| 38 |
int cost; |
| 39 |
double weight; |
| 40 |
char scanned; |
| 41 |
char tree_edge; |
| 42 |
char deleted; |
| 43 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 44 |
float q; |
| 45 |
int row; |
| 46 |
char can_be_doubled; /* tells whether this edge can potentially be used |
| 47 |
for a 1-customer route */ |
| 48 |
struct EDGE *other_data; |
| 49 |
#ifdef COMPILE_OUR_DECOMP |
| 50 |
char status; |
| 51 |
#endif |
| 52 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 53 |
}edge; |
| 54 |
|
| 55 |
typedef struct ELIST{ |
| 56 |
struct ELIST *next_edge; /* next edge in the edgelist */ |
| 57 |
struct EDGE *data; /* the data of the edge */ |
| 58 |
int other_end; /* the other end of the edge */ |
| 59 |
struct VERTEX *other; |
| 60 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 61 |
char superlink; |
| 62 |
int edgenum; |
| 63 |
struct EDGE **edges; |
| 64 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 65 |
}elist; |
| 66 |
|
| 67 |
typedef struct VERTEX{ |
| 68 |
int enodenum; /* the node number in the contracted graph */ |
| 69 |
int orignodenum;/* the node number in the original graph */ |
| 70 |
struct ELIST *first; /* points to the first edge in the adjacency list */ |
| 71 |
struct ELIST *last; /* points to the last edge in the adjacency list */ |
| 72 |
int comp; /* contains the component number if the graph is |
| 73 |
disconnected */ |
| 74 |
char scanned; |
| 75 |
int demand; /* contains the demand for this node */ |
| 76 |
int degree; /* contains the degree of the node in the graph */ |
| 77 |
int orig_node_list_size; |
| 78 |
int *orig_node_list; /* contains a list of the nodes that have been |
| 79 |
contracted into this node to make a |
| 80 |
"super node" */ |
| 81 |
int dfnumber; |
| 82 |
int low; |
| 83 |
char is_art_point; |
| 84 |
char deleted; |
| 85 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 86 |
float r; |
| 87 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 88 |
}vertex; |
| 89 |
|
| 90 |
typedef struct NETWORK{ |
| 91 |
int vertnum; /* the number of vertices in the graph */ |
| 92 |
char is_integral; /* indicates whether the graph is integral or |
| 93 |
not */ |
| 94 |
int edgenum; /* the number of edges in the graph */ |
| 95 |
float mincut; /* the value of the current mincut */ |
| 96 |
struct ELIST *adjlist; /* the array containing the adajacency lists for |
| 97 |
each node */ |
| 98 |
struct EDGE *edges; /* the list of edges in the graph */ |
| 99 |
struct VERTEX *verts; /* the list of vertices */ |
| 100 |
int *compnodes; /* number of nodes in each component */ |
| 101 |
double *new_demand; /* the amounts of demand for each node that gets |
| 102 |
added to it when the network is contracted */ |
| 103 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 104 |
struct VERTEX **tnodes; /* a binary tree of the exiisting vertices used by |
| 105 |
the min_cut routine */ |
| 106 |
struct VERTEX **enodes; /* a list of the nodes that still exist */ |
| 107 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 108 |
}network; |
| 109 |
|
| 110 |
network *createnet PROTO((int *xind, double *xval, int edgenum, double etol, |
| 111 |
int *edges, int *demands, int vertnum)); |
| 112 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 113 |
network *createnet2 PROTO((int *xind, double *xval, int edgenum, double etol, |
| 114 |
int *edges, int *demands, int vertnum, |
| 115 |
char *status)); |
| 116 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 117 |
int connected PROTO((network *n, int *compnodes, int *compdemands, |
| 118 |
int *compmembers, double *compcuts, double *compdensity)); |
| 119 |
void free_net PROTO((network *n)); |
| 120 |
|
| 121 |
#endif |