test/tsp_test.cc
changeset 1098 cf6084618b1b
parent 1092 dceba191c00d
child 1106 1ba759c76810
equal deleted inserted replaced
2:53badba99c6f 3:968cd1383719
    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");