Reputation: 111
I was searching for a c++ code to find connected components in an undirected graph. I have a big matrix which is called "directed". Its elements are zero or one. directed(i,j)=1 means i vertice has a directed link to j vertice. I want to find the number of different groups created by directly or indirectly connection of vertices and size of the groups. Below code takes connected vertices and print different groups' elements in different lines. Knowing directed matrix, could anyone help me to find the number of groups and size of each of them? This is the code:
// C++ program to print connected components in
// an undirected graph
#include<iostream>
#include <list>
using namespace std;
// Graph class represents a undirected graph
// using adjacency list representation
int input(istream& in=cin)
{
int x;
in >> x;
return x;
}
class Graph
{
int V; // No. of vertices
// Pointer to an array containing adjacency lists
list<int> *adj;
// A function used by DFS
void DFSUtil(int v, bool visited[]);
public:
Graph(int V); // Constructor
void addEdge(int v, int w);
void connectedComponents();
};
// Method to print connected components in an
// undirected graph
void Graph::connectedComponents()
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int v = 0; v < V; v++)
visited[v] = false;
for (int v=0; v<V; v++)
{
if (visited[v] == false)
{
// print all reachable vertices
// from v
DFSUtil(v, visited);
cout << "\n";
}
}
}
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";
// Recur for all the vertices
// adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
if(!visited[*i])
DFSUtil(*i, visited);
}
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
// method to add an undirected edge
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
// Drive program to test above
int main()
{
int directed[2][2];
directed[0][0]=1;
directed[0][1]=0;
directed[0][2]=0;
directed[1][1]=1;
directed[1][0]=1;
directed[1][2]=1;
directed[2][1]=0;
directed[2][2]=0;
directed[2][0]=1;
return 0;
}
Upvotes: 1
Views: 5584
Reputation: 394054
Could you please provide a runnable answer (x4)
Sure:
// C++ program to print connected components in
// an undirected graph
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
// Graph class represents a undirected graph
// using adjacency list representation
class Graph {
using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using Component = int;
using Mapping = std::map<G::vertex_descriptor, Component>;
G g;
public:
Graph(int V) : g(V) {}
void addEdge(int v, int w);
void connectedComponents();
};
// Method to print connected components in an
// undirected graph
void Graph::connectedComponents() {
Mapping mappings;
int n = boost::connected_components(g, boost::make_assoc_property_map(mappings));
for (Component c = 0; c<n; ++c) {
std::cout << "component " << c << ":";
for (auto& mapping : mappings)
if (mapping.second == c) std::cout << " " << mapping.first;
std::cout << "\n";
}
}
void Graph::addEdge(int v, int w) {
boost::add_edge(v, w, g);
}
int main() {
// Create a graph given in the above diagram
Graph g(5); // 5 vertices numbered from 0 to 4
g.addEdge(1, 0);
g.addEdge(2, 3);
g.addEdge(3, 4);
std::cout << "Following are connected components \n";
g.connectedComponents();
}
Prints
Following are connected components
component 0: 0 1
component 1: 2 3 4
Upvotes: 2
Reputation: 1621
Modify the DFSUtil
methord to return an int
the specifies the number of nodes visited.
int Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
int count = 0;
cout << v << " ";
// Recur for all the vertices
// adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
if(!visited[*i])
count += DFSUtil(*i, visited, count + 1);
else
return 1;
return count;
}
And with some booking keeping we'll know know many groups and the size of each group from this
// Method to print connected components in an
// undirected graph
void Graph::connectedComponents()
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int v = 0; v < V; v++)
visited[v] = false;
vector<pair<int,int>> groups;
for (int v=0; v<V; v++)
{
if (visited[v] == false)
{
// print all reachable vertices
// from v
int groupSize = DFSUtil(v, visited);
groups.push_back(make_pair(v, groupSize))
cout << "\n";
}
}
}
Upvotes: 1