در این جلسه تیم کدگیت را با آموزش مرتب سازی توپولوژیکی در جاوا همراهی کنید. پیش نیاز این آموزش شامل موارد زیر است:
- جست و جوی اول عمق در جاوا
- رابط برنامهنویسی گراف جهت دار
- صف در جاوا
- پشته در جاوا
- شی گرایی در جاوا
- Constructor در جاوا
- حلقه for در جاوا
- دستور if در جاوا
- مدیریت استثناها
- آشنایی با روش بازگشتی
مرتب سازی توپولوژیکی
در نظریه گرافها، یک مرتبسازی موضعی یا ترتیب موضعی یک گراف بدون دور جهت دار، یک ترتیب خطی از همه رئوس آن است به طوری که هر گره قبل از همه گرههایی میآید که از آن به آنها یال خارج شده است. هر درخت بدون دور جهت دار یک یا چند مرتبسازی موضعی دارد. اگر گراف بدون دور نباشد آنگاه هیچ ترتیب خطی به این صورت وجود ندارد (ویکیپدیا).
الگوریتم مرتب سازی توپولوژیکی
برای مرتبسازی گراف، روی گراف پیمایش عمقاول میزنیم به هر راسی که رسیدیم آنرا علامت میزنیم.
هنگام خروج از آن راس یک علامت دیگر به معنی پایان بررسی آن راس روی آن میزنیم و آنرا در پشتهای میریزیم که جواب مسئله یعنی رئوس مرتب شده است. حال اگر به راسی رسیدیم که علامت وارد شدن به آن بود ولی علامت پایان نداشت یعنی که در گراف دور وجود دارد و مرتبسازی ممکن نیست.
سپس روی بقیه رئوسی که علامت نخوردهاند پیمایش انجام میدهیم ولی وارد راسهایی که علامت دارند نمیشویم(opedia.ir).
کد الگوریتم مرتب سازی توپولوژیکی در جاوا
برای پیاده سازی این مرتب سازی، ما از پشته و صف نیز استفاده کردیم ولی در اینجا به توضیح آنها نمیپردازیم. کلاسهای به کار رفته در این پیاده سازی به صورت زیر است:
- Bag
- Stack
- Queue
- Node
- Digraph
- ListIterator
- DepthFirstOrder
- DirectedCycle
- Topological
در لیست بالا ما شمارههای 1 تا 6 را در آموزشهای قبلی توضیح دادهایم و در این آموزش سه کلاس DepthFirstOrder و DirectedCycle و Topological را بررسی میکنیم.
DirectedCycle
کار این کلاس پیدا کردن دور در گراف است و این کار را با پیمایش اول عمق انجام میدهد. کد این کلاس به صورت زیر میباشد:
public class DirectedCycle { private boolean[] marked; private int[] edgeTo; private boolean[] onStack; private Stack<Integer> cycle; public DirectedCycle(Digraph G) { marked = new boolean[G.V()]; onStack = new boolean[G.V()]; edgeTo = new int[G.V()]; for (int v = 0; v < G.V(); v++) if (!marked[v] && cycle == null) dfs(G, v); } // check that algorithm computes either the topological order or finds a // directed cycle private void dfs(Digraph G, int v) { onStack[v] = true; marked[v] = true; for (int w : G.adj(v)) { // short circuit if directed cycle found if (cycle != null) return; // found new vertex, so recur else if (!marked[w]) { edgeTo[w] = v; dfs(G, w); } // trace back directed cycle else if (onStack[w]) { cycle = new Stack<Integer>(); for (int x = v; x != w; x = edgeTo[x]) { cycle.push(x); } cycle.push(w); cycle.push(v); } } onStack[v] = false; } public boolean hasCycle() { return cycle != null; } public Iterable<Integer> cycle() { return (Iterable<Integer>) cycle; } }
این کلاس شامل متدهای زیر میباشد:
- Dfs: متد پیمایش اول عمق میباشد.
- HasCycle: در صورت دور در گراف متد true برمیگرداند.
- Cycle: لیست نودهایی که در گراف دور تشکیل دادهاند را برمیگرداند.
- DirectedCycle: این متد Constructor ما است و در ورودی یک گراف جهت دار را میگیرد.
همچنین در کد بالا از فیلدهای زیر استفاده شده است:
- Marked: در صورت ملاقات یک راس مقدار آن true میشود(Marked[v]).
- EdgeTo: راسهای قبلی در مسیر رسیدن به راس V را نگهداری میکند.
- Cycle: راسهایی که در گراف، دور تشکیل دادهاند.
- OnStack: راسهایی که در پشته هستند.
DepthFirstOrder
این کلاس مرتب سازی توپولوژیکی را برای ما انجام میدهد.کد این کلاس به صورت زیر است:
public class DepthFirstOrder { private boolean[] marked; private int[] pre; private int[] post; private Queue<Integer> preorder; private Queue<Integer> postorder; private int preCounter; private int postCounter; public DepthFirstOrder(Digraph G) { pre = new int[G.V()]; post = new int[G.V()]; postorder = new Queue<Integer>(); preorder = new Queue<Integer>(); marked = new boolean[G.V()]; for (int v = 0; v < G.V(); v++) if (!marked[v]) dfs(G, v); } private void dfs(Digraph G, int v) { marked[v] = true; pre[v] = preCounter++; for (int w : G.adj(v)) { if (!marked[w]) { dfs(G, w); } } postorder.enqueue(v); post[v] = postCounter++; } public Iterable<Integer> reversePost() { Stack<Integer> reverse = new Stack<Integer>(); for (int v : postorder) reverse.push(v); return reverse; } }
کد بالا شامل متدهای زیر میباشد:
- ReversePost: این متد راسهای مرتب شده را برمیگرداند.
- Dfs: متد پیمایش اول عمق
- DepthFirstOrder: این متد Constructor است و یک گراف جهت دار را به عنوان ورودی میگیرد.
همچنین کلاس بالا شامل فیلدهای زیر میباشد:
- Marked: در صورت ملاقات یک راس مقدار آن true میشود(Marked[v]).
- Pre: محل قرار گیری راس V در لیست PreOrder
- Post: محل قرار گیری راس V در لیست PostOrder
- PreCounter: تعداد راسها در PreOrder
- PostCounter: تعداد راسها در PostOrder
- PreOrder: لیست راسها در دنباله PreOrder
- PostOrder: لیست راسها در دنباله PostOrder
تست مرتب سازی توپولوژیکی در جاوا
برای تست کدهای بالا، کلاس Topological را به صورت زیر بنویسید:
public class Topological { private Iterable<Integer> order; private int[] rank; public Topological(Digraph G) { DirectedCycle finder = new DirectedCycle(G); if (!finder.hasCycle()) { DepthFirstOrder dfs = new DepthFirstOrder(G); order = dfs.reversePost(); rank = new int[G.V()]; int i = 0; for (int v : order) rank[v] = i++; } } public Iterable<Integer> order() { return order; } public static void main(String[] args) { try { Digraph directed_graph = new Digraph(new File("graph.txt")); Topological topological = new Topological(directed_graph); for (int v : topological.order()) { System.out.println(v); } } catch (FileNotFoundException e) { e.printStackTrace(); } } }
در کد بالا دو فیلد order و rank استفاده شده است که به ترتیب لیست راس های ما در مرتب سازی و محل قرار گیری راس ها در مرتب سازی است. یک Constructor هم نوشتیم که یک گراف جهت دار را میگیرد با استفاده از کلاس DirectedCycle بررسی میکند گراف دور دارد یا خیر! پس از بررسی با استفاده از کلاس DepthFirstOrder لیست مرتب سازی توپولوژیکی ما را دریافت و چاپ میکند. در Main نیز کلاس Topological را صدا زدیم.