With a graph structure it is possible that parts of the graph will not be connected to each other.\u00a0 An example of this would be with social networks, not all users are friends with other users.<\/p>\n
The code will find the total number of connected components of the graph, or graph parts in an undirected graph.<\/p>\n
See code below.<\/p>\n
<\/p>\n
#Uses python3\r\n# Given an undirected graph with n vertices and m edges,\r\n# compute the number of connected components in it.\r\n\r\nimport sys\r\n\r\nclass UserGraph:\r\n def __init__(self):\r\n self.data = [] # data list from user\r\n self.edges = [] # convert data list into edges\r\n self.cc = [] #connected components\r\n self.cc_cnt = 0 #connected components count\r\n self.visited = [] # keep track if visited node before\r\n self.adj = [] # adjancency matrix\r\n\r\n def read(self):\r\n \"\"\"read the input data file \"\"\"\r\n input = sys.stdin.read()\r\n self.data = list(map(int, input.split()))\r\n\r\n def explore(self,k_node):\r\n \"\"\"start with k_node and recursively check all edges \"\"\"\r\n self.visited[k_node] = True\r\n self.cc[k_node] = self.cc_cnt\r\n for j in range(len(self.visited)):\r\n if self.adj[k_node][j] and not self.visited[j]:\r\n success = self.explore(j)\r\n\r\n def number_of_components(self):\r\n \"\"\"Test if nodes are connected\r\n use depth first search and determine connected number_of_components\r\n check if nodes are in the same component\r\n \"\"\"\r\n for k_node in range(len(self.adj)):\r\n if not self.visited[k_node]:\r\n self.cc_cnt += 1\r\n self.explore(k_node)\r\n\r\n def process_input(self):\r\n \"\"\"process the input from data file \"\"\"\r\n n, m = self.data[0:2]\r\n self.data = self.data[2:]\r\n self.edges = list(zip(self.data[0:(2 * m):2], self.data[1:(2 * m):2]))\r\n\r\n self.adj = [[0] * n for _ in range(n)]\r\n self.visited = [False] * n # haven't visited any nodes\r\n self.cc = [-1] * n # nothing is connected\r\n\r\n\r\n def populate_adjacency_matrix(self):\r\n \"\"\" create symmetric adjancency matrix for undirected graph \"\"\"\r\n for (a, b) in self.edges:\r\n self.adj[a - 1][b-1] = 1\r\n self.adj[b - 1][a-1] = 1\r\n # print(self.adj)\r\n\r\n def graph_components(self):\r\n self.process_input()\r\n self.populate_adjacency_matrix()\r\n self.number_of_components()\r\n return self.cc_cnt\r\n\r\n\r\nif __name__ == '__main__':\r\n test_Graph = UserGraph()\r\n test_Graph.read()\r\n print(test_Graph.graph_components())<\/pre>\n<\/p>\n","protected":false},"excerpt":{"rendered":"
Testing for Unconnected Components in an Undirected Graph With a graph structure it is possible that parts of the graph will not be connected to each other.\u00a0 An example of this would be with social networks, not all users are friends with other users. The code will find the total number of connected components of […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_crdt_document":"","footnotes":""},"categories":[3,4],"tags":[28,30],"series":[],"class_list":["post-165","post","type-post","status-publish","format-standard","hentry","category-python","category-code","tag-python","tag-code"],"_links":{"self":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/165","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/comments?post=165"}],"version-history":[{"count":1,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/165\/revisions"}],"predecessor-version":[{"id":166,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/165\/revisions\/166"}],"wp:attachment":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/media?parent=165"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/categories?post=165"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/tags?post=165"},{"taxonomy":"series","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/series?post=165"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}