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)
	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.
bool	is_bipartite ()
	function to add edges to our graph

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.

Definition at line 51 of file is_graph_bipartite.cpp.

Constructor & Destructor Documentation

Graph()

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

inlineexplicit

Constructor that initializes the graph on creation.

Parameters

size	number of vertices of the graph

Definition at line 65 of file is_graph_bipartite.cpp.

                             {
        n = size;
        adj.resize(n);
        side.resize(n, -1);
    }

Member Function Documentation

addEdge()

void graph::is_graph_bipartite::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

Definition at line 83 of file is_graph_bipartite.cpp.

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

is_bipartite()

bool graph::is_graph_bipartite::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

Definition at line 106 of file is_graph_bipartite.cpp.

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

Member Data Documentation

adj

std::vector<std::vector<int> > graph::is_graph_bipartite::Graph::adj

private

adj stores the graph as an adjacency list

Definition at line 56 of file is_graph_bipartite.cpp.

n

int graph::is_graph_bipartite::Graph::n

private

size of the graph

Definition at line 53 of file is_graph_bipartite.cpp.

side

std::vector<int> graph::is_graph_bipartite::Graph::side

private

stores the side of the vertex

Definition at line 58 of file is_graph_bipartite.cpp.

---

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

• graph/is_graph_bipartite.cpp