Program Listing for File EdmondsKarp.hpp¶

/*
 * EdmondsKarp.hpp
 *
 *  Created on: 11.06.2014
 *      Author: Michael Wegner (michael.wegner@student.kit.edu), Michael Hamann
 * <michael.hamann@kit.edu>
 */

#ifndef NETWORKIT_FLOW_EDMONDS_KARP_HPP_
#define NETWORKIT_FLOW_EDMONDS_KARP_HPP_

#include <vector>

#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {

class EdmondsKarp final : public Algorithm {
    const Graph *graph;

    node source, sink;

    std::vector<edgeweight> flow;
    edgeweight flowValue;

public:
    EdmondsKarp(const Graph &graph, node source, node sink);

    void run() override;

    edgeweight getMaxFlow() const;

    std::vector<node> getSourceSet() const;

    edgeweight getFlow(node u, node v) const;

    edgeweight getFlow(edgeid eid) const {
        assureFinished();
        return flow[eid];
    };

    const std::vector<edgeweight> &getFlowVector() const;

private:
    void runUndirected();
    void runDirected();

    edgeweight BFS(std::vector<node> &pred) const;

    edgeweight directedBFS(const std::vector<count> &reverseEdges, std::vector<node> &pred) const;
};

} /* namespace NetworKit */

#endif // NETWORKIT_FLOW_EDMONDS_KARP_HPP_