Graph - Python

Graph adalah himpunan sisi atau edge, yang menghubungkan antar node atau verteks dalam suatu kumpulan data menjadi suatu simpul. graph dapat berfunsi sebagai database. Graph menggunakan type dictionary dinama ada kata kunci dan ada value.

1.      Fungsi all_path

Fungsi ini digunakan untuk menemukan semua path atau semua jalur dari titik A ke titik E. Pada fungsi ini menggunakan 4 buah parameter yaitu Graph sebagai data graph, start yang merupakan titik mulai dari urutan graph, end yang merupakan titik berakhir, dan Path=[] yang digunakan untuk menginisialisasi path berupa list kosong. Berikut penjelasan mengenai algoritma yang telah saya buat:

a.       Menginisialisasi path dengan isian path di gabung dengan start

b.      Jika start sama dengan akhir maka mengembalikan nilai path dalam list.

c.       Jika start tidak ada dalam graph maka dikembalikan nilai list kosong  []

d.      Inisialisasi list baru bernama  Paths dengan []

e.       Pengulangan setiap node (value) yang dimiliki oleh node tertentu dalam graph dengan list start.

f.       Jika node(value) tidak ada di dalam path  maka lakukan recursive dengan diinisialisai newpathsdengan mengganti beberapa parameter, yaitu:  start = node, path = [] dengan path..

g.      Lakukan looping sebanyak isi dari newpaths.

h.      Jika node sudah ada dalam path maka hentikan  lopping

i.        Ketika looping selesai lakukan pengembalian nilai list Paths

2.      Fungsi shortest_path

Fungsi ini digunakan untuk menemukan jalur tercepat dari titik A ke titik E.Pada fungsi ini menggunakan 4 buah parameter yang sama dengan parameter fungsi diatasnya.

Berikut algoritma dari program yang telah saya buat :

a.       Inisialisai list path dengan isian path di gabung dengan start

b.      Jika start sama dengan akhir maka mengembalikan nilai path dalam list.

c.       Jika start tidak ada dalam graph maka dikembalikan nilai None

d.      Inisialisasi variabel shortest dengan None

e.       Pengulangan setiap node (value) yang dimiliki oleh node tertentu.

f.       Jika node(value) tidak ada di dalam path  maka lakukan recursive diinisialisai newpath denganmengubah parameter start dengan node, path = [] dengan path bukan default

j.        Jika newpath dan shortest  ada nilainya (tidak sama dengan none) dan panjang newpath lebih kecil dari panjang shortest maka lakukan inisialisasi shortest dengan newpath.

k.      Jika node sudah ada dalam path lakukan lopping

l.        Ketika looping selesai lakukan pengembalian nilai shortest

3.      Fungsi find_ListShortestPath

Fungsi ini digunakan untuk menumakn jalur artenatif tercepat dari titik A ke Titik E.Pada fungsi ini menggunakan 2 parameter yaitu Allpaths yang merupakan inisialisasi dari ListAll_Path danShortestPath yang merupakan inisailisai dari ShortPath

Berikut Algoritma :

a.       Inisialisai shortest List []

b.      Looping sebanyak isi allpath

c.       Jika panjangnya sama dengan shortestpath maka masukkan ke dalam shortest list

d.      Jika looping selesai makan lakukan pengembalian nilai shortest list.

4.      Fungsi displayBlock

Fungsi ini digunakan untuk Menampilkan Dalam Bentuk List ke Bawah. Pada fungis ini paramter hanya satu yaitu hasil dari pengembalian nilai masing masiang fungsi soal agar bisa tampil dengan rapi. Fungsi iini tidak memiliki pengembalian.

Algoritma :

a.       Looping sepanjang data dalam list kemudian lakukan print masing masing data.

5.      Fungsi Find_All Edge

Fungsi ini digunakan untuk menemukan semua Edge atau penghubung antara dua titik.Pada fungsi kali ini menggunakan 1 parameter yaitu dict Graph

Berikut Algoritma :

a.       Inisialisasi Edge List []

b.      Looping sebanyak kata kunci atau node dari graph

c.       Jika kunci tersebut memiliki nilai maka lakukan looping sebanyak nilai node itu

d.      Gabungkan kunci dan nilai kemudian tampung di temp. Dan masukkan ke dalam Edge List.

e.       Jika looping telah selesai maka lakukan pengmbalian nilai Edge List

Penjelasan Program :

a.       Pemanggilan fungsi allpath ditampung di variabel Allpath kemudian lakukan print dengan menggunakan fungsi displayBlock agak hasil rapi.

b.      Tampung pemanggilan shortestpath dengan variabel Shortest, kemudian tampung hasil pemnggilan pencarian other shortest dari allpath menggunakan parameter Shortest dan Allpath.

c.       Memanggil fungsi find All edge dan di print.