Monday, March 15, 2010

Testing Bipartite Graph


We can use BFS to check whether an undirected graph is bipartite or not, with only a little modification...

We define bipartite graph as follows: A bipartite graph is an undirected graph G = (V, E) in which V can be partitioned into two sets V1 and V2 such that (u, v) ∈ E implies either u ∈ V1 and v ∈ V2 or u ∈ V2 and v ∈ V1. That is, all edges go between the two sets V1 and V2.

In other to determine if a graph G = (V, E) is bipartite, we perform a BFS on it with a little modification such that whenever the BFS is at a vertex u and encounters a vertex v that is already 'gray', i.e. visited, our modified BSF should check to see if the depth of both u and v are even, or if they are both odd. If either of these conditions holds which implies d[u] and d[v] have the same parity, then the graph is not bipartite. Note that this modification does not change the running time of BFS and remains Θ(V + E).

Here goes a simple implementation of the above idea. We'll just run a BFS, while tracking the partition in which every node falls. If, when visiting node v from node u, and they are members of same partition, then this graph is not bipartite. Well, this time, I think, we have nothing to do with the edge weights or costs, so it will also work on a weighted graph.

Formally, to check if the given graph is bipartite, the algorithm traverse the graph labelling the vertices 0 or 1 / 2 , corresponding to unvisited or visited, and partition 1 or partition 2 depending on which set the nodes are in. If an edge is detected between two vertices in the same partition, the algorithm returns false immediately.

Note: In this implementation, only one test at a time is possible, to run it for multiple cases, definitely cares must be taken about resetting the arrays and other values as necessary.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define MAX 1001

int n, e;
int partition[MAX], visited[MAX];
vector< int > G[MAX];

bool is_bipartite() {
    int i, u, v, start;
    queue< int > Q;
    start = 1; // nodes labeled from 1
    Q.push(start);
    partition[start] = 1; // 1 left, 2 right
    visited[start] = 1; // set gray
    while(!Q.empty()) {
        u = Q.front(); Q.pop();
        for(i=0; i < G[u].size(); i++) {
            v = G[u][i];
            if(partition[u] == partition[v]) return false;
            if(visited[v] == 0) {
                visited[v] = 1;
                partition[v] = 3 - partition[u]; // alter 1 and 2
                Q.push(v);
            }
        }
    }
    return true;
}

int main() {
    int i, u, v;
    scanf("%d %d", &n, &e);
    for(i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    if(is_bipartite()) printf("Yes\n");
    else printf("No\n");
    return 0;
}

As this algorithm traverses the graph it labels the vertices with a partition number consisted with the graph being bipartite. If at any vertex, algorithm detects an inconsistency, it shows with an invalid return value. Partition value of u will always be a valid number as it was en-queued at some point and its partition was assigned at that point. Partition of v will be unchanged if it is already set, otherwise it will be set to a value opposite to that of vertex u. So, if the algorithm returns true, it means, the graph is bipartite, i.e. bi-color-able, and partition[] holds the colors for each vertex.

Have fun, and let me know about errors, if any. [Note: The definition of bipartite graph is taken from this wonderful site]


11 comments:

  1. You need one more loop (and may be some bookkeeping) - for a bipartite graph may not be a connected graph.

    ReplyDelete
  2. Oh, I forgot to write I assumed it to be connected one. Of course, if its not connected, then one more loop is needed for every disjoint sub-graph. Thanks :)

    ReplyDelete
  3. Dude,
    Your material(apart from the C programme) is almost the same as in
    http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm
    If you have used the material, better acknowledge it. Otherwise, you are in for some serious trouble.

    ReplyDelete
  4. @Anonymous, thanks for pointing it. I have copied the definition of bipartite graph from his site. Because, anyone anyhow writes it will pretty much be the same. And no, I am not in any kind of trouble. Because, there is no copy-write claim on his site. I like that site very much, and probably if you have not noticed, his site is listed in the right panel's "Favorite Links" section from the start of the blog. Thanks for your comment.

    ReplyDelete
  5. I too have just arrived here from Google having read http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm

    No copyright statement is needed, copyright automatically applies. He does need to give explicit permission to allow you to copy it if that's his wish, e.g. by placing it under a Creative Commons licence.

    ReplyDelete
    Replies
    1. Obviously he didn't invent the definition, that is also copied from some books I have read years ago, if you catch my drift. You can't claim copyright for writing too much obvious things.

      Delete
  6. your block of code very beautiful, please give me CSS code to create block(box) like that.

    ReplyDelete
    Replies
    1. Please, give credit to this guy :)
      http://alexgorbatchev.com/SyntaxHighlighter/

      This is a free syntax highlighting tool. I am using an old version of it.

      The files can also be found here:
      http://code.google.com/p/syntaxhighlighter/

      And if you use wordpress, you have it built in with wordpress system. Read more here about wordpress.
      http://wordpress.org/extend/plugins/syntaxhighlighter/

      Thanks for visiting my blog :)

      Delete
  7. Wen I submit ur code in contests environment it is SHOWING COMPILE TIME ERROR
    Comparison between signed and unsigned integers.....

    ReplyDelete
    Replies
    1. its because size() from vector returns a size_t type value, which is essentially an int. but it should not be caught as an error, they give it as a warning.

      Delete
  8. Hey Zobayer I am not able to figure out how to do it for graphs that are not strongly connected. Could you help me please?

    ReplyDelete