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+ }
0 commit comments