aajjbb's blog

Maximum Flow with Edmonds-Karp
By aajjbb, 12 years ago, In English

Hi, I'm really new to Flow algorithms and I'm starting with maximum flow using the EdmondsKarp, I've implemented this version, for the test example extracted from SPOJ FASTFLOW the following test-case has a max-flow of 5, my code answers 3. what would be wrong ? Thanks

Test-Case:

4 6
1 2 3
2 3 4
3 1 2
2 2 5
3 4 3
4 3 3

int max_flow(int source, int sink) {
    int residual[MAXN][MAXN]; memset(residual, 0, sizeof(residual));
    while(1) {
        int prev[MAXN]; memset(prev, -1, sizeof(prev));
        int actual[MAXN]; memset(actual, 0, sizeof(actual));
        prev[source] = source;
        actual[source] = INF;
        queue<int> q; q.push(source);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int i = 0; i < graph[u].size(); i++) {
                int v = graph[u][i];
                if(capacity[u][v] - residual[u][v] > 0 && prev[v] == -1) {
                    prev[v] = u;
                    actual[v] = min(actual[u], capacity[u][v] - residual[u][v]);
                    if(v != sink) {
                        q.push(v);
                    } else {
                        while(prev[v] != v) {
                            u = prev[v];
                            residual[u][v] += actual[sink];
                            residual[v][u] -= actual[sink];
                            v = u;
                        }
                        goto end;
                    }
                }
            }
        }
        end:;
        if(prev[sink] == -1) {
            int sum = 0;
            for(int i = 0; i < MAXN; i++) {
                sum += residual[source][i];
            }
            return sum;
        }
    }
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (19)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Better forget about maximum flow unless your handle becomes violet or orange.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I know that my rank is low, but I'm studying a lot about graph theory, I think flows would be a next path since I'm starting to deal good with searches, shortest-paths, bridges and cut points, but I'm also training in other topics as DP, geometry and greedy ;)

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Many green and blue ranked users know flow.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      Oh, certainly it helps them a lot while they try to solve something like Div2 B/C/D.
      Why are they learn all these flows, treaps, suffix arrays if they cannot solve problems which don't require any knowledge of algorithms?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        hello, mr. dalex , learning algorithms is not just for contest or problem solving, its for life and fun. then does it matter whether one person is violet or orange ?

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        dalex You took birth, started competitive programming and without learning algorithms you directly became orange huh?

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes. I recently learned maxflow and the implementation of Dinic's algorithm. But I have a problem. I'm trying to solve FASTFLOW in SPOJ and I'm getting TLE with Dinic's algorithm. How to optimize? Here is my implementation — http://codeforces.com/blog/entry/15562

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think your code is correct, the max flow value here is 3. The edge (3, 4) can handle only flow of 3, not 5.

By the way you code is very pretty. (:

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you, I'm pretty sure it's correct also, do you know any problem which asks for maximum flow without a too strict time as FASTFLOW ? but I think it's wrong also, since there's a possible flow of 3 in the path 1 — 2 — 3 — 4 and 2 from 1 — 3 — 4.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, i got it: these are undirected edges. So for every edge (u, v, c), you should put also edge (v, u, c).

      Maybe you can find some problems on maxflow here on Codeforces, try searching the problems from the archive on maxflow tag or smth. Also I recall, Dinic's algorithm gets accepted on FASTFLOW.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but I'm mounting as an undirected graph, take a look:

        memset(capacity, 0, sizeof(capacity));
    int n, m, a, b, c;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        graph[a].push_back(b); capacity[a][b] = c;
        graph[b].push_back(a); capacity[b][a] = c;
    }
        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          That's because there are edges (3, 4, 3) and (4, 3, 3) in input. The code overwrites the previous capacities. Add them up and it'll be cool.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, it was the problem, thank you, I'll look for more flow problems, ;) Thanks.

            → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have solved these problems in java, time limit is not strict.

      Data Flow

      Internet Bandwidth

      The Problem with the Problem Setter

      Sabotage

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Your implementation is incorrect.

Taking the line "int maxflow(.." as line 1, in lines 21 and 22, you should be updating the capacity matrix as capacity[u][v] -= actual[sink], capacity[v][u] += actual[sink], also increase residual flow as residual[u][v] += actual[sink]. For finding augmenting path in the residual graph, you will need to check if there exists an edge between u and v in the residual graph. That is, in line 11, you will need to check all vertices that can take a flow from u at any point of time. Therefore it is better to take the graph[] as undirected one, or check for all vertices if capacity[u][v] > 0. Similarly in line 15, actual[v] will be checked for minimum with capacity[u][v] and not capacity[u][v] — residual[u][v].

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    After reading your comment, I still don't see why the implementation is wrong. The array residual is there to avoid unnecessary changes to array capacity, which can be used somewhere later in the code.

    Aren't capacity[u][v] -= actual[sink] and residual[u][v] += actual[sink] the same?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You are right, I think only taking the graph[] as undirected one will do. Sorry for the confusion.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know how Edmonds Karp works , but i know Dinic algorithm and i know that dinic is better that edmonds karp if we are talking about complexities.

Wiki

Nice Implementation of FASTFLOW with Dinic

Maybe this be can help you.

→ Reply