// Graph class represents a undirected graph

// using adjacency list representation

// Method to label connected components in an

// undirected graph

#include "graph.h"

// Insert a new node in the Graph

//

void Graph::addNode()

{

nodeGraph n;

vector<int> adjM;

n.cLabel = -1; // label Communit -1 as default

nodes.push_back(n);

adj.resize(nodes.size());

}

Graph::Graph()

{

// adj = new list<int>;

}

Graph::Graph(int qtyNodes)

{

for (int i = 0; i < qtyNodes; i++)

addNode();

adj.resize(qtyNodes);

}

//

// Insert a new edge in the graph

// return false if any of nodes doesn't exist

//

bool Graph::addEdge(int n, int m)

{

if (n < 0 || n >= nodes.size() || m < 0 || m >= nodes.size())

return false;

adj[n].push_back(m);

adj[m].push_back(n);

return true;

}

int Graph::getNumberNodes()

{

return nodes.size();

}

int Graph::getClassLabel(int n)

{

if (n < 0 || n >= nodes.size())

return -2;

return nodes[n].cLabel;

}

void Graph::DFSUtil(int n, int cLabel, bool visited[])

{

// Mark the current node as visited and print it

visited[n] = true;

nodes[n].cLabel = cLabel;

// Recur for all the vertices

// adjacent to this vertex

for(int i = 0; i < adj[n].size(); ++i)

{

int m = adj[n][i];

if(!visited[m])

DFSUtil(m, cLabel, visited);

}

}

void Graph::connectedComponents()

{

// Mark all the vertices as not visited

bool *visited = new bool[nodes.size()];

for(int n = 0; n < nodes.size(); n++)

visited[n] = false;

int classLabel = 0;

for (int n=0; n<nodes.size(); n++)

{

if (visited[n] == false)

{

// print all reachable vertices

// from v

DFSUtil(n, classLabel, visited);

classLabel++;

}

}

}