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

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 и сделали все внутри объекта.

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