How to Make Sense of the Bipartite Graph

Developing strength in the area of graph is a great outlet to sharpen your programming craft. It also has a ripple effect. You wander with a queue, a stack, a priority queue, and whatnot, while dealing with a graph.

To get a glimpse of it, in today’s issue, I’d like to communicate briefly the idea of a Bipartite Graph and its implementation in a very gentle manner. Let’s go.

The whole idea with graph is that we make connections between things, which form a network along its perimeter. A connection sets a bond between two nodes. And if it is possible for two distinct colors to be exhausted on each edge, then we wind up calling it a Bipartite.

Since the structure of a graph can be as broad as the ocean and simultaneously it can be as high as mountains, we can either traverse broadly by exploiting neighbor nodes before descendants, or can go deep by striking descendants first.

These two are the most common techniques to lean into when information is organized like this. The first one is BFS (Breadth First Search), and the latter one is DFS (Depth First Search).

Let’s lay out what steps the BFS Algorithm takes internally for the Bipartite check:

• entering the function with a starting node, the first thing it does is enqueue the starting node into the queue data structure
• gives the starting node a color (0 | 1, model as 2 distinct colors) in the colors[] array
• runs a loop until the queue is empty, and on each iteration:
  • dequeues a node
  • fires yet another loop to see all of its neighbors and look for the following things for each neighbor:
    • If the neighbor node is not yet colored, it gives a color opposed to the dequeued node’s color and enqueues that afterwards
    • else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away, but if it has the opposite color, then continue.
• Finally, the queue becomes empty here, which means it didn’t fall into the identical color consequences. Sure thing, we can safely say the given graph conforms to the bipartite rules.

Here’s the BFS implementation in TypeScript:

enum COLORS = {
  COLORED_RED: 0,
  COLORED_GREEN: 1,
  NOT_COLORED: -1
}

const checkBipartiteBFS = function (
  startingNode: number,
  adj: number[][],
  colors: COLORS[]
): boolean {
  // define a queue and give starting node a color and enqueue it
  const queue: number[] = [];
  colors[startingNode] = 0;
  queue.push(startingNode);

  // run a loop until queue becomes empty
  while (queue.length !== 0) {
    // dequeues a node
    const node = queue.shift() as number;

    // look for its neighbour nodes and do those checking stuffs and all
    for (let j = 0; j < adj[node].length; j++) {
      const neighbourNode = adj[node][j];

      // both the neighbour and dequeued node are having same color, not a bipartite
      if (colors[neighbourNode] === colors[node]) {
        return false;
      }

      // neighbour node is not colored,so color and enqueue it in turn
      if (colors[neighbourNode] === -1) {
        colors[neighbourNode] = (colors[node] + 1) % 2; // 0 becomes 1 and 1 becomes 0
        queue.push(neighbourNode);
      }
    }
  }

  // queue becomes empty here, it is a bipartite graph surely
  return true;
};

A quick Primer on Recursion —

Since DFS is recursive by nature, we don’t push a node into the queue every time we discover an un-colored node. Instead, we invoke the function again with the un-colored node. That’s it. That’s the only major difference to observe.

We are repeating the same thing on each iteration if we look closely at BFS. So why not call the function itself from within itself, but with a different node, otherwise the pitfall of recursion pops up, business as usual (shoutout to Stack Overflow).

With that in mind, let’s look at the steps of the DFS Algorithm for Bipartite:

• entering the function with a node and a color, it starts by giving the node that color in the colors[] array

• fires a loop to see all of its neighbors and look for the following:

  • If the neighbor node is not yet colored, it calls the DFS function again with the neighbor node and a color opposed to the dequeued node’s color. If the call comes back with a “false” value, then there is no need to iterate further; return “false” here as well. Because a rule broken by one node in the graph is enough to call it not a bipartite.

  • else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away with return “false”, but if it has the opposite color, then it continues.

• Lastly, the queue becomes empty here; this node didn’t fall into the identical color consequences. So it returns “true” here, which simply means this node is not the one that breaks the bipartiteness and exits this execution to go back to where the function came from.

Here’s the DFS implementation in TypeScript:

enum COLORS = {
  COLORED_RED: 0,
  COLORED_GREEN: 1,
  NOT_COLORED: -1,
}

const checkBipartiteDFS = function (
  node: number,
  color: 0 | 1,
  colors: COLORS[],
  adjList: number[][]
) {
  // give that node a color
  colors[node] = color;

  // look for its neighbours and do the checking and call the function recursively if needed
  for (const neighbourNode of adjList[node]) {
    // both having the same color, return false right away
    if (colors[neighbourNode] === colors[node]) return false;

    // neighbour node is not yet been colored, so call the function again with the opposite color  
    if (colors[neighbourNode] === -1 && 
        !checkBipartiteDFS(neighbourNode, color === 0 ? 1 : 0, colors, adjList)
     ){      
          return false;    
     }  
   }
  
   // the iteration has been done and this node did not break the bipertiteness, so we return true  
   return true;
};

There you have it. I hope it was helpful. Thanks so much for reading.

You can connect with me on LinkedIn.  There, I share programming-related things just like this one as I learn them.