Нахождение MST с заданным путем (C ++) - PullRequest
Новая
       38

Нахождение MST с заданным путем (C ++)

0 голосов
/ 15 ноября 2018

У меня есть код для поиска MST, который будет включать заданный путь к MST, который дает мне правильный вес MST (я знаю, каким должен быть вывод). Я пытался переписать одну часть кода, чтобы использовать std::map вместо std::vector для более эффективного поиска (станет ясно из приведенного ниже кода), но теперь он дает неправильный ответ, несмотря на то, что изучал его в течение нескольких часов Я не могу понять, где я допустил ошибку. Будем благодарны за любую помощь в поиске ошибки.

Старая версия, которая использует vector<Edge>. Проходит вектор всех ребер (m_all_edges). Если ребро e находится в vector<Edge> path, добавляет его к MST (m_mst). В противном случае добавляет его к потенциальным ребрам для 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;
}

Версия с 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){
        if ((path_map.count(x.first)>0)||(path_map.count(x.first.reversed())>0)) m_mst.push_back(x.first);
        else m_edges.push_back(x.first);
    }
}

Функция для нахождения MST (вызывается после вызова 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;
}

Из того, что я вижу, обе функции получают абсолютно одинаковые m_mst (и начинающиеся mst_weight) и одинаковые m_edges (но в разном порядке). Но упорядочение не должно быть проблемой для алгоритма (кроме упорядочения по весу, но это обрабатывается в m_compute_mst), верно?

Edge класс: 

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 {
        if ((k==v) || (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;
};

Да, я знаю, что передача по значению делает дополнительные копии. Это временная версия.

...