Skip to content

Commit bd0074c

Browse files
lemidialemidia
committed
Bipartite Graph Check added
1 parent ac21c2c commit bd0074c

File tree

2 files changed

+204
-1
lines changed

2 files changed

+204
-1
lines changed

‎AlgorithmCode/BipartiteGraphCheckAdjacencyList.java‎

Lines changed: 203 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,203 @@
1+
**
2+
* This file shows you how to determine if a graph is bipartite or not. This can be achieved in
3+
* linear time by coloring the visited nodes.
4+
*
5+
* <p>Time Complexity: O(V + E)
6+
*
7+
* @author William Fiset, william.alexandre.fiset@gmail.com
8+
*/
9+
10+
import com.williamfiset.algorithms.utils.graphutils.Utils;
11+
import java.util.List;
12+
13+
public class BipartiteGraphCheckAdjacencyList {
14+
15+
private int n;
16+
private int[] colors;
17+
private boolean solved;
18+
private boolean isBipartite;
19+
private List<List<Integer>> graph;
20+
21+
public static final int RED = 0b10, BLACK = (RED ^ 1);
22+
23+
public BipartiteGraphCheckAdjacencyList(List<List<Integer>> graph) {
24+
if (graph == null) throw new IllegalArgumentException("Graph cannot be null.");
25+
n = graph.size();
26+
this.graph = graph;
27+
}
28+
29+
// Checks whether the input graph is bipartite.
30+
public boolean isBipartite() {
31+
if (!solved) solve();
32+
return isBipartite;
33+
}
34+
35+
// If the input graph is bipartite it has a two coloring which can be obtained
36+
// through this method. Each index in the returned array is either RED or BLACK
37+
// indicating which color node i was colored.
38+
public int[] getTwoColoring() {
39+
return isBipartite() ? colors : null;
40+
}
41+
42+
private void solve() {
43+
if (n <= 1) return;
44+
45+
colors = new int[n];
46+
int nodesVisited = colorGraph(0, RED);
47+
48+
// The graph is not bipartite. Either not all the nodes were visited or the
49+
// colorGraph method returned -1 meaning the graph is not 2-colorable.
50+
isBipartite = (nodesVisited == n);
51+
solved = true;
52+
}
53+
54+
// Do a depth first search coloring the nodes of the graph as we go.
55+
// This method returns the count of the number of nodes visited while
56+
// coloring the graph or -1 if this graph is not bipartite.
57+
private int colorGraph(int i, int color) {
58+
colors[i] = color;
59+
60+
// Toggles the color between RED and BLACK by exploiting the binary representation
61+
// of the constants and flipping the least significant bit on and off.
62+
int nextColor = (color ^ 1);
63+
64+
int visitCount = 1;
65+
List<Integer> edges = graph.get(i);
66+
67+
for (int to : edges) {
68+
// Contradiction found. In a bipartite graph no two
69+
// nodes of the same color can be next to each other!
70+
if (colors[to] == color) return -1;
71+
if (colors[to] == nextColor) continue;
72+
73+
// If a contradiction is found propagate return -1
74+
// otherwise keep track of the number of visited nodes.
75+
int count = colorGraph(to, nextColor);
76+
if (count == -1) return -1;
77+
visitCount += count;
78+
}
79+
80+
return visitCount;
81+
}
82+
83+
/* Example usage */
84+
85+
public static void main(String[] args) {
86+
87+
// Singleton (not bipartite)
88+
int n = 1;
89+
List<List<Integer>> graph = Utils.createEmptyAdjacencyList(n);
90+
Utils.addUndirectedEdge(graph, 0, 0);
91+
displayGraph(graph);
92+
93+
// Prints:
94+
// Graph has 1 node(s) and the following edges:
95+
// 0 -> 0
96+
// 0 -> 0
97+
// This graph is bipartite: false
98+
99+
// Two nodes one edge between them (bipartite)
100+
n = 2;
101+
graph = Utils.createEmptyAdjacencyList(n);
102+
Utils.addUndirectedEdge(graph, 0, 1);
103+
displayGraph(graph);
104+
105+
// Prints:
106+
// Graph has 2 node(s) and the following edges:
107+
// 0 -> 1
108+
// 1 -> 0
109+
// This graph is bipartite: true
110+
111+
// Triangle graph (not bipartite)
112+
n = 3;
113+
graph = Utils.createEmptyAdjacencyList(n);
114+
Utils.addUndirectedEdge(graph, 0, 1);
115+
Utils.addUndirectedEdge(graph, 1, 2);
116+
Utils.addUndirectedEdge(graph, 2, 0);
117+
displayGraph(graph);
118+
119+
// Prints:
120+
// Graph has 3 node(s) and the following edges:
121+
// 0 -> 1
122+
// 0 -> 2
123+
// 1 -> 0
124+
// 1 -> 2
125+
// 2 -> 1
126+
// 2 -> 0
127+
// This graph is bipartite: false
128+
129+
// Disjoint graph is bipartite connected components (altogether not bipartite)
130+
n = 4;
131+
graph = Utils.createEmptyAdjacencyList(n);
132+
Utils.addUndirectedEdge(graph, 0, 1);
133+
Utils.addUndirectedEdge(graph, 2, 3);
134+
displayGraph(graph);
135+
136+
// Prints:
137+
// Graph has 4 node(s) and the following edges:
138+
// 0 -> 1
139+
// 1 -> 0
140+
// 2 -> 3
141+
// 3 -> 2
142+
// This graph is bipartite: false
143+
144+
// Square graph (bipartite)
145+
n = 4;
146+
graph = Utils.createEmptyAdjacencyList(n);
147+
Utils.addUndirectedEdge(graph, 0, 1);
148+
Utils.addUndirectedEdge(graph, 1, 2);
149+
Utils.addUndirectedEdge(graph, 2, 3);
150+
Utils.addUndirectedEdge(graph, 3, 0);
151+
displayGraph(graph);
152+
153+
// Prints:
154+
// Graph has 4 node(s) and the following edges:
155+
// 0 -> 1
156+
// 0 -> 3
157+
// 1 -> 0
158+
// 1 -> 2
159+
// 2 -> 1
160+
// 2 -> 3
161+
// 3 -> 2
162+
// 3 -> 0
163+
// This graph is bipartite: true
164+
165+
// Square graph with additional edge (not bipartite)
166+
n = 4;
167+
graph = Utils.createEmptyAdjacencyList(n);
168+
Utils.addUndirectedEdge(graph, 0, 1);
169+
Utils.addUndirectedEdge(graph, 1, 2);
170+
Utils.addUndirectedEdge(graph, 2, 3);
171+
Utils.addUndirectedEdge(graph, 3, 0);
172+
Utils.addUndirectedEdge(graph, 0, 2);
173+
displayGraph(graph);
174+
175+
// Prints:
176+
// Graph has 4 node(s) and the following edges:
177+
// 0 -> 1
178+
// 0 -> 3
179+
// 0 -> 2
180+
// 1 -> 0
181+
// 1 -> 2
182+
// 2 -> 1
183+
// 2 -> 3
184+
// 2 -> 0
185+
// 3 -> 2
186+
// 3 -> 0
187+
// This graph is bipartite: false
188+
189+
}
190+
191+
private static void displayGraph(List<List<Integer>> graph) {
192+
final int n = graph.size();
193+
194+
System.out.println("Graph has " + n + " node(s) and the following edges:");
195+
for (int f = 0; f < n; f++) for (int t : graph.get(f)) System.out.println(f + " -> " + t);
196+
197+
BipartiteGraphCheckAdjacencyList solver;
198+
solver = new BipartiteGraphCheckAdjacencyList(graph);
199+
200+
System.out.println("This graph is bipartite: " + (solver.isBipartite()));
201+
System.out.println();
202+
}
203+
}

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -156,7 +156,7 @@ In mathematics and computer science, an algorithm is a finite sequence of well-d
156156
- [Min Cost Max Flow](https://github.com/lemidia/Algorithm-and-Data-Structure/blob/master/AlgorithmCode/MinCostMaxFlow.java) - 최소비용 최대유량 알고리즘, 최소비용에는 SPFA Algorithm, 최대비용에는 Edmonds Karp Algorithm 적용
157157

158158
### Bipartite Matching - 이분매칭
159-
- Bipartite Matching - DFS Manner
159+
- [Bipartite Matching](https://github.com/lemidia/Algorithm-and-Data-Structure/blob/master/BipartiteGraphCheckAdjacencyList.java) - DFS Manner
160160

161161
### Strongly Connected Component - 강한 연결 요소
162162
- [Tarjan's Algorithm](https://github.com/lemidia/Algorithm-and-Data-Structure/blob/master/AlgorithmCode/TarjanScc.java) - O(V+E)

0 commit comments

Comments
 (0)