Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
graph::is_graph_bipartite::Graph Class Reference

Class for representing graph as an adjacency list. More...

Collaboration diagram for graph::is_graph_bipartite::Graph:
[legend]

Public Member Functions

 Graph (int size)
 Constructor that initializes the graph on creation. More...
 
void addEdge (int u, int v)
 Function that add an edge between two nodes or vertices of graph. More...
 
bool is_bipartite ()
 function to add edges to our graph More...
 

Private Attributes

int n
 size of the graph
 
std::vector< std::vector< int > > adj
 adj stores the graph as an adjacency list
 
std::vector< int > side
 stores the side of the vertex
 

Detailed Description

Class for representing graph as an adjacency list.

Constructor & Destructor Documentation

◆ Graph()

graph::is_graph_bipartite::Graph::Graph ( int  size)
inlineexplicit

Constructor that initializes the graph on creation.

Parameters
sizenumber of vertices of the graph
65  {
66  n = size;
67  adj.resize(n);
68  side.resize(n, -1);
69  }

Member Function Documentation

◆ addEdge()

void Graph::addEdge ( int  u,
int  v 
)

Function that add an edge between two nodes or vertices of graph.

Parameters
uis a node or vertex of graph
vis a node or vertex of graph
83  {
84  adj[u - 1].push_back(v - 1);
85  adj[v - 1].push_back(u - 1);
86 }
Here is the call graph for this function:

◆ is_bipartite()

bool Graph::is_bipartite ( )

function to add edges to our graph

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

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
false otherwise
106  {
107  bool check = true;
108  std::queue<int> q;
109  for (int current_edge = 0; current_edge < n; ++current_edge) {
110  if (side[current_edge] == -1) {
111  q.push(current_edge);
112  side[current_edge] = 0;
113  while (q.size()) {
114  int current = q.front();
115  q.pop();
116  for (auto neighbour : adj[current]) {
117  if (side[neighbour] == -1) {
118  side[neighbour] = (1 ^ side[current]);
119  q.push(neighbour);
120  } else {
121  check &= (side[neighbour] != side[current]);
122  }
123  }
124  }
125  }
126  }
127  return check;
128 }

The documentation for this class was generated from the following file:
std::vector::resize
T resize(T... args)
std::queue
STL class.
std::vector::push_back
T push_back(T... args)
graph::is_graph_bipartite::Graph::adj
std::vector< std::vector< int > > adj
adj stores the graph as an adjacency list
Definition: is_graph_bipartite.cpp:56
graph::is_graph_bipartite::Graph::side
std::vector< int > side
stores the side of the vertex
Definition: is_graph_bipartite.cpp:58
graph::is_graph_bipartite::Graph::n
int n
size of the graph
Definition: is_graph_bipartite.cpp:53