Graph Pada Python

Graph Pada Python

graf dalam komputer sains (ilmu komputer) adalah sebuah tipe data abstrak. Graf terdiri dari titik-titik (nodes) yang terhubung dengan sisi/busur (edge/arcs).

Berikut ini contoh graf yang akan kita tulis dalam kode program python:

Graf tersebut merupakan graf berarah yang memiliki enam buah titik dan delapan busur (arcs). Adapun delapan busur tersebut bisa kita nyatakan seperti berikut ini.

A -> B
A -> C
B -> C
B -> D
C -> D
D -> C
E -> F
F -> C

Graf sebenarnya bisa diubah ke dalam bentuk matriks dan ditulis dalam bentuk array dua dimensi ke dalam kode. Namun, karena contoh yang saya temukan menggunakan dictionary, maka graf di atas bisa dituliskan seperti berikut ini.

graf = {'A': ['B', 'C'],
        'B': ['C', 'D'],
        'C': ['D'],
        'D': ['C'],
        'E': ['F'],
        'F': ['C']}

Source code :

from __future__ import print_function

graph = { "a": ["c","d"],
          "b": ["c", "e"],
          "c": ["a", "b", "d", "e"],
          "d": ["c","e"],"e": ["c", "b"],
          "f": []}

def find_path(graph, start, end, path=[]):
                path = path + [start]
                for node in graph[start]:
                    if not node in path:
                        newpath = find_path(graph, node, end, path)
                        if newpath != None:
                            return newpath
                if start == end:
                    return path
                if not start in graph:
                    return None

def all_path(graph, start, end, path=[]):
                path = path + [start]
                if start == end:
                    return [path]
                if not start in graph:
                    return []
                paths = []
                for node in graph[start]:
                    if not node  in path:
                        newpaths = all_path(graph, node, end, path)
                        for newpath in newpaths:
                            paths.append(newpath)
                return paths

def shortest_path(graph, start, end, path=[]):
                path = path + [start]
                if start == end:
                    return path
                if not start in graph:
                    return None
             
                shortest = None
                for node in graph[start]:
                    if node not in path:
                        newpath = shortest_path(graph, node, end, path)
                        if newpath != None:
                            if not shortest or len(newpath) < len(shortest):
                                shortest = newpath
                return shortest

def main_menu():
    print ("=".center(80,"="))
    print("Selamat Datang Di Aplikasi (Graph)".upper().center(80))
    print("By : Moh. Irsad 170411100024".upper().center(80))
    print ("=".center(80,"="))
    stop = False
    while not stop:
        print ("=".center(30,"="))
        print ("Menu Aplikasi Graph")
        print ("=".center(30,"="))
        print ("1. Menemukan Jalur")
        print ("2. Tampilkan Semua Jalur")
        print ("3. Jalur Tercepat")
        print ("=".center(30,"="))
        opsi = int(input("Masukkan pilihan anda : "))
        print ()
     
        if opsi == 1 :
            print ("=".center(30,"="))
            print ("1. Menemukan Jalur")
            print ("=".center(30,"="))
            for i in graph:
                print ("Jalur ",i,":",graph[i])
            print ()
            awal = raw_input("Masukan Jalur Awal : ")
            akhir = raw_input("Masukan Jalur Tujuan Anda : ")
            print ()
            Kondisi = find_path(graph, awal, akhir)
            if Kondisi == None :
                print ("=".center(40,"="))
                print ("Jalur yang anda inginkan tidak ada!!!")
                print ("=".center(40,"="))
            else :
                print ("=".center(40,"="))
                print("Jalur Ditemukan :",find_path(graph, awal, akhir))
                print ("=".center(40,"="))
             
        elif opsi == 2:
            print ("=".center(30,"="))
            print ("2. Tampilkan Semua Jalur")
            print ("=".center(30,"="))
            for i in graph:
                print ("Jalur ",i,":",graph[i])
            print ()
            awal = raw_input("Masukan Jalur Awal : ")
            akhir = raw_input("Masukan Jalur Tujuan Anda : ")
            no = 1
            for i in all_path(graph,awal,akhir):
                print ("=".center(40,"="))
                print ("Jalur ke-%d : " %(no),i)
                print ("=".center(40,"="))
                no += 1
             
        elif opsi == 3:
            print ("=".center(30,"="))
            print ("3. Jalur Tercepat")
            print ("=".center(30,"="))
            for i in graph:
                print ("Jalur ",i,":",graph[i])
            print ()
            awal = raw_input("Masukan Jalur Awal : ")
            akhir = raw_input("Masukan Jalur Tujuan Anda : ")
            print ("=".center(40,"="))
            print("Jalur tercepat : ", shortest_path(graph,awal,akhir))
            print ("=".center(40,"="))
         
        else :
            print ("=".center(40,"="))
            print ("Pilihan yang anda masukan tidak ada".center(40))
            print ("=".center(40,"="))
             
        if opsi != 4:       
            opsi2 =raw_input("Apakah anda ingin mencoba opsi lain? (Yes/No) :")
            if opsi2 == 'No':
                stop = True
                print("=".center(80,"="))
                print("Terimakasih telah mencoba aplikasi kami.".upper().center(80))
                print("Moh. Irsad 170411100024".center(80))
                print("=".center(80,"="))

main_menu()