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 (ted@lehigh.edu) */ 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 122