{"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=&#8221;banner&#8221;]\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<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-python code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-python code-embed-code\"># Python program to find biconnected components in a given<br\/>#  undirected graph<br\/>#Complexity : O(V+E)<br\/> <br\/>  <br\/>from collections import defaultdict<br\/>  <br\/>#This class represents an directed graph <br\/># using adjacency list representation<br\/>class Graph:<br\/>  <br\/>    def __init__(self,vertices):<br\/>        #No. of vertices<br\/>        self.V= vertices <br\/>         <br\/>        # default dictionary to store graph<br\/>        self.graph = defaultdict(list)<br\/>         <br\/>        # time is used to find discovery times<br\/>        self.Time = 0<br\/>         <br\/>        # Count is number of biconnected components<br\/>        self.count = 0<br\/>  <br\/>    # function to add an edge to graph<br\/>    def addEdge(self,u,v):<br\/>        self.graph[u].append(v) <br\/>        self.graph[v].append(u)<br\/> <br\/>    &#039;&#039;&#039;A recursive function that finds and prints strongly connected<br\/>    components using DFS traversal<br\/>    u --&gt; The vertex to be visited next<br\/>    disc[] --&gt; Stores discovery times of visited vertices<br\/>    low[] -- &gt;&gt; earliest visited vertex (the vertex with minimum<br\/>               discovery time) that can be reached from subtree<br\/>               rooted with current vertex<br\/>    st -- &gt;&gt; To store visited edges&#039;&#039;&#039;<br\/>    def BCCUtil(self,u, parent, low, disc, st):<br\/> <br\/>        #Count of children in current node <br\/>        children =0<br\/> <br\/>        # Initialize discovery time and low value<br\/>        disc[u] = self.Time<br\/>        low[u] = self.Time<br\/>        self.Time += 1<br\/> <br\/> <br\/>        #Recur for all the vertices adjacent to this vertex<br\/>        for v in self.graph[u]:<br\/>            # If v is not visited yet, then make it a child of u<br\/>            # in DFS tree and recur for it<br\/>            if disc[v] == -1 :<br\/>                parent[v] = u<br\/>                children += 1<br\/>                st.append((u, v)) #store the edge in stack<br\/>                self.BCCUtil(v, parent, low, disc, st)<br\/> <br\/>                # Check if the subtree rooted with v has a connection to<br\/>                # one of the ancestors of u<br\/>                # Case 1 -- per Strongly Connected Components Article<br\/>                low[u] = min(low[u], low[v])<br\/> <br\/>                # If u is an articulation point,pop <br\/>                # all edges from stack till (u, v)<br\/>                if parent[u] == -1 and children &gt; 1 or parent[u] != -1 and low[v] &gt;= disc[u]:<br\/>                    self.count +=1 # increment count<br\/>                    w = -1<br\/>                    while w != (u,v):<br\/>                        w = st.pop()<br\/>                        print w,<br\/>                    print&quot;&quot;<br\/>             <br\/>            elif v != parent[u] and low[u] &gt; disc[v]:<br\/>                &#039;&#039;&#039;Update low value of &#039;u&#039; only of &#039;v&#039; is still in stack<br\/>                (i.e. it&#039;s a back edge, not cross edge).<br\/>                Case 2 <br\/>                -- per Strongly Connected Components Article&#039;&#039;&#039;<br\/> <br\/>                low[u] = min(low [u], disc[v])<br\/>     <br\/>                st.append((u,v))<br\/> <br\/> <br\/>    #The function to do DFS traversal. <br\/>    # It uses recursive BCCUtil()<br\/>    def BCC(self):<br\/>         <br\/>        # Initialize disc and low, and parent arrays<br\/>        disc = [-1] * (self.V)<br\/>        low = [-1] * (self.V)<br\/>        parent = [-1] * (self.V)<br\/>        st = []<br\/> <br\/>        # Call the recursive helper function to <br\/>        # find articulation points<br\/>        # in DFS tree rooted with vertex &#039;i&#039;<br\/>        for i in range(self.V):<br\/>            if disc[i] == -1:<br\/>                self.BCCUtil(i, parent, low, disc, st)<br\/> <br\/>            #If stack is not empty, pop all edges from stack<br\/>            if st:<br\/>                self.count = self.count + 1<br\/> <br\/>                while st:<br\/>                    w = st.pop()<br\/>                    print w,<br\/>                print &quot;&quot;<br\/> <br\/># Create a graph given in the above diagram<br\/> <br\/>g = Graph(12)<br\/>g.addEdge(0,1)<br\/>g.addEdge(1,2)<br\/>g.addEdge(1,3)<br\/>g.addEdge(2,3)<br\/>g.addEdge(2,4)<br\/>g.addEdge(3,4)<br\/>g.addEdge(1,5)<br\/>g.addEdge(0,6)<br\/>g.addEdge(5,6)<br\/>g.addEdge(5,7)<br\/>g.addEdge(5,8)<br\/>g.addEdge(7,8)<br\/>g.addEdge(8,9)<br\/>g.addEdge(10,11)<br\/> <br\/>g.BCC();<br\/>print (&quot;Above are %d biconnected components in graph&quot; %(g.count));<br\/> <\/code><\/pre> <\/div>\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=&#8221;banner&#8221;]\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}]}}