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 /* Capacitated Network Routing Problems. */ 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 /* CNRP include files */ 23 #include "cnrp_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 #ifdef DIRECTED_X_VARS 41 double weight1; 42 double weight2; 43 #endif 44 char scanned; 45 char tree_edge; 46 char deleted; 47 /*For minimum cut*/ 48 double q; 49 #ifdef ADD_FLOW_VARS 50 double flow1; 51 double flow2; 52 #endif 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 }elist; 61 62 typedef struct VERTEX{ 63 int enodenum; /* the node number in the contracted graph */ 64 int orignodenum;/* the node number in the original graph */ 65 struct ELIST *first; /* points to the first edge in the adjacency list */ 66 struct ELIST *last; /* points to the last edge in the adjacency list */ 67 int comp; /* contains the component number if the graph is 68 disconnected */ 69 char scanned; 70 double demand; /* contains the demand for this node */ 71 int degree; /* contains the degree of the node in the graph */ 72 int orig_node_list_size; 73 int *orig_node_list; /* contains a list of the nodes that have been 74 contracted into this node to make a 75 "super node" */ 76 int dfnumber; 77 int low; 78 char is_art_point; 79 char deleted; 80 double weight; /*For contracting the graph*/ 81 /*For minimum cut*/ 82 char orig_node_list2_size; 83 char *orig_node_list2; /* contains a list of the nodes that have been 84 contracted into this node to make a 85 "super node" */ 86 double r; 87 }vertex; 88 89 typedef struct NETWORK{ 90 int vertnum; /* the number of vertices in the graph */ 91 char is_integral; /* indicates whether the graph is integral or 92 not */ 93 int edgenum; /* the number of edges in the graph */ 94 float mincut; /* the value of the current mincut */ 95 struct ELIST *adjlist; /* the array containing the adajacency lists for 96 each node */ 97 struct EDGE *edges; /* the list of edges in the graph */ 98 struct VERTEX *verts; /* the list of vertices */ 99 int *compnodes; /* number of nodes in each component */ 100 double *new_demand; /* the amounts of demand for each node that gets 101 added to it when the network is contracted */ 102 103 /*For minimum cut algorithm*/ 104 struct VERTEX **tnodes; /*a binary tree of the existing vertices used by the 105 min_cut routine*/ 106 struct VERTEX **enodes; /*a list of the nodes that still exist*/ 107 }network; 108 109 network *create_net PROTO((int *xind, double *xval, int edgenum, double etol, 110 int *edges, double *demands, int vertnum)); 111 network *create_flow_net PROTO((int *xind, double *xval, int edgenum, 112 double etol, int *edges, double *demands, 113 int vertnum)); 114 int connected PROTO((network *n, int *compnodes, double *compdemands, 115 int *compmembers, double *compcuts, double *compdensity)); 116 int flow_connected PROTO((network *n, int *compnodes, double *compdemands, 117 int *compmembers, double *compcuts, 118 double *compdensity, double etol)); 119 void free_net PROTO((network *n)); 120 121 #endif 122