Mengimplementasikan Python dengan library networkx dalam Pembuatan Graf
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 undirected graph
yang terbentuk.
Script 3
import networkx as nx
import numpy as np
import sys
import time
class Graph:
def __init__(self):
# dictionary containing keys that map to the
corresponding vertex object
self.vertices = {}
def add_vertex(self, key):
"""Add a vertex with the given key to the
graph."""
vertex = Vertex(key)
self.vertices[key] = vertex
def get_vertex(self, key):
"""Return vertex object with the corresponding
key."""
return self.vertices[key]
def __contains__(self, key):
return key in self.vertices
def add_edge(self, src_key, dest_key, weight=1):
"""Add edge from src_key to dest_key with
given weight."""
self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)
def does_vertex_exist(self, key):
return key in self.vertices
def does_edge_exist(self, src_key, dest_key):
"""Return True if there is an edge from
src_key to dest_key."""
return
self.vertices[src_key].does_it_point_to(self.vertices[dest_key])
def display(self):
#print('Vertices: ', end='')
#for v in self:
# print(v.get_key(), end=' ')
#print()
list_edge = []
#print('Edges: ')
G_symmetric = nx.Graph()
tot_w = 0
tot_edge = 0
for v in self:
for dest in v.get_neighbours():
w =
v.get_weight(dest)
if
(int(v.get_key()) < int(dest.get_key())):
edge
= []
tot_w += w
tot_edge += 1
edge.append(v.get_key())
edge.append(dest.get_key())
edge.append(w)
#print('(src={}, dest={}, weight={}) '.format(v.get_key(),
#
dest.get_key(), w))
list_edge.append(edge)
print("Total nilai sapnning= %d dan jumlah
edge= %d"%(tot_w,tot_edge))
return list_edge
def __len__(self):
return len(self.vertices)
def __iter__(self):
return iter(self.vertices.values())
class Vertex:
def __init__(self, key):
self.key = key
self.points_to = {}
def get_key(self):
"""Return key corresponding to this vertex
object."""
return self.key
def add_neighbour(self, dest, weight):
"""Make this vertex point to dest with given
edge weight."""
self.points_to[dest] = weight
def get_neighbours(self):
"""Return all vertices pointed to by this
vertex."""
return self.points_to.keys()
def get_weight(self, dest):
"""Get weight of edge from this vertex to
dest."""
return self.points_to[dest]
def does_it_point_to(self, dest):
"""Return True if this vertex points to
dest."""
return dest in self.points_to
def mst_krusal(g):
"""Return a minimum cost spanning tree of the connected
graph g."""
mst = Graph() # create new Graph object to hold the MST
if len(g) == 1:
u = next(iter(g)) # get the single vertex
mst.add_vertex(u.get_key()) # add a copy of it
to mst
return mst
# get all the edges in a list
edges = []
for v in g:
for n in v.get_neighbours():
# avoid adding two edges for
each edge of the undirected graph
if v.get_key() < n.get_key():
edges.append((v,
n))
# sort edges
edges.sort(key=lambda edge: edge[0].get_weight(edge[1]))
# initially, each vertex is in its own component
component = {}
for i, v in enumerate(g):
component[v] = i
# next edge to try
edge_index = 0
# loop until mst has the same number of vertices as g
while len(mst) < len(g):
u, v = edges[edge_index]
edge_index += 1
# if adding edge (u, v) will not form a cycle
if component[u] != component[v]:
# add to mst
if not
mst.does_vertex_exist(u.get_key()):
mst.add_vertex(u.get_key())
if not
mst.does_vertex_exist(v.get_key()):
mst.add_vertex(v.get_key())
mst.add_edge(u.get_key(),
v.get_key(), u.get_weight(v))
mst.add_edge(v.get_key(),
u.get_key(), u.get_weight(v))
# merge components of u and v
for w in g:
if component[w] ==
component[v]:
component[w] = component[u]
return mst
g = Graph()
print('Undirected Graph')
print('Menu')
print('add vertex <key>')
print('add edge <src> <dest> <weight>')
print('mst')
print('display')
print('quit')
N = 10
for i in range (0,N):
g.add_vertex(str(i))
a = np.random.randint(2,200,(N,N), dtype=int)
print(a)
for i in range (0,N):
for j in range (0,N):
#if (i < j) :
g.add_edge(str(i),str(j),a[i,j])
start = time.time()
mst = mst_krusal(g)
print('Waktu Minimum Spanning Tree:%2f'%(time.time()-start))
l_edge = mst.display()
G_sym = nx.Graph()
for e in l_edge:
G_sym.add_edge(e[0],e[1],weight=int(e[2]))
nx.draw_networkx(G_sym)
sh_path = nx.shortest_path(G_sym,'0', str(N-1))
G_sp = nx.Graph()
print("Jalur terpendek dari node : 0 ke 9: ", sh_path)
for i in range (len(sh_path)-1):
v1 = g.get_vertex((sh_path[i]))
v2 = g.get_vertex((sh_path[i+1]))
print("weight dari ",v1.get_key()," ke ",v2.get_key()," =
",v1.get_weight(v2))
G_sp.add_edge(v1,v2,weight=v1.get_weight(v2))
#nx.draw_networkx(G_sp)
Hasil
Tugas Praktikum 6 - Moda Self-study
No comments