DosenIT.com

Bekerja dengan Graph

Graph adalah struktur data penting.

SciPy memberi kita modul scipy.sparse.csgraph untuk bekerja dengan struktur data seperti itu.

Matriks Adjacency

Matriks Adjacency adalah matriks nxn dimana n adalah jumlah elemen dalam suatu graph.

Dan nilai-nilai tersebut mewakili hubungan antar elemen.

Contoh:

Untuk graph seperti ini, dengan elemen A, B dan C, hubungannya adalah:

A & B dihubungkan dengan bobot 1.

A & C dihubungkan dengan bobot 2.

C & B tidak terhubung.

Adjency Matrix akan terlihat seperti ini:

Contoh di bawah ini mengikuti beberapa metode yang paling sering digunakan untuk bekerja dengan matriks adjacency.

Komponen Terhubung

Menemukan semua komponen yang terhubung dengan metode connected_components().
Contoh:

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(connected_components(newarr))

Dijkstra

Gunakan metode dijkstra untuk menemukan jalur terpendek dalam graph dari satu elemen ke elemen lainnya.

Dibutuhkan argumen berikut:

1. return_predecessors: boolean (True untuk mengembalikan seluruh jalur traversal jika tidak False).
2. indices : indeks elemen untuk mengembalikan semua jalur dari elemen itu saja.
3. limit : bobot jalur maks.

Contoh:
Temukan jalur terpendek dari elemen 1 ke 2

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(dijkstra(newarr, return_predecessors=True, indices=0))

Floyd Warshall

Gunakan metode floyd_warshall() untuk menemukan jalur terpendek di antara semua pasangan elemen.

Contoh:
Temukan jalur terpendek di antara semua pasangan elemen

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(floyd_warshall(newarr, return_predecessors=True))

Bellman Ford

Metode bellman_ford() juga bisa menemukan jalur terpendek di antara semua pasangan elemen, dan metode ini juga bisa menangani bobot negatif.

Contoh:
Temukan jalur terpendek dari elemen 1 ke 2 dengan graph yang diberikan dengan bobot negatif

import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

arr = np.array([
  [0, -1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(bellman_ford(newarr, return_predecessors=True, indices=0))

Depth First Order

Metode depth_first_order() mengembalikan traversal kedalaman pertama dari sebuah node.

Fungsi ini mengambil argumen berikut:

1. graph.
2. elemen awal untuk melintasi graph.

Contoh
Trasversal kedalaman graph pertama pada matriks adjacency  yang diberikan

import numpy as np
from scipy.sparse.csgraph import depth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(depth_first_order(newarr, 1))

Breadth First Order

Metode breadth_first_order() mengembalikan traversal luas yang pertama dari sebuah node.

Fungsi ini mengambil argumen berikut:

1. graph.
2. elemen awal untuk melintasi graph.

Contoh
Traversal luas graph pertama pada matriks adjacency yang diberikan

import numpy as np
from scipy.sparse.csgraph import breadth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(breadth_first_order(newarr, 1))