LC_Bi-Partite Graph Testing.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "5. Is Graph Bipartite?\n",
    "\n",
    "Given a graph, return true if and only if it is bipartite.\n",
    "\n",
    "Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.\n",
    "\n",
    "The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists.  Each node is an integer between 0 and graph.length - 1.  There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.\n",
    "\n",
    "Example 1:\n",
    "Input: [[1,3], [0,2], [1,3], [0,2]]\n",
    "Output: true\n",
    "Explanation: \n",
    "The graph looks like this:\n",
    "0----1\n",
    "|    |\n",
    "|    |\n",
    "3----2\n",
    "We can divide the vertices into two groups: {0, 2} and {1, 3}.\n",
    "\n",
    "Example 2:\n",
    "Input: [[1,2,3], [0,2], [0,1,3], [0,2]]\n",
    "Output: false\n",
    "Explanation: \n",
    "The graph looks like this:\n",
    "0----1\n",
    "| \\  |\n",
    "|  \\ |\n",
    "3----2\n",
    "We cannot find a way to divide the set of nodes into two independent ubsets.\n",
    "Note:\n",
    "\n",
    "    graph will have length in range [1, 100].\n",
    "    graph[i] will contain integers in range [0, graph.length - 1].\n",
    "    graph[i] will not contain i or duplicate values.\n",
    "\n",
    "Approach:\n",
    "========\n",
    "Assign RED color to the source vertex (putting into set U).\n",
    "Color all the neighbors with BLUE color (putting into set V).\n",
    "Color all neighbor’s neighbor with RED color (putting into set U).\n",
    "This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.\n",
    "While assigning colors, if we find a neighbor which is colored with same color as current vertex, then the graph cannot be colored with 2 vertices (or graph is not Bipartite).\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def isBipartite(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        Color  = dict()        \n",
    "        for i in range(0,len(graph)):\n",
    "            mycolor = \"none\"\n",
    "            if (i in Color):\n",
    "                mycolor = Color[i]\n",
    "            else:\n",
    "                peer_color = \"none\"\n",
    "                for n in graph[i]:\n",
    "                    if (n  not in Color):\n",
    "                        continue;\n",
    "                    if (peer_color == \"none\"):\n",
    "                        peer_color = Color[n]\n",
    "                    else:\n",
    "                        if (peer_color != Color[n]):\n",
    "                            return False;\n",
    "                if (peer_color == \"red\"):\n",
    "                    mycolor = \"black\"\n",
    "                elif (peer_color == \"none\" or peer_color ==\"black\"):\n",
    "                    mycolor = \"red\"\n",
    "            \n",
    "            for n in graph[i]:\n",
    "                if (n not in Color):\n",
    "                    if (mycolor == \"red\"):\n",
    "                        Color[n] = \"black\"\n",
    "                    else:\n",
    "                        Color[n] = \"red\"\n",
    "                else:\n",
    "                    if (Color[n] == mycolor):\n",
    "                        return False\n",
    "        \n",
    "        return True;    \n",
    "                    \n",
    "mySol = Solution()\n",
    "print (mySol.isBipartite([[1,3], [0,2], [1,3], [0,2]]))\n",
    "print (mySol.isBipartite([[1,2,3], [0,2], [0,1,3], [0,2]]))\n",
    "        \n",
    " "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}