Dip-All  0.91.0
TSP_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 TSP_BOOST_INCLUDED
14 #define TSP_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/adjacency_list.hpp>
26 #include <boost/graph/graph_utility.hpp>
27 #include <boost/graph/connected_components.hpp>
28 #include <boost/graph/kruskal_min_spanning_tree.hpp>
29 using namespace boost;
30 
31 typedef property<edge_weight_t, double,
32  property<edge_index_t, int> > edge_prop;
33 typedef adjacency_list<vecS, vecS, undirectedS,
34  no_property, edge_prop> Graph;
35 
36 // --------------------------------------------------------------------- //
37 class TSP_Boost {
38 public:
41 
42 public:
44  m_sg (),
45  m_cgV() {}
47 
48 public:
50  void buildSubGraph(const int len,
51  const double * val,
52  const double tol = 1.0e-6){
53 
54  property_map<Graph, edge_weight_t>::type e_weight
55  = get(edge_weight, m_sg);
56  property_map<Graph, edge_index_t>::type e_index
57  = get(edge_index, m_sg);
58  graph_traits<Graph>::edge_descriptor ed; bool inserted;
59  for (int c = 0; c < len; ++c) {
60  if(val[c] <= tol)
61  continue;
62  pair<int,int> uv = UtilBothEndsU(c);
63  tie(ed, inserted) = add_edge(uv.first, uv.second, m_sg);
64  e_weight[ed] = val[c];
65  e_index[ed] = c;
66  }
67  }
68 
69  void buildCompleteGraphMinusVert(const int vert,
70  const int nVerts){
71 
72  property_map<Graph, edge_index_t>::type e_index
73  = get(edge_index, m_cgV);
74  graph_traits<Graph>::edge_descriptor ed; bool inserted;
75  int u, v;
76  int index = 0;
77  for(u = 1; u < nVerts; u++){
78  for(v = 0; v < u; v++){
79  if(u != vert && v != vert){
80  tie(ed, inserted) = add_edge(u, v, m_cgV);
81  e_index[ed] = index;
82  }
83  index++;
84  }
85  }
86  }
87 
88  inline void clearSubGraph(){
89  m_sg.clear();
90  }
91 
92  inline int findConnectedComponents(vector<int> & component){
93  return connected_components(m_sg, &component[0]);
94  }
95 
96  inline int getDegree(const int nodeIndex){
97  return static_cast<int>(degree(nodeIndex, m_sg));
98  }
99 
100 };
101 
102 #endif
Graph m_cgV
Definition: TSP_Boost.h:40
int getDegree(const int nodeIndex)
Definition: TSP_Boost.h:96
~TSP_Boost()
Definition: TSP_Boost.h:46
int findConnectedComponents(vector< int > &component)
Definition: TSP_Boost.h:92
Graph m_sg
Definition: TSP_Boost.h:39
adjacency_list< vecS, vecS, undirectedS, no_property, edge_prop > Graph
Definition: TSP_Boost.h:34
pair< int, int > UtilBothEndsU(const int index)
TSP_Boost()
Definition: TSP_Boost.h:43
void clearSubGraph()
Definition: TSP_Boost.h:88
void buildSubGraph(const int len, const double *val, const double tol=1.0e-6)
Definition: TSP_Boost.h:50
property< edge_weight_t, double, property< edge_index_t, int > > edge_prop
Definition: TSP_Boost.h:32
void buildCompleteGraphMinusVert(const int vert, const int nVerts)
Definition: TSP_Boost.h:69