- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

VrpNetwork.h
Go to the documentation of this file.
1 /*===========================================================================*
2 * This file is part of a solver for the Vehicle Routing Problem *
3 * developed using the BiCePS Linear Integer Solver (BLIS). *
4 * *
5 * This solver is distributed under the Eclipse Public License as part of *
6 * the COIN-OR repository (http://www.coin-or.org). *
7 * *
8 * Authors: Yan Xu, Lehigh University *
9 * Ted Ralphs, Lehigh University *
10 * *
11 * Copyright (C) 2007 Yan Xu and Ted Ralphs. *
12 * All Rights Reserved. *
13 *===========================================================================*/
14
15 #ifndef VrpNetwork_h_
16 #define VrpNetwork_h_
17
18 #include <vector>
19
20 #include "CoinPackedVector.hpp"
21 #include "VrpConstants.h"
22 #include "VrpVariable.h"
23
24 //#############################################################################
25
26 #define OTHER_END(cur_edge, v) \
27 (cur_edge->data->v0 == v) ? cur_edge->data->v1 : cur_edge->data->v0
28
29 #ifndef MIN
30 #define MIN(x, y) (x < y ? x : y)
31 #endif
32
33 #ifndef MAX
34 #define MAX(x, y) (x > y ? x : y)
35 #endif
36
37 /*-----------------------------------------------------------------------*\
38 | These are data tructures used in constructing the solution graph used |
39 | by the cut generator to locate cuts. The graph is stored using |
40 | adjacency lists |
41 \*-----------------------------------------------------------------------*/
42
43 typedef struct EDGE{
44 int v0;
45 int v1;
46 int cost;
47 double weight;
48 bool scanned;
49 bool tree_edge;
50 bool deleted;
51 }edge;
52
53 typedef struct ELIST{
54 struct ELIST *next_edge; /* next edge in the edgelist */
55 struct EDGE *data; /* the data of the edge */
56 int other_end; /* the other end of the edge */
57 struct VERTEX *other;
58 }elist;
59
60 typedef struct VERTEX{
61 int enodenum; /* the node number in the contracted graph */
62 int orignodenum;/* the node number in the original graph */
63 struct ELIST *first; /* points to the first edge in the adjacency list */
64 struct ELIST *last; /* points to the last edge in the adjacency list */
65 int comp; /* contains the component number if the graph is
66 disconnected */
67 bool scanned;
68 int demand; /* contains the demand for this node */
69 int degree; /* contains the degree of the node in the graph */
70 int orig_node_list_size;
71 int *orig_node_list; /* contains a list of the nodes that have been
72 contracted into this node to make a
73 "super node" */
74 int dfnumber;
75 int low;
76 bool is_art_point;
77 bool deleted;
78 }vertex;
79
80 class VrpNetwork{
81
82 friend class VrpModel;
83 friend class VrpCutGenerator;
84 friend class VrpSolution;
85
86 private:
87
88 int edgenum_; /* the number of edges in the graph */
89 int maxEdgenum_; /* the number of edges allocated */
90 int vertnum_; /* the number of vertices in the graph */
91 bool isIntegral_; /* indicates whether the graph is integral or
92 not */
93 int numComps_; /* number of components */
94 struct EDGE *edges_; /* the list of edges in the graph */
95 struct VERTEX *verts_; /* the list of vertices */
96 double mincut_; /* the value of the current mincut */
97 struct ELIST *adjList_; /* the array containing the adajacency lists
98 for each node */
99 int *compNodes_; /* number of nodes in each component */
100 int *compDemands_; /* demand in each component */
101 double *compCuts_; /* weight of cprresponding cut */
102 int *compMembers_; /* which component each vertex belongs to */
103 int *newDemand_; /* the amounts of demand for each node to add
104 when the network is contracted */
105
106 public:
107
108 VrpNetwork() : edgenum_(0), vertnum_(0), isIntegral_(false), mincut_(0){
109 adjList_ = 0;
110 edges_ = 0;
111 verts_ = 0;
112 compNodes_ = 0;
113 compDemands_ = 0;
114 compCuts_ = 0;
115 compMembers_ = 0;
116 newDemand_ = 0;
117 }
118
119 VrpNetwork(int edgenum, int vertnum);
120
121 virtual ~VrpNetwork() {
122 gutsOfDestructor();
123 }
124
125 void createNet(CoinPackedVector *sol, int *demand,
126 std::vector<VrpVariable *> edgeList, double etol,
127 int vertnum);
128
129 void computeCompNums(vertex *v, int parent_comp, int *num_comps,
130 bool parent_is_art_point);
131
132 void depthFirstSearch(vertex *v, int *count1, int *count2);
133
134 int connected();
135
136 int biconnected();
137
138 void reduce_graph(double etol);
139
140 void gutsOfDestructor();
141
142 };
143
144 #endif
ELIST::other_end
int other_end
Definition: VrpNetwork.h:56
VrpNetwork::numComps_
int numComps_
Definition: VrpNetwork.h:93
VrpNetwork::newDemand_
int * newDemand_
Definition: VrpNetwork.h:103
VrpNetwork::edgenum_
int edgenum_
Definition: VrpNetwork.h:88
VrpNetwork::reduce_graph
void reduce_graph(double etol)
VERTEX::enodenum
int enodenum
Definition: VrpNetwork.h:61
VrpNetwork::biconnected
int biconnected()
VrpModel
Model class for VRP.
Definition: VrpModel.h:32
VrpNetwork::createNet
void createNet(CoinPackedVector *sol, int *demand, std::vector< VrpVariable * > edgeList, double etol, int vertnum)
vertex
struct VERTEX vertex
edge
struct EDGE edge
VERTEX
Definition: VrpNetwork.h:60
VERTEX::demand
int demand
Definition: VrpNetwork.h:68
VERTEX::last
struct ELIST * last
Definition: VrpNetwork.h:64
CoinPackedVector.hpp
elist
struct ELIST elist
VrpNetwork::compNodes_
int * compNodes_
Definition: VrpNetwork.h:99
VrpNetwork::mincut_
double mincut_
Definition: VrpNetwork.h:96
VrpNetwork::isIntegral_
bool isIntegral_
Definition: VrpNetwork.h:91
ELIST
Definition: VrpNetwork.h:53
VrpVariable.h
VrpNetwork::VrpNetwork
VrpNetwork()
Definition: VrpNetwork.h:108
VERTEX::is_art_point
bool is_art_point
Definition: VrpNetwork.h:76
VERTEX::first
struct ELIST * first
Definition: VrpNetwork.h:63
VrpNetwork::gutsOfDestructor
void gutsOfDestructor()
VERTEX::deleted
bool deleted
Definition: VrpNetwork.h:77
VrpNetwork
Definition: VrpNetwork.h:80
VrpNetwork::connected
int connected()
VrpNetwork::depthFirstSearch
void depthFirstSearch(vertex *v, int *count1, int *count2)
VERTEX::orig_node_list
int * orig_node_list
Definition: VrpNetwork.h:71
VrpNetwork::maxEdgenum_
int maxEdgenum_
Definition: VrpNetwork.h:89
VrpNetwork::compMembers_
int * compMembers_
Definition: VrpNetwork.h:102
ELIST::other
struct VERTEX * other
Definition: VrpNetwork.h:57
EDGE
Definition: VrpNetwork.h:43
EDGE::deleted
bool deleted
Definition: VrpNetwork.h:50
VrpNetwork::vertnum_
int vertnum_
Definition: VrpNetwork.h:90
VERTEX::degree
int degree
Definition: VrpNetwork.h:69
VrpNetwork::~VrpNetwork
virtual ~VrpNetwork()
Definition: VrpNetwork.h:121
EDGE::tree_edge
bool tree_edge
Definition: VrpNetwork.h:49
VERTEX::orig_node_list_size
int orig_node_list_size
Definition: VrpNetwork.h:70
ELIST::data
struct EDGE * data
Definition: VrpNetwork.h:55
VrpNetwork::adjList_
struct ELIST * adjList_
Definition: VrpNetwork.h:97
VrpNetwork::edges_
struct EDGE * edges_
Definition: VrpNetwork.h:94
ELIST::next_edge
struct ELIST * next_edge
Definition: VrpNetwork.h:54
VrpSolution
This class contains a vrp solution.
Definition: VrpSolution.h:26
VERTEX::comp
int comp
Definition: VrpNetwork.h:65
EDGE::v0
int v0
Definition: VrpNetwork.h:44
CoinPackedVector
Sparse Vector.
Definition: CoinPackedVector.hpp:123
EDGE::cost
int cost
Definition: VrpNetwork.h:46
EDGE::weight
double weight
Definition: VrpNetwork.h:47
VrpCutGenerator
Definition: VrpCutGenerator.h:34
VERTEX::orignodenum
int orignodenum
Definition: VrpNetwork.h:62
VrpNetwork::computeCompNums
void computeCompNums(vertex *v, int parent_comp, int *num_comps, bool parent_is_art_point)
VrpNetwork::verts_
struct VERTEX * verts_
Definition: VrpNetwork.h:95
EDGE::v1
int v1
Definition: VrpNetwork.h:45
VrpNetwork::compDemands_
int * compDemands_
Definition: VrpNetwork.h:100
VERTEX::scanned
bool scanned
Definition: VrpNetwork.h:67
VrpNetwork::compCuts_
double * compCuts_
Definition: VrpNetwork.h:101
EDGE::scanned
bool scanned
Definition: VrpNetwork.h:48
VERTEX::low
int low
Definition: VrpNetwork.h:75
VERTEX::dfnumber
int dfnumber
Definition: VrpNetwork.h:74
VrpConstants.h