Найдите преимущество с использованием алгоритма Форда Фулкерсона?

Question

Я пытаюсь реализовать Алгоритм Форда Фулкерсона в C++.

Однако у меня возникли проблемы с моей функцией find_edge. Когда я вызываю эту функцию в my_alg, она выбирает правильный край, а затем поток увеличивается в my_alg. Он выбирает правый край и увеличивает свой поток (flow), но когда я снова вызываю функцию find_edge, поток не увеличивается, как и должно быть.

Это приводит к бесконечному циклу моего алгоритма. Вероятно, я делаю что-то не так с указателями. Вы можете увидеть мой код ниже.

//An object of this class represents an edge in the graph. 
class Edge 
{ 
private: 
    //Node *prev; 

public: 
    int flow; 

    Edge(Node *firstNode, Node *secNode, unsigned inCost) { 
     orgNode = firstNode; 
     dstNode = secNode; 
     bridge_capacity = inCost; 
    } 

    Edge() { 
     flow=0; 
    } 
}; 

//An object of this class holds a vertex of the graph 
class Node 
{ 
public: 
    Node *prev; 

    vector<Edge>& getAdjNodeList() { 
     return adjNodeList; 
    } 
}; 

Edge *find_edge(Graph *g,Node *from,Node *to) { 
    vector<Edge> b=from->getAdjNodeList(); 
    for(int i=0;i<b.size();i++) { 
     if(b[i].getDstNode()==to) 
      return (&b[i]); 
    } 
    return NULL; 
} 

int my_alg(Graph *as,Node *source,Node *sink){ 
    Edge *find_edge(); 

    int max_flow=0; 

    while(bfs(as,source,sink)) { 
     Node *b=as->nodeList[num_isl]; 
     int inc=100000000; 
     while(b->prev!=NULL) { 
      Edge *bok=find_edge(as,b->prev,b); 
      inc=min(inc,bok->get_bridge_capacity()-bok->flow); 
      b=b->prev; 
     } 

     b=as->nodeList[num_isl]; 

     while(b->prev!=NULL){ 
      Edge *bok = find_edge(as,b->prev,b); 
      bok->flow += inc;  // This is the place the flow is incremented 
      bout << bok->flow;  // Here, everything is alright. 
      bok = find_edge(as,b->prev,b); 
      cout << bok->flow;  // However, this is is not the correct result. 
     } 
     max_flow+=inc; 
    } 
    return max_flow; 
} 

Answer 1

У меня был более тщательный взгляд на ваш код. Чтобы помочь вам отслеживать свои проблемы в будущем, я покажу вам пример процесса обнаружения ошибки.

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

class Edge { 
public: 
    int flow; 
};  

class Node { 
private: 
    vector<Edge> adjNodeList; // list of outgoing edges for this vertex 

public: 
    vector<Edge> & getAdjNodeList() { 
     return adjNodeList; 
    } 

    void addAdjNode(Node* newAdj) { 
     adjNodeList.push_back(Edge(newAdj)); 
    } 
};  


int main() { 
    Node *node1 = new Node(); 
    Node *node2 = new Node(); 
    node1->addAdjNode(node2); 

    vector<Edge> t = node1->getAdjNodeList(); 
    vector<Edge> f = node1->getAdjNodeList(); 
    t[0].flow = 11; 

    cout << t[0] << endl; 
    cout << f[0] << endl; 
} 

Если бы запустить этот код, то можно заметить, что t[0] и f[0] не то же самое. Поскольку я просто скопировал ключевые элементы вашего кода, причина должна быть одинаковой.

Что здесь происходит? При вызове

vector<Edge> t = node1->getAdjNodeList(); 

список смежности возвращаются по ссылке, которая должна оставить вас со ссылкой на первоначальный список - вы должны быть в состоянии изменить его элементы, не должны ли вы? Однако при назначении этой ссылки на вновь выделенный вектор t вызывается неявный конструктор копирования, поэтому t будет содержать копию (!) Вашего вектора, пока вы хотите сохранить ссылку.

Чтобы обойти эту проблему, вы могли бы просто сделали следующее:

vector<Edge> & t = node1->getAdjNodeList(); 

который сохраняет ссылку и не создает новый объект.

Я могу только предположить, почему указатели оказались идентичными между вызовами функции: объект, вероятно, каждый раз копировался в одно и то же место. Кроме того, обратите внимание, что вы увеличили значение объекта, который больше не существовал - копия была удалена с завершением find_edge -call.

Потребовалось некоторое время, чтобы дать ответ на ваш вопрос, поскольку вы сами не отследили проблему. Если бы вы приводили пример выше, я уверен, ваше решение было бы там в течение нескольких минут. Вам рекомендуется поднимать ваши проблемы при переполнении стека, однако большинство участников не захотят работать с большим количеством кода, чтобы идентифицировать проблему самостоятельно. Это означает, что ответы высокого качества обычно требуют вопросов, которые непосредственно доходят до сути. (Последний абзац был предназначен, чтобы помочь вам в будущем, однако его можно было бы уменьшить без изменения вопроса).

Кроме того, я настоятельно рекомендую вам не использовать свои объекты так, как вы. Передавая все как ссылки и делая все изменения вне объекта, вы в основном обходите инкапсуляцию, которая делает объектно-ориентированное программирование мощным.Например, было бы намного мудрее (и не дало бы вам вашей проблемы), если бы вы только что добавили еще одну функцию increaseFlow(Edge* to, int increment) к вашему Node и сделали все в пределах объекта.

Надеюсь, что смогу помочь.