graph-api

رابط برنامه نویسی گراف (Graph API)

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

  1. لیست پیوندی
  2. ماتریس مجاورت
  3. لیست همسایگی
  4. شی گرایی
  5. پیاده سازی گراف در جاوا
  6. گراف

رابط برنامه نویسی نرم‌افزار

رابط برنامه نویسی نرم‌افزار یا به صورت خلاصه رابط برنامه نویسی، رابط بین یک کتابخانه یا سیستم‌عامل و برنامه‌هایی است که از آن تقاضای سرویس می‌کنند.

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

برای مثال مایکروسافت برای APIهای ویندوز مرجع‌هایی استاندارد دارد که با استفاده از آنها برنامه‌نویسان می‌توانند از قابلیت‌ها و سرویس‌های سیستم‌عامل در توسعه و نوشتن برنامه‌های کاربردی خود استفاده کنند(ویکیپدیا).

 

پیاده سازی رابط برنامه نویسی گراف(graph api)

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

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

single linked list

کد کلاس 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

import java.util.Iterator;

import java.util.NoSuchElementException;

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) فرض میکنیم راس های گراف وزن دار نیستند و دوم راس ها را با عدد نمایش میدهیم تا بتوان از اندیس آرایه برای پیاده سازی گراف استفاده کرد و کار را برای ما راحت کند.( نحوه پیاده سازی گراف وزن دار در آموزش دیگر خواهیم گفت)و سوم گراف ها جهت دار نیستند(گراف جهت دار را در آموزش های دیگر خواهیم گفت).

رابط برنامه‌نویسی گراف

برای پیاده سازی رابط برنامه نویسی گراف ابتدا باید آرایه ای از راس ها را داشته باشیم و در هر راس همسایه های آن را ذخیره کنیم. برای این کار ما راس ها را به صورت ۰،۱،۲،….۱-V نامگذاری کردیم پس مثلا اگر بگوییم راس ۱ و ۴ با هم همسایه هستند پس ما به اندیس ۱ آرایه رئوس میرویم و عدد ۴ را به همسایه های آن اضافه میکنیم و برای راس ۴ هم به اندیس ۴ آرایه رئوس میرویم و عدد ۱ را به همسایه های آن اضافه میکنیم(چون گراف جهت دار نیست).

کد کلاس Graph

public class Graph {

     private final int V;

     private int E;

     private Bag<Integer>[] adj;

     public Graph(int V) {

          if (V < 0)

              throw new IllegalArgumentException(

                        “Number of vertices 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 int V() {

          return V;

     }

     public int E() {

          return E;

     }

     public void addEdge(int v, int w) {

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

              throw new IndexOutOfBoundsException();

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

              throw new IndexOutOfBoundsException();

          E++;

          adj[v].add(w);

          adj[w].add(v);

     }

     public Iterable<Integer> adj(int v) {

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

              throw new IndexOutOfBoundsException();

          return adj[v];

     }

}

کدی که در بالا زده شده شامل متدهای زیر است:

  1. ()Adj : متدی که لیست همسایه های راس مشخصی را به میدهد.
  2. ()addEdge : متدی که دو یال را به هم متصل میکند.
  3. ()E : متدی که تعدار یال را به ما میدهد.
  4. ()V : متدی که تعداد راس ها را به میدهد.
  5. ()Graph : متد constructor است و گراف را میسازد.

در کد گراف از سه فیلد استفاده شده است:

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

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

     public static void main(String[] args) {

          Graph g = new Graph(5);

          g.addEdge(1, 2);

          g.addEdge(1, 3);

          g.addEdge(2, 3);

          g.addEdge(0, 4);

          g.addEdge(3, 4);

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

              System.out.print(v+”->”);

              for (int w : g.adj[v]) {

                   System.out.print(w+” “);

              }

              System.out.println();

          }

     }

خروجی برنامه به صورت زیر است(تمام همسایه های هر راس را به میدهد).

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

همانطور که میبینید در رابط برنامه نویسی گراف بالا ما آمدیم و به صورت کدی تک تک یال ها را اضافه کردیم به گرافمان. حالا ممکن است ما گرافی بخواهیم با ۱۰۰ یال آیا باز هم مجبوریم ۱۰۰ خط بنویسیم تا تمام یال ها اضافه شوند و اگر بخواهیم عوض شود گراف باید ۱۰۰ خط دیگر بنویسیم!!!!!! ما برای این کار یک راهکار ساده پیشنهاد میدهیم. یک فایل txt ساده بنویسید که به صورت زیر باشد.

۱۳

۱۳

۰ ۵

۴ ۳

۰ ۱

۹ ۱۲

۶ ۴

۵ ۴

۰ ۲

۱۱ ۱۲

۹ ۱۰

۰ ۶

۷ ۸

۹ ۱۱

۵ ۳

در سطر اول تعداد راس ها و در سطر دوم تعداد یال ها را مینویسیم و از سطر سوم به بعد نام راس هایی که با هم همسایه هستند را مینویسیم.فقط توجه داشته باشید که بین هر دو راس یک space بزنید. وقتی فایل را ساختید constructor زیر را به برنامه اضافه کنید.

     public Graph(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();

          }

     }

کد بالا از فایل ما یک گراف درست میکند و ما به راحتی میتوانیم با تغییر فایل به گراف جدیدی برسیم بدون حتی تغییر یک کد!!!

برای main برنامه هم کافیست تغییر زیر را بدهید تا گراف شما از فایل گرفته شود.

          Graph graph = null;

          try {

              graph = new Graph(new File(“graph.txt”));

          } catch (FileNotFoundException e) {

              // TODO Auto-generated catch block

              e.printStackTrace();

          }

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

              System.out.print(v+”->”);

              for (int w : graph.adj[v]) {

                   System.out.print(w+” “);

              }

              System.out.println();

          }

 

ما یک رابط برنامه نویسی گراف را در این آموزش نوشتیم. در آموزش بعد از این رابط استفاده میکنیم و در یک گراف، جست و جوی عمق اول را انجام خواهیم داد.

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

استفاده از گراف در جستجوی اول عمق

استفاده از گراف در جستجوی اول سطح

استفاده از گراف در مولفه همبندی

لینک کمکی:

پیاده سازی گراف جهت دار در جاوا

یک دیدگاه برای “رابط برنامه نویسی گراف (Graph API)

پاسخ دهید

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