All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
EdmondsKarp.h
Go to the documentation of this file.
1 /*
2  * EdmondsKarp.h
3  *
4  * Created on: 11.06.2014
5  * Author: Michael Wegner (michael.wegner@student.kit.edu), Michael Hamann <michael.hamann@kit.edu>
6  */
7 
8 #ifndef EDMONDSKARP_H_
9 #define EDMONDSKARP_H_
10 
11 #include "../graph/Graph.h"
12 #include <vector>
13 
14 namespace NetworKit {
15 
20 class EdmondsKarp {
21 private:
22  const Graph &graph;
23 
24  node source;
25  node sink;
26 
27  std::vector<edgeweight> flow;
28  edgeweight flowValue;
29 
36  edgeweight BFS(std::vector< edgeweight > &residFlow, std::vector< node > &pred) const;
37 
38 public:
45  EdmondsKarp(const Graph &graph, node source, node sink);
46 
50  void run();
51 
57  edgeweight getMaxFlow() const;
58 
64  std::vector<node> getSourceSet() const;
65 
74  edgeweight getFlow(node u, node v) const;
75 
82  edgeweight getFlow(edgeid eid) const {
83  return flow[eid];
84  };
85 
92  std::vector<edgeweight> getFlowVector() const;
93 };
94 
95 } /* namespace NetworKit */
96 
97 #endif /* EDMONDSKARP_H_ */
The EdmondsKarp class implements the maximum flow algorithm by Edmonds and Karp.
Definition: EdmondsKarp.h:20
index edgeid
Definition: Globals.h:25
std::vector< node > getSourceSet() const
Returns the set of the nodes on the source side of the flow/minimum cut.
Definition: EdmondsKarp.cpp:93
std::vector< edgeweight > getFlowVector() const
Return a copy of the flow values of all edges.
Definition: EdmondsKarp.cpp:120
edgeweight getFlow(edgeid eid) const
Get the flow value of an edge.
Definition: EdmondsKarp.h:82
EdmondsKarp(const Graph &graph, node source, node sink)
Constructs an instance of the EdmondsKarp algorithm for the given graph, source and sink...
Definition: EdmondsKarp.cpp:15
index node
Definition: Globals.h:23
edgeweight getFlow(node u, node v) const
Get the flow value between two nodes u and v.
Definition: EdmondsKarp.cpp:116
void run()
Computes the maximum flow, executes the EdmondsKarp algorithm.
Definition: EdmondsKarp.cpp:54
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
edgeweight getMaxFlow() const
Returns the value of the maximum flow from source to sink.
Definition: EdmondsKarp.cpp:88
The BFS class is used to do a breadth-first search on a Graph from a given source node...
Definition: BFS.h:20
double edgeweight
Definition: Globals.h:24