Maximum Bipartite Matching by Kuhn’s Algorithm

                      Maximum Bipartite Matching by Kuhn’s Algorithm

 আপনি হলেন ঘটক পাখি ভাই এর এজেন্ট । আপনার কাছে পাঁচ জন পাত্র ( তুষার, সানিম, অর্ণব, পিয়াস,মাহির ) আর পাঁচ জন পাত্রী আছে ( বিলকিস, কুলসুম, সখিনা,  জরিনা , আম্বিয়া )   বুঝার সুবিধার্থে পাত্রীরা সব পাত্রকেই পছন্দ করে ( কারণ সবাই অনেক বস প্রোগ্রামার আর সবারই মেলা টাকা পয়সা আছে )  কিন্তু  পাত্রদের পার্সোনাল পছন্দ আছে ।

-      তুষার সব পাঁচটা মেয়েকেই পছন্দ  করে।

-      সানিম খুবই ভাল ছেলে ও খালি  জরিনাকে পছন্দ করে

-      অর্ণব ও ভাল ছেলে ও খালি কুলসুমকে পছন্দ করে ।

-      পিয়াস এর আবার সখিনা , আম্বিয়া দুইজনকেই পছন্দ।

-      মাহির সবচেয়ে খুঁতখুঁতে ছেলে ওর এদের কাউকেই পছন্দ না।  

এখন ঘটক পাখি ভাই এর এজেন্ট হিসাবে আপনাকে তাদের এমন ভাবে ম্যাচ করতে হবে যেন ম্যাচিং এর পর বেশির ভাগ মানুষ  খুশী থাকে। ধরেন সানিম খালি জরিনাকে পছন্দ করে এখন আপনি জোর করে ওকে কুলসুম এর সাথে বিয়ে দিয়ে দিতে পারবেন না কারণ তো কুলসুমকে পছন্দ করে না।হয় সানিম জরিনাকে বিয়ে করবে না হলে কাউকেই না। Maximum Matching করানোর জন্য আপনাকে এইভাবে সাজাতে হবে যেন আপনি Maximum বিয়া সাদি দিতে পারেন। 

আচ্ছা Bipartite Graph কি তা একটু বলি । যদি কোন গ্রাফ এর N টা নোড থাকে , এমন এই N টা নোডকে U, V দুইটা Independent   set এ বিভক্ত করা যাবে যাতে U Set  এর প্রত্যেকটা নোড এর সাথে V set  এর কোন না কোন নোড এর সাথে connect থাকবে । এই গ্রাফ এ কোন odd cycle থাকবে না। যেহেতু U,V দুইটা মাত্রই set এ নোড গুলো বিভক্ত odd cycle থাকা possible ও না। আর Independent set U,V এর নিজেদের মধ্যে কোন কানেকশন থাকবে না। মানে U set এর কোন নোড নিজেদের মধ্যে connected থাকবে না।

Solution :::

kuhn’s Algorithm এ আমরা গ্রাফ এর নোড গুলোকে দুইটা পার্ট এ ভাগ করে নেই। এই প্রবলেম এ  Left side ( এইখানে পাত্রদের সেট ) Right side ( পাত্রীদের সেট )  তারপর কোন একটা পার্ট এর থেকে corresponding opposite side এ কানেকশন possible কিনা তা চেক করে bipartite  matching কতটা হচ্ছে তা হিসাব করা হয়। একটু কঠিন হচ্ছে , কোড এর সাথে ব্যাখ্যা করলে সহজ হয়ে যাবে। আমরা পাত্রদের সেটকে (০-৪) নাম্বারিং করি আর পাত্রীদের সেটকে (৫-৯) নাম্বারিং করি।

তাহলে পাত্রদের সেট                                                                                         

                              তুষার == ০ নাম্বার নোড                                               

                              সানিম == ১ নাম্বার নোড

                              অর্ণব == ২ নাম্বার নোড

                              পিয়াস == ৩ নাম্বার নোড

                              মাহির == ৪ নাম্বার নোড

এবং পাত্রীদের সেট                                                                                                                        

                             বিলকিস == ৫ নাম্বার নোড

                              কুলসুম == ৬ নাম্বার নোড

                              সখিনা == ৭ নাম্বার নোড

                              জরিনা == ৮ নাম্বার নোড

                             আম্বিয়া == ৯ নাম্বার নোড

এখন process টা বলে যাই কিভাবে কাজ করে তারপর ব্যাখ্যা করব। যেকোনো এক পার্ট এর নোড থেকে চেক করতে হয় যে ও কোন ম্যাচ পেয়েছে কিনা যদি পেয়ে যায় তাহলে counting  এর জন্য  একটা variable  রাখা হয় যার value   বাড়িয়ে দেওয়া হয় আমরা  একটা ম্যাচ  successfully করতে পেরেছি । আমরা দুইটা সেট কে Left ও Right দুইটা গ্রুপ এ ভাগ করি । ধরে নেই পাত্রদের সেট হল Left .।যেহেতু আমরা নোড গুলোকে নাম্বারিং করে দিয়েছি দুইটা গ্রুপ কে দুইটা array  তে convert করতে পারি .।

 int Left[MAX],Right[MAX];

Left  এ আছে  পাত্রদের ইনডেক্স গুলা , Right  এ আছে পাত্রীদের ইনডেক্সগুলা। প্রথমে সবাইকে -1 দিয়ে initialize করে দেই, মানে কোন ম্যাচ এখনও হয় নাই তাদের মধ্যে । এখন যে কোন এক পার্ট দিয়ে চেক করব। বুঝার সুবিধার্থে Left পার্ট আমরা বেছে নিলাম । Left পার্ট এ আছে পাত্রদের ইনডেক্স । এখন আমাদের একটা loop 0-4 পর্যন্ত চালাইলে হয়ে যায়। 0-4  পর্যন্ত চালানো সময় আমি তাদের চেক করব, কোনভাবে আমরা ম্যাচিং করাতে পারি কিনা, করাতে পারলে আমরা যে count variable এ ম্যাচিং কয়টা হচ্ছে count করছি তা ভ্যালু এক করে বাড়িয়ে দিব। ধরেন প্রথমে তুষার ভাই এর জন্য আমরা ম্যাচ করাব। তুষার ভাই সবাইকে পছন্দ করে। বুঝানোর সুবিধার্থে ধরলাম তুষার ভাই বলল আমি জরিনাকে বিয়ে করব। আমরা তুষার ভাই এর সাথে জরিনার ম্যাচ দিলাম। তারপর আমরা আসলাম সানিম ভাইয়ার ম্যাচ করাতে । সানিম ভাইয়া জরিনা ছাড়া কিছুই বুঝে না, জরিনা তাহার জান প্রাণ । ম্যাচ করাতে গিয়ে দেখি তুষার ভাই জরিনাকে বুক দিয়ে রাখছে আর সানিম ভাইয়ার ও জরিনা ছাড়া অন্য কোন পছন্দ নাই, জরিনা ছাড়া ও বাঁচবে না । আমরা তো মহা বিপদে এখন। কি করব কি করব। অনেক সাহস কইরা গেলাম আবার তুষার ভাই এর কাছে বললাম দেখ ভাই সানিম তো জরিনা ছাড়া বাঁচবে না ও তো  suicide করবে এখন তুমি ভাই জরিনাকে মুক্ত করে দেও। এই কথা শুইনা তো তুষার ভাই  ও কান্নাকাটি করতে লাগল । “ সানিম সুইসাইড করলে তো বাংলাদেশ এত বস প্রোগ্রামার হারাইয়া ফেলবে, না ভাই আমি এই পাপ কাজ করতে পারব না , দিলাম ভাই জরিনাকে মুক্ত করে। তোমরা আমার সাথে কুলসুম এর ম্যাচ করাইয়া দেও। ” আমাদের জানে পানি এলো। করলাম ম্যাচ সানিম ভাইয়ার সাথে জরিনার আর তুষার ভাই এর সাথে কুলসুম এর successful match করাইলাম। এখন পালা অর্ণব ভাইয়ার । অর্ণব এরও একমাত্র পছন্দ কুলসুম। তুষার ভাই কুলসুমকে বুক দিছে শুইনা অর্ণব এর বুক ফাটে তো মুখ ফুটে না অবস্থা । আমরা আবার মহা বিপদে । আবার গেলাম তুষার ভাইয়ের কাছে । সব শুইনা তুষার ভাই এরও মুখ শুকাইয়া গেল। কষ্টে কষ্টে বলল কি আর করা আমারে তাইলে সখিনাকে দেও। আমাদের জানে আবার প্রাণ ( মানে পানি ) এলো। এইবার পিয়াস ভাইয়ার পালা। ও বলে আমারে সখিনা দেও । তুষার ভাইকে দুই দুইবার আমরা কষ্ট দিছে এখন তো আর পারব না, পিয়াস ভাইয়া কে বললাম সখিনাকে তুমি ভুলে যাও ভাই তোমার তো  আম্বিয়াকেও পছন্দ তুমি আম্বিয়া নেও। পিয়াস ভাইয়া ও সব বুঝে রাজি হল। আমরা পাইলাম তুষার ভাই সখিনা, সানিম ভাইয়া জরিনা , অর্ণব ভাইয়া কুলসুম , পিয়াস ভাইয়া আম্বিয়া চারটা ম্যাচ। তারপর পালা মাহির ভাইয়া , ও দেবদাস । কাউকেই ওর পছন্দ না। কি আর করা আমরা চারটা highest matching করাতে পারলাম। এইটাই maximum Bipartite matching .

কোড টা দেখি

কোড এ আমরা দেখতেই পারছি Left , Right নামে দুই গ্রুপ এ আমরা প্রথমে গ্রাফটাকে ভাগ করছি । তারপর কোন পার্ট নিয়ে চেক করছি কয়টা ম্যাচিং possible হচ্ছে । এই কাজটা আমরা dfs or bfs দিয়ে করতে পারি। একটা পার্ট বলি। প্রথমে তুষার ভাই এর জন্য সব Right side free ছিল । তাই প্রথমেই জরিনাকে assign করা গেছে  । এখন সানিম এর সময় এসে দেখি জরিনা এর সাথে আগে থেকেই তুষার ভাই  assigned , তাই আমরা যে ভ্যালু বা যার সাথে ছিল ওকে অন্যকোনটা সাথে ম্যাচ করানো যায় কিনা তা kuhn(Right[v]) দ্বারা কল করে দেখা হচ্ছে। কোড বুঝতে এখন ও প্রবলেম হলে খাতা কলম নিয়ে একটু আকাআকি করলেই হবে।    সব বুঝা হয়ে গেলে লাইট অজি এর ১১৪৯ এখন সল্ভ করা যেতে পারে।

               ************************  HappY Coding ************************

Reference  Link :::: 1.http://apps.topcoder.com/forums/;jsessionid=67A7E36F9522573AFEBF1DADBFBE2313?module=Thread&threadID=684427&start=0&mc=11#1679384

2. http://translate.google.com/translate?hl=en&sl=auto&tl=en&u=http%3A%2F%2Fe-maxx.ru%2Falgo%2F