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

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-вызов.

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

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

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