<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Hansani Perera on Medium]]></title>
        <description><![CDATA[Stories by Hansani Perera on Medium]]></description>
        <link>https://medium.com/@perera.hansani95?source=rss-331631a8da76------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*r7sRDCGdYplH_r4vFT6n8g.jpeg</url>
            <title>Stories by Hansani Perera on Medium</title>
            <link>https://medium.com/@perera.hansani95?source=rss-331631a8da76------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 13:11:11 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@perera.hansani95/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Strongly Connected Digraph]]></title>
            <link>https://medium.com/@perera.hansani95/strongly-connected-digraph-42da5c41dceb?source=rss-331631a8da76------2</link>
            <guid isPermaLink="false">https://medium.com/p/42da5c41dceb</guid>
            <dc:creator><![CDATA[Hansani Perera]]></dc:creator>
            <pubDate>Wed, 13 May 2020 13:28:46 GMT</pubDate>
            <atom:updated>2020-05-13T13:28:46.970Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Uj20XLRzmjS8rIBO-qCmFA.png" /></figure><p><em>In this article you will find out how Strongly Connected Graphs are formed,algorithm to find Strongly Connected graphs and algorithm implementation using C language.</em></p><p>A directed graph is strongly connected if there is a path between any two pair of vertices.Simply, if it is possible to reach any vertex starting from any other vertex in the graph that is called a Strongly Connected Graph.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/971/1*UAj6ujuGNLRFnBLz4JZx8A.png" /><figcaption>Figure 1</figcaption></figure><p>Graph 1 in the Figure 1 is not strongly connected because we cannot traverse the entire graph starting from any vertex.But Graph 2 is strongly connected since we can traverse through every vertex starting from any vertex.</p><p>Strongly connected graph can be identified if a DFS(Depth First Search) is done on the graph V(number of vertices) times starting from every vertex.The time complexity will be O(V*(V+E)).</p><p>But using the Strongly Connected Component algorithm(SCC), we can check if a graph is Strongly connected in O(V+E) time.If the algorithm returns 1 SCC,then the graph is strongly connected.</p><p><strong>To find out the Strongly Connected Component(SCC) algorithm refer my previous article on </strong><a href="https://medium.com/@perera.hansani95/strongly-connected-components-algorithm-in-c-9c60968bd0e0"><strong>Kosaraju’s Algorithm</strong></a><strong>.</strong></p><p>Steps of Kosaraju’s algorithm in brief,</p><ol><li>Create an empty stack and perform depth first search on whole graph.If all the vertices are not visited then graph is not strongly connected.</li><li>Reverse the direction of all edges and create the transpose graph.</li><li>Perform depth first search on reversed graph.If depth first search traversal does not visit all the vertices return graph is not strongly connected otherwise graph is strongly connected.</li></ol><p><strong>Let’s move to the algorithm implementation in C</strong></p><blockquote><em>Here I implement a weighted directed graph, but it is not necessary for the any part of the algorithm(If you want, you can omit the weight and continue with directed graph)</em></blockquote><p>Define libraries, structures to store data of graphs.</p><pre>#include &lt;stdio.h&gt;<br>#include &lt;stdlib.h&gt;<br>#include &lt;stdbool.h&gt;</pre><pre>#define MAX_SIZE 5</pre><pre>// A structure to represent an adjacency list node<br>struct adj_list_node{<br> int dest;<br> int weight;<br> struct adj_list_node *next;<br>};</pre><pre>// A structure to represent an adjacency list<br>struct adj_list{<br> struct adj_list_node *head;<br>};</pre><pre>// A structure to represent a graph<br>struct Graph{<br> int V;<br> int *visited;<br> struct adj_list *array;<br>};</pre><p>Declare functions to implement the graph, add edges to the graph, implement transpose graph</p><pre>//**************START OF METHODS RELATED TO GRAPH******************</pre><pre>// Function to create a new adjacency list node<br>struct adj_list_node *new_adj_list_node(int dest, int weight){<br> struct adj_list_node *newNode = (struct adj_list_node *)malloc(sizeof(struct adj_list_node));<br> newNode-&gt;dest = dest;<br> newNode-&gt;weight = weight;<br> newNode-&gt;next = NULL;<br> return newNode;<br>}</pre><pre>// Function to creates a graph with V vertices<br>struct Graph *create_graph(int V){<br> struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));<br> graph-&gt;V = V;</pre><pre>graph-&gt;array = (struct adj_list *)malloc(V * sizeof(struct adj_list));</pre><pre>int i;<br> for (i = 0; i &lt; V; ++i)<br> graph-&gt;array[i].head = NULL;</pre><pre>return graph;<br>}</pre><pre>// Fuction to add edges to graph<br>void add_edge(struct Graph *graph, struct Graph *gr, int src, int dest, int weight){</pre><pre>struct adj_list_node *newNode = new_adj_list_node(dest, weight);<br>newNode-&gt;next = graph-&gt;array[src].head;<br>graph-&gt;array[src].head = newNode;</pre><pre>get_transpose(gr, src, dest, weight);<br>}</pre><pre>// Function to print the graph<br>void print_graph(struct Graph *graph1){<br> int v;<br> for (v = 0; v &lt; graph1-&gt;V; ++v) {<br> struct adj_list_node *temp = graph1-&gt;array[v].head;<br> while (temp) {<br> printf(“(%d -&gt; %d(%d))\t”, v, temp-&gt;dest, temp-&gt;weight);<br> temp = temp-&gt;next;<br> }<br> }<br>}</pre><pre>// A recursive function to print DFS starting from v<br>void dfs_recursive(struct Graph *gr, int v, bool visited[]){</pre><pre>visited[v] = true;<br> //printf(“%d “, v);<br> struct adj_list_node *temp = gr-&gt;array[v].head;</pre><pre>while (temp) {<br> if (!visited[temp-&gt;dest]) {<br> dfs_recursive(gr, temp-&gt;dest, visited);<br> }<br> temp = temp-&gt;next;<br> }<br>}</pre><pre>// Fuction to add edges to transpose graph<br>void get_transpose(struct Graph *gr, int src, int dest, int weight){<br> struct adj_list_node *newNode = new_adj_list_node(src, weight);<br> newNode-&gt;next = gr-&gt;array[dest].head;<br> gr-&gt;array[dest].head = newNode;<br>}</pre><pre>//****************END OF METHODS RELATED TO GRAPH******************<br></pre><p>Check if the graph is strongly connected.Function return 1 if Strongly connected otherwise 0.</p><pre>//**********START OF STRONGLY CONNECTED COMPONENTS CHECK***********</pre><pre>int strongly_connectivity(struct Graph *graph, struct Graph *gr, int v){</pre><pre>bool visited[v];<br> for (int i = 0; i &lt; v; i++)<br> visited[i] = false;</pre><pre> dfs_recursive(graph,0, visited);<br> <br> for (int i = 0; i &lt; v; i++){<br> if (visited[i] == false)<br> return 0;<br> }</pre><pre> for (int i = 0; i &lt; v; i++)<br> visited[i] = false;<br> <br>dfs_recursive(gr, 0, visited);</pre><pre> for (int i = 0; i &lt; v; i++)<br> if (visited[i] == false)<br> return 0;</pre><pre>return 1;<br>}</pre><pre>//*******END OF STRONGLY CONNECTED COMPONENTS CHECK********<br></pre><p>Driver program to test above functions</p><pre>int main(){</pre><pre>struct Graph *graph1 = create_graph(MAX_SIZE);<br>struct Graph *gr1 = create_graph(MAX_SIZE);</pre><pre> add_edge(graph1, gr1, 1, 0, 2);<br> add_edge(graph1, gr1, 0, 2, 2);<br> add_edge(graph1, gr1, 2, 1, 2);<br> add_edge(graph1, gr1, 0, 3, 2);<br> add_edge(graph1, gr1, 3, 4, 2);</pre><pre> int t1 = strongly_connectivity(graph1, gr1, MAX_SIZE);<br> printf(“Graph 1:\n”);<br> if(t1 == 0){<br> printf(“Graph is not Strongly connected\n”);<br> }else if(t1 == 1){<br> printf(“Graph is Strongly connected\n”);<br> }</pre><pre> struct Graph *graph2 = create_graph(MAX_SIZE-2);<br> struct Graph *gr2 = create_graph(MAX_SIZE);</pre><pre> add_edge(graph2, gr2, 1, 0, 2);<br> add_edge(graph2, gr2, 0, 2, 2);<br> add_edge(graph2, gr2, 2, 1, 2);</pre><pre> int t2 = strongly_connectivity(graph2, gr2, MAX_SIZE-2);<br> printf(“Graph 2:\n”);<br> if(t2 == 0){<br> printf(“Graph is not Strongly connected\n”);<br> }else if(t2 == 1){<br> printf(“Graph is Strongly connected\n”);<br> }</pre><pre>return 0;<br>}</pre><p>Output</p><pre>Graph 1:<br>Graph is not Strongly connected<br>Graph 2:<br>Graph is Strongly connected</pre><p>Try to implement the code by your own and visit my <a href="https://github.com/hansaniperera/Strongly-Connected-Digraph">Github repository</a> to find out my code.</p><p>Hope you understood the algorithm and the code implementation.</p><p>Thank you for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=42da5c41dceb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Strongly Connected Components Algorithm in C]]></title>
            <link>https://medium.com/@perera.hansani95/strongly-connected-components-algorithm-in-c-9c60968bd0e0?source=rss-331631a8da76------2</link>
            <guid isPermaLink="false">https://medium.com/p/9c60968bd0e0</guid>
            <category><![CDATA[connected-components]]></category>
            <category><![CDATA[kosaraju-algorithm]]></category>
            <category><![CDATA[c-coding]]></category>
            <category><![CDATA[graph-data-structure]]></category>
            <category><![CDATA[strongly-connected]]></category>
            <dc:creator><![CDATA[Hansani Perera]]></dc:creator>
            <pubDate>Sat, 09 May 2020 12:45:18 GMT</pubDate>
            <atom:updated>2020-05-09T12:45:18.240Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*DO2UwQM3v9m06_WdXXlKFg.png" /></figure><p><em>In this article you will find out how Strongly Connected Components(SCC) are formed,explanation of Kosaraju’s algorithm to find SCC and algorithm implementation using C language.</em></p><p>A strongly connected component is a partition of a directed graph in which there is a path from each vertex to another vertex in the partition. This is applied only on <strong>Directed graphs</strong>.</p><p>For example following graph contains 3 SCCs :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/645/1*Y4FpyIsijYC7z_jtkDvbyw.png" /><figcaption>Figure 1</figcaption></figure><p>We can find all the SCCs in a graph using Kosaraju’s algorithm in O(V+E) time(If the graph is described using an adjacency list). If the graph is represented as an adjacency matrix, the algorithm requires <em>Ο(V²)</em> time.This algorithm is DFS based and it does DFS two times.Let’s see how Kosaraju’s algorithm works.</p><h3>Kosaraju’s Algorithm</h3><p>Basically this algorithm involve 3 steps.</p><ol><li>Create an empty stack and perform depth first search on whole graph</li></ol><p>Let’s start from vertex-0, then visit all of its child vertices, and mark them as visited. If a vertex leads to an already visited vertex, then push this vertex to the stack.</p><p>For example in Figure 1: Starting from vertex-0,go to vertex-2,vertex-1,then vertex-1 leads to vertex-0 which was already visited.So push the vertex-1 (current source vertex) to the stack.</p><p>Go to the previous vertex (vertex-2) and visit its child vertices if they exist. (In here vertex-2 do not have child vertices which are not visited already) Since push vertex-2 into the stack.</p><p>Then again go to the previous vertex (vertex-0) and it has child vertices which are not visited (vertex-3),visit vertex-3, go to vertex-4.Since there is nowhere to go from vertex-4, push it into the stack.</p><p>Again go to the previous vertex (vertex-3) and it has no child vertices which are not visited.Since push it to the stack.Then go to previous vertex (vertex-0) push it to the stack since it has no child vertices which are not visited already.</p><p>Then final stack is created and all the vertices are visited.</p><p>2. Reverse the direction of all edges and create the transpose graph</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/827/1*OXNaoPExvBnKMNsusu0DPA.png" /><figcaption>Filled stack and transpose graph</figcaption></figure><p>3. Perform depth first search on reversed graph</p><p>Start from the top vertex of the stack. Traverse through all of its child vertices until already visited vertex is reached, then one strongly connected component is formed.</p><p>For example in Figure 1: Pop vertex-0 from the stack. Starting from vertex-0, traverse through its child vertices (vertex-0, vertex-1, vertex-2 in sequence) and mark them as visited. The child of vertex-2 (vertex-0) is already visited, so these visited vertices form one strongly connected component.</p><p>Go to the stack and pop the top vertex if already visited. Otherwise, choose the top vertex from the stack and traverse through its child vertices as above.(In here top of stack has vertex-3 and it is not visited,pop vertex-3 and vertex-3 do not have child vertices even.Therefore vertex-3 form one strongly connected component.)</p><p>Similarly vertex-4 even form one strongly connected component.</p><p>Now again pop the top vertex(current top vertex is vertex-2) since it is already visited.Next top vertex is vertex-1 and it even already visited,therefore pop it.Now the stack is empty and all the vertices are visited.</p><p>And we are done finding all the SCCs.</p><p><strong>Let’s move to the algorithm implementation in C</strong></p><blockquote>Here I implement a weighted directed graph, but it is not necessary for the any part of the algorithm(If you want, you can omit the weight and continue with directed graph)</blockquote><p>Define libraries, structures to store data of stacks and graphs.</p><pre>#include &lt;stdio.h&gt;<br>#include &lt;stdlib.h&gt;<br>#include &lt;stdbool.h&gt;<br>#define MAX_SIZE 5</pre><pre>struct Graph *graph;<br>struct Graph *gr;<br>int stack[MAX_SIZE], top;</pre><pre>// A structure to represent an adjacency list node<br>struct adj_list_node{<br>int dest;<br>int weight;<br>struct adj_list_node *next;<br>};</pre><pre>// A structure to represent an adjacency list<br>struct adj_list{<br>struct adj_list_node *head;<br>};</pre><pre>// A structure to represent a graph<br>struct Graph{<br>int V;<br>int *visited;<br>struct adj_list *array;<br>};</pre><p>Declare functions to implement the graph, add edges to the graph, implement transpose graph, fill the stack and do DFS traversal</p><pre>//*************START OF METHODS RELATED TO GRAPH**************</pre><pre>// Function to create a new adjacency list node<br>struct adj_list_node *new_adj_list_node(int dest, int weight){</pre><pre>struct adj_list_node *newNode = (struct adj_list_node *)malloc(sizeof(struct adj_list_node));</pre><pre>newNode-&gt;dest = dest;<br>newNode-&gt;weight = weight;<br>newNode-&gt;next = NULL;<br>return newNode;<br>}</pre><pre>// Function to creates a graph with V vertices<br>struct Graph *create_graph(int V){</pre><pre>struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));<br>graph-&gt;V = V;<br>graph-&gt;array = (struct adj_list *)malloc(V * sizeof(struct adj_list));<br>int i;</pre><pre>for (i = 0; i &lt; V; ++i)<br>graph-&gt;array[i].head = NULL;</pre><pre>return graph;<br>}</pre><pre>// Fuction to add edges to graph<br>void add_edge(struct Graph *graph, struct Graph *gr, int src, int dest, int weight){</pre><pre>struct adj_list_node *newNode = new_adj_list_node(dest, weight);</pre><pre>newNode-&gt;next = graph-&gt;array[src].head;<br>graph-&gt;array[src].head = newNode;<br>get_transpose(gr, src, dest, weight);<br>}</pre><pre>// Function to print the graph<br>void print_graph(struct Graph *graph1){</pre><pre>int v;<br>for (v = 0; v &lt; graph1-&gt;V; ++v){<br>struct adj_list_node *temp = graph1-&gt;array[v].head;</pre><pre>while (temp){<br>printf(“(%d -&gt; %d(%d))\t”, v, temp-&gt;dest, temp-&gt;weight);<br>temp = temp-&gt;next;<br>}<br>}<br>}</pre><pre>// Fuction to fill the stack<br>void set_fill_order(struct Graph *graph, int v, bool visited[], int *stack){</pre><pre>visited[v] = true;<br>int i = 0;<br>struct adj_list_node *temp = graph-&gt;array[v].head;</pre><pre>while (temp){<br>if (!visited[temp-&gt;dest])<br>{<br>set_fill_order(graph, temp-&gt;dest, visited, stack);<br>}<br>temp = temp-&gt;next;<br>}<br>push(v);<br>}</pre><pre>// A recursive function to print DFS starting from v<br>void dfs_recursive(struct Graph *gr, int v, bool visited[]){</pre><pre>visited[v] = true;<br>printf(“%d “, v);<br>struct adj_list_node *temp = gr-&gt;array[v].head;</pre><pre>while (temp){<br>if (!visited[temp-&gt;dest]){<br>dfs_recursive(gr, temp-&gt;dest, visited);<br>}<br>temp = temp-&gt;next;<br>}<br>}</pre><pre>// Fuction to add edges to transpose graph<br>void get_transpose(struct Graph *gr, int src, int dest, int weight){</pre><pre>struct adj_list_node *newNode = new_adj_list_node(src, weight);<br>newNode-&gt;next = gr-&gt;array[dest].head;<br>gr-&gt;array[dest].head = newNode;<br>}</pre><pre>//***************END OF METHODS RELATED TO GRAPH****************</pre><p>Find the strongly connected components</p><pre>//**********START OF STRONGLY CONNECTED COMPONENTS CHECK**********</pre><pre>void strongly_connected_components(struct Graph *graph, struct Graph *gr, int V){</pre><pre>bool visited[V];<br>for (int i = 0; i &lt; V; i++)<br>visited[i] = false;</pre><pre>for (int i = 0; i &lt; V; i++){<br>if (visited[i] == false){<br>set_fill_order(graph, i, visited, stack);<br>}<br>}</pre><pre>int count = 1;<br>for (int i = 0; i &lt; V; i++)<br>visited[i] = false;</pre><pre>while (top != -1){<br>int v = stack[top];<br>pop();</pre><pre>if (visited[v] == false){<br>printf(“Strongly connected component %d: \n”, count++);<br>dfs_recursive(gr, v, visited);<br>printf(“\n”);<br>}<br>}<br>}//****************END OF STRONGLY CONNECTED COMPONENTS CHECK***************</pre><p>Functions to push and pop items from the stack</p><pre>//***************START OF STACK FUNCTIONS**********************</pre><pre>// Function to push item to stack<br>void push(int x){</pre><pre>if (top &gt;= MAX_SIZE — 1){<br>printf(“\n\tSTACK is over flow”);<br>}<br>else{<br>top++;<br>stack[top] = x;<br>}<br>}</pre><pre>// Function to pop item to stack<br>void pop(){</pre><pre>if (top &lt;= -1){<br>printf(“\n\t Stack is under flow”);<br>}else{<br>top — ;<br>}<br>}//*****************END OF STACK FUNCTIONS**********************</pre><p>Driver program to test above functions</p><pre>int main(){</pre><pre>top = -1;<br>int v = 5;</pre><pre>struct Graph *graph = create_graph(v);<br>struct Graph *gr = create_graph(v);</pre><pre>add_edge(graph, gr, 1, 0, 2);<br>add_edge(graph, gr, 0, 2, 2);<br>add_edge(graph, gr, 2, 1, 2);<br>add_edge(graph, gr, 0, 3, 2);<br>add_edge(graph, gr, 3, 4, 2);<br>strongly_connected_components(graph, gr, v);</pre><pre>return 0;<br>}</pre><p><strong>Applications of Strongly connected components:</strong></p><ul><li>Vehicle-routing applications</li><li>Find connected groups in Social Networks</li></ul><p>Try to implement the code by your own and visit my <a href="https://github.com/hansaniperera/Kosaraju-Algorithm">Github repository</a> to find out my code.</p><p>Hope you understood the algorithm and the code implementation.</p><p>Thank you for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9c60968bd0e0" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>