{CodeGate}

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

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

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

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

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

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

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

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

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

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

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

کد کلاس Bag

کد کلاس Node

کد کلاس ListIterator

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

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

کد کلاس Graph

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

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

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

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

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

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

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

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

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

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

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

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

پسورد: www.codegate.ir

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

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz