VRP_Boost.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef VRP_BOOST_INCLUDED
00014 #define VRP_BOOST_INCLUDED
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include <boost/graph/graphviz.hpp>
00026 #include <boost/graph/graph_utility.hpp>
00027 #include <boost/graph/adjacency_list.hpp>
00028 #include <boost/graph/connected_components.hpp>
00029 #include <boost/graph/kruskal_min_spanning_tree.hpp>
00030 using namespace boost;
00031 using namespace std;
00032
00033 typedef property<edge_weight_t, double,
00034 property<edge_index_t, int> > edge_prop;
00035 typedef adjacency_list<vecS, vecS, undirectedS,
00036 no_property, edge_prop> Graph;
00037
00038
00039
00040
00041
00042
00043 template < class EdgeWeight >
00044 class sg_label_writer {
00045 public:
00046 sg_label_writer(EdgeWeight e_) : weight(e_) {}
00047 template <class VertexOrEdge>
00048 void operator()(ostream & out, const VertexOrEdge & e) const {
00049 if(weight[e] >= 0.9999999)
00050 out << "[style=solid]";
00051 else
00052 out << "[label=\"" << weight[e] << "\", stype=dashed]";
00053 }
00054 private:
00055 EdgeWeight weight;
00056 };
00057 template <class EdgeWeight >
00058 inline sg_label_writer<EdgeWeight> sg_make_label_writer(EdgeWeight e) {
00059 return sg_label_writer<EdgeWeight>(e);
00060 }
00061
00062
00063
00064
00065
00066
00067
00068 class sg_label_writer_vertex {
00069 public:
00070 sg_label_writer_vertex(const int * vertex_wt)
00071 : demand(vertex_wt) {}
00072 template <class VertexOrEdge>
00073 void operator()(ostream & out, const VertexOrEdge & v) const {
00074 if(v == 0)
00075 out << " [style=filled, fillcolor=black]";
00076 else{
00077 out << " [label=\"" << v << " : "
00078 << demand[v] << "\" width=\"0.5\" height=\"0.5\"]";
00079 }
00080 }
00081 private:
00082 const int * demand;
00083 };
00084 inline sg_label_writer_vertex
00085 sg_make_label_writer_vertex(const int * vertex_wt) {
00086 return sg_label_writer_vertex(vertex_wt);
00087 }
00088
00089
00090 class VRP_Boost {
00091 public:
00092 Graph m_sg;
00093 Graph m_sg0;
00094 double m_depotDegree;
00095
00096 public:
00097 VRP_Boost() :
00098 m_sg (),
00099 m_sg0 (),
00100 m_depotDegree(0.0)
00101 {}
00102 ~VRP_Boost() {}
00103
00104 public:
00106 void buildSubGraph(const int len,
00107 const double * val,
00108 const double tol = 1.0e-6){
00109
00110
00111
00112
00113
00114
00115 property_map<Graph, edge_weight_t>::type e_weight
00116 = get(edge_weight, m_sg);
00117 property_map<Graph, edge_index_t>::type e_index
00118 = get(edge_index, m_sg);
00119 graph_traits<Graph>::edge_descriptor ed; bool inserted;
00120
00121 int c;
00122 m_depotDegree = 0.0;
00123 for (c = 0; c < len; ++c) {
00124 if(val[c] <= tol)
00125 continue;
00126 pair<int,int> uv = UtilBothEndsU(c);
00127
00128 if(uv.first == 0 || uv.second == 0){
00129 m_depotDegree += val[c];
00130 }
00131
00132 tie(ed, inserted) = add_edge(uv.first, uv.second, m_sg);
00133 e_weight[ed] = val[c];
00134 e_index[ed] = c;
00135 }
00136 }
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159 inline void printGraph(const Graph & g) const {
00160 print_graph(g);
00161 }
00162
00163 inline void printDotFile(const string & fileName,
00164 const int * vertexWt,
00165 const Graph & g) const {
00166
00167 ofstream os;
00168 UtilOpenFile(os, fileName);
00169
00170 printf("PrintDotFile fileName = %s\n", fileName.c_str());
00171
00172 map<string, string> graph_attr, vertex_attr, edge_attr;
00173 graph_attr ["fontsize"] = "20";
00174
00175 vertex_attr["fontsize"] = "20";
00176 vertex_attr["shape"] = "circle";
00177
00178 edge_attr ["style"] = "dotted";
00179 edge_attr ["len"] = "1.7";
00180 edge_attr ["fontsize"] = "20";
00181
00182
00183
00184
00185 write_graphviz(os, g,
00186 sg_make_label_writer_vertex(vertexWt),
00187 sg_make_label_writer(get(edge_weight, g)),
00188 make_graph_attributes_writer(graph_attr,
00189 vertex_attr,
00190 edge_attr));
00191 os.close();
00192 }
00193
00194 inline void copyGraph(const Graph & gFrom,
00195 Graph & gTo){
00196 gTo = gFrom;
00197 }
00198
00199 inline void clearSubGraph(){
00200 m_sg.clear();
00201 }
00202
00203 inline void clearSubGraph(Graph & g){
00204 g.clear();
00205 }
00206
00207 inline void clearVertex(const int vertex,
00208 Graph & g){
00209 clear_vertex(0, g);
00210 }
00211
00212 inline int findConnectedComponents(vector<int> & component){
00213 return connected_components(m_sg, &component[0]);
00214 }
00215
00216 inline int findConnectedComponents(Graph & g,
00217 vector<int> & component){
00218 return connected_components(g, &component[0]);
00219 }
00220
00221 inline int getDegree(const int nodeIndex){
00222 return degree(nodeIndex, m_sg);
00223 }
00224
00225 inline double getDepotDegree(){
00226 return m_depotDegree;
00227 }
00228
00229 };
00230
00231 #endif