در این پروژه باید گراف را به چهار روش زیر پیاده سازی کنید.
-
Edge List
-
Adjacency List
-
Adjacency Map
-
Adjacency Matrix
برای پیاده سازی کافی است واسطی ( یا کلاس ابسترکت ) برای گراف طراحی کرده که شامل توابع زیر باشد و سپس چهارنوع پیاده سازی برای هریک از توابع را در کلاس های ارثبری شده از واسط ( یا کلاس ابسترکت) انجام دهید.
توابعی که باید پیاده سازی شوند به صورت زیر هستند :
- numVertices()
- vertices()
- numEdges()
- edges()
- getEdge(u,v)
- endVertices(e)
- opposite(v,e)
- outDegree(v)
- inDegree(v)
- outgoingEdges(v)
- incomingEdges(v)
- insertVertex(x)
- insertEdge(u,v,x)
- removeVertex(v)
- removeEdge(e)
توضیحات هریک از توابع و روش های پیاده سازی گراف در اسلایدهای استاد ذکر شده است . (صفحات ۱۳و ۱۴و ۱۵ و ۱۶ از اسلایدهای بخش گراف )
نکته : هر یک از اعضای تیم باید دوتا از پیاده سازی های گراف را انجام داده باشند و دو پیاده سازی ای هم که توسط هم تیمی خود انجام شده را در هنگام ارائه مسلط باشند.
پس از پیاده سازی چهار روش گراف، با استفاده از توابع واسط یا کلاس ابسترکت، می‌توانین از هرکدام از روش‌های پیاده سازی، برای پروژه استفاده نمایید و سرعت و بهینه بودن آن هارا با هم مقایسه کنید.