TSP_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-2015, Lehigh University, Matthew Galati, and Ted Ralphs//
00010 // All Rights Reserved.                                                      //
00011 //===========================================================================//
00012 
00013 #ifndef TSP_BOOST_INCLUDED
00014 #define TSP_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/adjacency_list.hpp>
00026 #include <boost/graph/graph_utility.hpp>
00027 #include <boost/graph/connected_components.hpp>
00028 #include <boost/graph/kruskal_min_spanning_tree.hpp>
00029 using namespace boost;
00030 
00031 typedef property<edge_weight_t, double,
00032                  property<edge_index_t, int> > edge_prop;
00033 typedef adjacency_list<vecS, vecS, undirectedS,
00034                        no_property, edge_prop> Graph;
00035 
00036 // --------------------------------------------------------------------- //
00037 class TSP_Boost {
00038 public:
00039    Graph m_sg;
00040    Graph m_cgV;
00041 
00042 public:
00043    TSP_Boost() :
00044       m_sg (),
00045       m_cgV()  {}
00046    ~TSP_Boost() {}
00047    
00048 public:
00050    void buildSubGraph(const int      len,
00051                       const double * val,
00052                       const double   tol = 1.0e-6){      
00053 
00054       property_map<Graph, edge_weight_t>::type e_weight 
00055      = get(edge_weight, m_sg);
00056       property_map<Graph, edge_index_t>::type  e_index  
00057      = get(edge_index,  m_sg);
00058       graph_traits<Graph>::edge_descriptor ed; bool inserted;      
00059       for (int c = 0; c < len; ++c) {
00060      if(val[c] <= tol)
00061         continue;
00062      pair<int,int> uv  = UtilBothEndsU(c);
00063      tie(ed, inserted) = add_edge(uv.first, uv.second, m_sg);
00064      e_weight[ed]      = val[c];
00065      e_index[ed]       = c;
00066       }      
00067    }
00068 
00069    void buildCompleteGraphMinusVert(const int vert,
00070                     const int nVerts){
00071       
00072       property_map<Graph, edge_index_t>::type  e_index  
00073      = get(edge_index,  m_cgV);
00074       graph_traits<Graph>::edge_descriptor ed; bool inserted;            
00075       int u, v;
00076       int index = 0;
00077       for(u = 1; u < nVerts; u++){
00078      for(v = 0; v < u; v++){
00079         if(u != vert && v != vert){
00080            tie(ed, inserted) = add_edge(u, v, m_cgV);
00081            e_index[ed]       = index;
00082         }
00083         index++;    
00084      }
00085       }
00086    }
00087 
00088    inline void clearSubGraph(){
00089       m_sg.clear();
00090    }
00091 
00092    inline int findConnectedComponents(vector<int> & component){
00093       return connected_components(m_sg, &component[0]);
00094    }
00095 
00096    inline int getDegree(const int nodeIndex){
00097       return static_cast<int>(degree(nodeIndex, m_sg));
00098    }
00099    
00100 };
00101 
00102 #endif

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