#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Posts
    2
    Rep Power
    0

    Checking for bipartite graph


    Hi guys,

    Well I have an assignment which requires me to check if a graph is bipartite or not using a dfs algorithm. I generated a rather simple code but am not sure if it works.

    Code:
    int bipart(int v)
    {
          int w, bipartite=0;/* colour = 0 (not visited), =1 (blue), = 2 (red) */
         count = count + 1;
         sequence[count] = v;
         visit[v] = 1;
         
         if(colour[v] == 0) /* Starting vertex would have not been visited */
         colour[v] = 1;
         
         for(w=1; w<=V; w++)
         {
                  if(a[v][w] == 1 && visit[w] == 0 && colour[w] == 0) /* Adjacent vertex which has not been visited and coloured */
                  {
                             parent[w] = v;     
                             if(colour[v] == 1)
                             colour[w] = 2;
                             else
                             colour[w] = 1;
                             bipart(w);
                  }
    
                  else if(a[v][w] == 1 && visit[w] == 1 && colour[w] == colour[v]) /*Adjacent vertex visited and of similar colour as parent*/
                  {
                       bipartite = bipartite + 1;
                       printf("\nThe graph is not a bipartite graph.");
                       return bipartite;
                  }
    
                  else if(a[v][w] == 1 && visit[w] == 1 && colour [w] != colour[v]) /*Adjacent vertex visited and of different colour as parent*/
                  {
                       parent[w] = v;
                       bipart(w);
                  }
         }
         
         return bipartite;
    }
    In the main function, if(bipart(i) == 0), then print The graph is a bipartite graph.

    Can anyone guide me?

    Do appreciate any input.

    Thanks!

    Drendal
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    Interesting problem. What does DFS stand for? Is this some variation on the parity scheme?

    It seems you have not posted enough of your code. Where are colour and visit defined?

    Originally Posted by Drendal
    I generated a rather simple code but am not sure if it works.
    Well test it and find out. Feed it graphs that are known to be bipartite and not bipartite. Use sets of graphs that are 1, 2, 3, odd, even length number of nodes in both categories. Make sure you have bipartite graphs with only 1 node in one of the sets and try building those sets with the node at the start, middle and end of the graph.

    Why don't these schools teach unit testing before they jump into algorithms?
    I no longer wish to be associated with this site.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2010
    Posts
    2
    Rep Power
    0
    DFS = Depth-first search
    Oh and I think i forgot to mention that it's coded in C.

    I would test it out if I knew how to represent a bipartite graph in adjacency matrix form but I'm totally clueless on it. I just built this code solely based on theory so I'm not sure if it works.. :(

    visit[v] is basically an array which will note the vertices of the graph which have been traversed by the dfs algorithm.

    and colour[v] is also an array initialized in the start of the main function, basically since a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets, colour[v] = 1 is one set whereas colour[v] = 2 is another set.

    Not too sure if my logic is right here..
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    I'm assuming we're dealing with undirected graphs? (There's a similar characterization for directed graphs.) An easy way to generate bipartite adjacency matrices is (in block form):
    Code:
    [0  A]
    [A' 0]
    (where A' is the transpose of A). In fact, if M is the adjacency matrix of an arbitrary graph, then the graph is bipartite if and only if PMP' is of the above form for some permutation matrix P.

IMN logo majestic logo threadwatch logo seochat tools logo