{"id":28364,"date":"2017-12-24T15:24:16","date_gmt":"2017-12-24T09:54:16","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=28364"},"modified":"2017-12-24T15:24:16","modified_gmt":"2017-12-24T09:54:16","slug":"python-programming-biconnected-components","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-biconnected-components\/","title":{"rendered":"PYTHON PROGRAMMING &#8211; Biconnected Components"},"content":{"rendered":"<p>A biconnected component is a maximal biconnected subgraph.<span id=\"more-133356\"><\/span><\/p>\n<p>Biconnected Graph is already discussed here. In this article, we will see how to find biconnected component in a graph using algorithm by John Hopcroft and Robert Tarjan.<\/p>\n<p>In above graph, following are the biconnected components:<\/p>\n<ul>\n<li>4\u20132 3\u20134 3\u20131 2\u20133 1\u20132<\/li>\n<li>8\u20139<\/li>\n<li>8\u20135 7\u20138 5\u20137<\/li>\n<li>6\u20130 5\u20136 1\u20135 0\u20131<\/li>\n<li>10\u201311<\/li>\n<\/ul>\n[ad type=\u201dbanner\u201d]\n<p>Algorithm is based on Disc and Low Values discussed in Strongly Connected Components Article.<\/p>\n<p>Idea is to store visited edges in a stack while DFS on a graph and keep looking for Articulation Points (highlighted in above figure). As soon as an Articulation Point u is found, all edges visited while DFS from node u onwards will form one biconnected component. When DFS completes for one connected component, all edges present in stack will form a biconnected component.<br \/>\nIf there is no Articulation Point in graph, then graph is biconnected and so there will be one biconnected component which is the graph itself.<\/p>\n<p>PYTHON PROGRAMMING:<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20find%20biconnected%20components%20in%20a%20given%0A%23%20%20undirected%20graph%0A%23Complexity%20%3A%20O(V%2BE)%0A%20%0A%20%20%0Afrom%20collections%20import%20defaultdict%0A%20%20%0A%23This%20class%20represents%20an%20directed%20graph%20%0A%23%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%20%23No.%20of%20vertices%0A%20%20%20%20%20%20%20%20self.V%3D%20vertices%20%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20default%20dictionary%20to%20store%20graph%0A%20%20%20%20%20%20%20%20self.graph%20%3D%20defaultdict(list)%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20time%20is%20used%20to%20find%20discovery%20times%0A%20%20%20%20%20%20%20%20self.Time%20%3D%200%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Count%20is%20number%20of%20biconnected%20components%0A%20%20%20%20%20%20%20%20self.count%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)%20%0A%20%20%20%20%20%20%20%20self.graph%5Bv%5D.append(u)%0A%20%0A%20%20%20%20\u201d\u2019A%20recursive%20function%20that%20finds%20and%20prints%20strongly%20connected%0A%20%20%20%20components%20using%20DFS%20traversal%0A%20%20%20%20u%20\u2013%3E%20The%20vertex%20to%20be%20visited%20next%0A%20%20%20%20disc%5B%5D%20\u2013%3E%20Stores%20discovery%20times%20of%20visited%20vertices%0A%20%20%20%20low%5B%5D%20\u2013%20%3E%3E%20earliest%20visited%20vertex%20(the%20vertex%20with%20minimum%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20discovery%20time)%20that%20can%20be%20reached%20from%20subtree%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rooted%20with%20current%20vertex%0A%20%20%20%20st%20\u2013%20%3E%3E%20To%20store%20visited%20edges\u201d\u2019%0A%20%20%20%20def%20BCCUtil(self%2Cu%2C%20parent%2C%20low%2C%20disc%2C%20st)%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%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%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%20disc%5Bv%5D%20%3D%3D%20-1%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%20st.append((u%2C%20v))%20%23store%20the%20edge%20in%20stack%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.BCCUtil(v%2C%20parent%2C%20low%2C%20disc%2C%20st)%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%20%23%20Case%201%20\u2013%20per%20Strongly%20Connected%20Components%20Article%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%20If%20u%20is%20an%20articulation%20point%2Cpop%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20all%20edges%20from%20stack%20till%20(u%2C%20v)%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%20or%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%20self.count%20%2B%3D1%20%23%20increment%20count%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20w%20%3D%20-1%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20w%20!%3D%20(u%2Cv)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20w%20%3D%20st.pop()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%20w%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%22%22%0A%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%20and%20low%5Bu%5D%20%3E%20disc%5Bv%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20\u201d\u2019Update%20low%20value%20of%20\u2019u\u2019%20only%20of%20\u2019v\u2019%20is%20still%20in%20stack%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(i.e.%20it\u2019s%20a%20back%20edge%2C%20not%20cross%20edge).%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Case%202%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20\u2013%20per%20Strongly%20Connected%20Components%20Article\u201d\u2019%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20low%5Bu%5D%20%3D%20min(low%20%5Bu%5D%2C%20disc%5Bv%5D)%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20st.append((u%2Cv))%0A%20%0A%20%0A%20%20%20%20%23The%20function%20to%20do%20DFS%20traversal.%20%0A%20%20%20%20%23%20It%20uses%20recursive%20BCCUtil()%0A%20%20%20%20def%20BCC(self)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Initialize%20disc%20and%20low%2C%20and%20parent%20arrays%0A%20%20%20%20%20%20%20%20disc%20%3D%20%5B-1%5D%20*%20(self.V)%0A%20%20%20%20%20%20%20%20low%20%3D%20%5B-1%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%20%20%20st%20%3D%20%5B%5D%0A%20%0A%20%20%20%20%20%20%20%20%23%20Call%20the%20recursive%20helper%20function%20to%20%0A%20%20%20%20%20%20%20%20%23%20find%20articulation%20points%0A%20%20%20%20%20%20%20%20%23%20in%20DFS%20tree%20rooted%20with%20vertex%20\u2019i\u2019%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(self.V)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20disc%5Bi%5D%20%3D%3D%20-1%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.BCCUtil(i%2C%20parent%2C%20low%2C%20disc%2C%20st)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23If%20stack%20is%20not%20empty%2C%20pop%20all%20edges%20from%20stack%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20st%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.count%20%3D%20self.count%20%2B%201%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20st%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20w%20%3D%20st.pop()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%20w%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%20%22%22%0A%20%0A%23%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0A%20%0Ag%20%3D%20Graph(12)%0Ag.addEdge(0%2C1)%0Ag.addEdge(1%2C2)%0Ag.addEdge(1%2C3)%0Ag.addEdge(2%2C3)%0Ag.addEdge(2%2C4)%0Ag.addEdge(3%2C4)%0Ag.addEdge(1%2C5)%0Ag.addEdge(0%2C6)%0Ag.addEdge(5%2C6)%0Ag.addEdge(5%2C7)%0Ag.addEdge(5%2C8)%0Ag.addEdge(7%2C8)%0Ag.addEdge(8%2C9)%0Ag.addEdge(10%2C11)%0A%20%0Ag.BCC()%3B%0Aprint%20(%22Above%20are%20%25d%20biconnected%20components%20in%20graph%22%20%25(g.count))%3B%0A%20\u2033 message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<div class=\"responsive-tabs-wrapper\">\n<div class=\"responsive-tabs responsive-tabs--enabled\">\n<div id=\"tablist1-panel2\" class=\"tabcontent responsive-tabs__panel responsive-tabs__panel--active\">\n[ad type=\u201dbanner\u201d]\n<p>Output:<\/p>\n<pre>4--2 3--4 3--1 2--3 1--2\r\n8--9\r\n8--5 7--8 5--7\r\n6--0 5--6 1--5 0--1 \r\n10--11\r\nAbove are 5 biconnected components in graph<\/pre>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>PYTHON PROGRAMMING &#8211; Biconnected Components &#8211; learn in 30 sec from microsoft awarded MVP , A biconnected component is a maximal biconnected subgraph.<\/p>\n<p>Biconnected Graph is already discussed here.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,78385,73906],"tags":[78213,78211,78214,78208,78260,78207,78206,78210],"class_list":["post-28364","post","type-post","status-publish","format-standard","hentry","category-coding","category-connectivity","category-graph-algorithms","tag-biconnected-components-and-articulation-points-ppt","tag-biconnected-components-definition","tag-biconnected-components-of-an-undirected-graph-ppt","tag-biconnected-components-pdf","tag-biconnected-components-ppt","tag-biconnected-graph-example","tag-biconnected-subgraph","tag-connected-components-in-daa"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28364","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=28364"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28364\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=28364"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=28364"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=28364"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}