MaxFlow :: Dinitz Algorithm

Here is a nice implementation of Dinitz blocking flow algorithm in C++ (with special thanks to Fahim vai). Works in undirected large graph containing multiple edges and self loops as well. No STL used. This implementation is pretty fast.

Here, input is, number of nodes 2≤n≤5000, number of input edges 0≤e≤30000, then e undirected edges in the form (u, v, cap) (1≤u,v≤n and 1≤cap≤10^9). Source and Sink are assumed 1 and n accordingly, can be changed in the init() function call.

#define SET(p) memset(p, -1, sizeof(p))
#define CLR(p) memset(p, 0, sizeof(p))
#define i64 long long

const int INF = 0x7fffffff;
const int MAXN = 5005, MAXE = 60006;

int src, snk, nNode, nEdge;
int Q[MAXN], fin[MAXN], pro[MAXN], dist[MAXN];
int flow[MAXE], cap[MAXE], next[MAXE], to[MAXE];

inline void init(int _src, int _snk, int _n) {
    src = _src, snk = _snk, nNode = _n, nEdge = 0;
    SET(fin);
}

inline void add(int u, int v, int c) {
    to[nEdge] = v, cap[nEdge] = c, flow[nEdge] = 0, next[nEdge] = fin[u], fin[u] = nEdge++;
    to[nEdge] = u, cap[nEdge] = c, flow[nEdge] = 0, next[nEdge] = fin[v], fin[v] = nEdge++;
}

bool bfs() {
    int st, en, i, u, v;
    SET(dist);
    dist[src] = st = en = 0;
    Q[en++] = src;
    while(st < en) {
        u = Q[st++];
        for(i=fin[u]; i>=0; i=next[i]) {
            v = to[i];
            if(flow[i] < cap[i] && dist[v]==-1) {
                dist[v] = dist[u]+1;
                Q[en++] = v;
            }
        }
    }
    return dist[snk]!=-1;
}

int dfs(int u, int fl) {
    if(u==snk) return fl;
    for(int &e=pro[u], v, df; e>=0; e=next[e]) {
        v = to[e];
        if(flow[e] < cap[e] && dist[v]==dist[u]+1) {
            df = dfs(v, min(cap[e]-flow[e], fl));
            if(df>0) {
                flow[e] += df;
                flow[e^1] -= df;
                return df;
            }
        }
    }
    return 0;
}

i64 dinitz() {
    i64 ret = 0;
    int df;
    while(bfs()) {
        for(int i=1; i<=nNode; i++) pro[i] = fin[i];
        while(true) {
            df = dfs(src, INF);
            if(df) ret += (i64)df;
            else break;
        }
    }
    return ret;
}

int main() {
    int n, e, u, v, c, i;
    scanf("%d%d", &n, &e);
    init(1, n, n);
    for(i=0; i<e; i++) {
        scanf("%d%d%d", &u, &v, &c);
        if(u!=v) add(u, v, c);
    }
    printf("%lld\n", dinitz());
    return 0;
}

Using adjacency matrix and/or STL makes it 10 to 4 times slower.

C++ :: Get Variable's Name

How to print a variables name instead of its value? (not just by giving the name yourself)

This can be easily done with a #define pre-processor directive. As #define treats the preceding expression as cstring, it is possible to get the variables name as a string. Look below:

#include <stdio.h>

#define getVarName(varName,holder) sprintf(holder, "%s", #varName)

int main() {
    int var = 100; // just any type of identifier
    char name[100]; // it will get the variables name
    getVarName(var, name);
    puts(name);
    return 0;
}

It will print "var" instead of "100" or something other. I saw it years ago somewhere I can't remember now. Today, it suddenly struck me and I think it might be useful who knows when...

Maximum Matching (DFS)

Maximum bipartite matching in a bipartite graph

Although Hopcroft Karp is faster and smarter, this one is pretty simple to code specially in contest time and when the graph is relatively smaller. It uses a DFS subroutine to cut and establish matching and thus produces a maximum matching. This version of BPM takes the adjacency list of left side of the bipartite graph and updates the Left[] and Right[] arrays with their respective matches.

Here, in the DFS subroutine, there are two for loops, where, the first one checks for yet unestablished connections, and the second one is the recursive DFS step. These two steps could be written in a single loop and the condition modified as "( Right[v]==-1 || dfs(Right[v]) )", actually separating them increases performance by some factors, because, first time it checks all the unmatched nodes before going into DFS.

A sample C++ implementation:

#define SET(x) memset(x, -1, sizeof(x))
#define CLR(x) memset(x, 0, sizeof(x))
#define MAX 100

vector < int > edges[MAX];
bool visited[MAX];
int Left[MAX], Right[MAX];

bool dfs(int u) {
    if(visited[u]) return false;
    visited[u] = true;
    int len = edges[u].size(), i, v;
    for(i=0; i<len; i++) {
        v = edges[u][i];
        if(Right[v]==-1) {
            Right[v] = u, Left[u] = v;
            return true;
        }
    }
    for(i=0; i<len; i++) {
        v = edges[u][i];
        if(dfs(Right[v])) {
            Right[v] = u, Left[u] = v;
            return true;
        }
    }
    return false;
}

int match() {
    SET(Left);
    SET(Right);
    int i, ret = 0;
    bool done;
    do {
        done = true;
        CLR(visited);
        for(i=0; i<MAX; i++) {
            if(Left[i]==-1 && dfs(i)) {
                done = false;
            }
        }
    } while(!done);
    for(i=0; i<MAX; i++) ret += (Left[i]!=-1);
    return ret;
}

Notes: Here, edges[MAX] is the left side adjacency list, implemented with vector, Left[MAX] and Right[MAX] holds the matching and the procedure match() returns maximum matching. Pretty straight forward.

Expression Evaluation

Infix to Postfix transformation and evaluation

Here, I would like to share a java source for converting an Infix expression to a Postfix equivalent and evaluate the Postfix expression. Postfix is also known as "Reverse Polish Notation". If you want to know more about this algorithm, this will be helpful.

Here is a simple java implementation. (Oh, we could do it a lot easily in C++, but, actually it has a academic purpose as well). A few things to note:

• Fixed format of input, as this is just a demonstration. Do not use spaces.
• It doesn't check whether the given expression is consistent or not.
• No math error is checked here, you have to add it to your own.
• Check sample execution for more details.
• Only for binary operators +,-,*,/,%,^ and parenthesis ()

Java Source

//
// @author Zobayer
// @date May 10, 2010
//

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

//
// Demonstrates Expression evaluation process.
// Doesn't take care of wrong input,
// You need to handle that on your own.
//

public class Expression {

    // A sample main() method to demonstrate this process
    public static void main(String[] args) throws IOException {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        String expr;
        List<String> inFix, postFix;
        int result;

        while((expr = stdin.readLine())!=null) {
            expr = "(" + expr + ")";
            inFix = getInFix(expr);
            postFix = getPostFix(inFix);
            result = evaluate(postFix);
            System.out.println("Postfix form: " + postFix);
            System.out.println("Result: " + result);
        }
    }

    // Parse the input string and form an infix notation
    static List<String> getInFix(String expr) {
        List<String> list = new ArrayList<String>();
        int n, i;
        char ch;
        boolean hasInt;

        for(i = n = 0, hasInt = false; i < expr.length(); i++) {
            ch = expr.charAt(i);
            if(!isDigit(ch)) {
                if(hasInt) {
                    list.add("" + n);
                    n = 0;
                    hasInt = false;
                }
                list.add("" + ch);
            }
            else {
                n = n * 10 + (ch - 48);
                hasInt = true;
            }
        }
        
        return list;
    }

    // Enlist the tokens in a postfix notation
    static List<String> getPostFix(List<String> inFix) {
        List<String> list = new ArrayList<String>();
        Stack<String> oper = new Stack<String>();
        int i;
        char ch;
        String token, peek;

        for(i = 0; i < inFix.size(); i++) {
            token = inFix.get(i);
            ch = token.charAt(0);
            if(isDigit(ch)) list.add(token);
            else if(ch=='(') oper.push("" + ch);
            else if(ch==')') {
                while(!oper.empty()) {
                    peek = oper.pop();
                    if(peek.charAt(0)!='(') list.add(peek);
                    else break;
                }
            }
            else {
                while(!oper.empty()) {
                    peek = oper.peek();
                    if(peek.charAt(0)!='(' && preced(ch) <= preced(peek.charAt(0))) {
                        list.add(peek);
                        oper.pop();
                    }
                    else {
                        oper.push(token);
                        break;
                    }
                }
            }
        }
        
        return list;
    }

    // Evaluate the postfix notation passed as a list
    static int evaluate(List<String> postFix) {
        Stack<Integer> stack = new Stack<Integer>();
        int i, a, b;
        String token;
        char ch;

        for(i = 0; i < postFix.size(); i++) {
            token = postFix.get(i);
            ch = token.charAt(0);
            if(isDigit(ch)) stack.push(Integer.parseInt(token));
            else {
                b = stack.pop();
                a = stack.pop();
                switch(ch) {
                    case '+': a = a + b; break;
                    case '-': a = a - b; break;
                    case '*': a = a * b; break;
                    case '/': a = a / b; break;
                    case '%': a = a % b; break;
                    case '^': a = (int)Math.pow(a, b); break;
                }
                stack.push(a);
            }
        }
        
        return stack.pop();
    }

    // Provides operator precedence
    static int preced(char op) {
        if(op=='^') return 3;
        if(op=='*' || op=='/' || op=='%') return 2;
        if(op=='+' || op=='-') return 1;
        return 0;
    }

    // Checks if ch is a digit or not
    static boolean isDigit(char ch) {
        return (ch >= '0' && ch <= '9');
    }
}

Sample run

(3+8-90*36)*((((89-5%6+2^3-10-10-10)))-8)+100
Postfix form: [3, 8, +, 90, 36, *, -, 89, 5, 6, %, -, 2, 3, ^, +, 10, -, 10, -, 10, -, 8, -, *, 100, +]
Result: -174266
90+0
Postfix form: [90, 0, +]
Result: 90
6+763-67*2367-(54/234)
Postfix form: [6, 763, +, 67, 2367, *, -, 54, 234, /, -]
Result: -157820

The algorithm implemented here is pretty simple, so I guess I haven't made a mistake yet, but who knows? So please check it...

Maximum Matching (Hopcroft)

Hopcroft-Karp is one of the fastest algorithm that finds the maximum cardinality matching on a bipartite graph. It has the best known worst case time complexity. More details can be found here [courtesy of Wikipedia].

C++ Source Code:

#define MAX 100001
#define NIL 0
#define INF (1<<28)

vector< int > G[MAX];
int n, m, match[MAX], dist[MAX];
// n: number of nodes on left side, nodes are numbered 1 to n
// m: number of nodes on right side, nodes are numbered n+1 to n+m
// G = NIL[0] ∪ G1[G[1---n]] ∪ G2[G[n+1---n+m]]

bool bfs() {
    int i, u, v, len;
    queue< int > Q;
    for(i=1; i<=n; i++) {
        if(match[i]==NIL) {
            dist[i] = 0;
            Q.push(i);
        }
        else dist[i] = INF;
    }
    dist[NIL] = INF;
    while(!Q.empty()) {
        u = Q.front(); Q.pop();
        if(u!=NIL) {
            len = G[u].size();
            for(i=0; i<len; i++) {
                v = G[u][i];
                if(dist[match[v]]==INF) {
                    dist[match[v]] = dist[u] + 1;
                    Q.push(match[v]);
                }
            }
        }
    }
    return (dist[NIL]!=INF);
}

bool dfs(int u) {
    int i, v, len;
    if(u!=NIL) {
        len = G[u].size();
        for(i=0; i<len; i++) {
            v = G[u][i];
            if(dist[match[v]]==dist[u]+1) {
                if(dfs(match[v])) {
                    match[v] = u;
                    match[u] = v;
                    return true;
                }
            }
        }
        dist[u] = INF;
        return false;
    }
    return true;
}

int hopcroft_karp() {
    int matching = 0, i;
    // match[] is assumed NIL for all vertex in G
    while(bfs())
        for(i=1; i<=n; i++)
            if(match[i]==NIL && dfs(i))
                matching++;
    return matching;
}

The implementation is quite straight forward as the algorithm on Wikipedia page. I am looking for some optimizations.