در این آموزش تیم کدگیت را با توضیح و پیاده سازی رابط برنامه نویسی گراف همراهی کنید. پیش نیاز این آموزش شامل موارد زیر است:
- آشنایی با گراف
- آشنایی با لیست پیوندی در جاوا
- Iterator در جاوا
- آشنایی با واژه رابطه برنامه نویسی(منظور api است)
- آشنایی با This در جاوا
- آشنایی با Constructor در جاوا
- آشنایی با متد در جاوا
- آشنایی با آرایه
- آشنایی با خواندن و نوشتن فایل در جاوا
- حلقه while در جاوا
- آشنایی مدیریت استثناها
- آشنایی با if
- آشنایی به for
- آشنایی با شی گرایی
رابط برنامهنویسی نرمافزار
رابط برنامهنویسی نرمافزار یا به صورت خلاصه رابط برنامه نویسی، رابط بین یک کتابخانه یا سیستمعامل و برنامههایی است که از آن تقاضای سرویس میکنند.
رابط کارکردهایی را تعریف میکند که کتابخانه یا سیستمعامل میتواند ارائه دهد و مفهومی مجرد است. این کارکردها سپس در قالب یک نرمافزار یا کتابخانه پیادهسازی میشوند. به عبارت سادهتر، رابط برنامهنویسی مجموعه توابعی است که یک برنامه میتواند از یک برنامه دیگر فرا بخواند.
برای مثال مایکروسافت برای APIهای ویندوز مرجعهایی استاندارد دارد که با استفاده از آنها برنامهنویسان میتوانند از قابلیتها و سرویسهای سیستمعامل در توسعه و نوشتن برنامههای کاربردی خود استفاده کنند(ویکیپدیا).
پیاده سازی رابط برنامه نویسی گراف(graph api)
در آموزش های قبل درباره ماتریس مجاورت و لیست همسایگی صحبت شد. در این قسمت یک رابط برنامهنویسی خواهیم نوشت و گراف را با لیست همسایگی در جاوا پیاده سازی میکنیم.
ابتدا یک کلاس به نام 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
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) فرض میکنیم راس های گراف وزن دار نیستند و دوم راس ها را با عدد نمایش میدهیم تا بتوان از اندیس آرایه برای پیاده سازی گراف استفاده کرد و کار را برای ما راحت کند.( نحوه پیاده سازی گراف وزن دار در آموزش دیگر خواهیم گفت)و سوم گراف ها جهت دار نیستند(گراف جهت دار را در آموزش های دیگر خواهیم گفت).
برای پیاده سازی رابط برنامه نویسی گراف ابتدا باید آرایه ای از راس ها را داشته باشیم و در هر راس همسایه های آن را ذخیره کنیم. برای این کار ما راس ها را به صورت 0،1،2،….1-V نامگذاری کردیم پس مثلا اگر بگوییم راس 1 و 4 با هم همسایه هستند پس ما به اندیس 1 آرایه رئوس میرویم و عدد 4 را به همسایه های آن اضاف میکنیم و برای راس 4 هم به اندیس 4 آرایه رئوس میرویم و عدد 1 را به همسایه های آن اضافه میکنیم(چون گراف جهت دار نیست).
کد کلاس Graph
public class Graph {
private 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];
}
}
کدی که در بالا زده شده شامل متدهای زیر است:
- Adj : متدی که لیست همسایه های راس مشخصی را به میدهد.
- addEdge: متدی که دو یال را به هم متصل میکند.
- E : متدی که تعدار یال را به ما میدهد.
- V : متدی که تعداد راس ها را به ما میدهد.
- Graph: متد constructor است و گراف را میسازد.
در کد گراف از سه فیلد استفاده شده است:
- E : متغییری که تعداد یال ها را نگه میدارد.
- V : متغییری که تعداد راس ها را نگه میدارد.
- 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();
}
}
خروجی برنامه به صورت زیر است.
همانطور که میبینید در رابط برنامه نویسی گراف بالا ما آمدیم و به صورت کدی تک تک یال ها را اضافه کردیم به گرافمان. حالا ممکن است ما گرافی بخواهیم با 100 یال آیا باز هم مجبوریم 100 خط بنویسیم تا تمام یال ها اضافه شوند و اگر بخواهیم عوض شود گراف باید 100 خط دیگر بنویسیم!!!!!! ما برای این کار یک راهکار ساده پیشنهاد میدهیم. یک فایل txt ساده بنویسید که به صورت زیر باشد.
13
13
0 5
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3
در سطر اول تعداد راس ها و در سطر دوم تعداد یال ها را مینویسیم و از سطر سوم به بعد نام راس هایی که با هم همسایه هستند را مینویسیم.فقط توجه داشته باشید که بین هر دو راس یک 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();
}
ما یک رابط برنامه نویسی گراف را در این آموزش نوشتیم. در آموزش بعد از این رابط استفاده میکنیم و در یک گراف، جست و جوی عمق اول را انجام خواهیم داد.