```
/**
* @brief Check whether a given graph is bipartite or not
* @details
* A bipartite graph is the one whose nodes can be divided into two
* disjoint sets in such a way that the nodes in a set are not
* connected to each other at all, i.e. no intra-set connections.
* The only connections that exist are that of inter-set,
* i.e. the nodes from one set are connected to a subset of nodes
* in the other set.
* In this implementation, using a graph in the form of adjacency
* list, check whether the given graph is a bipartite or not.
*
* References used:
* [GeeksForGeeks](https://www.geeksforgeeks.org/bipartite-graph/)
* @author [tushar2407](https://github.com/tushar2407)
*/
#include <cassert> /// for assert
#include <iostream> /// for IO operations
#include <queue> /// for queue data structure
#include <vector> /// for vector data structure
/**
* @namespace graph
* @brief Graphical algorithms
*/
namespace graph {
/**
* @brief function to check whether the passed graph is bipartite or not
* @param graph is a 2D matrix whose rows or the first index signify the node
* and values in that row signify the nodes it is connected to
* @param index is the valus of the node currently under observation
* @param visited is the vector which stores whether a given node has been
* traversed or not yet
* @returns boolean
*/
bool checkBipartite(const std::vector<std::vector<int64_t>> &graph,
int64_t index, std::vector<int64_t> *visited) {
std::queue<int64_t> q; ///< stores the neighbouring node indexes in squence
/// of being reached
q.push(index); /// insert the current node into the queue
(*visited)[index] = 1; /// mark the current node as travelled
while (q.size()) {
int64_t u = q.front();
q.pop();
for (uint64_t i = 0; i < graph[u].size(); i++) {
int64_t v =
graph[u][i]; ///< stores the neighbour of the current node
if (!(*visited)[v]) /// check whether the neighbour node is
/// travelled already or not
{
(*visited)[v] =
((*visited)[u] == 1)
? -1
: 1; /// colour the neighbouring node with
/// different colour than the current node
q.push(v); /// insert the neighbouring node into the queue
} else if ((*visited)[v] ==
(*visited)[u]) /// if both the current node and its
/// neighbour has the same state then it
/// is not a bipartite graph
{
return false;
}
}
}
return true; /// return true when all the connected nodes of the current
/// nodes are travelled and satisify all the above conditions
}
/**
* @brief returns true if the given graph is bipartite else returns false
* @param graph is a 2D matrix whose rows or the first index signify the node
* and values in that row signify the nodes it is connected to
* @returns booleans
*/
bool isBipartite(const std::vector<std::vector<int64_t>> &graph) {
std::vector<int64_t> visited(
graph.size()); ///< stores boolean values
/// which signify whether that node had been visited or
/// not
for (uint64_t i = 0; i < graph.size(); i++) {
if (!visited[i]) /// if the current node is not visited then check
/// whether the sub-graph of that node is a bipartite
/// or not
{
if (!checkBipartite(graph, i, &visited)) {
return false;
}
}
}
return true;
}
} // namespace graph
/**
* @brief Self-test implementations
* @returns void
*/
static void test() {
std::vector<std::vector<int64_t>> graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
assert(graph::isBipartite(graph) ==
true); /// check whether the above
/// defined graph is indeed bipartite
std::vector<std::vector<int64_t>> graph_not_bipartite = {
{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
assert(graph::isBipartite(graph_not_bipartite) ==
false); /// check whether
/// the above defined graph is indeed bipartite
std::cout << "All tests have successfully passed!\n";
}
/**
* @brief Main function
* Instantitates a dummy graph of a small size with
* a few edges between random nodes.
* On applying the algorithm, it checks if the instantiated
* graph is bipartite or not.
* @returns 0 on exit
*/
int main() {
test(); // run self-test implementations
return 0;
}
```