Counting Connected Subgraphs

یک گراف ساده ی بدون جهت با حداکثر 15 راس داریم. الگوریتمی پیشنهاد بدهید که تعداد زیر گراف های همبند آن را پیدا کند.

بیشتر افراد، از جمله من، وقتی عدد 15 را می بینند، سعی می کنند مساله را با استفاده از برنامه سازی پویا (Dynamic Programming) مدل سازی کنند و رابطه ای بازگشتی برای پیدا کردن جواب مساله برای مجموعه راس های S را مستقیما با استفاده از حل زیر مساله های کوچکتر برای زیر مجموعه های مجموعه ی S پیدا کنند. که احتمالا به جواب هم نمی رسند.

ولی یک حل کننده ی مساله ی خوب زیاد به یک راه حل گیر نمی دهد و سعی می کند راه های دیگری را نیز امتحان کند.

یکی از کارهای خوبی که می توان هنگام حل کردن مساله انجام داد این است که تعیین کرد که با داشتن چه چیز هایی می توانیم جواب مساله را پیدا کنیم. مثلا در این مساله می توان از رابطه ی تعداد زیر گراف های همبند + تعداد زیر گراف های ناهمبند = تعداد کل زیرگراف ها استفاده کرد و برای پیدا کردن جواب مساله به دنبال پیدا کردن تعداد کل زیرگراف ها و تعداد زیرگراف های ناهمبند بود:

1. تعداد کل زیر گراف ها می باشد که در آن |E| تعداد یال ها ی گراف می باشد. این قسمت از مساله که یک مساله شمارش ساده بود.

2. تعداد زیر گراف های ناهمبند: یک زیر گراف ناهمبند را در نظر بگیرید. در این زیر گراف تعدادی از راس ها با راس اول مولفه ای همبند تشکیل می دهند و بقیه ی راس ها جدا از این مولفه می باشد. توجه کنید که مجموعه ی راس های جدا از این مولفه نباید تهی باشد. بقیه ی راس ها می توانند هر گونه گرافی را بسازند.

پس برای پیدا کردن تعداد زیرگراف های ناهمبند یک مجموعه راس S کافی است تمام زیر مجموعه های 'S ای از این مجموعه را که S مخالف 'S باشد و 'S شامل اولین راس S باشد را در نظر بگیریم و تعداد زیر مجموعه های همبند گراف 'S ضرب در 2 به توان تعداد یال های گراف با مجموعه راس 'S-S را به جوابمان اضافه کنیم. پس این قسمت را نیز می توان با استفاده از رابطه ای بازگشتی و برنامه سازی پویا حل کرد.

در قسمت بعدی به چند نکته ی پیاده سازی مفید در پیاده سازی این مساله اشاره خواهم کرد.

در اين قسمت می خواهيم کمی به جزئيات پياده سازی راه حل ارائه شده برای اين مساله بپردازيم. فرض کنيد تعداد راس های گراف N باشد.

ابتدا يک pseudo-code برای اين راه حل ارائه می دهيم:

function CountConnectedSubgraphs(V, E):
   Result = 2 ^ |E|
   for each subset V' of V such that (V' contains V[0]) and (V' != V) do:
      Result -= CountConnectedSubgraphs(V', E') * 2 ^ E(V-V')
   return Result

برای اين مساله، فرض می کنيم که گراف را در يک ماتريس مجاورت ذخيره می کنيم:

 int graph[15][15];

برای پياده سازی pseudo-code فوق، نياز داريم که:

1. ساختمان داده ای برای نمايش زير مجموعه ای از راس های گراف داشته باشيم. هر زير مجموعه را با استفاده از يک عدد 15 بيتی که يک يا صفر بودن بيت i-ام آن نشانگر اين است که آيا راس i-ام عضوی از زير مجموعه ی مورد نظر است يا نه.

2. تعداد يال های هر کدام از زيرگراف ها (که با يک زير مجموعه از راس ها مشخص می شوند) را داشته باشيم. اين کار را با يک حلقه ی 2 به توان N تايي انجام می دهيم. هر عضو از آرايه ی نتيجه نشانگر تعداد يال های زير گراف مربوطه می باشد:

 int E[1<<15];
 
for(int i = 0; i < (1 << N); i++)
{
   E[i] = 0;
   for(int j = 0; j < N; j++)
      for(int k = 0; k < N; k++)
         // Check if j-th and k-th vertices are member of i
         if(((1 << j) & i) && ((1 << k) & i))
            // Check if there is an edge from j to k
            if(graph[j][k])
               E[i] += 1;
}

3. روشی نياز داريم که توسط آن بتوانيم زيرمجموعه های يک مجموعه را بدست بياوريم. در واقع، چون هر مجموعه را با يک عدد 15 بيتی نمايش می دهيم، می خواهيم اعدادی را به دست بياوريم که يک های آنها زير مجموعه ای از عدد متناظر با مجموعه ی مورد نظر باشند. فرض کنيد مجموعه ی مورد نظر را با X نمايش دهيم. می خواهيم اعداد Y ای را بدست بياوريم که X & Y برابر با Y باشد. (& = bitwise and). ساده ترين روش برای انجام دادن اين کار:

 for(int i = 0; i < (1 << N); i++)
   if((X & i) == i)
   {
      // do calculations here
   }

ولی روش بهتری برای انجام دادن عمل بالا وجود دارد:

 int Y = X;
do{
   // do calculations here
   …
   // Move to next subset
   Y = (Y - 1) & X;
}while(Y);

4. اگر راه حل بالا را به صورت بازگشتی ساده بنويسيم، چون حالات تکراری زيادی بوجود می آيد، زمان اجرای برنامه خيلی زياد خواهد بود. برای جلوگيری از محاسبه ی دوباره ی حالات تکراری، از يک آرايه استفاده می کنيم که مقدار اوليه ی همه ی عناصر آن 1- می باشد و پس از محاسبه ی جواب برای هر زير گراف، نتيجه را در آن قرار می دهيم تا در دفعات بعدی از آن استفاده کنيم:

 int arr[1<<15];

و در نهايت، از کنار هم قرار دادن قطعات بالا، سورس کد زير به دست می آيد:

int graph[1 << 15];
int arr[1 << 15];
int N;
 
void CalculateEdges()
{
   for(int i = 0; i < (1 << N); i++)
   {
      E[i] = 0;
      for(int j = 0; j < N; j++)
         for(int k = 0; k < N; k++)
            // Check if j-th and k-th vertices are member of i
            if(((1 << j) & i) && ((1 << k) & i))
               // Check if there is an edge from j to k
               if(graph[j][k])
                  E[i] += 1;
   }
}
 
int CountConnectedSubgraphs(int V)
{
   if(arr[V] != -1)
      return arr[V];
   int FirstBit = 1;
   while((FirstBit & V) == 0)
      FirstBit *= 2;
   int Result = (1 << E[V]);
   int Y = V;
   do
   {
      if((Y & FirstBit) && Y != V)
      {
         int X = ~Y & V; // X = V - Y
         Result -= CountConnectedSubgraphs(Y) * (1 << E[X]);
      }
      Y = (Y - 1) & V;
   }while(Y);
 
   return arr[V] = Result;
}
 
int main()
{
   // Read N and Graph here
   …
   memset(arr, -1, sizeof arr);
   CalculateEdges();
   cout << CountConnectedSubgraphs((1 << N) - 1) << endl;
   return 0;
}

همان طور که گفتيم، هر مجموعه را با يک عدد 15 بيتی نمايش می دهيم که اگر بيت i-ام يک باشد يعنی چيز i-ام عضو مجموعه ی مورد نظر است، و گرنه نيست. حال می خواهيم روشی را ارائه کنيم که زير مجموعه بعدی يک مجموعه را که از لحاظ ارزش عددی کمتر از زير مجموعه ی جاری است را پيدا کند. از اين به بعد فقط با نمايش دودوئی اعداد سر و کار داريم. کم کردن يک از يک عدد را در نظر بگيريد. چه اتفاقی می افتد؟ سمت راست ترين 1 تبديل به صفر می شود و تمام صفر های سمت راست آن به 1 تبديل می شوند.

مثلا 100 تبديل به 11 می شود و 100110 تبديل به 100101 می شود.

حال هنگامی که می خواهيم زير مجموعه ی بعدی يک مجموعه (P) را پيدا کنيم، بايد اتفاقی مشابه بيافتد: سمت راست ترين 1 تبديل به صفر شود و تمام صفر های سمت راست آن که عضو مجموعه ی P هستند تبديل به يک شوند. اگر زير مجموعه ی جاری را منهای يک کنيم، سمت راست ترين 1 تبديل به صفر می شود و تمام صفر های سمت راست آن تبديل به يک می شوند. چون ما می خواهيم فقط بيت های عضو مجموعه ی P تبديل به يک شوند، حاصل تفريق را با مجموعه ی P “و” منطقی می کنيم. در نتيجه زير مجموعه ی از لحاظ عددی کوچکتر به دست می آيد.

پيچيدگی زمانی تابع CalculateEdges همان طور که آشکار است از مرتبه ی می باشد.برای بررسی تابع CountConnectedSubgraphs، جفت V و Y را در نظر بگيريد. پيچيدگی زمانی اين تابع متناظر با تعداد حالت های اين جفت می باشد. اگر بيت های متناظر V و Y را در نظر بگيريم، می فهميم که حالت هايی که ممکن است پيش بيايد عبارت است از: (1 و 0) – (1 و 1) – (0 و 0) . حالت (0 و 1) ممکن نيست، چون عضوی که عضو مجموعه ای نيست نمی تواند عضو زيرمجموعه ی آن بشود. پس، تعداد حالت ها خواهد بود و پيچيدگی زمانی اين تابع از مرتبه ی .