00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #ifndef VrpNetwork_h_
00016 #define VrpNetwork_h_
00017
00018 #include <vector>
00019
00020 #include "CoinPackedVector.hpp"
00021 #include "VrpConstants.h"
00022 #include "VrpVariable.h"
00023
00024
00025
00026 #define OTHER_END(cur_edge, v) \
00027 (cur_edge->data->v0 == v) ? cur_edge->data->v1 : cur_edge->data->v0
00028
00029 #ifndef MIN
00030 #define MIN(x, y) (x < y ? x : y)
00031 #endif
00032
00033 #ifndef MAX
00034 #define MAX(x, y) (x > y ? x : y)
00035 #endif
00036
00037
00038
00039
00040
00041
00042
00043 typedef struct EDGE{
00044 int v0;
00045 int v1;
00046 int cost;
00047 double weight;
00048 bool scanned;
00049 bool tree_edge;
00050 bool deleted;
00051 }edge;
00052
00053 typedef struct ELIST{
00054 struct ELIST *next_edge;
00055 struct EDGE *data;
00056 int other_end;
00057 struct VERTEX *other;
00058 }elist;
00059
00060 typedef struct VERTEX{
00061 int enodenum;
00062 int orignodenum;
00063 struct ELIST *first;
00064 struct ELIST *last;
00065 int comp;
00066
00067 bool scanned;
00068 int demand;
00069 int degree;
00070 int orig_node_list_size;
00071 int *orig_node_list;
00072
00073
00074 int dfnumber;
00075 int low;
00076 bool is_art_point;
00077 bool deleted;
00078 }vertex;
00079
00080 class VrpNetwork{
00081
00082 friend class VrpModel;
00083 friend class VrpCutGenerator;
00084 friend class VrpSolution;
00085
00086 private:
00087
00088 int edgenum_;
00089 int maxEdgenum_;
00090 int vertnum_;
00091 bool isIntegral_;
00092
00093 int numComps_;
00094 struct EDGE *edges_;
00095 struct VERTEX *verts_;
00096 double mincut_;
00097 struct ELIST *adjList_;
00098
00099 int *compNodes_;
00100 int *compDemands_;
00101 double *compCuts_;
00102 int *compMembers_;
00103 int *newDemand_;
00104
00105
00106 public:
00107
00108 VrpNetwork() : edgenum_(0), vertnum_(0), isIntegral_(false), mincut_(0){
00109 adjList_ = 0;
00110 edges_ = 0;
00111 verts_ = 0;
00112 compNodes_ = 0;
00113 compDemands_ = 0;
00114 compCuts_ = 0;
00115 compMembers_ = 0;
00116 newDemand_ = 0;
00117 }
00118
00119 VrpNetwork(int edgenum, int vertnum);
00120
00121 virtual ~VrpNetwork() {
00122 gutsOfDestructor();
00123 }
00124
00125 void createNet(CoinPackedVector *sol, int *demand,
00126 std::vector<VrpVariable *> edgeList, double etol,
00127 int vertnum);
00128
00129 void computeCompNums(vertex *v, int parent_comp, int *num_comps,
00130 bool parent_is_art_point);
00131
00132 void depthFirstSearch(vertex *v, int *count1, int *count2);
00133
00134 int connected();
00135
00136 int biconnected();
00137
00138 void reduce_graph(double etol);
00139
00140 void gutsOfDestructor();
00141
00142 };
00143
00144 #endif