java, جاوا, ساختمان داده در جاوا, گراف در جاوا

رابط برنامه نویسی گراف جهت دار (Directed Graph Api)

رابط برنامه نویسی گراف جهت دار

در این آموزش تیم کدگیت را با پیاده سازی رابط برنامه نویسی گراف جهت دار در جاوا همراهی کنید. پیش نیاز این آموزش شامل موارد زیر است:

  1. آشنایی با گراف
  2. آشنایی با لیست پیوندی در جاوا
  3. Iterator در جاوا
  4. آشنایی با واژه رابطه برنامه نویسی(منظور api است)
  5. آشنایی با This در جاوا
  6. آشنایی با Constructor در جاوا
  7. آشنایی با متد در جاوا
  8. آشنایی با آرایه
  9. آشنایی با خواندن و نوشتن فایل در جاوا
  10. حلقه while در جاوا
  11. آشنایی مدیریت استثناها
  12. آشنایی با if
  13. آشنایی به for
  14. آشنایی با شی گرایی

گراف جهت دار

تعریف زیر در سایت ویکیپدیا آمده است:

گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از مجموعه تمام زوج مرتب‌های متشکل از اعضای V است.

به صورت ساده میتوان گفت گراف جهت دار گرافی است که در یالها مسیر مشخص شده است. شکل زیر یک گراف جهت دار است.

پیاده سازی رابط برنامه نویسی گراف جهت دار در جاوا

در آموزش های قبل درباره ماتریس مجاورت و لیست همسایگی صحبت شد. در این قسمت یک رابط برنامه‌‌نویسی خواهیم نوشت و گراف را با لیست همسایگی در جاوا پیاده سازی میکنیم.

ابتدا یک کلاس به نام bag خواهیم نوشت. این کلاس همان لیست پیوندی است که در آموزشهای قبل کامل توضیح آن داده شده است. در اینجا کاری که کلاس bag برای ما میکند این است که همسایه های یک راس را در خود به صورت لیست پیوندی نگه میدارد.کد این کلاس تقریبا همان لیست پیوندی است پس در مورد کد توضیحات اضافی نمیدهیم.

کد کلاس Bag

import java.util.Iterator;

public class Bag<Item> implements Iterable<Item> {

     private Node<Item> first;
     private int size;

     public Bag() {
          size = 0;
          first = null;
     }

     public boolean isEmpty() {
          return first == null;
     }

     public int size() {
          return size;
     }

     public void add(Item item) {
          Node<Item> oldfirst = first;
          first = new Node<Item>(item, oldfirst);
          size++;
     }

     public Iterator<Item> iterator() {
          return new ListIterator<Item>(first);
     }

}

کد کلاس Node

public class Node<Item> {

     private Item data;
     private Node next_node;

     public Node(Item data, Node next_node) {
          this.data = data;
          this.next_node = next_node;
     }

     public Item getData() {
          return data;
     }

     public Node getNext_node() {
          return next_node;
     }



}

کد کلاس listIterator

public class ListIterator<Item> implements Iterator<Item> {
     private Node<Item> current;

     public ListIterator(Node<Item> first) {
          current = first;
     }

     public boolean hasNext() {
          return current != null;
     }


     public Item next() {
          if (!hasNext())
              throw new NoSuchElementException();
          Item item = current.getData();
          current = current.getNext_node();
          return item;
     }
}

خب حالا تقریبا نصف راه برای نوشتن رابط برنامه نویسی گراف جهت دار را رفته ایم. فقط چند نکته قبل از پیاده سازی کلاس گراف را بگوییم. اول ما در این رابط برنامه‌نویسی(api) فرض میکنیم راس های گراف وزن دار نیستند و دوم راس ها را با عدد نمایش میدهیم تا بتوان از اندیس آرایه برای پیاده سازی گراف استفاده کرد و کار را برای ما راحت کند.( نحوه پیاده سازی گراف وزن دار در آموزش دیگر خواهیم گفت)

برای پیاده سازی رابط برنامه نویسی گراف جهت دار ابتدا باید آرایه ای از راس ها را داشته باشیم و در هر راس همسایه های آن را ذخیره کنیم. برای این کار ما راس ها را به صورت 0،1،2،….1-V نامگذاری کردیم پس مثلا اگر بگوییم راس 1 و 4 با هم همسایه هستند پس ما به اندیس 1 آرایه رئوس میرویم و عدد 4 را به همسایه های آن اضاف میکنیم.

کد گراف جهت دار

import java.io.BufferedReader;

import java.io.File;

import java.io.FileNotFoundException;

import java.io.FileReader;

import java.io.IOException;

import java.util.InputMismatchException;

import java.util.NoSuchElementException;



public class Digraph {

     private int V;

     private int E;

     private Bag<Integer>[] adj;



     public Digraph(int V) {

          if (V < 0)

              throw new IllegalArgumentException(

                        "Number of vertices in a Digraph must be nonnegative");

          this.V = V;

          this.E = 0;

          adj = (Bag<Integer>[]) new Bag[V];

          for (int v = 0; v < V; v++) {

              adj[v] = new Bag<Integer>();

          }

     }



     public Digraph(File file) throws FileNotFoundException {



          if (file.exists()) {

              try {

                   BufferedReader buffer = new BufferedReader(new FileReader(file));

                   V = Integer.parseInt(buffer.readLine());

                   E = Integer.parseInt(buffer.readLine());



                   adj = (Bag<Integer>[]) new Bag[V];



                   for (int v = 0; v < V; v++) {

                        adj[v] = new Bag<Integer>();

                   }



                   String line;

                   while ((line = buffer.readLine()) != null) {

                        int v = Integer.parseInt(line.split(" ")[0]);

                        int w = Integer.parseInt(line.split(" ")[1]);

                        addEdge(v, w);

                   }



              } catch (FileNotFoundException e) {

                   // TODO Auto-generated catch block

                   e.printStackTrace();

              } catch (NumberFormatException e) {

                   // TODO Auto-generated catch block

                   e.printStackTrace();

              } catch (IOException e) {

                   // TODO Auto-generated catch block

                   e.printStackTrace();

              }

          } else {

              throw new FileNotFoundException();

          }



     }



     public int V() {

          return V;

     }



     public int E() {

          return E;

     }



     public void addEdge(int v, int w) {

          if (v < 0 || v >= V)

              throw new IndexOutOfBoundsException("vertex " + v

                        + " is not between 0 and " + (V - 1));

          if (w < 0 || w >= V)

              throw new IndexOutOfBoundsException("vertex " + w

                        + " is not between 0 and " + (V - 1));

          adj[v].add(w);

          E++;

     }



     public Iterable<Integer> adj(int v) {

          if (v < 0 || v >= V)

              throw new IndexOutOfBoundsException();

          return adj[v];

     }



     public Digraph reverse() {

          Digraph R = new Digraph(V);

          for (int v = 0; v < V; v++) {

              for (int w : adj(v)) {

                   R.addEdge(w, v);

              }

          }

          return R;

     }



     public String toString() {

          StringBuilder s = new StringBuilder();

          String NEWLINE = System.getProperty("line.separator");

          s.append(V + " vertices, " + E + " edges " + NEWLINE);

          for (int v = 0; v < V; v++) {

              s.append(String.format("%d: ", v));

              for (int w : adj[v]) {

                   s.append(String.format("%d ", w));

              }

              s.append(NEWLINE);

          }

          return s.toString();

     }



}

کد رابط برنامه نویسی گراف جهت دار که در بالا زده شده شامل متدهای زیر است:

  1. Adj : متدی که لیست همسایه های راس مشخصی را به میدهد.
  2. addEdge : متدی که دو راس در ورودی میگیرد(v و w) و راس v را به w متصل میکند.
  3. E : متدی که تعدار یال را به ما میدهد.
  4. V : متدی که تعداد راس ها را به ما میدهد.
  5. Reverse: متدی که جهت یال های گراف را برعکس میکند
  6. toString: نمایش کل گراف به صورت راس به راس.
  7. Digraph : متد constructor است. ما دو constructor داریم. اولی فقط یک تعداد راس ورودی میگیرد و گراف خالی تحویل میدهد.  دومی فایلی از گراف میگیرد که در آن فایل، راس های متصل به هم نشان داده شده است.

در کد رابط برنامه نویسی گراف جهت دار از سه فیلد استفاده شده است:

  1. E : متغییری که تعداد یال ها را نگه میدارد.
  2. V : متغییری که تعداد راس ها را نگه میدارد.
  3. Bag : آرایه ای از کلاس bag که لیست همسایه های هر راس به صورت جداگانه در آن نگهداری میشود. بدین معنی که در آرایه هر اندیس یک راس از گراف هست و لیستی از همسایه ها در خود نگه میدارد.

برای تست برنامه کد main زیر را بزنید.

    public static void main(String[] args) {

          try {
              Digraph directed_graph = new Digraph(new File("graph.txt"));
              System.out.println(directed_graph);
          } catch (FileNotFoundException e) {
              // TODO Auto-generated catch block
              e.printStackTrace();
          }
    }

در کد رابط برنامه نویسی گراف جهت دار ما از یک فایل (graph.txt) استفاده کردیم که گراف و راس هایی که میخواهیم در آن است. فایل به صورت زیر است:

13
22
4 2
2 3
3 2
6 0
0 1
2 0
11 12
12 9
9 10
9 11
7 9
10 12
11 4
4 3
3 5
6 8
8 6
5 4
0 5
6 4
6 9
7 6

سطر اول تعداد راس ها و سطر دوم تعداد یال ها است. سطر سوم به بعد راس هایی که به هم یال دارند نوشته شده است. به طور مثال  راس 4 و 2 به هم متصل هستند بدین معنی که از راس 4 به راس 2 یالی وجود دارد و نه برعکس(گراف جهت دار است).

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *