{"id":27021,"date":"2018-01-02T20:53:46","date_gmt":"2018-01-02T15:23:46","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27021"},"modified":"2018-01-02T20:53:46","modified_gmt":"2018-01-02T15:23:46","slug":"python-programming-biconnected-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-biconnected-graph\/","title":{"rendered":"PYTHON Programming – Biconnected graph"},"content":{"rendered":"

An undirected graph is called Biconnected if there are two vertex-disjoint paths between any two vertices. <\/span>In a Biconnected Graph, there is a simple cycle through any two vertices.
\nBy convention, two nodes connected by an edge form a biconnected graph, but this does not verify the above properties. For a graph with more than two vertices, the above properties must be there for it to be Biconnected.<\/p>\n

Following are some examples.<\/p>\n

How to find if a given graph is Biconnected or not?<\/strong>
\nA connected graph is Biconnected if it is connected and doesn\u2019t have any Articulation Point<\/a><\/em>. We mainly need to check two things in a graph.
\n1) The graph is connected.
\n2) There is not articulation point in graph.<\/p>\n[ad type=\u201dbanner\u201d]\n

We start from any vertex and do DFS traversal. In DFS traversal, we check if there is any articulation point. If we don\u2019t find any articulation point, then the graph is Biconnected. Finally, we need to check whether all vertices were reachable in DFS or not. If all vertices were not reachable, then the graph is not even connected.<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20find%20if%20a%20given%20undirected%20graph%20is%0A%23%20biconnected%0A%20%20%0Afrom%20collections%20import%20defaultdict%0A%20%20%0A%23This%20class%20represents%20an%20undirected%20graph%20using%20adjacency%20list%20representation%0Aclass%20Graph%3A%0A%20%20%0A%20%20%20%20def%20__init__(self%2Cvertices)%3A%0A%20%20%20%20%20%20%20%20self.V%3D%20vertices%20%23No.%20of%20vertices%0A%20%20%20%20%20%20%20%20self.graph%20%3D%20defaultdict(list)%20%23%20default%20dictionary%20to%20store%20graph%0A%20%20%20%20%20%20%20%20self.Time%20%3D%200%0A%20%20%0A%20%20%20%20%23%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20def%20addEdge(self%2Cu%2Cv)%3A%0A%20%20%20%20%20%20%20%20self.graph%5Bu%5D.append(v)%0A%20%20%20%20%20%20%20%20self.graph%5Bv%5D.append(u)%0A%20%20%0A%20%20%20%20\u201d\u2019A%20recursive%20function%20that%20returns%20true%20if%20there%20is%20an%20articulation%0A%20%20%20%20point%20in%20given%20graph%2C%20otherwise%20returns%20false.%0A%20%20%20%20This%20function%20is%20almost%20same%20as%20isAPUtil()%0A%20%20%20%20u%20\u2013%3E%20The%20vertex%20to%20be%20visited%20next%0A%20%20%20%20visited%5B%5D%20\u2013%3E%20keeps%20tract%20of%20visited%20vertices%0A%20%20%20%20disc%5B%5D%20\u2013%3E%20Stores%20discovery%20times%20of%20visited%20vertices%0A%20%20%20%20parent%5B%5D%20\u2013%3E%20Stores%20parent%20vertices%20in%20DFS%20tree\u201d\u2019%0A%20%20%20%20def%20isBCUtil(self%2Cu%2C%20visited%2C%20parent%2C%20low%2C%20disc)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23Count%20of%20children%20in%20current%20node%20%0A%20%20%20%20%20%20%20%20children%20%3D0%0A%20%0A%20%20%20%20%20%20%20%20%23%20Mark%20the%20current%20node%20as%20visited%20and%20print%20it%0A%20%20%20%20%20%20%20%20visited%5Bu%5D%3D%20True%0A%20%0A%20%20%20%20%20%20%20%20%23%20Initialize%20discovery%20time%20and%20low%20value%0A%20%20%20%20%20%20%20%20disc%5Bu%5D%20%3D%20self.Time%0A%20%20%20%20%20%20%20%20low%5Bu%5D%20%3D%20self.Time%0A%20%20%20%20%20%20%20%20self.Time%20%2B%3D%201%0A%20%0A%20%20%20%20%20%20%20%20%23Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20%20%20%20%20for%20v%20in%20self.graph%5Bu%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20v%20is%20not%20visited%20yet%2C%20then%20make%20it%20a%20child%20of%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20in%20DFS%20tree%20and%20recur%20for%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20visited%5Bv%5D%20%3D%3D%20False%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bv%5D%20%3D%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20children%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20self.isBCUtil(v%2C%20visited%2C%20parent%2C%20low%2C%20disc)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Check%20if%20the%20subtree%20rooted%20with%20v%20has%20a%20connection%20to%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20one%20of%20the%20ancestors%20of%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20low%5Bu%5D%20%3D%20min(low%5Bu%5D%2C%20low%5Bv%5D)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20u%20is%20an%20articulation%20point%20in%20following%20cases%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20(1)%20u%20is%20root%20of%20DFS%20tree%20and%20has%20two%20or%20more%20chilren.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20parent%5Bu%5D%20%3D%3D%20-1%20and%20children%20%3E%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23(2)%20If%20u%20is%20not%20root%20and%20low%20value%20of%20one%20of%20its%20child%20is%20more%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20than%20discovery%20value%20of%20u.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20parent%5Bu%5D%20!%3D%20-1%20and%20low%5Bv%5D%20%3E%3D%20disc%5Bu%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20elif%20v%20!%3D%20parent%5Bu%5D%3A%20%23%20Update%20low%20value%20of%20u%20for%20parent%20function%20calls.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20low%5Bu%5D%20%3D%20min(low%5Bu%5D%2C%20disc%5Bv%5D)%0A%20%0A%20%20%20%20%20%20%20%20return%20False%0A%20%0A%20%0A%20%20%20%20%23%20The%20main%20function%20that%20returns%20true%20if%20graph%20is%20Biconnected%2C%0A%20%20%20%20%23%20otherwise%20false.%20It%20uses%20recursive%20function%20isBCUtil()%0A%20%20%20%20def%20isBC(self)%3A%0A%20%20%0A%20%20%20%20%20%20%20%20%23%20Mark%20all%20the%20vertices%20as%20not%20visited%20and%20Initialize%20parent%20and%20visited%2C%20%0A%20%20%20%20%20%20%20%20%23%20and%20ap(articulation%20point)%20arrays%0A%20%20%20%20%20%20%20%20visited%20%3D%20%5BFalse%5D%20*%20(self.V)%0A%20%20%20%20%20%20%20%20disc%20%3D%20%5Bfloat(%22Inf%22)%5D%20*%20(self.V)%0A%20%20%20%20%20%20%20%20low%20%3D%20%5Bfloat(%22Inf%22)%5D%20*%20(self.V)%0A%20%20%20%20%20%20%20%20parent%20%3D%20%5B-1%5D%20*%20(self.V)%0A%20%20%20%20%20%0A%20%0A%20%20%20%20%20%20%20%20%23%20Call%20the%20recursive%20helper%20function%20to%20find%20if%20there%20is%20an%20%0A%20%20%20%20%20%20%20%20%23%20articulation%20points%20in%20given%20graph.%20We%20do%20DFS%20traversal%20starting%0A%20%20%20%20%20%20%20%20%23%20from%20vertex%200%0A%20%20%20%20%20%20%20%20if%20self.isBCUtil(0%2C%20visited%2C%20parent%2C%20low%2C%20disc)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20False%0A%20%0A%20%20%20%20%20%20%20%20\u201d\u2019Now%20check%20whether%20the%20given%20graph%20is%20connected%20or%20not.%0A%20%20%20%20%20%20%20%20An%20undirected%20graph%20is%20connected%20if%20all%20vertices%20are%0A%20%20%20%20%20%20%20%20reachable%20from%20any%20starting%20point%20(we%20have%20taken%200%20as%0A%20%20%20%20%20%20%20%20starting%20point)\u201d\u2019%0A%20%20%20%20%20%20%20%20if%20any(i%20%3D%3D%20False%20for%20i%20in%20visited)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20False%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20True%0A%20%20%0A%23%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0Ag1%20%3D%20%20Graph(2)%0Ag1.addEdge(0%2C%201)%0Aprint%20%22Yes%22%20if%20g1.isBC()%20else%20%22No%22%0A%20%0Ag2%20%3D%20Graph(5)%0Ag2.addEdge(1%2C%200)%0Ag2.addEdge(0%2C%202)%0Ag2.addEdge(2%2C%201)%0Ag2.addEdge(0%2C%203)%0Ag2.addEdge(3%2C%204)%0Ag2.addEdge(2%2C%204)%0Aprint%20%22Yes%22%20if%20g2.isBC()%20else%20%22No%22%0A%20%0Ag3%20%3D%20Graph(3)%0Ag3.addEdge(0%2C%201)%0Ag3.addEdge(1%2C%202)%0Aprint%20%22Yes%22%20if%20g3.isBC()%20else%20%22No%22%0A%20%0A%20%20%0Ag4%20%3D%20Graph%20(5)%0Ag4.addEdge(1%2C%200)%0Ag4.addEdge(0%2C%202)%0Ag4.addEdge(2%2C%201)%0Ag4.addEdge(0%2C%203)%0Ag4.addEdge(3%2C%204)%0Aprint%20%22Yes%22%20if%20g4.isBC()%20else%20%22No%22%0A%20%0Ag5%20%3D%20Graph(3)%0Ag5.addEdge(0%2C%201)%0Ag5.addEdge(1%2C%202)%0Ag5.addEdge(2%2C%200)%0Aprint%20%22Yes%22%20if%20g5.isBC()%20else%20%22No%22\u2033 message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Output:<\/p>\n

Yes\r\nYes\r\nNo\r\nNo\r\nYes<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
PYTHON Programming – Biconnected graph – An undirected graph is called Biconnected if there are two vertex – disjoint paths between any two vertices.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[78385,73906],"tags":[79016,78213,78212,78208,78207,78216,80658],"class_list":["post-27021","post","type-post","status-publish","format-standard","hentry","category-connectivity","category-graph-algorithms","tag-biconnected-components-and-articulation-points","tag-biconnected-components-and-articulation-points-ppt","tag-biconnected-components-of-an-undirected-graph","tag-biconnected-components-pdf","tag-biconnected-graph-example","tag-what-is-articulation-point","tag-what-is-biconnected-components"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27021","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27021"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27021\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27021"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27021"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27021"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}