Search for the largest connected component in the graph of the controller matrix?

Question

I am trying to figure this out, there is a way to find the largest connected component in the matrix column adj. For instance:

0000000110 0001100000 0000000000 0100000010 0100000100 0000000100 0000000000 1000110000 1001000000 0000000000 

I have a problem with Google, and I am struggling to find something, I also read an article on wikis on graph theory and without joy. I assume that they should be an algorithm to solve this problem. Can someone point me in the right direction and give me some guidance on what I should do to solve this myself?

Answer 1

Select a starting point and start “walking” to other nodes until you exhaust yourself. Do this until you find all the components. This will work in O(n) , where n is the size of the graph.

Skeleton solutions in Python:

 class Node(object): def __init__(self, index, neighbors): self.index = index # A set of indices (integers, not Nodes) self.neighbors = set(neighbors) def add_neighbor(self, neighbor): self.neighbors.add(neighbor) class Component(object): def __init__(self, nodes): self.nodes = nodes self.adjacent_nodes = set() for node in nodes: self.adjacent_nodes.add(node.index) self.adjacent_nodes.update(node.neighbors) @property def size(self): return len(self.nodes) @property def node_indices(self): return set(node.index for node in self.nodes) @property def is_saturated(self): return self.node_indices == self.adjacent_nodes def add_node(self, node): self.nodes.append(node) self.adjacent_nodes.update(node.neighbors) adj_matrix = [[0, 0, 0, 0, 0, 0, 0, 1, 1, 0], [0, 0, 0, 1, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 1, 0], [0, 1, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 1, 1, 0, 0, 0, 0], [1, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] matrix_size = len(adj_matrix) nodes = {} for index in range(matrix_size): neighbors = [neighbor for neighbor, value in enumerate(adj_matrix[index]) if value == 1] nodes[index] = Node(index, neighbors) components = [] index, node = nodes.popitem() component = Component([node]) while nodes: if not component.is_saturated: missing_node_index = component.adjacent_nodes.difference(component.node_indices).pop() missing_node = nodes.pop(missing_node_index) component.add_node(missing_node) else: components.append(component) index, node = nodes.popitem() component = Component([node]) # Final component needs to be appended as well components.append(component) print max([component.size for component in components]) 

Answer 2

• Apply an algorithm for related components.

  For an undirected graph, just select node and do a width search. If there are any nodes left after the first BFS, select one of the left frames and execute another BFS. (You get one connected component on BFS.)

  Note that oriented graphics require a slightly stronger algorithm to find highly related components. The Kosaraju algorithm comes to mind.

• Count the number of nodes in each of the connected components from (1). Choose the largest.

Answer 3

 #include<iostream> #include<cstdlib> #include<list> using namespace std; class GraphDfs { private: int v; list<int> *adj; int *label; int DFS(int v,int size_connected) { size_connected++; cout<<(v+1)<<" "; label[v]=1; list<int>::iterator i; for(i=adj[v].begin();i!=adj[v].end();++i) { if(label[*i]==0) { size_connected=DFS(*i,size_connected); } } return size_connected; } public: GraphDfs(int k) { v=k; adj=new list<int>[v]; label=new int[v]; for(int i=0;i<v;i++) { label[i]=0; } } void DFS() { int flag=0; int size_connected=0; int max=0; for(int i=0;i<v;i++) { size_connected=0; if(label[i]==0) { size_connected=DFS(i,size_connected); max=size_connected>max?size_connected:max; cout<<size_connected<<endl; flag++; } } cout<<endl<<"The number of connected compnenets are "<<flag<<endl; cout<<endl<<"The size of largest connected component is "<<max<<endl; //cout<<cycle; } void insert() { int u=0;int a=0;int flag=1; while(flag==1) { cout<<"Enter the edges in (u,v) form"<<endl; cin>>u>>a; adj[a-1].push_back(u-1); adj[u-1].push_back(a-1); cout<<"Do you want to enter more??1/0 "<<endl; cin>>flag; } } }; int main() { cout<<"Enter the number of vertices"<<endl; int v=0; cin>>v; GraphDfs g(v); g.insert(); g.DFS(); system("Pause"); }