Cycle Detection In a Graph

কম্পিটিটিভ প্রোগ্রামিংয়ে আমরা সাধারনত দুই ধরনের গ্রাফ নিয়ে কাজ করে থাকি(আরও অনেক ধরনের গ্রাফ আছে)। ডিরেক্টেড গ্রাফ এবং আনডিরেক্টেড গ্রাফ।
সাধারনত যে সব গ্রাফের দিক নির্দেশক থাকে অর্থাৎ এক নোড থেকে এক্সাক্টলি কোন কোন কোন নোডে যাওয়া যাবে তার দিকে নির্দেশক থাকে সেই গুলাকে ডিরেক্টেড গ্রাফ বলে, অন্যদিকে যে গুলাতে নির্দেশক থাকে না ঐগুলা কে আনডিরেক্টেড গ্রাফ বলে।

গ্রাফের একটা নোড থেকে ভিসিট করা শুরু করলে যদি কোনো একটা টাইমে ঐ নোডেই ফিরে আসা যায় তাহলে বুঝতে হবে এটা একটা সাইকেল।
পাশের ছবিতে দুইটা গ্রাফ আছে , একটা ডিরেক্টেড এবং আরেকটা আনডিরেক্টেড।
ডিরেক্টেড গ্রাফের ১,২ এবং ৩ নাম্বার নোড একটা সাইকেল তৈরি করে।
অন্যদিকে আনডিরেক্টেড গ্রাফের ১,২,৩ এবং ২,৩,৪ দুইটা সাইকেল তৈরি করে।

আমরা এই সাইকেল খোজা কাজটা প্রোগ্রামিং এর মাধ্যমে কিভাবে করতে পারি এবং সাইকেল টাও যেনো প্রিন্ট করতে পারি, এটাই আজকের আলোচ্য বিষয়। All nodes are 0 based.

সাইকেল খুজতে যা যা জানা থাকলে দ্রুত বুঝতে সুবিধা হবেঃ
১ঃ যেকোনো প্রোগ্রামিং ল্যাংগুয়েজ দিয়ে কিভাবে গ্রাফ এর কাজ(ইনপুট/আউটপুট/ট্রাভার্স) করে। 

২ঃ রিকার্সন

ডিরেক্টেড গ্রাফে সাইকেল খোজা

প্রথমে আমরা তিনটা বক্সের সাথে পরিচত হয়ে নিই।
১। সাদা বক্স - শূন্য দ্বারা রিপ্রেজেন্ট করবো (নোড এখোনো ভিজিট হইনাই)
২। ধুসর বক্স - এক দ্বারা রিপ্রেজেন্ট করবো (নোড ভিজিটেড)
৩। কালো বক্স - দুই দ্বারা রিপ্রেজেন্ট করবো (নোডের সব চাইল্ড ভিজিটেড)
একটা Color Array দিয়ে বক্সের কাজ করবো।

একই সাথে সাইকেল এর শুরু এবং শেষ বুঝতে দুইটা ভেরিয়েবল নিবো এবং প্রত্যেকটা নোড এর প্যারেন্ট নোড মার্ক করে রাখতে একটা Array নিবো, যাতে আমাদের সাইকেল প্রিন্ট করতে সুবিধা হয়।

যেহুতু আমরা রিকার্সন জানি, তারমানে আমরা DFS ও জানি, DFS হচ্ছে একটা গ্রাফ Traversing Algorithm. এখানে আমাদের DFS Function টা হবে বুলিয়ান টাইপ্স।

এইগুলা দিয়ে কয়েকটা স্টেপে ডিরেক্টেড গ্রাফে সাইকেল খোজা সম্ভব
১। প্রথমে সব গুলা নোডকে শূন্য(0) দ্বারা মার্ক করে নিবো অর্থাৎ সাদা বক্সে রেখে দিবো, সবগুলা নোডের প্যারেন্ট -1 করে দিবো, Cycle_Start ভ্যারিয়েবল -1 করে রাখবো অর্থাৎ DFS শেষ হবার পরেও Cycle_Start = -1 থাকা মানে কোনো সাইকেল পাইনি।

২। একটা নোড যখন DFS এ ঢুকবে তখন সেটাকে ১ দ্বারা মার্ক করবো অর্থাৎ ধুসর বক্সে রাখবো।
৩। ঐ নোড এর Adjacent অর্থাৎ চাইল্ড নোড গুলা ভিজিট করা শুরু করবো, একটা লুপ দিয়েই করা যায়।
এইখানে দুইটা কেইস হইতে পারে,
-> যদি ঐ নোডের চাইল্ড এখনো সাদা বক্সেই থাকে অর্থাৎ এখনো তাকে ভিজিট না করা হয়ে থাকে তাহলে আমরা সেই চাইল্ডের প্যারেন্ট অর্থাৎ বর্তমান নোডকে মার্ক করবো। সাথে সাথে ঐ চাইল্ড দিয়ে আবার DFS চালাবো একইসাথে দেখবো সে True রিটার্ন করে কিনা।
-> যদি ঐ নোডের চাইল্ড কে আমরা অলরেডি ধুসর বক্সে দেখি অর্থাৎ সে ভিজিটেড(১ দ্বারা মার্ক) থাকে তাহলে বুঝতে হবে এখানে সাইকেল আছে।
যার শুরু ঐ নোড থেকে এবং শেষ ঐ নোডের চাইল্ডে, এটা মার্ক করার জন্য অলরেডি আমরা দুইটা ভ্যারিয়েবল ডিক্লেয়ার করে রাখছি।

৪। ঐ নোডের Adjacent অর্থাৎ সব চাইল্ড ভিজিট করা শেষ হয়ে গেলে আমরা তাকে কালো বক্সে অর্থাৎ ২ দ্বারা মার্ক করে রাখবো, একই সাথে False return করবো। কারন আপাতত আমরা কোনো সাইকেল পাইনি।

Easy Implementation



আনডিরেক্টেড গ্রাফে সাইকেল খোজা

আমরা জানি আনডিরেক্টেড গ্রাফে কোনও দিক নির্দেশক থাকে না অর্থাৎ যেকোনো নোড থেকে বাকি যেকোনো নোডে যাওয়া যাবে। 
এইখানে সাইকেল খোজার জন্য আমাদেরকে কালারিং করার কোনো দরকার নাই কারন যে নোডে আমরা একবার ভিজিট করবো তার চাইল্ড একবার ই ভিজিট  হবে, এর বেশি হবে না। 
সুতরাং আমরা এখানে একটা Visited Array ব্যবহার করবো।

এখানেও কয়েকটা ধাপে আমরা সাইকেল সাইকেল পাইতে পারি।

১। প্রথমে সব গুলা নোড আনভিজিটেড অর্থাৎ Initially False করে রাখবো, সব গুলা নোডের Parent -1 করে রাখবো ।

২। Traversing এর শুরুতে অর্থাৎ নোড যখন DFS এ ঢুকবে তখন ভিজিটিড (True) করে দিবো।

৩। ঐ নোডের চাইল্ড নোড গুলা Traverse করবো, একটা লুপ চালিয়েই করা যাবে, চাইল্ড যদি তার প্যারেন্টের এর সমান হয় তাহলে ঐ চাইল্ড কে ইগ্নোর করবো।

চাইল্ড ভিজিটিং এর ক্ষেত্রে দুইটা কেইস হইতে পারে,

->  যদি চাইল্ড নোড ভিজিটেড থাকে তাহলে আমরা এখানে সাইকেল পাবো,একই ভাবে আগের মত সাইকেলের শুরু এবং শেষ মার্ক করবো। একই সাথে True Return করে দিবো।

এর পর চাইল্ড এর Parent নোড আপডেট করবো।

-> চাইল্ড কে তার প্যারেন্ট নোড দিয়ে আবার DFS এ চেইক করবো True Return করে কিনা।
৩। সব শেষে False Return করবো।

Easy Implementation



ডিরেক্টেড এবং আনডিরেক্টেড গ্রাফের সাইকেল প্রিন্টিং

ডিরেক্টেড এবং আনডিরেক্টেড দুই ক্ষেত্রেই সাইকেল প্রিন্টিং এর কাজ টা সেইম।

আমরা দুই ক্ষেত্রেই প্রত্যেকটা Node এর Parent মার্ক করে রাখছি একই সাথে সাইকেলে র শুরু এবং শেষ মার্ক করে রাখছি।

এখন, একটা লুপের মাধ্যমেই আমরা পুরো সাইকেল টা খুজে পাইতে পারি। প্রথমে একটা Cycle Array রাখবো সাইকেলের নোড গুলা প্রিন্ট স্টোর করার জন্য।

        for(int v = cycle_end; v != cycle_start; v = parent[v]){

            cycle.push_back(v);

        }
এখানে সাইকেলের শেষ থেকে লুপ শুরু হইছে, যতক্ষন না সাইকেলে র শুরু তে না পৌছায় ততক্ষন লুপ চলতে থাকবে । প্রত্যেকবার ঐ নোডের প্যারেন্ট দ্বারা লুপ আপডেট করবো।

জিনিসটা আরো সুন্দর ভাবে বোঝা যেতে পারে, ধরি আমরা একটা নোড v তে আছি, এর প্যারেন্ট নোড এর প্যারেন্ট নোডে যাইতে v কে , V এর প্যারেন্ট দ্বারা আপডেট করবো।

Easy Implementation



Full Cycle Detection Implementation



Related Problems:

Round Trip
Round Trip II
Find Eventual Safe States (find nodes that are not in a cycle)
Cyclic Components