#### Is Graph Bipartite

F
A
```/**
* @file
*
* @brief Algorithm to check whether a graph is
* [bipartite](https://en.wikipedia.org/wiki/Bipartite_graph)
*
* @details
* A graph is a collection of nodes also called vertices and these vertices
* are connected by edges. A graph is bipartite if its vertices can be
* divided into two disjoint and independent sets U and V such that every edge
* connects a vertex in U to one in V.
*
* The algorithm implemented in this file determines whether the given graph
* is bipartite or not.
*
* <pre>
*  Example - Here is a graph g1 with 5 vertices and is bipartite
*
*     1   4
*    / \ / \
*   2   3   5
*
* Example - Here is a graph G2 with 3 vertices and is not bipartite
*
*   1 --- 2
*    \   /
*      3
*
* </pre>
*
* @author [Akshat Vaya](https://github.com/AkVaya)
*
*/
#include <iostream>
#include <queue>
#include <vector>

/**
* @namespace graph
* @brief Graph algorithms
*/
namespace graph {
/**
* @namespace is_graph_bipartite
* @brief Functions for checking whether a graph is bipartite or not
*/
namespace is_graph_bipartite {
/**
* @brief Class for representing graph as an adjacency list.
*/
class Graph {
private:
int n;  ///< size of the graph

std::vector<std::vector<int> >

std::vector<int> side;  ///< stores the side of the vertex

public:
/**
* @brief Constructor that initializes the graph on creation
* @param size number of vertices of the graph
*/
explicit Graph(int size) {
n = size;
side.resize(n, -1);
}

void addEdge(int u, int v);  /// function to add edges to our graph

bool
is_bipartite();  /// function to check whether the graph is bipartite or not
};

/**
* @brief Function that add an edge between two nodes or vertices of graph
*
* @param u is a node or vertex of graph
* @param v is a node or vertex of graph
*/
void Graph::addEdge(int u, int v) {
}

/**
* @brief function that checks whether the graph is bipartite or not
* the function returns true if the graph is a bipartite graph
* the function returns false if the graph is not a bipartite graph
*
* @details
* Here, side refers to the two disjoint subsets of the bipartite graph.
* Initially, the values of side are set to -1 which is an unassigned state. A
* for loop is run for every vertex of the graph. If the current edge has no
* side assigned to it, then a Breadth First Search operation is performed. If
* two neighbours have the same side then the graph will not be bipartite and
* the value of check becomes false. If and only if each pair of neighbours have
* different sides, the value of check will be true and hence the graph
* bipartite.
*
* @returns `true` if th graph is bipartite
* @returns `false` otherwise
*/
bool Graph::is_bipartite() {
bool check = true;
std::queue<int> q;
for (int current_edge = 0; current_edge < n; ++current_edge) {
if (side[current_edge] == -1) {
q.push(current_edge);
side[current_edge] = 0;
while (q.size()) {
int current = q.front();
q.pop();
for (auto neighbour : adj[current]) {
if (side[neighbour] == -1) {
side[neighbour] = (1 ^ side[current]);
q.push(neighbour);
} else {
check &= (side[neighbour] != side[current]);
}
}
}
}
}
return check;
}
}  // namespace is_graph_bipartite
}  // namespace graph

/**
* Function to test the above algorithm
* @returns none
*/
static void test() {
graph::is_graph_bipartite::Graph G1(
5);  /// creating graph G1 with 5 vertices
/// adding edges to the graphs as per the illustrated example

graph::is_graph_bipartite::Graph G2(
3);  /// creating graph G2 with 3 vertices
/// adding edges to the graphs as per the illustrated example

/// checking whether the graphs are bipartite or not
if (G1.is_bipartite()) {
std::cout << "The given graph G1 is a bipartite graph\n";
} else {
std::cout << "The given graph G1 is not a bipartite graph\n";
}
if (G2.is_bipartite()) {
std::cout << "The given graph G2 is a bipartite graph\n";
} else {
std::cout << "The given graph G2 is not a bipartite graph\n";
}
}

/**
* Main function
*/
int main() {
test();  /// Testing
return 0;
}
```  