Cara menggunakan digraph in python

Graph adalah salah satu model paling umum dari struktur alam dan buatan manusia. Mereka dapat digunakan untuk memodelkan berbagai jenis hubungan dan dinamika proses dalam ilmu komputer, sistem fisik, biologi dan sosial. Banyak masalah yang menjadi perhatian praktis dapat diwakili oleh teori graph. Secara umum teori graph memiliki berbagai aplikasi di berbagai bidang. 

Network graph secara sederhana disebut sebagai graph. Ini terdiri dari satu set node yang dihubungkan oleh cabang. Dalam grafik, simpul adalah titik temu dari dua cabang atau lebih. Artinya, segmen garis pada grafik mewakili cabang yang sesuai dengan elemen graph tersebut.

Pada artikel ini, dibuat program graph serta menghitung shortest-path dari sebuah graph. Implementasi perhitungan shortest-path sangatlah dibutuhkan dalam penyelesaian permasalahan dunia nyata.

Sebagai contoh, aplikasi pemesanan moda transportasi yang biasa Anda gunakan sangat bergantung pada performa dari algoritma permodelan graph yang mereka untuk mementukan driver mana yang terdekat untuk mengambil pesanan Anda.

Pada graf pertama digunakan library networkx untuk melakukan pembentukan graf tidak berarah atau undirected graph. Terlihat bahwa digunakan sintaks G_asymmetric.add_edge() untuk membentuk node dan vertex pada graf tersebut. Library networkx akan dengan otomatis menampilkan bagaimana graf terlihat apabila dibentuk dari input-input statis yang dimasukkan pengguna.

Script 1

import networkx as nx

G_symmetric = nx.Graph()

G_symmetric.add_edge('Amitabh Bachchan','Abhishek Bachchan')

G_symmetric.add_edge('Amitabh Bachchan','Aamir Khan')

G_symmetric.add_edge('Amitabh Bachchan','Akshay Kumar')

G_symmetric.add_edge('Amitabh Bachchan','Dev Anand')

G_symmetric.add_edge('Abhishek Bachchan','Aamir Khan')

G_symmetric.add_edge('Abhishek Bachchan','Akshay Kumar')

G_symmetric.add_edge('Abhishek Bachchan','Dev Anand')

G_symmetric.add_edge('Dev Anand','Aamir Khan')

nx.draw_networkx(G_symmetric)

G_asymmetric = nx.DiGraph()

G_asymmetric.add_edge('A','B')

G_asymmetric.add_edge('A','D')

G_asymmetric.add_edge('C','A')

G_asymmetric.add_edge('D','E')

G_asymmetric.add_edge('A','E')

Hasil

Pada graf kedua dibuat menggunakan library matplotlib.pyplot untuk membuat sebuah bidang yang terbentuk dari beberapa sudut x dan y. Dengan library matplotlib.pyplot dibantu dengan numpy, kita dapat mendefinisikan semacam sudut standar yang akan membantu kita tahu bahwa apabila value dari masing-masing sudut di rubah akan menunjukkan dimana posisi sebenarnya dari bidang yang telah dibuat tersebut.

Caranya yang pertama yaitu dengan menggunakan plt.axes(), dilanjutkan di baris baru dengan plt.axes([0.65, 0.65, 0.2, 0.2]) ß hanya contoh, valuenya bisa apa saja yang kita inginkan.

Sebelumnya juga harus diperhatikan bahwa matplotlib.pyplot memerlukan penggunanya untuk mendefinisikan style macam apa yang ingin mereka gunakan (seperti template awal). Hal itu dilakukan dengan plt.style.use(‘nama-style’). Beberapa style yang bisa digunakan adalah seaborn-white dan fivethirtyeight. Tanpa menggunakan itu, graf tidak dapat terbentuk.

Script 2

import matplotlib.pyplot as plt

plt.style.use('seaborn-white')

import numpy as np

ax1 = plt.axes()  # standard axes

ax2 = plt.axes([0.65, 0.65, 0.2, 0.2])

Hasil

Pada graf ketiga ini, dengan dictionary, mudah untuk mengimplementasikan daftar adjasensi dengan Python. Dalam implementasi tipe data abstrak Graf , dibuat contoh seperti dibawah, yang menyimpan daftar master dari simpul, dan Vertex, yang akan merepresentasikan setiap simpul pada graf.

Masing-masing Vertex menggunakan dictionary untuk melacak simpul yang terhubung, dan bobot setiap sisi. Jika bobot tidak diperlukan, satu set dapat digunakan sebagai pengganti kamus. Untuk menangani kedua kasus, dictionary yang dipanggil adalah neighbors.

Script dibawah ini menunjukkan kode untuk Vertex kelas tersebut. Metode inisialisasi hanya menginisialisasi key, yang biasanya berupa string, dan dictionary neighbors. Metode add_neighbor yang digunakan menambahkan koneksi dari vertex ini ke yang lain. Metode connections mengembalikan semua simpul dalam daftar adjasensi, yang diwakili oleh neighbors variabel contoh. Metode weight mengembalikan berat tepi dari titik ini ke titik dilewatkan sebagai parameter.

Kelas Graph, yang diperlihatkan dalam script dibawah ini, berisi dictionary yang memetakan nama simpul ke objek simpul. Graph juga menyediakan metode untuk menambahkan simpul ke graf dan menghubungkan satu simpul ke simpul lainnya. Diimplementasikan metode __iter__ untuk memudahkan pengulangan semua objek simpul dalam graf tertentu. Bersama-sama, kedua metode memungkinkan Anda untuk melakukan iterasi pada simpul dalam graf berdasarkan nama, atau objek itu sendiri.

Contoh script dibawah ini digunakan untuk menentukan waktu minimum spanning tree, total nilai spanning, jumlah edge, jalur terpendek dari node 0 ke 9 dan weight dari node 0 ke 9 dari sebuah