Repository: keon/algorithms
Pull request #347 (2018-06-10 12:13:47)

Created check_bipartite.py in algorithms/graph + test cases
I implemented a function that checks whether the graph is a bipartite graph or not. Also added three different test cases in tests/test_graph.py.

- [X] **If creating a new file :**
  - [X] added links to it in the README files ?
  - [X] included tests with it ?
  - [X] added description (overview of algorithm, time and space compleixty, and possible edge case) in docstrings ?



coveralls: ## Pull Request Test Coverage Report for [Build 602](https://coveralls.io/builds/17412678)

* **25** of **26**   **(96.15%)**  changed or added relevant lines in **2** files are covered.
* **1** unchanged line in **1** file lost coverage.
* Overall coverage increased (+**0.1%**) to **69.739%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/graph/check_bipartite.py](https://coveralls.io/builds/17412678/source?filename=algorithms%2Fgraph%2Fcheck_bipartite.py#L27) | 16 | 17 | 94.12%
<!-- | **Total:** | **25** | **26** | **96.15%** | -->

|  Files with Coverage Reduction | New Missed Lines | % |
| :-----|--------------|--: |
| [algorithms/linkedlist/is_palindrome.py](https://coveralls.io/builds/17412678/source?filename=algorithms%2Flinkedlist%2Fis_palindrome.py#L85) | 1 | 93.33% |
<!-- | **Total:** | **1** |  | -->

|  Totals | [![Coverage Status](https://coveralls.io/builds/17412678/badge)](https://coveralls.io/builds/17412678) |
| :-- | --: |
| Change from base [Build 601](https://coveralls.io/builds/17412219): |  0.1% |
| Covered Lines: | 3390 |
| Relevant Lines: | 4861 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/README.md b/README.md
index 18858ce..0ccc81e 100644
--- a/README.md
+++ b/README.md
@@ -139,6 +139,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
 - [graph](algorithms/graph)
+    - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
     - [clone_graph](algorithms/graph/clone_graph.py)
     - [cycle_detection](algorithms/graph/cycle_detection.py)
diff --git a/README_CN.md b/README_CN.md
index db759e9..7a791bb 100644
--- a/README_CN.md
+++ b/README_CN.md
@@ -142,6 +142,7 @@ pip3 uninstall -y algorithms
     - [regex_matching：正则匹配](algorithms/dp/regex_matching.py)
     - [word_break：单词分割](algorithms/dp/word_break.py)
 - [graph：图](graph)
+    - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [2-sat：2-sat](algorithms/graph/satisfiability.py)
     - [clone_graph：克隆图](algorithms/graph/clone_graph.py)
     - [cycle_detection：判断圈算法](algorithms/graph/cycle_detection.py)
diff --git a/README_GE.md b/README_GE.md
index f0a48ca..1f6c5b3 100644
--- a/README_GE.md
+++ b/README_GE.md
@@ -146,6 +146,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
 - [graph](algorithms/graph)
+    - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
     - [clone_graph](algorithms/graph/clone_graph.py)
     - [cycle_detection](algorithms/graph/cycle_detection.py)
diff --git a/README_JP.md b/README_JP.md
index d50f012..1e0a2d2 100644
--- a/README_JP.md
+++ b/README_JP.md
@@ -140,6 +140,7 @@ if __name__ == "__main__":
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
 - [graph : グラフ](algorithms/graph)
+    - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
     - [clone_graph](algorithms/graph/clone_graph.py)
     - [cycle_detection](algorithms/graph/cycle_detection.py)
diff --git a/README_KR.md b/README_KR.md
index dd78fa0..ff96562 100644
--- a/README_KR.md
+++ b/README_KR.md
@@ -137,6 +137,7 @@ if __name__ == "__main__":
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
 - [graph : 그래프](algorithms/graph)
+    - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
     - [clone_graph](algorithms/graph/clone_graph.py)
     - [cycle_detection](algorithms/graph/cycle_detection.py)
diff --git a/algorithms/graph/__init__.py b/algorithms/graph/__init__.py
index bfb208e..f94f12c 100644
--- a/algorithms/graph/__init__.py
+++ b/algorithms/graph/__init__.py
@@ -1,1 +1,2 @@
 from .tarjan import *
+from .check_bipartite import *
diff --git a/algorithms/graph/check_bipartite.py b/algorithms/graph/check_bipartite.py
new file mode 100644
index 0000000..dacc003
--- /dev/null
+++ b/algorithms/graph/check_bipartite.py
@@ -0,0 +1,39 @@
+"""
+
+Bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets.
+(https://en.wikipedia.org/wiki/Bipartite_graph)
+
+Time complexity is O(|E|)
+Space complexity is O(|V|)
+
+"""
+
+def check_bipartite(adj_list):
+
+    V = len(adj_list)
+
+    # Divide vertexes in the graph into set_type 1 and 2
+    # Initialize all set_types as -1
+    set_type = [-1 for v in range(V)]
+    set_type[0] = 0
+
+    q = [0]
+
+    while q:
+        v = q.pop(0)
+
+        # If there is a self-loop, it cannot be bipartite
+        if adj_list[v][v]:
+            return False
+
+        for u in range(V):
+            if adj_list[v][u]:
+                if set_type[u] == set_type[v]:
+                    return False
+                elif set_type[u] == -1:
+                    # set type of u opposite of v
+                    set_type[u] = 1 - set_type[v]
+                    q.append(u)
+
+    return True
+


Test patch:
diff --git a/tests/test_graph.py b/tests/test_graph.py
index 63937db..d402b86 100644
--- a/tests/test_graph.py
+++ b/tests/test_graph.py
@@ -1,4 +1,5 @@
 from algorithms.graph import Tarjan
+from algorithms.graph import check_bipartite
 
 import unittest
 
@@ -42,3 +43,17 @@ class TestTarjan(unittest.TestCase):
 
         g = Tarjan(example)
         self.assertEqual(g.sccs, [['A', 'B', 'E'], ['C', 'D'], ['F', 'G'], ['H']])
+
+        
+class TestCheckBipartite(unittest.TestCase):
+    
+    def test_check_bipartite(self):
+        
+        adj_list_1 = [[0, 0, 1], [0, 0, 1], [1, 1, 0]]
+        self.assertEqual(True, check_bipartite(adj_list_1))
+        
+        adj_list_2 = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0]]
+        self.assertEqual(True, check_bipartite(adj_list_2))
+        
+        adj_list_3 = [[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]]
+        self.assertEqual(False, check_bipartite(adj_list_3))