Проверьте, есть ли Edge в std :: vector (ускорение) - PullRequest
Новая
       26

Проверьте, есть ли Edge в std :: vector (ускорение)

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

У меня есть некоторый код, который работает, но он проводит большую часть времени в этой функции, будучи крайне неэффективным.

Общая задача: получить MST, который включает кратчайший путь между указанными вершинами. 

void MSTPath::m_add_shortest_path(vector<Edge> path){
    for (Edge e : path) m_graph->union_vu(e.get_node(),e.get_opposite_node(-1));

    for (Edge e : m_all_edges){
        if (MSTPath::m_in_path(e,path)) m_mst.push_back(e);
        else m_edges.push_back(e);
}

Что делает эта функция: добавляет все ребра из vector<Edge> path (кратчайший путь в графе) в MST, чтобы вычисленный MST включал этот путь. Все остальные Edges это объявляет m_edges, который является вектором "кандидатов" на ребра в MST. 

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

Как это выглядит для вычисления MST: 

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);
        }
    }

Edge: 

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

    int get_node(){ return v; }
    int get_opposite_node(int k){
        if ((k==v) || (k==-1)) return u;
        else return v;
    }

    int v, u, weight;
};

Вопрос: есть ли более эффективный способ проверки, находится ли Edge e в vector<Edge> path, чем тот, который определен в bool MSTPath::m_in_path? Или, в более общем смысле, может быть, более эффективный способ построения m_edges и m_mst из m_all_edges и path?

...