64 template <typename Container> |
64 template <typename Container> |
65 bool checkTour(const FullGraph &gr, const Container &p) { |
65 bool checkTour(const FullGraph &gr, const Container &p) { |
66 FullGraph::NodeMap<bool> used(gr, false); |
66 FullGraph::NodeMap<bool> used(gr, false); |
67 |
67 |
68 int node_cnt = 0; |
68 int node_cnt = 0; |
69 for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) { |
69 for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) |
70 FullGraph::Node node = *it; |
70 { |
71 if (used[node]) return false; |
71 FullGraph::Node node = *it; |
72 used[node] = true; |
72 if (used[node]) return false; |
73 ++node_cnt; |
73 used[node] = true; |
74 } |
74 ++node_cnt; |
|
75 } |
75 |
76 |
76 return (node_cnt == gr.nodeNum()); |
77 return (node_cnt == gr.nodeNum()); |
77 } |
78 } |
78 |
79 |
79 // Checks tour validity |
80 // Checks tour validity |
262 // metricCostTest(); |
263 // metricCostTest(); |
263 |
264 |
264 tspTestSmall<NearestNeighborTsp<ConstMap<Edge, int> > >("Nearest Neighbor"); |
265 tspTestSmall<NearestNeighborTsp<ConstMap<Edge, int> > >("Nearest Neighbor"); |
265 tspTestSmall<GreedyTsp<ConstMap<Edge, int> > >("Greedy"); |
266 tspTestSmall<GreedyTsp<ConstMap<Edge, int> > >("Greedy"); |
266 tspTestSmall<NearestInsertionTsp<ConstMap<Edge, int> > >("Nearest Insertion"); |
267 tspTestSmall<NearestInsertionTsp<ConstMap<Edge, int> > >("Nearest Insertion"); |
267 tspTestSmall<FarthestInsertionTsp<ConstMap<Edge, int> > >("Farthest Insertion"); |
268 tspTestSmall<FarthestInsertionTsp<ConstMap<Edge, int> > > |
268 tspTestSmall<CheapestInsertionTsp<ConstMap<Edge, int> > >("Cheapest Insertion"); |
269 ("Farthest Insertion"); |
|
270 tspTestSmall<CheapestInsertionTsp<ConstMap<Edge, int> > > |
|
271 ("Cheapest Insertion"); |
269 tspTestSmall<RandomInsertionTsp<ConstMap<Edge, int> > >("Random Insertion"); |
272 tspTestSmall<RandomInsertionTsp<ConstMap<Edge, int> > >("Random Insertion"); |
270 tspTestSmall<ChristofidesTsp<ConstMap<Edge, int> > >("Christofides"); |
273 tspTestSmall<ChristofidesTsp<ConstMap<Edge, int> > >("Christofides"); |
271 tspTestSmall<Opt2Tsp<ConstMap<Edge, int> > >("2-opt"); |
274 tspTestSmall<Opt2Tsp<ConstMap<Edge, int> > >("2-opt"); |
272 |
275 |
273 tspTestRandom<NearestNeighborTsp<DoubleEdgeMap > >("Nearest Neighbor"); |
276 tspTestRandom<NearestNeighborTsp<DoubleEdgeMap > >("Nearest Neighbor"); |