Articaulation point

Articulation Point

উপরের গ্রাফ চিত্রে যেসব নোড দেওয়া আছে এগুলোকে আমরা একটি ষ্টেশন হিসেবে বিবেচনা করি। আমরা এসব এক ষ্টেশন হতে অন্য ষ্টেশনে সহজেই যাতায়ত করতে পারি। মনে করি কোন এক প্রাকৃতিক দুর্যোগের কারনে এসব ষ্টেশনের মধ্যে একটির অস্তিত্ব বিনষ্ট হয়ে গেছে। এখন যদি এমন অবস্থা হয় যে,আমরা ঐ ষ্টেশনটি ছাড়া এক ষ্টেশন থেকে অন্য ষ্টেশনে সহজেই পৌছাতে পারি তাহলে আমাদের গ্রাফে(যাতায়তে) ঐ ষ্টেশনটি কোন সমস্যার সৃষ্টি করে নি,তাহলে আমরা ঐ ষ্টেশনটিকে(তথা node কে) Articulation point বলা যাবে না। যেমন আমরা যদি মনে করি A ষ্টেশনটি বিনষ্ট হয়ে গেছে,তাহলে দেখা যাবে আমাদের গ্রাফে(যাতায়তে) ঐ ষ্টেশনটি কোন সমস্যার সৃষ্টি করে নি।

আমরা উপরের গ্রাফ থেকে থেকে দেখতা পারছি যে
আমরা যদি B থেকে যদি G তে চাই তাহলে easily যেতে পারি।
আবার যদি C থেকে যদি G তে চাই তাহলে easily যেতে পারি। and so on......... আবার যদি মনে করি F ষ্টেশনটি বিনষ্ট হয়ে গেছে,তাহলে দেখা যাবে আমাদের গ্রাফে(যাতায়তে) ঐ ষ্টেশনটি সমস্যার সৃষ্টি করছে।

আমরা উপরের গ্রাফ থেকে থেকে দেখতা পারছি যে
আমরা যদি B থেকে যদি G তে চাই তাহলে আমরা কোনভাবে যেতে পারছি না।
আমরা যদি C থেকে যদি G তে চাই তাহলে আমরা কোনভাবে যেতে পারছি না।
and so on.........

তাহলে আমরা বলতে পারি 'F' একটি Articaulation point.

তাহলে আমরা বলতে পারি যে node টির absent এর কারনে একটি গ্রাফ দুই বা ততোধিক সাবগ্রাফে বিভক্ত হয় তাহলে ঐ node কে articulation point বলা হয়।


Procedure of finding articulation point

1.প্রথমে আমি প্রতিটি নোডের জন্য দুটি value রাখব,একটি হল dfs_num এবং আরেকটি হল dfs_low।

2. এখানে dfs_num এ যে value আছে তাহল ঐ নোডের Traversing number মানে ঐ node টা কততম position এ traversing করা হয়েছে । এবং dfs_low এর মধ্যে যে value থাকবে তা হল node টি যদি অন্য একটি পথের মাধ্যমে(back edge) অন্য একটি node এর সাথে connect থাকে। যদি dfs_low এর value এর parrent node এর dfs_num এর value থেকে কম হয় ,তাহলে বুঝতে হবে node টি back edge দ্বারা অন্য একটি নোডের সাথে connect আছে । এবং এই node টি articulation point হবে না।


Source code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
vector<int>my[100];
int dfs_num[100],dfs_low[100],dfs_parrent[100];
int dfs_counter=0;
int articulation_vertex[100];
int dfs_root,rootchildren;
void articulation_point(int u)
{
  dfs_num[u]=dfs_low[u]=dfs_counter++;
  for(int i=0;i<my[u].size();i++)
  {
      int v=my[u][i];
     if(dfs_num[v]==-1)
     {
         dfs_parrent[v]=u;
         if(dfs_root==u)
          rootchildren++;
         articulation_point(v);
         if(dfs_low[v]>=dfs_num[u])
            articulation_vertex[u]=1;
            if(dfs_low[v]>dfs_num[u])
               printf("Edge (%d %d) is a bridge\n",u,v);
         dfs_low[u] = min(dfs_low[u], dfs_low[v]);
     }
     else if(v!=dfs_parrent[u])
        dfs_low[u]=min(dfs_low[u],dfs_num[v]);
  }
}
int main()
{
   my[0].push_back(1);
   my[1].push_back(0);
   my[1].push_back(2);
   my[1].push_back(3);
   my[1].push_back(4);
   my[1].push_back(5);
   my[2].push_back(1);
   my[3].push_back(1);
   my[4].push_back(1);
   my[5].push_back(1);
   my[4].push_back(5);
   my[5].push_back(4);
   memset(dfs_num,-1,sizeof dfs_num);
   cout<<"Articualtion bridges:\n";
   for(int i=0;i<6;i++)
   {
     if(dfs_num[i]==-1)
     {
         dfs_root=i,rootchildren=0;
        articulation_point(i);
        articulation_vertex[i]=(rootchildren>1);///special cases
     }
   }
   printf("Articulation points:\n");
   for(int i=0;i<6;i++)
   {
     if(articulation_vertex[i])
        cout<<i<<endl;
   }
 return 0;
}