VRP_Boost.h

Go to the documentation of this file.
00001 //===========================================================================//
00002 // This file is part of the Decomp Solver Framework.                         //
00003 //                                                                           //
00004 // Decomp is distributed under the Common Public License as part of the      //
00005 // COIN-OR repository (http://www.coin-or.org).                              //
00006 //                                                                           //
00007 // Author: Matthew Galati, Lehigh University                                 //
00008 //                                                                           //
00009 // Copyright (C) 2002-2007, Lehigh University, Matthew Galati, and Ted Ralphs//
00010 // All Rights Reserved.                                                      //
00011 //===========================================================================//
00012 
00013 #ifndef VRP_BOOST_INCLUDED
00014 #define VRP_BOOST_INCLUDED
00015 
00016 //---
00017 //--- Interface class to Boost/Graph (an open source graph library).
00018 //---
00019 
00020 //THINK design:
00021 //design wise there should be a class that just wraps boost algos
00022 //then one that carries boost data specific to your application
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 //--- utility classes for writing to graphviz format (edges)
00041 //---   TODO: convert double to closest fraction?
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 //--- utility classes for writing to graphviz format (vertices)
00066 //---   TODO: convert double to closest fraction?
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;          //for storage of support graph
00093    Graph  m_sg0;         //for storage of support graph minus depot
00094    double m_depotDegree; //degree at depot (since we can have single-customers)
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       //--- build the boost subgraph as the support graph for x=val
00112       //---  at the same time, calculate the depot degree since we can 
00113       //---  have single-customer routes with x=2.0
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    void buildCompleteGraphMinusVert(const int vert,
00140                     const int nVerts){
00141       
00142       property_map<Graph, edge_index_t>::type  e_index  
00143      = get(edge_index,  m_cgV);
00144       graph_traits<Graph>::edge_descriptor ed; bool inserted;            
00145       int u, v;
00146       int index = 0;
00147       for(u = 1; u < nVerts; u++){
00148      for(v = 0; v < u; v++){
00149         if(u != vert && v != vert){
00150            tie(ed, inserted) = add_edge(u, v, m_cgV);
00151            e_index[ed]    = index;
00152         }
00153         index++;    
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       //property_map<Graph, edge_weight_t>::type e_weight
00183       //   = get(edge_weight, g);
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

Generated on 12 Feb 2015 for Dip-All by  doxygen 1.6.1