graph::is_graph_bipartite::Graph Class Reference

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

Collaboration diagram for graph::is_graph_bipartite::Graph:

Public Member Functions
	Graph (int size=nax)
	Constructor that initializes the graph on creation.
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
std::vector< std::vector< int > >	adj
	size of the graph
std::vector< int >	side
	adj stores the graph as an adjacency list

Static Private Attributes
static const int	nax = 5e5 + 1
	stores the side of the vertex

Detailed Description

Class for representing graph as an adjacency list.

Member Function Documentation

addEdge()

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

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

Parameters

u	is a node or vertex of graph
v	is a node or vertex of graph

                                        {
            adj[u-1].push_back(v-1);
            adj[v-1].push_back(u-1);
        }

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.

                                {
            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;
        }

---

The documentation for this class was generated from the following file:

• graph/is_graph_bipartite.cpp