TSP_Concorde.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef TSP_CONCORDE_INCLUDED
00014 #define TSP_CONCORDE_INCLUDED
00015
00016
00017
00018
00019
00020
00021 extern "C"{
00022 #include "TSP_ConcordeI.h"
00023 }
00024
00025
00026 #include <vector>
00027 using namespace std;
00028
00029
00030 #include "UtilMacros.h"
00031
00032
00033 class ConcordeSubtourCut {
00034 public:
00035 vector<int> S;
00036 vector<bool> inS;
00037 public:
00038 void print(){
00039 cout << "ConcordeSubtour: ";
00040 for(int i = 0; i < static_cast<int>(inS.size()); i++){
00041 if(inS[i]){
00042 cout << i << " ";
00043 }
00044 }
00045 cout << endl;
00046 }
00047 ConcordeSubtourCut(const int nVerts) :
00048 S(),
00049 inS(nVerts, false) {}
00050
00051 ~ConcordeSubtourCut() {}
00052 };
00053
00054
00055 class TSP_Concorde {
00056 public:
00057
00058 int m_nVerts;
00059 vector<int> m_edgeList;
00060 vector<double> m_edgeValue;
00061
00062 public:
00064 void clearSubGraph(){
00065 m_nVerts = 0;
00066 m_edgeList.clear();
00067 m_edgeValue.clear();
00068 }
00069
00070 void buildSubGraph(const int nVerts,
00071 const int nEdges,
00072 const double * edgeWeight,
00073 const double tol = 1.0e-6){
00074
00075 int i;
00076 clearSubGraph();
00077 m_nVerts = nVerts;
00078 m_edgeList.reserve(2*nEdges);
00079 m_edgeValue.reserve(nEdges);
00080 for(i = 0; i < nEdges; i++){
00081 if(edgeWeight[i] <= tol)
00082 continue;
00083 pair<int,int> uv = UtilBothEndsU(i);
00084 m_edgeValue.push_back(edgeWeight[i]);
00085 m_edgeList.push_back(uv.first);
00086 m_edgeList.push_back(uv.second);
00087 }
00088 }
00089
00090 int generateCutsSubtour(vector<ConcordeSubtourCut> & subtourCuts){
00091 CCtsp_lpcut_in * tsp_cuts = NULL;
00092 CCtsp_lpcut_in * tsp_cut = NULL;
00093 CCtsp_lpcut_in * tsp_cut_next = NULL;
00094
00095 int i, c, tmp;
00096 int n_subtour = 0;
00097 int n_edgeList = static_cast<int>(m_edgeValue.size());
00098 int retCode = CCtsp_exact_subtours(&tsp_cuts,
00099 &n_subtour,
00100 m_nVerts,
00101 n_edgeList,
00102 &m_edgeList[0],
00103 &m_edgeValue[0]);
00104 assert(!retCode);
00105
00106
00107
00108 tsp_cut = tsp_cuts;
00109 for(c = 0; c < n_subtour; c++){
00110 ConcordeSubtourCut subtourCut(m_nVerts);
00111 assert(tsp_cut);
00112 CC_FOREACH_NODE_IN_CLIQUE(i, tsp_cut->cliques[0], tmp){
00113 subtourCut.S.push_back(i);
00114 subtourCut.inS[i] = true;
00115 }
00116
00117 subtourCuts.push_back(subtourCut);
00118 tsp_cut = tsp_cut->next;
00119 }
00120
00121 for (tsp_cut = tsp_cuts; tsp_cut; tsp_cut = tsp_cut_next){
00122 tsp_cut_next = tsp_cut->next;
00123 CCtsp_free_lpcut_in(tsp_cut);
00124 free(tsp_cut);
00125 }
00126 tsp_cuts = NULL;
00127 return static_cast<int>(subtourCuts.size());
00128 }
00129
00130 public:
00131 TSP_Concorde() :
00132 m_nVerts (0),
00133 m_edgeList (),
00134 m_edgeValue()
00135 {}
00136 ~TSP_Concorde()
00137 {}
00138 };
00139
00140 #endif