Graph Optimization with NetworkX in Python

Dalam tutorial ini, Anda akan mengatasi masalah yang telah mapan dalam teori graf yang disebut Chinese Postman Problem. Ada beberapa komponen algoritme yang meski secara konsep sederhana, ternyata cukup intens secara komputasi. Namun, untuk tutorial ini, hanya diperlukan sedikit pengetahuan sebelumnya tentang Python: tidak diperlukan latar belakang matematika, ilmu komputer, atau teori graf yang ketat.

Tutorial ini pertama-tama akan membahas blok bangunan dasar graf (node, edge, path, dll.) dan menyelesaikan masalah pada graf nyata (jaringan jalur di sebuah taman negara bagian) menggunakan pustaka NetworkX di Python. Anda akan fokus pada konsep inti dan implementasinya. Bagi pembaca yang tertarik, referensi bacaan lebih lanjut tentang inti optimisasi disediakan.

Motivasi Optimisasi Graf

Masalahnya

Anda mungkin pernah mendengar Travelling Salesman Problem yang bermuara pada pencarian rute terpendek (misalnya, jalan) yang menghubungkan sekumpulan node (misalnya, kota). Meskipun kurang dikenal, Chinese Postman Problem (CPP), juga disebut sebagai Route Inspection atau Arc Routing problem, cukup mirip. Tujuan CPP adalah menemukan lintasan terpendek yang melintasi semua tautan (jalan) pada sebuah graf setidaknya sekali. Jika hal ini dapat dilakukan tanpa harus kembali melalui jalan yang sama dua kali, bagus; Itulah skenario ideal dan masalahnya cukup sederhana. Namun, jika beberapa jalan harus dilalui lebih dari sekali, Anda memerlukan sedikit matematika untuk menemukan rute terpendek yang melewati setiap jalan setidaknya sekali dengan total jarak tempuh serendah mungkin.

Motivasi Pribadi

(Berikut adalah catatan pribadi: agak gombal, jenaka, dan 100% tidak diperlukan untuk mempelajari optimisasi graf di Python)

Saya memiliki aplikasi kehidupan nyata untuk menyelesaikan masalah ini: meraih peringkat Giantmaster Marathoner.

Apa itu Giantmaster? Giantmaster adalah seseorang (anjing atau manusia) yang telah menyusuri setiap jalur di Sleeping Giant State Park di Hamden CT (bertetangga dengan kampung halaman saya di Wallingford)... sepanjang hidupnya. Giantmaster Marathoner adalah seseorang yang telah menyusuri semua jalur tersebut dalam satu hari.

Berkat pencatatan yang teliti oleh Sleeping Giant Park Association, daftar lengkap para Giantmaster dan level Giantmastering mereka dapat ditemukan di sini. Harus saya akui ini sangat memotivasi saya untuk memulai proyek sampingan ini dan turun ke jalur. Sementara saya sendiri mencapai status Giantmaster pada musim dingin 2006 saat saya menjadi relawan muda di Sleeping Giant Trail Crew (yang dengan senang hati saya lihat tercatat dalam arsip SG), tantangan baru sejak itu bermunculan. Meski kategori Giantmaster 12-bulan dan 4-musim mengesankan dan menggoda, keduanya juga akan menuntut lebih banyak perjalanan dari rumah saya saat ini (DC) ke kampung halaman saya (CT) daripada yang secara realistis bisa saya lakukan... dan keduanya juga tidak terlalu menarik untuk optimisasi graf, jadi Giantmaster Marathon adalah pilihannya!

Untuk referensi lain, peta jalur Sleeping Giant disediakan di bawah ini:

Mengenal Graf

Hal yang menyenangkan tentang graf adalah konsep dan istilahnya umumnya intuitif. Meski begitu, berikut beberapa istilah dasar:

Graf adalah struktur yang memetakan relasi antar objek. Objek tersebut disebut node dan koneksi di antara mereka disebut edge dalam tutorial ini. Perhatikan bahwa edge dan node sering disebut dengan beberapa nama yang pada umumnya berarti hal yang sama persis:

node == vertex == point
edge == arc == link

Graf awal bersifat tak berarah. Artinya, edge Anda tidak memiliki orientasi: mereka dua arah. Contoh: A<--->B == B<--->A.
Sebaliknya, graf yang mungkin Anda buat untuk menentukan lintasan terpendek untuk menyusuri setiap jalur bisa berupa graf berarah, tempat urutan dan arah edge penting. Contoh: A--->B != B--->A.

Graf ini juga merupakan graf berbobot edge di mana jarak (dalam mil) antara setiap pasangan node yang bertetangga merepresentasikan bobot sebuah edge. Ini ditangani sebagai sebuah atribut edge bernama "distance".

Degree mengacu pada jumlah edge yang insiden (menyentuh) sebuah node. Node disebut odd-degree ketika jumlah ini ganjil dan even-degree ketika genap.

Solusi untuk masalah CPP ini akan berupa tur Euler: graf tempat dapat dibuat sebuah siklus yang melalui setiap edge tepat sekali dari node awal kembali ke dirinya sendiri (tanpa mundur). Tur Euler juga dikenal dengan beberapa nama:

Eulerian tour == Eulerian circuit == Eulerian cycle

Matching adalah himpunan bagian edge di mana tidak ada node yang muncul lebih dari sekali. Minimum weight matching mencari matching dengan jumlah bobot edge serendah mungkin.

NetworkX: Manipulasi dan Analisis Graf

NetworkX adalah paket Python paling populer untuk memanipulasi dan menganalisis graf. Beberapa paket lain menawarkan tingkat manipulasi graf dasar yang sama, terutama igraph yang juga memiliki binding untuk R dan C++. Namun, saya menemukan bahwa NetworkX memiliki algoritme graf terkuat yang saya butuhkan untuk menyelesaikan CPP.

Menginstal Paket

Jika Anda pernah melakukan analisis data di Python atau menggunakan distribusi Anaconda, kemungkinan Anda sudah memiliki pandas dan matplotlib. Namun, Anda mungkin belum memiliki networkx. Ini seharusnya menjadi satu-satunya dependensi di luar Python Standard Library yang Anda perlukan untuk menjalankan tutorial ini. Instalasinya mudah dengan pip:

pip install pandas
pip install networkx
pip install matplotlib

Ini seharusnya semua paket yang Anda butuhkan untuk saat ini. imageio dan numpy diimpor di bagian akhir untuk membuat animasi GIF dari solusi CPP. Animasi disematkan dalam artikel ini, jadi paket-paket tersebut opsional.

import itertools
import copy
import networkx as nx
import pandas as pd
import matplotlib.pyplot as plt

Muat Data

Daftar Edge

Daftar edge adalah struktur data sederhana yang akan Anda gunakan untuk membuat graf. Setiap baris merepresentasikan satu edge dari graf dengan beberapa atribut edge.

• node1 & node2: nama node yang terhubung.
• trail: atribut edge yang menunjukkan nama singkat jalur untuk setiap edge. Contoh: rs = red square
• distance: atribut edge yang menunjukkan panjang jalur dalam mil.
• color: warna jalur yang digunakan untuk plotting.
• estimate: atribut edge yang menunjukkan apakah jarak edge diperkirakan dari hasil menaksir peta jalur (1=ya, 0=tidak) karena beberapa jarak tidak disediakan. Ini hanya untuk referensi; tidak digunakan untuk analisis.

# Grab edge list data hosted on Gist
edgelist = pd.read_csv('https://gist.githubusercontent.com/brooksandrew/e570c38bcc72a8d102422f2af836513b/raw/89c76b2563dbc0e88384719a35cba0dfc04cd522/edgelist_sleeping_giant.csv')

# Preview edgelist
edgelist.head(10)

Daftar Node

Daftar node biasanya bersifat opsional di networkx dan pustaka graf lain ketika daftar edge disediakan karena nama node tercantum pada dua kolom pertama daftar edge. Namun, dalam kasus ini, ada beberapa atribut node yang ingin kita tambahkan: koordinat X, Y dari node (perpotongan jalur) sehingga Anda dapat memplot graf dengan tata letak yang sama seperti peta jalur.

Saya menghabiskan satu sore memberi anotasi ini secara manual dengan menelusuri gambar menggunakan GIMP:

• id: nama node yang sesuai dengan node1 dan node2 pada daftar edge.
• X: posisi/koordinat horizontal node relatif terhadap kiri atas.
• Y posisi/koordinat vertikal node relatif terhadap kiri atas.

Catatan tentang Pembuatan Daftar Node & Edge

Membuat nama node juga memerlukan sedikit usaha manual. Setiap node merepresentasikan perpotongan dua jalur atau lebih. Jika memungkinkan, node dinamai dengan format trail1_trail2 di mana trail1 mendahului trail2 dalam urutan alfabet.

Keadaan menjadi sedikit sulit ketika jalur yang sama berpotongan lebih dari sekali. Misalnya, jalur Oranye dan Putih. Dalam kasus ini, saya menambahkan akhiran _2 atau _3 pada nama node. Misalnya, Anda memiliki dua nama node yang berbeda untuk dua perpotongan Oranye dan Putih yang berbeda: o_w dan o_w_2.

Ini memerlukan banyak coba-coba dan membandingkan plot yang dihasilkan dengan koordinat X,Y terhadap peta jalur sebenarnya.

# Grab node list data hosted on Gist
nodelist = pd.read_csv('https://gist.githubusercontent.com/brooksandrew/f989e10af17fb4c85b11409fea47895b/raw/a3a8da0fa5b094f1ca9d82e1642b384889ae16e8/nodelist_sleeping_giant.csv')

# Preview nodelist
nodelist.head(5)

Buat Graf

Sekarang Anda gunakan daftar edge dan daftar node untuk membuat objek graf di networkx.

# Create empty graph
g = nx.Graph()

Loop melalui baris-baris daftar edge dan tambahkan setiap edge beserta atributnya ke graf g.

# Add edges and edge attributes
for i, elrow in edgelist.iterrows():
    g.add_edge(elrow[0], elrow[1], attr_dict=elrow[2:].to_dict())

Untuk mengilustrasikan apa yang terjadi di sini, mari cetak nilai dari baris terakhir dalam daftar edge yang ditambahkan ke graf g:

# Edge list example
print(elrow[0]) # node1
print(elrow[1]) # node2
print(elrow[2:].to_dict()) # edge attribute dict

o_gy2
y_gy2
{'color': 'yellowgreen', 'estimate': 0, 'trail': 'gy2', 'distance': 0.12}

Demikian pula, Anda melakukan loop pada baris-baris daftar node dan menambahkan atribut node tersebut.

# Add node attributes
for i, nlrow in nodelist.iterrows():
    g.node[nlrow['id']] = nlrow[1:].to_dict()

Berikut contoh dari baris terakhir daftar node:

# Node list example
print(nlrow)

id    y_rt
X      977
Y     1666
Name: 76, dtype: object

Inspeksi Graf

Edge

Edge pada graf Anda direpresentasikan oleh daftar tuple dengan panjang 3. Dua elemen pertama adalah nama node yang dihubungkan oleh edge. Elemen ketiga adalah kamus atribut edge.

# Preview first 5 edges
g.edges(data=True)[0:5]

[('rs_end_south',
  'y_rs',
  {'color': 'red', 'distance': 0.39, 'estimate': 0, 'trail': 'rs'}),
 ('w_gy2',
  'park_east',
  {'color': 'gray', 'distance': 0.12, 'estimate': 0, 'trail': 'w'}),
 ('w_gy2',
  'g_gy2',
  {'color': 'yellowgreen', 'distance': 0.05, 'estimate': 0, 'trail': 'gy2'}),
 ('w_gy2',
  'b_w',
  {'color': 'gray', 'distance': 0.42, 'estimate': 0, 'trail': 'w'}),
 ('w_gy2',
  'b_gy2',
  {'color': 'yellowgreen', 'distance': 0.03, 'estimate': 1, 'trail': 'gy2'})]

Node

Demikian pula, node Anda direpresentasikan oleh daftar tuple dengan panjang 2. Elemen pertama adalah ID node, diikuti oleh kamus atribut node.

# Preview first 10 nodes
g.nodes(data=True)[0:10]

[('rs_end_south', {'X': 1865, 'Y': 1598}),
 ('w_gy2', {'X': 2000, 'Y': 954}),
 ('rd_end_south_dupe', {'X': 273, 'Y': 1869}),
 ('w_gy1', {'X': 1184, 'Y': 1445}),
 ('g_rt', {'X': 908, 'Y': 1378}),
 ('v_rd', {'X': 258, 'Y': 1684}),
 ('g_rs', {'X': 1676, 'Y': 775}),
 ('rc_end_north', {'X': 867, 'Y': 618}),
 ('v_end_east', {'X': 2131, 'Y': 921}),
 ('rh_end_south', {'X': 721, 'Y': 1925})]

Statistik Ringkas

Cetak beberapa statistik ringkas sebelum memvisualisasikan graf.

print('# of edges: {}'.format(g.number_of_edges()))
print('# of nodes: {}'.format(g.number_of_nodes()))

# of edges: 123
# of nodes: 77

Visualisasikan Graf

Atur Warna dan Tata Letak

Posisi: Pertama Anda perlu memanipulasi posisi node dari graf menjadi sebuah kamus. Ini akan memungkinkan Anda untuk membuat ulang graf dengan tata letak yang sama seperti peta jalur sebenarnya. Y dinegasikan untuk mengubah titik asal sumbu Y dari kiri atas ke kiri bawah.

# Define node positions data structure (dict) for plotting
node_positions = {node[0]: (node[1]['X'], -node[1]['Y']) for node in g.nodes(data=True)}

# Preview of node_positions with a bit of hack (there is no head/slice method for dictionaries).
dict(list(node_positions.items())[0:5])

{'b_rd': (268, -1744),
 'g_rt': (908, -1378),
 'o_gy1': (1130, -1297),
 'rh_end_tt_2': (550, -1608),
 'rs_end_south': (1865, -1598)}

Warna: Sekarang Anda memanipulasi warna edge dari graf menjadi daftar sederhana sehingga Anda dapat memvisualisasikan jalur berdasarkan warnanya.

# Define data structure (list) of edge colors for plotting
edge_colors = [e[2]['color'] for e in g.edges(data=True)]

# Preview first 10
edge_colors[0:10]

['red',
 'gray',
 'yellowgreen',
 'gray',
 'yellowgreen',
 'blue',
 'black',
 'yellowgreen',
 'gray',
 'gray']

Plot

Sekarang Anda dapat membuat plot yang selaras rapi dengan peta jalur Sleeping Giant:

plt.figure(figsize=(8, 6))
nx.draw(g, pos=node_positions, edge_color=edge_colors, node_size=10, node_color='black')
plt.title('Graph Representation of Sleeping Giant Trail Map', size=15)
plt.show()

Representasi graf ini jelas tidak menangkap semua lekuk dan belokan jalur, namun tidak perlu khawatir: ini terekam akurat dalam atribut distance pada edge yang digunakan untuk komputasi. Visualnya memang menangkap jarak antar node (perpotongan jalur) secara garis lurus, yang tampaknya merupakan pendekatan yang cukup baik.

Gambaran Umum Algoritme CPP

Oke, jadi setelah Anda mendefinisikan beberapa istilah dan membuat graf, bagaimana cara menemukan lintasan terpendek melaluinya?

Menyelesaikan Chinese Postman Problem cukup sederhana secara konsep:

1. Temukan semua node dengan derajat ganjil (sangat mudah).
   (Temukan semua perpotongan jalur tempat jumlah jalur yang menyentuh perpotongan tersebut bernilai ganjil)
   
   

2. Tambahkan edge ke graf sehingga semua node berderajat ganjil menjadi genap. Edge yang ditambahkan ini harus merupakan duplikat dari graf asli (kita asumsikan tidak ada jalan pintas menembus semak untuk masalah ini). Himpunan edge yang ditambahkan harus berjumlah jarak minimum yang mungkin (sulit... tepatnya np-hard).
   (Secara sederhana, minimalkan jumlah langkah mundur pada rute yang melewati setiap jalur)
   
   

3. Diberikan titik awal, temukan tur Euler pada dataset yang telah diaugmentasi (cukup mudah).
   (Setelah kita tahu jalur mana yang akan dilalui dua kali, barulah hitung rute dari awal hingga akhir)

Asumsi dan Penyederhanaan

Meski rute yang lebih pendek dan lebih presisi dapat dihasilkan dengan melonggarkan asumsi di bawah ini, hal tersebut akan menambah kompleksitas di luar cakupan tutorial ini yang berfokus pada CPP.

Asumsi 1: Hanya jalur yang diwajibkan

Seperti yang terlihat pada peta jalur di atas, ada jalan di sepanjang perbatasan taman yang dapat digunakan untuk menghubungkan jalur, khususnya jalur merah. Ada juga beberapa jalur (Horseshoe dan tanda tak bertanda) yang tidak diwajibkan menurut log Giantmaster, namun dapat membantu mencegah langkah mundur yang panjang. Penyertaan jalur opsional sebenarnya adalah varian mapan dari CPP yang disebut Rural Postman Problem. Kita abaikan jalur opsional dalam tutorial ini dan fokus pada jalur yang diwajibkan saja.

Asumsi 2: Menanjak == menurun

CPP mengasumsikan bahwa biaya menyusuri jalur setara dengan jaraknya, terlepas dari arah perjalanan. Namun, beberapa jalur ini cukup berbukit dan akan membutuhkan lebih banyak energi untuk berjalan naik dibanding turun. Beberapa metrik yang menggabungkan jarak dan perubahan elevasi pada graf berarah dapat dimasukkan ke dalam ekstensi CPP yang disebut Windy Postman Problem.

Asumsi 3: Tidak ada edge (jalur) paralel

Meskipun memungkinkan, penyertaan edge paralel (beberapa jalur yang menghubungkan dua node yang sama) menambah kompleksitas komputasi. Untungnya ini hanya terjadi dua kali di sini (Blue <=> Red Diamond dan Blue <=> Tower Trail). Ini ditangani dengan sedikit trik pada daftar edge: node duplikat disertakan dengan akhiran _dupe untuk menangkap setiap jalur sekaligus mempertahankan keunikan pada edge. Implementasi CPP dalam paket postman_problems yang saya tulis menangani edge paralel secara tangguh dengan cara yang lebih elegan jika Anda ingin menyelesaikan CPP pada graf Anda sendiri dengan banyak edge paralel.

Langkah CPP 1: Temukan Node Berderajat Ganjil

Ini adalah komputasi penghitungan yang cukup lugas. Anda melihat bahwa 36 dari 76 node memiliki derajat ganjil. Ini sebagian besar adalah jalur buntu (derajat 1) dan perpotongan 3 jalur. Ada segelintir node berderajat 5.

# Calculate list of nodes with odd degree
nodes_odd_degree = [v for v, d in g.degree_iter() if d % 2 == 1]

# Preview
nodes_odd_degree[0:5]

['rs_end_south', 'rc_end_north', 'v_end_east', 'rh_end_south', 'b_end_east']

# Counts
print('Number of nodes of odd degree: {}'.format(len(nodes_odd_degree)))
print('Number of total nodes: {}'.format(len(g.nodes())))

Number of nodes of odd degree: 36
Number of total nodes: 77

Langkah CPP 2: Temukan Pasangan Jarak Minimum

Ini sebenarnya inti dari masalahnya. Anda akan memecahnya menjadi 5 bagian:

1. Hitung semua pasangan node berderajat ganjil.
2. Hitung lintasan terpendek antara setiap pasangan node yang dihitung pada 1.
3. Buat sebuah complete graph yang menghubungkan setiap pasangan node pada 1. dengan atribut jarak lintasan terpendek yang dihitung pada 2.
4. Hitung sebuah minimum weight matching dari graf yang dihitung pada 3.
   (Ini bermuara pada menentukan bagaimana memasangkan node ganjil sehingga jumlah jarak antar pasangan sekecil mungkin).
5. Augmentasi graf asli dengan lintasan terpendek antara pasangan node yang dihitung pada 4.

Langkah 2.1: Hitung Pasangan Node

Anda menggunakan fungsi itertools combination untuk menghitung semua pasangan yang mungkin dari node berderajat ganjil. Graf Anda tak berarah, jadi kita tidak peduli urutannya: Misalnya, (a,b) == (b,a).

# Compute all pairs of odd nodes. in a list of tuples
odd_node_pairs = list(itertools.combinations(nodes_odd_degree, 2))

# Preview pairs of odd degree nodes
odd_node_pairs[0:10]

[('rs_end_south', 'rc_end_north'),
 ('rs_end_south', 'v_end_east'),
 ('rs_end_south', 'rh_end_south'),
 ('rs_end_south', 'b_end_east'),
 ('rs_end_south', 'b_bv'),
 ('rs_end_south', 'rt_end_south'),
 ('rs_end_south', 'o_rt'),
 ('rs_end_south', 'y_rt'),
 ('rs_end_south', 'g_gy2'),
 ('rs_end_south', 'b_tt_3')]

# Counts
print('Number of pairs: {}'.format(len(odd_node_pairs)))

Number of pairs: 630

Mari konfirmasi bahwa jumlah pasangan ini benar dengan kombinatorik di bawah. Untungnya, Anda hanya memiliki 630 pasangan untuk diurus. Waktu komputasi Anda untuk menyelesaikan contoh CPP ini sepele (beberapa detik).

Namun, jika Anda memiliki 3.600 pasangan node ganjil, Anda akan memiliki ~6,5 juta pasangan untuk dioptimalkan. Itu ~10.000x peningkatan keluaran dengan peningkatan masukan 100x.

Langkah 2.2: Hitung Lintasan Terpendek antar Pasangan Node

Ini adalah langkah pertama yang melibatkan komputasi nyata. Untungnya networkx memiliki implementasi yang nyaman dari Algoritme Dijkstra untuk menghitung lintasan terpendek antara dua node. Anda menerapkan fungsi ini ke setiap pasangan (semua 630) yang dihitung di atas dalam odd_node_pairs.

def get_shortest_paths_distances(graph, pairs, edge_weight_name):
    """Compute shortest distance between each pair of nodes in a graph.  Return a dictionary keyed on node pairs (tuples)."""
    distances = {}
    for pair in pairs:
        distances[pair] = nx.dijkstra_path_length(graph, pair[0], pair[1], weight=edge_weight_name)
    return distances

# Compute shortest paths.  Return a dictionary with node pairs keys and a single value equal to shortest path distance.
odd_node_pairs_shortest_paths = get_shortest_paths_distances(g, odd_node_pairs, 'distance')

# Preview with a bit of hack (there is no head/slice method for dictionaries).
dict(list(odd_node_pairs_shortest_paths.items())[0:10])

{('b_bv', 'y_gy1'): 1.22,
 ('b_bw', 'rc_end_south'): 1.35,
 ('b_end_east', 'b_bw'): 3.0400000000000005,
 ('b_end_east', 'rd_end_north'): 3.83,
 ('g_gy1', 'nature_end_west'): 0.9900000000000001,
 ('o_rt', 'y_gy1'): 0.53,
 ('rc_end_north', 'rd_end_south'): 2.21,
 ('rc_end_north', 'rs_end_north'): 1.79,
 ('rs_end_north', 'o_tt'): 2.0999999999999996,
 ('w_bw', 'rd_end_north'): 1.02}

Langkah 2.3: Buat Complete Graph

Sebuah complete graph adalah graf yang setiap nodenya terhubung ke setiap node lain oleh sebuah edge unik.

Berikut contoh dasar dari Wikipedia berupa complete graph 7 node dengan 21 edge (7 pilih 2):

Graf yang Anda buat di bawah ini memiliki 36 node dan 630 edge dengan bobot edge (jarak) yang sesuai.

create_complete_graph didefinisikan untuk menghitungnya. Parameter flip_weights digunakan untuk mentransformasikan distance menjadi atribut weight di mana angka kecil mencerminkan jarak besar dan angka besar mencerminkan jarak pendek. Ini terdengar agak berlawanan dengan intuisi, tetapi diperlukan untuk Langkah 2.4 di mana Anda menghitung minimum weight matching pada complete graph.

Idealnya Anda menghitung minimum weight matching secara langsung, namun NetworkX hanya mengimplementasikan fungsi max_weight_matching yang memaksimalkan, bukan meminimalkan bobot edge. Kita akali sedikit dengan menegasikan (mengalikan dengan -1) atribut distance untuk mendapatkan weight. Ini memastikan bahwa urutan dan skala berdasarkan jarak dipertahankan, tetapi dibalik.

def create_complete_graph(pair_weights, flip_weights=True):
    """
    Create a completely connected graph using a list of vertex pairs and the shortest path distances between them
    Parameters:
        pair_weights: list[tuple] from the output of get_shortest_paths_distances
        flip_weights: Boolean. Should we negate the edge attribute in pair_weights?
    """
    g = nx.Graph()
    for k, v in pair_weights.items():
        wt_i = - v if flip_weights else v
        g.add_edge(k[0], k[1], attr_dict={'distance': v, 'weight': wt_i})
    return g

# Generate the complete graph
g_odd_complete = create_complete_graph(odd_node_pairs_shortest_paths, flip_weights=True)

# Counts
print('Number of nodes: {}'.format(len(g_odd_complete.nodes())))
print('Number of edges: {}'.format(len(g_odd_complete.edges())))

Number of nodes: 36
Number of edges: 630

Untuk visual bantu, complete graph dari pasangan node berderajat ganjil dipetakan di bawah. Perhatikan bahwa Anda mempertahankan koordinat X, Y setiap node, namun edge tidak selalu merepresentasikan jalur sebenarnya. Misalnya, dua node dapat dihubungkan oleh satu edge dalam graf ini, tetapi lintasan terpendek di antara keduanya bisa 5 lompatan melalui node berderajat genap (tidak ditampilkan di sini).

# Plot the complete graph of odd-degree nodes
plt.figure(figsize=(8, 6))
pos_random = nx.random_layout(g_odd_complete)
nx.draw_networkx_nodes(g_odd_complete, node_positions, node_size=20, node_color="red")
nx.draw_networkx_edges(g_odd_complete, node_positions, alpha=0.1)
plt.axis('off')
plt.title('Complete Graph of Odd-degree Nodes')
plt.show()

Langkah 2.4: Hitung Minimum Weight Matching

Ini adalah langkah paling kompleks dalam CPP. Anda perlu menemukan pasangan node berderajat ganjil yang jumlah gabungannya (jarak di antara mereka) sekecil mungkin. Jadi untuk masalah Anda, ini bermuara pada memilih 18 edge optimal (36 node ganjil / 2) dari graf ruwet yang dihasilkan pada 2.3.

Baik implementasi maupun intuisinya berada di luar cakupan tutorial ini... seperti 800+ baris kode dan badan literatur akademik yang melampaui cakupan ini.

Namun, sekilas untuk pembaca yang berminat:

Terima kasih banyak kepada Joris van Rantwijk yang menulis implementasi asli di blognya jauh pada tahun 2008. Saya tersandung masalah ini dengan cara yang mirip dengan niat yang sama seperti Joris. Dari tulisan Joris tahun 2008:

Karena saya tidak menemukan implementasi Perl untuk maximum weighted matching, saya dengan enteng memutuskan untuk menulis kode sendiri. Ternyata saya meremehkan masalah ini, tetapi pada saat saya menyadari kesalahan saya, saya begitu terobsesi dengan masalah tersebut sehingga saya menolak untuk menyerah.

Namun, saya menyerah. Untungnya Joris tidak.

Maximum Weight Matching ini sejak itu dimasukkan dan dipelihara dalam paket NetworkX. Terima kasih juga kepada 10+ kontributor di GitHub yang telah memelihara basis kode besar ini.

Ini adalah komputasi yang sulit dan intensif. Terobosan pertama pada tahun 1965 membuktikan bahwa masalah Maximum Matching dapat diselesaikan dalam waktu polinomial. Itu diterbitkan oleh Jack Edmonds dengan mungkin salah satu judul makalah akademik terindah: "Paths, trees, and flowers" [1]. Kumpulan literatur sejak itu membangun pekerjaan ini, menyempurnakan prosedur optimisasi. Kode yang diimplementasikan dalam fungsi NetworkX max_weight_matching didasarkan pada Galil, Zvi (1986) [2] yang menggunakan algoritme berwaktu O(n³).

# Compute min weight matching.
# Note: max_weight_matching uses the 'weight' attribute by default as the attribute to maximize.
odd_matching_dupes = nx.algorithms.max_weight_matching(g_odd_complete, True)

print('Number of edges in matching: {}'.format(len(odd_matching_dupes)))

Number of edges in matching: 36

Keluaran matching (odd_matching_dupes) adalah kamus. Meski ada 36 edge dalam matching ini, Anda hanya menginginkan 18. Setiap pasangan-edge muncul dua kali (sekali dengan node 1 sebagai key dan kedua kalinya dengan node 2 sebagai key dari kamus).

# Preview of matching with dupes
odd_matching_dupes

{'b_bv': 'v_bv',
 'b_bw': 'rh_end_tt_1',
 'b_end_east': 'g_gy2',
 'b_end_west': 'rd_end_south',
 'b_tt_3': 'rt_end_north',
 'b_v': 'v_end_west',
 'g_gy1': 'rc_end_north',
 'g_gy2': 'b_end_east',
 'g_w': 'w_bw',
 'nature_end_west': 'o_y_tt_end_west',
 'o_rt': 'o_w_1',
 'o_tt': 'rh_end_tt_2',
 'o_w_1': 'o_rt',
 'o_y_tt_end_west': 'nature_end_west',
 'rc_end_north': 'g_gy1',
 'rc_end_south': 'y_gy1',
 'rd_end_north': 'rh_end_north',
 'rd_end_south': 'b_end_west',
 'rh_end_north': 'rd_end_north',
 'rh_end_south': 'y_rh',
 'rh_end_tt_1': 'b_bw',
 'rh_end_tt_2': 'o_tt',
 'rh_end_tt_3': 'rh_end_tt_4',
 'rh_end_tt_4': 'rh_end_tt_3',
 'rs_end_north': 'v_end_east',
 'rs_end_south': 'y_gy2',
 'rt_end_north': 'b_tt_3',
 'rt_end_south': 'y_rt',
 'v_bv': 'b_bv',
 'v_end_east': 'rs_end_north',
 'v_end_west': 'b_v',
 'w_bw': 'g_w',
 'y_gy1': 'rc_end_south',
 'y_gy2': 'rs_end_south',
 'y_rh': 'rh_end_south',
 'y_rt': 'rt_end_south'}

Anda mengonversi kamus ini menjadi daftar tuple karena Anda memiliki graf tak berarah dan urutan tidak penting. Menghapus duplikasi menghasilkan 18 pasangan-edge unik yang secara kumulatif berjumlah jarak paling kecil.

# Convert matching to list of deduped tuples
odd_matching = list(pd.unique([tuple(sorted([k, v])) for k, v in odd_matching_dupes.items()]))

# Counts
print('Number of edges in matching (deduped): {}'.format(len(odd_matching)))

Number of edges in matching (deduped): 18

# Preview of deduped matching
odd_matching

[('rs_end_south', 'y_gy2'),
 ('b_end_west', 'rd_end_south'),
 ('b_bv', 'v_bv'),
 ('rh_end_tt_3', 'rh_end_tt_4'),
 ('b_bw', 'rh_end_tt_1'),
 ('o_tt', 'rh_end_tt_2'),
 ('g_w', 'w_bw'),
 ('b_end_east', 'g_gy2'),
 ('nature_end_west', 'o_y_tt_end_west'),
 ('g_gy1', 'rc_end_north'),
 ('o_rt', 'o_w_1'),
 ('rs_end_north', 'v_end_east'),
 ('rc_end_south', 'y_gy1'),
 ('rh_end_south', 'y_rh'),
 ('rt_end_south', 'y_rt'),
 ('b_tt_3', 'rt_end_north'),
 ('rd_end_north', 'rh_end_north'),
 ('b_v', 'v_end_west')]

Mari visualisasikan pasangan-pasangan ini pada complete graph yang dipetakan sebelumnya di langkah 2.3. Seperti sebelumnya, meski posisi node mencerminkan graf sebenarnya (peta jalur) di sini, jarak edge yang ditampilkan (garis biru) adalah secara garis lurus. Rute terpendek sebenarnya dari satu node ke node lain dapat melibatkan beberapa edge yang berkelok-kelok dengan jarak yang jauh lebih panjang.

plt.figure(figsize=(8, 6))

# Plot the complete graph of odd-degree nodes
nx.draw(g_odd_complete, pos=node_positions, node_size=20, alpha=0.05)

# Create a new graph to overlay on g_odd_complete with just the edges from the min weight matching
g_odd_complete_min_edges = nx.Graph(odd_matching)
nx.draw(g_odd_complete_min_edges, pos=node_positions, node_size=20, edge_color='blue', node_color='red')

plt.title('Min Weight Matching on Complete Graph')
plt.show()

Untuk mengilustrasikan bagaimana ini menyatu dengan graf asli, Anda memplot pasangan bobot minimum yang sama (garis biru), tetapi di atas peta jalur (pudar) alih-alih complete graph. Sekali lagi, perhatikan bahwa garis biru adalah rute menembus semak (edge garis lurus, bukan jalur sebenarnya). Anda masih memiliki sedikit pekerjaan untuk menemukan edge yang menyusun lintasan terpendek antara setiap pasangan pada Langkah 3.

plt.figure(figsize=(8, 6))

# Plot the original trail map graph
nx.draw(g, pos=node_positions, node_size=20, alpha=0.1, node_color='black')

# Plot graph to overlay with just the edges from the min weight matching
nx.draw(g_odd_complete_min_edges, pos=node_positions, node_size=20, alpha=1, node_color='red', edge_color='blue')

plt.title('Min Weight Matching on Orginal Graph')
plt.show()

Langkah 2.5: Augmentasi Graf Asli

Sekarang Anda mengaugmentasi graf asli dengan edge dari matching yang dihitung pada 2.4. Fungsi sederhana untuk melakukan ini didefinisikan di bawah, yang juga mencatat bahwa edge baru ini berasal dari graf augmentasi. Anda perlu mengetahui ini pada 3. saat Anda benar-benar membuat sirkuit Euler melalui graf tersebut.

def add_augmenting_path_to_graph(graph, min_weight_pairs):
    """
    Add the min weight matching edges to the original graph
    Parameters:
        graph: NetworkX graph (original graph from trailmap)
        min_weight_pairs: list[tuples] of node pairs from min weight matching
    Returns:
        augmented NetworkX graph
    """

    # We need to make the augmented graph a MultiGraph so we can add parallel edges
    graph_aug = nx.MultiGraph(graph.copy())
    for pair in min_weight_pairs:
        graph_aug.add_edge(pair[0],
                           pair[1],
                           attr_dict={'distance': nx.dijkstra_path_length(graph, pair[0], pair[1]),
                                      'trail': 'augmented'}
                          )
    return graph_aug

Mari konfirmasi bahwa graf augmentasi Anda menambahkan jumlah (18) edge yang diharapkan:

# Create augmented graph: add the min weight matching edges to g
g_aug = add_augmenting_path_to_graph(g, odd_matching)

# Counts
print('Number of edges in original graph: {}'.format(len(g.edges())))
print('Number of edges in augmented graph: {}'.format(len(g_aug.edges())))

Number of edges in original graph: 123
Number of edges in augmented graph: 141

Mari juga konfirmasi bahwa setiap node sekarang berderajat genap:

pd.value_counts(g_aug.degree())

4    54
2    18
6     5
dtype: int64

Langkah CPP 3: Hitung Sirkuit Euler

Sekarang Anda memiliki graf dengan derajat genap maka pekerjaan optimisasi yang sulit telah selesai. Seperti yang terkenal dipostulatkan Euler pada tahun 1736 dengan masalah Tujuh Jembatan di Königsberg, ada lintasan yang mengunjungi setiap edge tepat sekali jika semua node berderajat genap. Carl Hierholzer kemudian secara formal membuktikan hasil ini pada tahun 1870-an.

Ada banyak sirkuit Euler dengan jarak yang sama yang dapat dibangun. Anda dapat menyelesaikan 90% kebutuhan dengan fungsi eulerian_circuit dari NetworkX. Namun ada beberapa keterbatasan.

Keterbatasan yang akan Anda perbaiki:

1. Graf augmentasi bisa (dan kemungkinan akan) berisi edge yang tidak ada pada graf asli. Untuk mendapatkan sirkuit (tanpa menembus semak), Anda harus memecah edge augmentasi ini menjadi lintasan terpendek melalui edge yang benar-benar ada.

2. eulerian_circuit hanya mengembalikan urutan kita mengenai node yang dikunjungi. Ia tidak mengembalikan atribut edge yang diperlukan untuk melengkapi sirkuit. Ini perlu karena Anda harus melacak edge mana yang sudah dilalui ketika ada beberapa edge antara dua node.

Keterbatasan yang tidak akan Anda perbaiki:

3. Untuk menghemat tenaga kaki Anda, Anda dapat melonggarkan asumsi sirkuit Euler bahwa mulai dan selesai di node yang sama. Sebuah jalur Euler (kasus umum dari sirkuit Euler), juga dapat ditemukan jika ada tepat dua node berderajat ganjil. Ini akan menghemat sedikit langkah mundur... dengan asumsi Anda bisa mendapatkan tumpangan kembali dari ujung taman yang lain. Namun, pada saat penulisan ini, NetworkX belum menyediakan algoritme Jalur Euler. Kode eulerian_circuit tidak terlalu buruk dan bisa diadaptasi untuk kasus ini, tetapi kita tetap sederhana di sini.

Sirkuit Naif

Meski begitu, mari mulai dengan solusi sederhana namun belum lengkap:

naive_euler_circuit = list(nx.eulerian_circuit(g_aug, source='b_end_east'))

Sesuai harapan, panjang sirkuit Euler naif sama dengan jumlah edge pada graf augmentasi.

print('Length of eulerian circuit: {}'.format(len(naive_euler_circuit)))

Length of eulerian circuit: 141

Keluaran ini hanya daftar tuple yang mewakili pasangan node. Perhatikan bahwa node pertama dari setiap pasangan sama dengan node kedua dari pasangan sebelumnya.

# Preview naive Euler circuit
naive_euler_circuit[0:10]

[('b_end_east', 'g_gy2'),
 ('g_gy2', 'b_g'),
 ('b_g', 'b_w'),
 ('b_w', 'b_gy2'),
 ('b_gy2', 'w_gy2'),
 ('w_gy2', 'b_w'),
 ('b_w', 'w_rs'),
 ('w_rs', 'g_rs'),
 ('g_rs', 'b_g'),
 ('b_g', 'b_rs')]

Sirkuit yang Benar

Sekarang mari kita definisikan fungsi yang memanfaatkan graf asli untuk memberi tahu Anda jalur mana yang digunakan untuk pergi dari node A ke node B. Meskipun kodenya verbose, logika ini sebenarnya cukup sederhana. Anda cukup mentransformasikan sirkuit naif yang menyertakan edge yang tidak ada pada graf asli menjadi sirkuit Euler yang hanya menggunakan edge yang ada pada graf asli.

Anda melakukan loop melalui setiap edge dalam sirkuit Euler naif (naive_euler_circuit). Di mana pun Anda menemukan edge yang tidak ada dalam graf asli, Anda menggantinya dengan urutan edge yang menyusun lintasan terpendek antara nodenya menggunakan graf asli.

def create_eulerian_circuit(graph_augmented, graph_original, starting_node=None):
    """Create the eulerian path using only edges from the original graph."""
    euler_circuit = []
    naive_circuit = list(nx.eulerian_circuit(graph_augmented, source=starting_node))

    for edge in naive_circuit:
        edge_data = graph_augmented.get_edge_data(edge[0], edge[1])    

        if edge_data[0]['trail'] != 'augmented':
            # If `edge` exists in original graph, grab the edge attributes and add to eulerian circuit.
            edge_att = graph_original[edge[0]][edge[1]]
            euler_circuit.append((edge[0], edge[1], edge_att))
        else:
            aug_path = nx.shortest_path(graph_original, edge[0], edge[1], weight='distance')
            aug_path_pairs = list(zip(aug_path[:-1], aug_path[1:]))

            print('Filling in edges for augmented edge: {}'.format(edge))
            print('Augmenting path: {}'.format(' => '.join(aug_path)))
            print('Augmenting path pairs: {}\n'.format(aug_path_pairs))

            # If `edge` does not exist in original graph, find the shortest path between its nodes and
            #  add the edge attributes for each link in the shortest path.
            for edge_aug in aug_path_pairs:
                edge_aug_att = graph_original[edge_aug[0]][edge_aug[1]]
                euler_circuit.append((edge_aug[0], edge_aug[1], edge_aug_att))

    return euler_circuit

Anda mengakali keterbatasan 3 sedikit dengan memulai sirkuit Euler di ujung timur jauh taman pada jalur Biru (node "b_end_east"). Saat benar-benar menjalankannya, Anda bisa cukup melewati arahan terakhir yang kembali lagi.

Pernyataan cetak yang verbose ditambahkan untuk menyampaikan apa yang terjadi ketika Anda mengganti edge yang tidak ada dari graf augmentasi dengan lintasan terpendek menggunakan edge yang benar-benar ada.

# Create the Eulerian circuit
euler_circuit = create_eulerian_circuit(g_aug, g, 'b_end_east')

Filling in edges for augmented edge: ('b_end_east', 'g_gy2')
Augmenting path: b_end_east => b_y => b_o => b_gy2 => w_gy2 => g_gy2
Augmenting path pairs: [('b_end_east', 'b_y'), ('b_y', 'b_o'), ('b_o', 'b_gy2'), ('b_gy2', 'w_gy2'), ('w_gy2', 'g_gy2')]

Filling in edges for augmented edge: ('b_bw', 'rh_end_tt_1')
Augmenting path: b_bw => b_tt_1 => rh_end_tt_1
Augmenting path pairs: [('b_bw', 'b_tt_1'), ('b_tt_1', 'rh_end_tt_1')]

Filling in edges for augmented edge: ('b_tt_3', 'rt_end_north')
Augmenting path: b_tt_3 => b_tt_2 => tt_rt => v_rt => rt_end_north
Augmenting path pairs: [('b_tt_3', 'b_tt_2'), ('b_tt_2', 'tt_rt'), ('tt_rt', 'v_rt'), ('v_rt', 'rt_end_north')]

Filling in edges for augmented edge: ('rc_end_north', 'g_gy1')
Augmenting path: rc_end_north => v_rc => b_rc => g_rc => g_gy1
Augmenting path pairs: [('rc_end_north', 'v_rc'), ('v_rc', 'b_rc'), ('b_rc', 'g_rc'), ('g_rc', 'g_gy1')]

Filling in edges for augmented edge: ('y_gy1', 'rc_end_south')
Augmenting path: y_gy1 => y_rc => rc_end_south
Augmenting path pairs: [('y_gy1', 'y_rc'), ('y_rc', 'rc_end_south')]

Filling in edges for augmented edge: ('b_end_west', 'rd_end_south')
Augmenting path: b_end_west => b_v => rd_end_south
Augmenting path pairs: [('b_end_west', 'b_v'), ('b_v', 'rd_end_south')]

Filling in edges for augmented edge: ('rh_end_north', 'rd_end_north')
Augmenting path: rh_end_north => v_rh => v_rd => rd_end_north
Augmenting path pairs: [('rh_end_north', 'v_rh'), ('v_rh', 'v_rd'), ('v_rd', 'rd_end_north')]

Filling in edges for augmented edge: ('v_end_east', 'rs_end_north')
Augmenting path: v_end_east => v_rs => rs_end_north
Augmenting path pairs: [('v_end_east', 'v_rs'), ('v_rs', 'rs_end_north')]

Filling in edges for augmented edge: ('y_gy2', 'rs_end_south')
Augmenting path: y_gy2 => y_rs => rs_end_south
Augmenting path pairs: [('y_gy2', 'y_rs'), ('y_rs', 'rs_end_south')]

Anda melihat bahwa panjang sirkuit Euler lebih panjang daripada sirkuit naif, yang masuk akal.

print('Length of Eulerian circuit: {}'.format(len(euler_circuit)))

Length of Eulerian circuit: 158

Hitung Solusi CPP

Teks

Berikut cetakan solusi dalam bentuk teks:

# Preview first 20 directions of CPP solution
for i, edge in enumerate(euler_circuit[0:20]):
    print(i, edge)

0 ('b_end_east', 'b_y', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 1.32})
1 ('b_y', 'b_o', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.08})
2 ('b_o', 'b_gy2', {'color': 'blue', 'estimate': 1, 'trail': 'b', 'distance': 0.05})
3 ('b_gy2', 'w_gy2', {'color': 'yellowgreen', 'estimate': 1, 'trail': 'gy2', 'distance': 0.03})
4 ('w_gy2', 'g_gy2', {'color': 'yellowgreen', 'estimate': 0, 'trail': 'gy2', 'distance': 0.05})
5 ('g_gy2', 'b_g', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.45})
6 ('b_g', 'b_w', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.16})
7 ('b_w', 'b_gy2', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.41})
8 ('b_gy2', 'w_gy2', {'color': 'yellowgreen', 'estimate': 1, 'trail': 'gy2', 'distance': 0.03})
9 ('w_gy2', 'b_w', {'color': 'gray', 'estimate': 0, 'trail': 'w', 'distance': 0.42})
10 ('b_w', 'w_rs', {'color': 'gray', 'estimate': 1, 'trail': 'w', 'distance': 0.06})
11 ('w_rs', 'g_rs', {'color': 'red', 'estimate': 0, 'trail': 'rs', 'distance': 0.18})
12 ('g_rs', 'b_g', {'color': 'green', 'estimate': 1, 'trail': 'g', 'distance': 0.05})
13 ('b_g', 'b_rs', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.07})
14 ('b_rs', 'g_rs', {'color': 'red', 'estimate': 0, 'trail': 'rs', 'distance': 0.11})
15 ('g_rs', 'g_rc', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.45})
16 ('g_rc', 'g_gy1', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.37})
17 ('g_gy1', 'g_rt', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.26})
18 ('g_rt', 'g_w', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.31})
19 ('g_w', 'o_w_1', {'color': 'gray', 'estimate': 0, 'trail': 'w', 'distance': 0.18})

Anda dapat segera melihat bahwa algoritme ini tidak terlalu setia pada jalur tertentu, melompat dari satu jalur ke jalur lain dengan cepat. Perluasan pendekatan ini bisa dibuat lebih canggih dengan memasukkan gagasan loyalitas jalur ke dalam fungsi objektif agar rute ini lebih mudah dijalankan.

Statistik

Mari intip solusi Anda untuk melihat seberapa masuk akal hasilnya.
(Tidak perlu berlama-lama pada kode yang verbose ini, cukup pada keluaran yang dicetak)

# Computing some stats
total_mileage_of_circuit = sum([edge[2]['distance'] for edge in euler_circuit])
total_mileage_on_orig_trail_map = sum(nx.get_edge_attributes(g, 'distance').values())
_vcn = pd.value_counts(pd.value_counts([(e[0]) for e in euler_circuit]), sort=False)
node_visits = pd.DataFrame({'n_visits': _vcn.index, 'n_nodes': _vcn.values})
_vce = pd.value_counts(pd.value_counts([sorted(e)[0] + sorted(e)[1] for e in nx.MultiDiGraph(euler_circuit).edges()]))
edge_visits = pd.DataFrame({'n_visits': _vce.index, 'n_edges': _vce.values})

# Printing stats
print('Mileage of circuit: {0:.2f}'.format(total_mileage_of_circuit))
print('Mileage on original trail map: {0:.2f}'.format(total_mileage_on_orig_trail_map))
print('Mileage retracing edges: {0:.2f}'.format(total_mileage_of_circuit-total_mileage_on_orig_trail_map))
print('Percent of mileage retraced: {0:.2f}%\n'.format((1-total_mileage_of_circuit/total_mileage_on_orig_trail_map)*-100))

print('Number of edges in circuit: {}'.format(len(euler_circuit)))
print('Number of edges in original graph: {}'.format(len(g.edges())))
print('Number of nodes in original graph: {}\n'.format(len(g.nodes())))

print('Number of edges traversed more than once: {}\n'.format(len(euler_circuit)-len(g.edges())))  

print('Number of times visiting each node:')
print(node_visits.to_string(index=False))

print('\nNumber of times visiting each edge:')
print(edge_visits.to_string(index=False))

Mileage of circuit: 33.59
Mileage on original trail map: 25.76
Mileage retracing edges: 7.83
Percent of mileage retraced: 30.40%

Number of edges in circuit: 158
Number of edges in original graph: 123
Number of nodes in original graph: 77

Number of edges traversed more than once: 35

Number of times visiting each node:
n_nodes  n_visits
     18         1
     38         2
     20         3
      1         4

Number of times visiting each edge:
n_edges  n_visits
     88         1
     35         2

Visualisasikan Solusi CPP

Meskipun NetworkX juga menyediakan fungsionalitas untuk memvisualisasikan graf, mereka cukup rendah hati di departemen ini:

NetworkX menyediakan fungsionalitas dasar untuk memvisualisasikan graf, tetapi tujuan utamanya adalah untuk memungkinkan analisis graf daripada melakukan visualisasi graf. Di masa depan, fungsionalitas visualisasi graf mungkin dihapus dari NetworkX atau hanya tersedia sebagai paket tambahan.

Visualisasi graf yang tepat itu sulit, dan kami sangat merekomendasikan agar orang memvisualisasikan graf mereka dengan alat yang didedikasikan untuk tugas itu. Contoh terkenal dari alat visualisasi graf yang lengkap adalah Cytoscape, Gephi, Graphviz dan, untuk penataan LaTeX, PGF/TikZ.

Meski begitu, fungsionalitas gambar bawaan NetworkX dengan matplotlib cukup kuat untuk melihat sekilas dan mengeksplorasi graf dasar secara visual, jadi Anda bertahan dengan draw NetworkX untuk tutorial ini.

Saya menggunakan graphviz dan bahasa deskripsi graf dot untuk memvisualisasikan solusi dalam paket Python saya postman_problems. Meski butuh sedikit upaya untuk mengonversi struktur graf NetworkX menjadi graf dot, ini membuka kualitas dan kontrol visualisasi yang lebih baik.

Buat Graf CPP

Langkah pertama Anda adalah mengonversi daftar edge yang akan dilalui dalam sirkuit Euler menjadi daftar edge dengan atribut yang ramah plot.

create_cpp_edgelist Membuat daftar edge dengan beberapa atribut tambahan yang akan Anda gunakan untuk plotting:

• sequence: mencatat urutan kapan kita menyusuri setiap edge.
• visits: adalah jumlah kali kita menyusuri edge tertentu.

def create_cpp_edgelist(euler_circuit):
    """
    Create the edgelist without parallel edge for the visualization
    Combine duplicate edges and keep track of their sequence and # of walks
    Parameters:
        euler_circuit: list[tuple] from create_eulerian_circuit
    """
    cpp_edgelist = {}

    for i, e in enumerate(euler_circuit):
        edge = frozenset([e[0], e[1]])

        if edge in cpp_edgelist:
            cpp_edgelist[edge][2]['sequence'] += ', ' + str(i)
            cpp_edgelist[edge][2]['visits'] += 1

        else:
            cpp_edgelist[edge] = e
            cpp_edgelist[edge][2]['sequence'] = str(i)
            cpp_edgelist[edge][2]['visits'] = 1

    return list(cpp_edgelist.values())

Mari buat daftar edge CPP:

cpp_edgelist = create_cpp_edgelist(euler_circuit)

Sesuaikan dengan harapan, daftar edge Anda memiliki jumlah edge yang sama dengan graf asli.

print('Number of edges in CPP edge list: {}'.format(len(cpp_edgelist)))

Number of edges in CPP edge list: 123

Daftar edge CPP terlihat mirip dengan euler_circuit, hanya dengan beberapa atribut tambahan.

# Preview CPP plot-friendly edge list
cpp_edgelist[0:3]

[('rh_end_tt_4',
  'nature_end_west',
  {'color': 'black',
   'distance': 0.2,
   'estimate': 0,
   'sequence': '73',
   'trail': 'tt',
   'visits': 1}),
 ('rd_end_south',
  'b_rd',
  {'color': 'red',
   'distance': 0.13,
   'estimate': 0,
   'sequence': '95',
   'trail': 'rd',
   'visits': 1}),
 ('w_gy1',
  'w_rc',
  {'color': 'gray',
   'distance': 0.33,
   'estimate': 0,
   'sequence': '151',
   'trail': 'w',
   'visits': 1})]

Sekarang mari buat grafnya:

# Create CPP solution graph
g_cpp = nx.Graph(cpp_edgelist)

Visualisasi 1: Menapaki Ulang Langkah

Di sini Anda mengilustrasikan edge mana yang dilalui sekali (abu-abu) dan lebih dari sekali (biru). Ini adalah versi "benar" dari visualisasi yang dibuat pada 2.4 yang menunjukkan koneksi naif (secara garis lurus) antara pasangan node ganjil (merah). Hal itu dikoreksi di sini dengan menelusuri lintasan terpendek melalui edge yang benar-benar ada untuk setiap pasangan node berderajat ganjil.

Jika optimisasinya bagus, garis biru ini harus merepresentasikan jarak paling kecil. Secara spesifik, jarak minimum yang dibutuhkan untuk menghasilkan sebuah matching dari node berderajat ganjil.

plt.figure(figsize=(14, 10))

visit_colors = {1:'lightgray', 2:'blue'}
edge_colors = [visit_colors[e[2]['visits']] for e in g_cpp.edges(data=True)]
node_colors = ['red'  if node in nodes_odd_degree else 'lightgray' for node in g_cpp.nodes()]

nx.draw_networkx(g_cpp, pos=node_positions, node_size=20, node_color=node_colors, edge_color=edge_colors, with_labels=False)
plt.axis('off')
plt.show()

Visualisasi 2: Urutan Solusi CPP

Di sini Anda memplot graf asli (peta jalur) yang dianotasi dengan nomor urutan saat kita menyusuri jalur sesuai solusi CPP. Beberapa nomor menunjukkan jalur yang harus kita lalui dua kali.

Anda mulai di jalur biru di kanan bawah (arah ke-0 dan ke-157).

plt.figure(figsize=(14, 10))

edge_colors = [e[2]['color'] for e in g_cpp.edges(data=True)]
nx.draw_networkx(g_cpp, pos=node_positions, node_size=10, node_color='black', edge_color=edge_colors, with_labels=False, alpha=0.5)

bbox = {'ec':[1,1,1,0], 'fc':[1,1,1,0]}  # hack to label edges over line (rather than breaking up line)
edge_labels = nx.get_edge_attributes(g_cpp, 'sequence')
nx.draw_networkx_edge_labels(g_cpp, pos=node_positions, edge_labels=edge_labels, bbox=bbox, font_size=6)

plt.axis('off')
plt.show()

Visualisasi 3: Film

Film di bawah yang menelusuri sirkuit Euler dari awal hingga akhir disematkan di bawah ini. Edge diwarnai hitam saat pertama kali dilalui dan merah saat kedua kalinya.

Perhatikan bahwa gif ini tidak memberikan keadilan visual penuh pada edge yang saling bertumpuk atau terlalu kecil untuk divisualisasikan dengan tepat. Pustaka visualisasi yang lebih tangguh seperti graphviz dapat mengatasi ini dengan memplot spline alih-alih garis lurus antar node.

Kode yang membuatnya disajikan di bawah sebagai referensi.

Pertama sebuah gambar PNG diproduksi untuk setiap arahan (edge yang dilalui) dari solusi CPP.

visit_colors = {1:'black', 2:'red'}
edge_cnter = {}
g_i_edge_colors = []
for i, e in enumerate(euler_circuit, start=1):

    edge = frozenset([e[0], e[1]])
    if edge in edge_cnter:
        edge_cnter[edge] += 1
    else:
        edge_cnter[edge] = 1

    # Full graph (faded in background)
    nx.draw_networkx(g_cpp, pos=node_positions, node_size=6, node_color='gray', with_labels=False, alpha=0.07)

    # Edges walked as of iteration i
    euler_circuit_i = copy.deepcopy(euler_circuit[0:i])
    for i in range(len(euler_circuit_i)):
        edge_i = frozenset([euler_circuit_i[i][0], euler_circuit_i[i][1]])
        euler_circuit_i[i][2]['visits_i'] = edge_cnter[edge_i]
    g_i = nx.Graph(euler_circuit_i)
    g_i_edge_colors = [visit_colors[e[2]['visits_i']] for e in g_i.edges(data=True)]

    nx.draw_networkx_nodes(g_i, pos=node_positions, node_size=6, alpha=0.6, node_color='lightgray', with_labels=False, linewidths=0.1)
    nx.draw_networkx_edges(g_i, pos=node_positions, edge_color=g_i_edge_colors, alpha=0.8)

    plt.axis('off')
    plt.savefig('fig/png/img{}.png'.format(i), dpi=120, bbox_inches='tight')
    plt.close()

Lalu gambar PNG dijahit bersama untuk membuat gif kecil yang bagus di atas.

Pertama PNG diurutkan dalam urutan dari 0 hingga 157. Lalu dijahit menggunakan imageio pada 3 frame per detik untuk membuat gif.

import glob
import numpy as np
import imageio
import os

def make_circuit_video(image_path, movie_filename, fps=5):
    # sorting filenames in order
    filenames = glob.glob(image_path + 'img*.png')
    filenames_sort_indices = np.argsort([int(os.path.basename(filename).split('.')[0][3:]) for filename in filenames])
    filenames = [filenames[i] for i in filenames_sort_indices]

    # make movie
    with imageio.get_writer(movie_filename, mode='I', fps=fps) as writer:
        for filename in filenames:
            image = imageio.imread(filename)
            writer.append_data(image)

make_circuit_video('fig/png/', 'fig/gif/cpp_route_animation.gif', fps=3)

Langkah Berikutnya

Selamat, Anda telah menyelesaikan tutorial ini dengan memecahkan Chinese Postman Problem di Python. Anda telah menempuh banyak hal dalam tutorial ini (tepatnya 33,6 mil jalur). Untuk pendalaman dasar-dasar jaringan, Anda mungkin tertarik dengan kursus Network Analysis in Python dari Datacamp yang memberikan pembahasan lebih menyeluruh tentang konsep inti.

Jangan ragu untuk memeriksa dokumentasi NetworkX untuk mempelajari lebih lanjut cara membuat, memanipulasi, dan menelusuri jaringan kompleks ini. Dokumentasinya komprehensif dengan sejumlah contoh dan serangkaian tutorial.

Jika Anda tertarik untuk menyelesaikan CPP pada graf Anda sendiri, saya telah mengemas fungsionalitas dalam tutorial ini ke dalam paket Python postman_problems di Github. Anda juga dapat merangkai blok kode dari tutorial ini dengan daftar edge dan node yang berbeda, tetapi paket postman_problems mungkin akan membawa Anda ke sana lebih cepat dan lebih rapi.

Suatu hari saya berencana mengimplementasikan ekstensi CPP (Rural dan Windy Postman Problem) di sini juga. Saya juga punya ambisi besar untuk menulis tentang ekstensi ini dan pengalaman menguji rute di jalur pada blog saya di sini. Aplikasi lain yang berencana saya jelajahi dan tulis adalah memasukkan koordinat lintang/bujur untuk mengembangkan (atau menggunakan) mekanisme mengirimkan arahan belok-demi-belok ke jam tangan Garmin saya.

Dan tentu saja satu langkah berikutnya terakhir: keluar dan lari lintasan rutenya!

Jika Anda ingin mempelajari lebih lanjut tentang Jaringan di Python, lihat kursus DataCamp berikut:

Introduction to Network Analysis in Python

Intermediate Network Analysis in Python

Referensi

1: Edmonds, Jack (1965). "Paths, trees, and flowers". Canad. J. Math. 17: 449–467.
2: Galil, Z. (1986). "Efficient algorithms for finding maximum matching in graphs". ACM Computing Surveys. Vol. 18, No. 1: 23-38.