Send in a proper set to the MST algorithm, instead of letting it deduce it itself...

diff --git a/tsp/tsp.cpp b/tsp/tsp.cpp
index a87585f6f321695ced5b6406bc08802df7daac09..5fd1dcb615becbf5e6b7142a1d4b4c36e2fff128 100644 (file)
--- a/tsp/tsp.cpp
+++ b/tsp/tsp.cpp
@@ -94,12 +94,9 @@ int optimistic_distance(int row_from, int switch_from, int row_to, int switch_to
 }
 
 // extremely primitive O(V^2) prim
-int prim_mst(std::vector<std::pair<unsigned, unsigned> > &points, try_order *temp, unsigned toi)
+int prim_mst(std::set<std::pair<unsigned, unsigned> > &set1)
 {
-       std::set<std::pair<unsigned, unsigned> > set1, set2;
-
-       for (unsigned i = 0; i < toi; ++i)
-               set1.insert(points[temp[i].o.pt]);
+       std::set<std::pair<unsigned, unsigned> > set2;
 
        // pick the first one
        std::set<std::pair<unsigned, unsigned> >::iterator start = set1.begin();
@@ -175,6 +172,9 @@ unsigned do_tsp(std::vector<std::pair<unsigned, unsigned> > &points, order *ord,
        unsigned last_switch = points[ord[ind-1].pt].second;
        unsigned last_side = ord[ind-1].side;
        
+       std::set<std::pair<unsigned, unsigned> > mst_set;
+       mst_set.insert(std::make_pair(last_row, last_switch));
+       
        for (unsigned i = 0; i < points.size(); ++i) {
                /* taken earlier? */
                for (unsigned j = 0; j < ind; ++j) {
@@ -194,12 +194,14 @@ unsigned do_tsp(std::vector<std::pair<unsigned, unsigned> > &points, order *ord,
                temp[toi].cost = distance(last_row, last_switch, last_side,
                        points[i].first, points[i].second, +1);
                ++toi;
+       
+               mst_set.insert(points[i]);
 
 taken:
                1;
        }
 
-       unsigned min_rest_cost = prim_mst(points, temp, toi);
+       unsigned min_rest_cost = prim_mst(mst_set);
        if (cost_so_far + min_rest_cost >= best_so_far) {
                return UINT_MAX;
        }