1 files changed, 18 insertions, 53 deletions

diff --git a/src/tsp_approx.rs b/src/tsp_approx.rs
index 6a19b22..4c886cd 100644
--- a/src/tsp_approx.rs
+++ b/src/tsp_approx.rs
@@ -1,72 +1,39 @@
 use indicatif::{ProgressBar, ProgressStyle};
 use multiset::HashMultiSet;
-use priority_queue::PriorityQueue;
-use std::{
-    cmp::Ordering,
-    collections::{HashMap, HashSet},
-};
+use partitions::partition_vec::PartitionVec;
+use std::collections::{HashMap, HashSet};
 
 use crate::{MetricElem, TspAlg};
 
-// wrapper struct to
-// - reverse the ordering
-// - implement Ord, even though the type is backed by an f64
-#[repr(transparent)]
-#[derive(Debug, PartialEq)]
-struct DownOrd(f64);
-impl Eq for DownOrd {}
-impl PartialOrd for DownOrd {
-    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
-        Some(self.cmp(other))
-    }
-}
-impl Ord for DownOrd {
-    fn cmp(&self, other: &Self) -> Ordering {
-        self.0.partial_cmp(&other.0).unwrap().reverse()
-    }
-}
-
 fn get_mst<M>(embeds: &[M]) -> HashMap<usize, Vec<usize>>
 where
     M: MetricElem,
 {
     let num_embeds = embeds.len();
 
-    let mut possible_edges =
-        PriorityQueue::with_capacity((num_embeds * num_embeds - num_embeds) / 2);
+    let mut possible_edges = Vec::with_capacity((num_embeds * num_embeds - num_embeds) / 2);
     let mut mst = HashMap::with_capacity(num_embeds);
 
-    // here, we start at 0.
-    // we might get a better result in the end if we started with a vertex next
-    // to the lowest-cost edge, but we don't know which one that is (though we
-    // could compute that without changing our asymptotic complexity)
+    // insert all edges we could ever use
     mst.insert(0, Vec::new());
-    for i in 1..num_embeds {
-        possible_edges.push((0, i), DownOrd(embeds[0].dist(&embeds[i])));
+    for a in 0..num_embeds {
+        for b in a + 1..num_embeds {
+            possible_edges.push((embeds[a].dist(&embeds[b]), a, b));
+        }
     }
 
-    // prims algorithm or something like that
-    while mst.len() < num_embeds {
-        // find the edge with the least cost that connects us to a new vertex
-        let (new, old) = loop {
-            let ((a, b), _) = possible_edges.pop().unwrap();
-            if !mst.contains_key(&a) {
-                break (a, b);
-            } else if !mst.contains_key(&b) {
-                break (b, a);
-            }
-        };
-        mst.insert(new, vec![old]);
+    let mut subtrees: PartitionVec<usize> = (0..num_embeds).collect();
 
-        // insert all the new edges we could take
-        mst.entry(old).and_modify(|v| v.push(new));
-        for i in 0..num_embeds {
-            // don't consider edges taking us to nodes we already visited
-            if mst.contains_key(&i) {
-                continue;
-            }
+    possible_edges.sort_unstable_by(|(da, _, _), (db, _, _)| da.partial_cmp(db).unwrap());
+    for (_, a, b) in possible_edges.into_iter() {
+        if !subtrees.same_set(a, b) {
+            mst.entry(a).or_default().push(b);
+            mst.entry(b).or_default().push(a);
 
-            possible_edges.push((new, i), DownOrd(embeds[new].dist(&embeds[i])));
+            subtrees.union(a, b);
+        }
+        if mst.len() >= num_embeds {
+            break;
         }
     }
 
@@ -110,7 +77,6 @@ where
     for &x in verts {
         for &y in verts {
             if x != y {
-                //possible_edges.push((x, y), DownOrd(embeds[x].dist(&embeds[y])));
                 possible_edges.push((embeds[x].dist(&embeds[y]), x, y));
             }
         }
@@ -165,7 +131,6 @@ fn euler_tour(
         match e.iter().next() {
             Some(&next) => {
                 e.remove(&next);
-                // TODO das hier lässt vllt deduplizieren
                 graph.get_mut(&next).unwrap().remove(&cur);
 
                 r.entry(cur).or_default().push((pprev, prev, next));