00001 /*===========================================================================*/ 00002 /* */ 00003 /* This file is part of a demonstration application for use with the */ 00004 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */ 00005 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */ 00006 /* */ 00007 /* (c) Copyright 2000-2008 Ted Ralphs. All Rights Reserved. */ 00008 /* */ 00009 /* This application was developed by Ted Ralphs (tkralphs@lehigh.edu) */ 00010 /* */ 00011 /* This software is licensed under the Common Public License. Please see */ 00012 /* accompanying file for terms. */ 00013 /* */ 00014 /*===========================================================================*/ 00015 00016 #ifndef _NETWORK 00017 #define _NETWORK 00018 00019 /* SYMPHONY include files */ 00020 #include "sym_proto.h" 00021 00022 /* VRP include files */ 00023 #include "vrp_const.h" 00024 00025 #define NOT_INTEGRAL -1 00026 #define OTHER_END(cur_edge, v) \ 00027 (cur_edge->data->v0 == v) ? cur_edge->data->v1 : cur_edge->data->v0 00028 00029 /*-----------------------------------------------------------------------*\ 00030 | These are data tructures used in constructing the solution graph used | 00031 | by the cut generator to locate cuts. The graph is stored using | 00032 | adjacency lists | 00033 \*-----------------------------------------------------------------------*/ 00034 00035 typedef struct EDGE{ 00036 int v0; 00037 int v1; 00038 int cost; 00039 double weight; 00040 char scanned; 00041 char tree_edge; 00042 char deleted; 00043 }edge; 00044 00045 typedef struct ELIST{ 00046 struct ELIST *next_edge; /* next edge in the edgelist */ 00047 struct EDGE *data; /* the data of the edge */ 00048 int other_end; /* the other end of the edge */ 00049 struct VERTEX *other; 00050 }elist; 00051 00052 typedef struct VERTEX{ 00053 int enodenum; /* the node number in the contracted graph */ 00054 int orignodenum;/* the node number in the original graph */ 00055 struct ELIST *first; /* points to the first edge in the adjacency list */ 00056 struct ELIST *last; /* points to the last edge in the adjacency list */ 00057 int comp; /* contains the component number if the graph is 00058 disconnected */ 00059 char scanned; 00060 int demand; /* contains the demand for this node */ 00061 int degree; /* contains the degree of the node in the graph */ 00062 int orig_node_list_size; 00063 int *orig_node_list; /* contains a list of the nodes that have been 00064 contracted into this node to make a 00065 "super node" */ 00066 int dfnumber; 00067 int low; 00068 char is_art_point; 00069 char deleted; 00070 }vertex; 00071 00072 typedef struct NETWORK{ 00073 int vertnum; /* the number of vertices in the graph */ 00074 char is_integral; /* indicates whether the graph is integral or 00075 not */ 00076 int edgenum; /* the number of edges in the graph */ 00077 float mincut; /* the value of the current mincut */ 00078 struct ELIST *adjlist; /* the array containing the adajacency lists for 00079 each node */ 00080 struct EDGE *edges; /* the list of edges in the graph */ 00081 struct VERTEX *verts; /* the list of vertices */ 00082 int *compnodes; /* number of nodes in each component */ 00083 double *new_demand; /* the amounts of demand for each node that gets 00084 added to it when the network is contracted */ 00085 }network; 00086 00087 network *createnet PROTO((int *xind, double *xval, int edgenum, double etol, 00088 int *edges, int *demands, int vertnum)); 00089 int connected PROTO((network *n, int *compnodes, int *compdemands, 00090 int *compmembers, double *compcuts, double *compdensity)); 00091 void free_net PROTO((network *n)); 00092 00093 #endif
1.4.7