Cara menggunakan graph python program

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 dictionaryneighbors. 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 ')

print('add edge ')

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