Myujth

I have a code for finding MST which would include a given path to MST, which gives me correct weight of MST (I know what the output is supposed to be). I tried to rewrite one part of the code to use std::map instead of std::vector for more efficient look-up (will become clear from the code below), but now it gives wrong answer, and despite looking into it for few hours, I am unable to understand where did I make a mistake. Any help with locating a bug will be appreciated.

Old version that uses vector<Edge>. Goes through the vector of all edges (m_all_edges). If an edge e is in vector<Edge> path, adds it to MST (m_mst). Otherwise, adds it to candidate edges for MST (m_edges).

void MSTPath::m_add_shortest_path_old(vector<Edge> path)
 for (auto e : path)
 m_graph->union_vu(e.get_node(),e.get_opposite_node(-1));
 
 for (auto e : m_all_edges)
 if (tempfunc(e,path)) m_mst.push_back(e);
 else m_edges.push_back(e);
 


bool MSTPath::tempfunc(Edge e, vector<Edge> path)
 for (auto edge : path)
 if((edge.get_node()==e.get_node())&&(edge.get_opposite_node(-1)==e.get_opposite_node(-1))) return true;
 
 return false;

Version with std::map.

void MSTPath::m_add_shortest_path(map<Edge,int> path_map)
 for (auto const& x : path_map)
 Edge e = x.first;
 m_graph->union_vu(e.get_node(),e.get_opposite_node(-1));
 
 for (auto const& x : m_all_edges_map)(path_map.count(x.first.reversed())>0)) m_mst.push_back(x.first);
 else m_edges.push_back(x.first);
 

Function for finding MST (called after calling m_add_shortest_path / m_add_shortest_path_old).

int MSTPath::m_compute_mst()
 sort(m_edges.begin(),m_edges.end(),(Edge e1, Edge e2) return e1.weight < e2.weight; );
 int i = 0;
 int mst_size = m_mst.size();

 int mst_weight = 0;
 int v,u;
 for (Edge e : m_mst) mst_weight += e.weight;

 while (mst_size<m_N-1)
 Edge edge = m_edges[i++];
 v = m_graph->find(edge.get_node());
 u = m_graph->find(edge.get_opposite_node(-1));
 if (u!=v)
 mst_size++;
 mst_weight += edge.weight;
 if (mst_weight>=min_mst_weight) return numeric_limits<int>::max();
 m_mst.push_back(edge);
 m_graph->union_vu(v,u);
 
 
 return mst_weight;

From what I see, both function get exactly the same m_mst (and starting mst_weight) and the same m_edges (but in different order). But ordering should not be a problem for the algorithm (except for ordering by weight, but this is handles in m_compute_mst), right?

Edge class:

class Edge
public:
 Edge(int v_e, int u_e, int w)
 v = v_e;
 u = u_e;
 weight = w;
 

 int get_node() const return v; 
 int get_opposite_node(int k) const (k==-1)) return u;
 else return v;
 

 Edge reversed() const 
 return Edge(u,v,weight);
 

 bool operator<(const Edge& e) const 
 if (this->get_node()<e.get_node()) return true;
 else if (this->get_node()==e.get_node()) return this->get_opposite_node(-1)<e.get_opposite_node(-1);
 else return false;
 

 int v, u, weight;
;

Yes, I know that passing by value makes additional copies. This is a temporary version.