Dip-All  0.91.0
VRP_Boost.h
Go to the documentation of this file.
1 //===========================================================================//
2 // This file is part of the Decomp Solver Framework. //
3 // //
4 // Decomp is distributed under the Common Public License as part of the //
5 // COIN-OR repository (http://www.coin-or.org). //
6 // //
7 // Author: Matthew Galati, Lehigh University //
8 // //
9 // Copyright (C) 2002-2015, Lehigh University, Matthew Galati, and Ted Ralphs//
10 // All Rights Reserved. //
11 //===========================================================================//
12 
13 #ifndef VRP_BOOST_INCLUDED
14 #define VRP_BOOST_INCLUDED
15 
16 //---
17 //--- Interface class to Boost/Graph (an open source graph library).
18 //---
19 
20 //THINK design:
21 //design wise there should be a class that just wraps boost algos
22 //then one that carries boost data specific to your application
23 
24 // --------------------------------------------------------------------- //
25 #include <boost/graph/graphviz.hpp>
26 #include <boost/graph/graph_utility.hpp>
27 #include <boost/graph/adjacency_list.hpp>
28 #include <boost/graph/connected_components.hpp>
29 #include <boost/graph/kruskal_min_spanning_tree.hpp>
30 using namespace boost;
31 using namespace std;
32 
33 typedef property<edge_weight_t, double,
34  property<edge_index_t, int> > edge_prop;
35 typedef adjacency_list<vecS, vecS, undirectedS,
36  no_property, edge_prop> Graph;
37 
38 // --------------------------------------------------------------------- //
39 //---
40 //--- utility classes for writing to graphviz format (edges)
41 //--- TODO: convert double to closest fraction?
42 //---
43 template < class EdgeWeight >
45 public:
46  sg_label_writer(EdgeWeight e_) : weight(e_) {}
47  template <class VertexOrEdge>
48  void operator()(ostream & out, const VertexOrEdge & e) const {
49  if(weight[e] >= 0.9999999)
50  out << "[style=solid]";
51  else
52  out << "[label=\"" << weight[e] << "\", stype=dashed]";
53  }
54 private:
55  EdgeWeight weight;
56 };
57 template <class EdgeWeight >
60 }
61 
62 
63 // --------------------------------------------------------------------- //
64 //---
65 //--- utility classes for writing to graphviz format (vertices)
66 //--- TODO: convert double to closest fraction?
67 //---
69 public:
70  sg_label_writer_vertex(const int * vertex_wt)
71  : demand(vertex_wt) {}
72  template <class VertexOrEdge>
73  void operator()(ostream & out, const VertexOrEdge & v) const {
74  if(v == 0)
75  out << " [style=filled, fillcolor=black]";
76  else{
77  out << " [label=\"" << v << " : "
78  << demand[v] << "\" width=\"0.5\" height=\"0.5\"]";
79  }
80  }
81 private:
82  const int * demand;
83 };
85 sg_make_label_writer_vertex(const int * vertex_wt) {
86  return sg_label_writer_vertex(vertex_wt);
87 }
88 
89 // --------------------------------------------------------------------- //
90 class VRP_Boost {
91 public:
92  Graph m_sg; //for storage of support graph
93  Graph m_sg0; //for storage of support graph minus depot
94  double m_depotDegree; //degree at depot (since we can have single-customers)
95 
96 public:
98  m_sg (),
99  m_sg0 (),
100  m_depotDegree(0.0)
101  {}
103 
104 public:
106  void buildSubGraph(const int len,
107  const double * val,
108  const double tol = 1.0e-6){
109 
110  //---
111  //--- build the boost subgraph as the support graph for x=val
112  //--- at the same time, calculate the depot degree since we can
113  //--- have single-customer routes with x=2.0
114  //---
115  property_map<Graph, edge_weight_t>::type e_weight
116  = get(edge_weight, m_sg);
117  property_map<Graph, edge_index_t>::type e_index
118  = get(edge_index, m_sg);
119  graph_traits<Graph>::edge_descriptor ed; bool inserted;
120 
121  int c;
122  m_depotDegree = 0.0;
123  for (c = 0; c < len; ++c) {
124  if(val[c] <= tol)
125  continue;
126  pair<int,int> uv = UtilBothEndsU(c);
127 
128  if(uv.first == 0 || uv.second == 0){
129  m_depotDegree += val[c];
130  }
131 
132  tie(ed, inserted) = add_edge(uv.first, uv.second, m_sg);
133  e_weight[ed] = val[c];
134  e_index[ed] = c;
135  }
136  }
137 
138  /*
139  void buildCompleteGraphMinusVert(const int vert,
140  const int nVerts){
141 
142  property_map<Graph, edge_index_t>::type e_index
143  = get(edge_index, m_cgV);
144  graph_traits<Graph>::edge_descriptor ed; bool inserted;
145  int u, v;
146  int index = 0;
147  for(u = 1; u < nVerts; u++){
148  for(v = 0; v < u; v++){
149  if(u != vert && v != vert){
150  tie(ed, inserted) = add_edge(u, v, m_cgV);
151  e_index[ed] = index;
152  }
153  index++;
154  }
155  }
156  }
157  */
158 
159  inline void printGraph(const Graph & g) const {
160  print_graph(g);
161  }
162 
163  inline void printDotFile(const string & fileName,
164  const int * vertexWt,
165  const Graph & g) const {
166 
167  ofstream os;
168  UtilOpenFile(os, fileName);
169 
170  printf("PrintDotFile fileName = %s\n", fileName.c_str());
171 
172  map<string, string> graph_attr, vertex_attr, edge_attr;
173  graph_attr ["fontsize"] = "20";
174 
175  vertex_attr["fontsize"] = "20";
176  vertex_attr["shape"] = "circle";
177 
178  edge_attr ["style"] = "dotted";
179  edge_attr ["len"] = "1.7";
180  edge_attr ["fontsize"] = "20";
181 
182  //property_map<Graph, edge_weight_t>::type e_weight
183  // = get(edge_weight, g);
184 
185  write_graphviz(os, g,
186  sg_make_label_writer_vertex(vertexWt),
187  sg_make_label_writer(get(edge_weight, g)),
188  make_graph_attributes_writer(graph_attr,
189  vertex_attr,
190  edge_attr));
191  os.close();
192  }
193 
194  inline void copyGraph(const Graph & gFrom,
195  Graph & gTo){
196  gTo = gFrom;
197  }
198 
199  inline void clearSubGraph(){
200  m_sg.clear();
201  }
202 
203  inline void clearSubGraph(Graph & g){
204  g.clear();
205  }
206 
207  inline void clearVertex(const int vertex,
208  Graph & g){
209  clear_vertex(0, g);
210  }
211 
212  inline int findConnectedComponents(vector<int> & component){
213  return connected_components(m_sg, &component[0]);
214  }
215 
217  vector<int> & component){
218  return connected_components(g, &component[0]);
219  }
220 
221  inline int getDegree(const int nodeIndex){
222  return degree(nodeIndex, m_sg);
223  }
224 
225  inline double getDepotDegree(){
226  return m_depotDegree;
227  }
228 
229 };
230 
231 #endif
void printGraph(const Graph &g) const
Definition: VRP_Boost.h:159
sg_label_writer< EdgeWeight > sg_make_label_writer(EdgeWeight e)
Definition: VRP_Boost.h:58
void clearSubGraph()
Definition: VRP_Boost.h:199
adjacency_list< vecS, vecS, undirectedS, no_property, edge_prop > Graph
Definition: TSP_Boost.h:34
const int * demand
Definition: VRP_Boost.h:82
void buildSubGraph(const int len, const double *val, const double tol=1.0e-6)
Definition: VRP_Boost.h:106
pair< int, int > UtilBothEndsU(const int index)
EdgeWeight weight
Definition: VRP_Boost.h:55
void printDotFile(const string &fileName, const int *vertexWt, const Graph &g) const
Definition: VRP_Boost.h:163
VRP_Boost()
Definition: VRP_Boost.h:97
int findConnectedComponents(vector< int > &component)
Definition: VRP_Boost.h:212
void copyGraph(const Graph &gFrom, Graph &gTo)
Definition: VRP_Boost.h:194
void operator()(ostream &out, const VertexOrEdge &e) const
Definition: VRP_Boost.h:48
void UtilOpenFile(ifstream &fs, const char *fileName)
Definition: UtilMacros.h:526
sg_label_writer_vertex sg_make_label_writer_vertex(const int *vertex_wt)
Definition: VRP_Boost.h:85
double getDepotDegree()
Definition: VRP_Boost.h:225
Graph m_sg
Definition: VRP_Boost.h:92
sg_label_writer_vertex(const int *vertex_wt)
Definition: VRP_Boost.h:70
property< edge_weight_t, double, property< edge_index_t, int > > edge_prop
Definition: TSP_Boost.h:32
int findConnectedComponents(Graph &g, vector< int > &component)
Definition: VRP_Boost.h:216
double m_depotDegree
Definition: VRP_Boost.h:94
~VRP_Boost()
Definition: VRP_Boost.h:102
void clearSubGraph(Graph &g)
Definition: VRP_Boost.h:203
void clearVertex(const int vertex, Graph &g)
Definition: VRP_Boost.h:207
Graph m_sg0
Definition: VRP_Boost.h:93
sg_label_writer(EdgeWeight e_)
Definition: VRP_Boost.h:46
void operator()(ostream &out, const VertexOrEdge &v) const
Definition: VRP_Boost.h:73
int getDegree(const int nodeIndex)
Definition: VRP_Boost.h:221