Python ile NetworkX Kullanarak Graf Optimizasyonu

Bu eğitimle, graf teorisinde yerleşik bir problem olan Çinli Postacı Problemini ele alacaksınız. Algoritmanın bazı bileşenleri kavramsal olarak basit olsa da hesaplama açısından yoğun olabilir. Ancak bu eğitim için yalnızca Python hakkında biraz ön bilgi yeterlidir: sıkı bir matematik, bilgisayar bilimi veya graf teorisi geçmişine gerek yok.

Bu eğitim önce grafın temel yapı taşları (düğümler, kenarlar, yollar vb.) üzerinden geçecek ve Python’da NetworkX kütüphanesini kullanarak gerçek bir graf (bir eyalet parkının patika ağı) üzerinde problemi çözecek. Odak noktanız temel kavramlar ve uygulama olacak. İlgilenen okur için, optimizasyonun iç işleyişi hakkında daha fazla okuma önerileri de verilecektir.

Graf Optimizasyonuna Motivasyon

Problem

Muhtemelen bir dizi düğümü (ör. şehirler) bağlayan en kısa rotayı (ör. yollar) bulmaya dayanan Gezgin Satıcı Problemini duymuşsunuzdur. Daha az bilinse de, Çinli Postacı Problemi (CPP), Rota Denetimi veya Yay Yönlendirme problemi olarak da anılır ve oldukça benzerdir. CPP’nin amacı, bir graf üzerindeki tüm bağlantıları (yolları) en az bir kez kapsayan en kısa yolu bulmaktır. Eğer bunu aynı yolu iki kez geri dönmeden yapmak mümkünse, harika; bu ideal senaryodur ve problem oldukça basittir. Ancak bazı yolların birden fazla kez geçilmesi gerekiyorsa, her yolu en az bir kez en düşük toplam mesafe ile kapsayan en kısa rotayı bulmak için biraz matematik gerekir.

Kişisel Motivasyon

(Aşağıdaki kişisel bir nottur: biraz duygusal, biraz nüktedan ve Python’da graf optimizasyonu öğrenmek için kesinlikle gerekli değildir)

Bu problemi çözmek için gerçek bir uygulama sebebim vardı: Giantmaster Maratoncusu rütbesine erişmek.

Giantmaster nedir? Bir Giantmaster, Hamden CT’deki (memleketim Wallingford’un komşusu) Sleeping Giant Eyalet Parkı’ndaki her patikayı ... yaşamı boyunca yürümüş olan (köpek veya insan) kişidir. Giantmaster Maratoncusu ise tüm bu patikaları tek bir günde yürümüş olandır.

Sleeping Giant Park Derneği’nin titiz kayıt tutma sayesinde, tüm Giantmaster’ların tam listesi ve seviyeleri burada bulunabilir. İtiraf etmeliyim ki bu, bu yan projeye başlamam ve patikalara çıkıp koşmam için beni epey motive etti. Ben, Sleeping Giant Patika Ekibi’nin genç bir gönüllüsü olduğum 2006 kışında Giantmaster statüsüne ulaştım (ki bunun SG arşivinde kayda geçtiğini görmekten memnun oldum), ancak o zamandan beri yeni zorluklar ortaya çıktı. 12 aylık ve 4 mevsimlik Giantmaster kategorileri etkileyici ve cazip olsa da, mevcut evimden (DC) büyüdüğüm eve (CT) makul olandan daha fazla seyahat gerektirirdi... ve graf optimizasyonu açısından da o kadar ilginç değiller; bu yüzden hedef Giantmaster Maratonu!

Başka bir referans için, Sleeping Giant patika haritası aşağıda verilmiştir:

Graflara Giriş

Grafların güzel yanı, kavramların ve terminolojinin genellikle sezgisel olmasıdır. Yine de, işte bazı temel ifadeler:

Graflar, nesneler arasındaki ilişkileri haritalayan yapılardır. Bu eğitimde nesnelere düğüm, aralarındaki bağlantılara ise kenar denecektir. Kenar ve düğümlerin genellikle tam olarak aynı anlama gelen farklı isimlerle de anıldığını unutmayın:

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

Başlangıçtaki graf yönsüzdür. Yani kenarlar yön içermez: çift yönlüdür. Örneğin: A<--->B == B<--->A.
Buna karşılık, her patikayı yürümek için en kısa yolu belirtmek üzere oluşturabileceğiniz graf bir yönlü graf olabilir; burada kenarların sırası ve yönü önemlidir. Örneğin: A--->B != B--->A.

Graf aynı zamanda bir kenar ağırlıklı graftır; burada bitişik her düğüm çifti arasındaki mesafe (mil cinsinden) bir kenarın ağırlığını temsil eder. Bu, "distance" adlı bir kenar özniteliği olarak ele alınır.

Derece, bir düğüme temas eden (değen) kenar sayısını ifade eder. Bu sayı tek ise düğümler tek dereceli, çift ise çift dereceli olarak adlandırılır.

Bu CPP probleminin çözümü bir Euler turlu olacaktır: her kenardan tam olarak bir kez geçen ve bir başlangıç düğümünden başlayıp yine kendisine dönen (geri izleme olmadan) bir çevrimin yapılabildiği bir graf. Bir Euler Turu aşağıdaki isimlerle de bilinir:

Eulerian tour == Eulerian circuit == Eulerian cycle

Bir eşleştirme, hiçbir düğümün birden fazla kez yer almadığı kenar alt kümesidir. Minimum ağırlıklı eşleştirme ise toplam kenar ağırlığı en düşük olan eşleştirmeyi bulur.

NetworkX: Graf İşleme ve Analizi

NetworkX, grafları işlemek ve analiz etmek için en popüler Python paketidir. Aynı temel düzeyde graf işleme sunan birkaç paket daha vardır; özellikle R ve C++ bağları da olan igraph. Ancak CPP’yi çözmek için ihtiyaç duyduğum en güçlü graf algoritmalarının NetworkX’te olduğunu gördüm.

Paketlerin Kurulması

Python’da herhangi bir veri analizi yaptıysanız veya Anaconda dağıtımını kullanıyorsanız, muhtemelen pandas ve matplotlib vardır. Ancak networkx olmayabilir. Bu eğitim boyunca çalıştırmak için Python Standart Kütüphanesi dışında ihtiyacınız olan tek bağımlılıklar bunlar olmalı. pip ile kurulumları kolaydır:

pip install pandas
pip install networkx
pip install matplotlib

Şimdilik ihtiyacınız olan tüm paketler bunlar olmalı. imageio ve numpy, CPP çözümünün GIF animasyonunu oluşturmak için en sonda içe aktarılır. Animasyon bu yazıya gömülüdür, dolayısıyla bu paketler isteğe bağlıdır.

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

Veriyi Yükleyin

Kenar Listesi

Kenar listesi, grafı oluşturmak için kullanacağınız basit bir veri yapısıdır. Her satır, bazı kenar öznitelikleriyle birlikte grafın tek bir kenarını temsil eder.

• node1 & node2: bağlanan düğümlerin adları.
• trail: her kenar için patikanın kısaltılmış adını belirten kenar özniteliği. Örneğin: rs = kırmızı kare
• distance: patika uzunluğunu mil cinsinden belirten kenar özniteliği.
• color: çizimde kullanılacak patika rengi.
• estimate: bazı mesafeler verilmediği için mesafenin patika haritasına bakarak tahmini olup olmadığını belirten kenar özniteliği (1=evet, 0=hayır). Bu yalnızca referans içindir; analizde kullanılmaz.

# 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)

Düğüm Listesi

Düğüm listeleri, networkx ve diğer graf kütüphanelerinde kenar listeleri sağlandığında genellikle isteğe bağlıdır; çünkü düğüm adları kenar listesinin ilk iki sütununda verilir. Ancak bu durumda, eklemek istediğimiz bazı düğüm öznitelikleri var: düğümlerin (patika kesişimleri) X, Y koordinatları; böylece grafı patika haritasıyla aynı yerleşimle çizebilirsiniz.

Bu koordinatları, görseli GIMP ile üzerinden geçerek bir öğleden sonramı harcayıp elle notladım:

• id: kenar listesindeki node1 ve node2 ile eşleşen düğüm adı.
• X: düğümün sol üst köşeye göre yatay konumu/koordinatı.
• Y düğümün sol üst köşeye göre dikey konumu/koordinatı.

Düğüm ve Kenar Listelerini Oluşturma Üzerine Not

Düğüm adlarını oluşturmak da biraz manuel çaba gerektirdi. Her düğüm, iki veya daha fazla patikanın kesişimini temsil eder. Mümkün olduğunda, düğüm patika1_patika2 şeklinde adlandırıldı; burada patika1 alfabetik olarak patika2’nin önünde gelir.

Aynı patikalar birden fazla kez kesiştiğinde işler biraz zorlaştı. Örneğin, Turuncu ve Beyaz patika. Bu durumlarda, düğüm adına _2 veya _3 ekledim. Örneğin, Turuncu ve Beyaz’ın iki ayrı kesişimi için iki ayrı düğüm adınız olur: o_w ve o_w_2.

Bu süreç, X,Y koordinatlarıyla oluşturulan çizimleri gerçek patika haritasıyla karşılaştırıp çokça deneme-yanılma gerektirdi.

# 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)

Graf Oluşturma

Şimdi kenar listesini ve düğüm listesini kullanarak networkx’te bir graf nesnesi oluşturacaksınız.

# Create empty graph
g = nx.Graph()

Kenar listesinin satırlarında dolaşarak her kenarı ve karşılık gelen özniteliklerini g grafına ekleyin.

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

Burada ne olduğunu göstermek için, g grafına eklenen kenar listesinin son satırındaki değerleri yazdıralım:

# 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}

Benzer şekilde, düğüm listesinin satırlarında dolaşarak bu düğüm özniteliklerini ekleyin.

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

İşte düğüm listesinin son satırından bir örnek:

# Node list example
print(nlrow)

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

Grafı İnceleyin

Kenarlar

Grafınızdaki kenarlar, uzunluğu 3 olan demetlerden oluşan bir listeyle temsil edilir. İlk iki öğe, kenarla bağlanan düğüm adlarıdır. Üçüncüsü, kenar öznitelikleri sözlüğüdür.

# 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'})]

Düğümler

Benzer şekilde, düğümleriniz uzunluğu 2 olan demetlerden oluşan bir listeyle temsil edilir. İlk öğe düğüm kimliği, ardından düğüm öznitelikleri sözlüğü gelir.

# 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})]

Özet İstatistikler

Grafı görselleştirmeden önce bazı özet istatistikleri yazdırın.

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

# of edges: 123
# of nodes: 77

Grafı Görselleştirin

Renkleri ve Yerleşimi Düzenleyin

Konumlar: Önce grafdaki düğüm konumlarını bir sözlüğe dönüştürmeniz gerekir. Bu, grafı gerçek patika haritasıyla aynı yerleşimle yeniden oluşturmanızı sağlayacaktır. Y, Y ekseni başlangıcını sol üstten sol alta dönüştürmek için negatiflenir.

# 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)}

Renkler: Şimdi kenar renklerini grafdan basit bir listeye dönüştürerek patikaları renklerine göre görselleştirebilirsiniz.

# 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']

Çizim

Şimdi Sleeping Giant patika haritasıyla güzelce hizalanan bir grafik çizebilirsiniz:

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()

Bu graf gösterimi, patikaların tüm kıvrımlarını ve zikzaklarını elbette yakalamaz; ancak endişelenmeyin: bunlar hesaplama için kullanılan distance kenar özniteliğinde doğru şekilde yer alır. Görsel, düğümler (patika kesişimleri) arasındaki mesafeyi kuş uçuşu gösterir ve bu da fena olmayan bir yaklaşımdır.

CPP Algoritmasına Genel Bakış

Peki, bazı terimleri tanımladığınıza ve grafı oluşturduğunuza göre, içinden en kısa yolu nasıl bulursunuz?

Çinli Postacı Problemini çözmek kavramsal olarak oldukça basittir:

1. Tüm tek derece düğümleri bulun (çok kolay).
   (Bir kesişime değen patika sayısının tek olduğu tüm patika kesişimlerini bulun)
   
   

2. Grafa kenarlar ekleyin; böylece tek dereceye sahip tüm düğümler çift yapılır. Bu eklenen kenarlar, orijinal graftan kopyalar olmak zorundadır (bu problem için orman içinden kestirme yok varsayacağız). Eklenen kenarların kümesi, mümkün olan en düşük mesafeye toplamda ulaşmalıdır (zor... daha doğrusu np-zor).
   (Daha basit ifadeyle, her patikaya uğrayan bir rotadaki geri dönüş miktarını minimize edin)
   
   

3. Bir başlangıç noktası verildiğinde, genişletilmiş veri kümesi üzerinde Euler turunu bulun (orta derecede kolay).
   (Hangi patikalarda geri gidiş yapacağımızı bildikten sonra, rotayı baştan sona hesaplayın)

Varsayımlar ve Basitleştirmeler

Aşağıdaki varsayımları gevşeterek daha kısa ve daha hassas bir yol üretmek mümkün olsa da, bu durum CPP’ye odaklanan bu eğitimin kapsamını aşan bir karmaşıklık ekler.

Varsayım 1: Yalnızca zorunlu patikalar

Yukarıdaki patika haritasından da görebileceğiniz gibi, parkın sınırları boyunca özellikle kırmızı patikaları bağlamak için kullanılabilecek yollar var. Ayrıca Giantmaster günlüğüne göre zorunlu olmayan, ancak uzun geri dönüşleri önlemeye yardımcı olabilecek bazı patikalar (Horseshoe ve işaretsiz izler) de var. İsteğe bağlı patikaların dahil edilmesi aslında Kırsal Postacı Problemi adı verilen CPP’nin bilinen bir varyantıdır. Bu eğitimde isteğe bağlı patikaları yok sayıyor ve yalnızca zorunlu patikalara odaklanıyoruz.

Varsayım 2: Yokuş yukarı == yokuş aşağı

CPP, bir patikayı yürümenin maliyetinin, hangi yönde yüründüğünden bağımsız olarak mesafesine eşit olduğunu varsayar. Ancak bazı patikalar epey engebelidir ve yukarı yürümek aşağı yürümekten daha fazla enerji gerektirir. Hem mesafeyi hem de irtifa değişimini yönlü bir graf üzerinde birleştiren bir metrik, Rüzgarlı Postacı Problemi adı verilen CPP’nin bir uzantısına dahil edilebilir.

Varsayım 3: Paralel kenar (patika) yok

Mümkün olsa da, paralel kenarların (aynı iki düğümü bağlayan birden çok patikanın) dahil edilmesi hesaplamaya karmaşıklık katar. Neyse ki burada bu durum yalnızca iki kez meydana geliyor (Mavi <=> Kırmızı Elmas ve Mavi <=> Kule Patikası). Bu, kenar listesine küçük bir hile ile ele alınır: kenarların benzersizliğini korurken her patikayı yakalamak için _dupe sonekiyle yinelenen düğümler eklenir. Kendi grafınızda çok sayıda paralel kenar varsa CPP’yi çözmek isterseniz yazdığım postman_problems paketindeki CPP uygulaması paralel kenarları daha zarif bir şekilde sağlam ele alır.

CPP Adım 1: Tek Dereceli Düğümleri Bulun

Bu oldukça düz bir sayma hesaplamasıdır. 76 düğümün 36’sının tek dereceye sahip olduğunu görürsünüz. Bunların çoğu çıkmaz patikalar (derece 1) ve 3 patikanın kesişimleri. Birkaç tane de derece 5 düğüm var.

# 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

CPP Adım 2: Minimum Mesafeli Çiftleri Bulun

Asıl işin yoğun olduğu yer burası. Bunu 5 parçaya böleceksiniz:

1. Tek dereceli düğümlerin tüm olası çiftlerini hesaplayın.
2. 1.’de hesaplanan her düğüm çifti arasındaki en kısa yolu hesaplayın.
3. 2.’de hesaplanan en kısa yol mesafesi öznitelikleriyle 1.’deki her düğüm çiftini bağlayan bir tam graf oluşturun.
4. 3.’te hesaplanan grafın bir minimum ağırlıklı eşleştirmesini hesaplayın.
   (Bu, tek düğümlerin nasıl eşleştirileceğini, aralarındaki mesafelerin toplamı mümkün olduğunca küçük olacak şekilde belirlemeye indirgenir).
5. 4.’te hesaplanan düğüm çiftleri arasındaki en kısa yollarla orijinal grafı zenginleştirin.

Adım 2.1: Düğüm Çiftlerini Hesaplayın

itertools combination fonksiyonunu kullanarak tek dereceli düğümlerin tüm olası çiftlerini hesaplarsınız. Grafınız yönsüzdür, dolayısıyla sıra önemli değildir: Örneğin, (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

Aşağıdaki kombinatorik ile bu çift sayısının doğru olduğunu doğrulayalım. Neyse ki yalnızca 630 çift ile uğraşacaksınız. Bu CPP örneğini çözme hesaplama süreniz önemsizdir (birkaç saniye).

Ancak 3.600 tek düğüm çifti olsaydı, ~6,5 milyon çifti optimize etmeniz gerekirdi. Bu da giriş boyutundaki 100 kat artışa karşılık çıktı boyutunda ~10.000 kat artış demektir.

Adım 2.2: Düğüm Çiftleri Arasındaki En Kısa Yolları Hesaplayın

Bu, gerçek hesaplamayı içeren ilk adımdır. Neyse ki networkx, iki düğüm arasındaki en kısa yolu hesaplamak için Dijkstra algoritmasının kullanışlı bir uygulamasını sunar. Bu fonksiyonu yukarıda odd_node_pairs içinde hesaplanan her çifte (toplam 630) uygularsınız.

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}

Adım 2.3: Tam Graf Oluşturun

Bir tam graf, her düğümün benzersiz bir kenarla her diğer düğüme bağlandığı bir graftır.

İşte Wikipedia’dan 21 kenarlı (7’nin 2’li kombinasyonu) 7 düğümlü bir tam graf örneği:

Aşağıda oluşturduğunuz graf, 36 düğüm ve karşılık gelen kenar ağırlıkları (mesafe) ile 630 kenara sahiptir.

create_complete_graph fonksiyonu bunu hesaplamak için tanımlanır. flip_weights parametresi, distance özniteliğini weight özniteliğine dönüştürmek için kullanılır; burada küçük sayılar büyük mesafeleri, yüksek sayılar ise kısa mesafeleri yansıtır. Bu biraz sezgiye aykırı gelebilir; ancak 2.4 Adımında, tam graf üzerinde minimum ağırlıklı eşleştirmeyi hesaplamak için gereklidir.

İdeal olarak minimum ağırlıklı eşleştirmeyi doğrudan hesaplardınız; fakat NetworkX yalnızca kenar ağırlığını maksimize eden max_weight_matching fonksiyonunu uygular. Bunu, distance özniteliğini ters işaretle (−1 ile çarparak) weight elde edecek şekilde biraz hileyle çözüyoruz. Bu, mesafeye göre sıralamanın ve ölçeğin korunmasını, ancak tersine çevrilmesini sağlar.

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

Görsel destek için, tek dereceli düğüm çiftlerinin tamamen bağlandığı graf aşağıda çizilmiştir. Düğümlerin X, Y koordinatlarını koruduğunuza, ancak kenarların mutlaka gerçek patikaları temsil etmediğine dikkat edin. Örneğin, bu grafta iki düğüm tek bir kenarla bağlanmış olabilir; ancak aralarındaki en kısa yol, burada gösterilmeyen çift dereceli düğümler üzerinden 5 sıçrama olabilir.

# 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()

Adım 2.4: Minimum Ağırlıklı Eşleştirmeyi Hesaplayın

Bu, CPP’nin en karmaşık adımıdır. Birlikte toplamları (aralarındaki mesafelerin) mümkün olduğunca küçük olan tek dereceli düğüm çiftlerini bulmanız gerekir. Yani probleminiz için bu, 2.3’te üretilen karmakarışık graftan en uygun 18 kenarı (36 tek derece düğüm / 2) seçmeye indirgenir.

Bu optimizasyonun hem uygulaması hem de sezgisi bu eğitimin kapsamı dışındadır... 800+ satır kod ve bu kapsamın ötesinde bir akademik literatür.

Yine de meraklı okur için kısaca:

2008’de blogunda orijinal uygulamayı yazdığı için Joris van Rantwijk’e büyük teşekkürler. Benzer şekilde probleme daldım ve Joris’le aynı amaçtaydım. Joris’in 2008 tarihli yazısından:

Maximum weighted matching’in Perl uygulamalarını bulamadığım için, kendi kendime biraz kod yazayım dedim. Sorunu hafife aldığımı anladığımda artık çok geçti; hatamı fark ettiğimde bile, probleme o kadar takılmıştım ki vazgeçmeyi reddettim.

Ben ise vazgeçtim. Neyse ki Joris vazgeçmedi.

Bu Maksimum Ağırlıklı Eşleştirme, o zamandan beri NetworkX paketine dahil edildi ve burada bakımı sürdürülüyor. Bu ağır kod tabanını sürdüren 10+ GitHub katılımcısına da büyük teşekkürler.

Bu zor ve yoğun bir hesaplamadır. 1965’teki ilk atılım, Maksimum Eşleştirme probleminin polinom zamanda çözülebileceğini kanıtladı. Jack Edmonds tarafından, belki de yazılmış en güzel akademik makale başlıklarından biriyle yayımlandı: "Paths, trees, and flowers" [1]. Bu çalışmanın üzerine inşa edilen bir literatür gövdesi, optimizasyon prosedürünü geliştirdi. NetworkX’te uygulanan max_weight_matching fonksiyonundaki kod, O(n³) zaman algoritması kullanan Galil, Zvi (1986) [2] temel alınarak yazılmıştır.

# 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

Eşleştirme çıktısı (odd_matching_dupes) bir sözlüktür. Bu eşleştirmede 36 kenar olmasına rağmen, sizin yalnızca 18’ine ihtiyacınız var. Her kenar çifti sözlükte iki kez geçer (bir kez anahtar olarak düğüm 1 ve ikinci kez anahtar olarak düğüm 2 ile).

# 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'}

Sözlüğü bir demet listesine dönüştürürsünüz; çünkü grafınız yönsüzdür ve sıra önemli değildir. Yinelenenleri kaldırmak, toplamda en kısa mesafeyi veren benzersiz 18 kenar çiftini verir.

# 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')]

Bu çiftleri, 2.3 adımında çizdiğiniz tam graf üzerinde görselleştirelim. Önceden olduğu gibi, düğüm konumları burada gerçek grafı (patika haritası) yansıtırken, gösterilen kenar mesafeleri (mavi çizgiler) kuş uçuşudur. Bir düğümden diğerine gerçek en kısa rota, oldukça daha uzun mesafeli ve kıvrımlı birden çok kenar içerebilir.

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()

Bunun orijinal graf ile nasıl örtüştüğünü göstermek için, aynı minimum ağırlıklı çiftleri (mavi çizgiler) bu kez tam graf yerine (soluklaştırılmış) patika haritası üzerinde çizelim. Yine, mavi çizgilerin arazi keserek giden (kuş uçuşu, gerçek patikalar olmayan) rotayı gösterdiğine dikkat edin. 3. Adımda her çift arasındaki en kısa rotayı oluşturan kenarları bulmak için hâlâ biraz işiniz var.

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()

Adım 2.5: Orijinal Grafı Zenginleştirin

Şimdi, 2.4’te hesaplanan eşleştirmeden gelen kenarlarla orijinal grafı zenginleştiriyorsunuz. Bunu yapmak için aşağıda basit bir fonksiyon tanımlanmıştır; ayrıca bu yeni kenarların zenginleştirilmiş graftan geldiğini de not eder. Bu bilgiye, grafta gerçek Euler çevrimini oluştururken 3. adımda ihtiyacınız olacak.

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

Zenginleştirilmiş grafın beklenen sayıda (18) kenar eklediğini doğrulayalım:

# 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

Her düğümün artık çift dereceye sahip olduğunu da doğrulayalım:

pd.value_counts(g_aug.degree())

4    54
2    18
6     5
dtype: int64

CPP Adım 3: Euler Çevrimini Hesaplayın

Artık çift dereceye sahip bir grafa sahip olduğunuza göre zor optimizasyon işi bitti. Euler, 1736’da Königsberg’in Yedi Köprüsü problemiyle ünlü şekilde ortaya koyduğu üzere, tüm düğümler çift dereceye sahipse her kenarı tam olarak bir kez ziyaret eden bir yol vardır. Carl Hierholzer bu sonucu 1870’lerde resmen kanıtladı.

Aynı mesafeye sahip birçok Euler çevrimi oluşturulabilir. NetworkX’in eulerian_circuit fonksiyonuyla işin %90’ını halledebilirsiniz. Ancak bazı kısıtlar vardır.

Düzelteceğiniz kısıtlar:

1. Zenginleştirilmiş graf, orijinal grafta olmayan kenarlar içerebilir (ve muhtemelen içerecektir). Çevrimi (araziden kestirme yapmadan) elde etmek için bu zenginleştirilmiş kenarları, gerçekte var olan kenarlar üzerinden geçen en kısa yola parçalamanız gerekir.

2. eulerian_circuit yalnızca her düğüme hangi sırada uğradığımızı döndürür. Çevrimi tamamlamak için gereken kenar özniteliklerini döndürmez. Bu gereklidir; çünkü iki düğüm arasında birden fazla kenar olduğunda, hangi kenarların daha önce yüründüğünü takip etmeniz gerekir.

Düzeltmeyeceğiniz kısıtlar:

3. Bacaklarınızı biraz olsun kurtarmak için, Euler çevriminin aynı düğümde başlayıp bitmesi varsayımını gevşetebilirdiniz. Euler yolu (Euler çevriminin genel hali), tam olarak iki düğüm tek dereceye sahipse bulunabilir. Bu, biraz geri dönüş tasarrufu sağlar... parkın öbür ucundan geri dönüş için bir araç bulabileceğinizi varsayarsak. Ancak bu yazı yazıldığı sırada, NetworkX bir Euler Yolu algoritması sunmuyor. eulerian_circuit kodu çok da kötü değil ve bu duruma uyarlanabilir; ama burada basit tutacağız.

Naif Çevrim

Yine de, basit ama eksik çözümle başlayalım:

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

Beklendiği gibi, naif Euler çevriminin uzunluğu, zenginleştirilmiş graftaki kenar sayısına eşittir.

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

Length of eulerian circuit: 141

Çıktı, düğüm çiftlerini temsil eden demetlerden oluşan bir listedir. Her çiftin ilk düğümünün, bir önceki çiftin ikinci düğümüyle aynı olduğuna dikkat edin.

# 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')]

Doğru Çevrim

Şimdi sizi, düğüm A’dan düğüm B’ye gitmek için hangi patikaları kullanmanız gerektiğini orijinal graftan yararlanarak söyleyen bir fonksiyon tanımlayalım. Kod olarak uzun olsa da mantık aslında oldukça basit. Naif çevrimi, orijinal grafta var olmayan kenarları içeren halinden, yalnızca orijinal grafta var olan kenarları kullanan bir Euler çevrimine dönüştürürsünüz.

Naif Euler çevrimindeki (naive_euler_circuit) her kenarda dolaşırsınız. Orijinal grafta var olmayan bir kenarla karşılaştığınızda, bunu orijinal grafı kullanarak düğümleri arasındaki en kısa yolu oluşturan kenar dizisiyle değiştirirsiniz.

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

Kısıt 3’ü, Euler çevrimini parkın en doğu ucundaki Mavi patikada ("b_end_east" düğümü) başlatarak biraz hileyle aşıyoruz. Bunu gerçekten koşarken, geriye dönüş olan son yönü atlayabilirsiniz.

Zenginleştirilmiş graftaki var olmayan kenarları, gerçekte var olan kenarlar üzerinden en kısa yol ile değiştirirken neler olduğunu göstermek için ayrıntılı yazdırmalar eklendi.

# 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')]

Euler çevriminin uzunluğunun naif çevrimden daha uzun olduğunu görürsünüz; bu mantıklıdır.

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

Length of Eulerian circuit: 158

CPP Çözümünü Hesaplayın

Metin

İşte çözümün metin çıktısı:

# 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})

Algoritmanın herhangi bir patikaya çok da sadık olmadığını, birinden diğerine hızlıca atladığını çabucak fark edebilirsiniz. Bu yaklaşımın bir uzantısı, rotayı gerçekten koşmayı daha yönetilebilir kılmak için amaç fonksiyonuna bir tür patika sadakati kavramı ekleyebilir.

İstatistikler

Çözümünüze göz atıp ne kadar makul göründüğüne bakalım.
(Bu ayrıntılı koda takılmak önemli değil, yalnızca yazdırılan çıktılar)

# 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

CPP Çözümünü Görselleştirin

NetworkX, grafları görselleştirme işlevi de sunsa da, bu departmanda oldukça mütevazıdır:

NetworkX, grafları görselleştirmek için temel işlevsellik sağlar; ancak asıl amacı graf analizi yapmayı mümkün kılmaktır; graf görselleştirmesi yapmak değil. Gelecekte graf görselleştirme işlevleri NetworkX’ten kaldırılabilir veya yalnızca bir eklenti paket olarak sunulabilir.

Doğru graf görselleştirmesi zordur ve insanlara bu iş için özel olarak geliştirilmiş araçlarla graflarını görselleştirmelerini şiddetle tavsiye ederiz. Bu alana adanmış ve tam özellikli araçlara örnek olarak Cytoscape, Gephi, Graphviz ve LaTeX dizgisi için PGF/TikZ verilebilir.

Öyle olsa da, NetworkX’in matplotlib ile yerleşik çizim işlevselliği temel grafları gözden geçirmek ve görsel olarak keşfetmek için yeterince güçlüdür; bu eğitimde NetworkX’in draw fonksiyonuna bağlı kalacaksınız.

Ben, çözümü Python paketim postman_problems’ta görselleştirmek için graphviz ve dot graf tanımlama dilini kullandım. NetworkX graf yapısını dot grafa dönüştürmek biraz emek istese de, görselleştirmelerde kaliteyi ve kontrolü artırır.

CPP Grafını Oluşturun

İlk adımınız, Euler çevriminde yürünecek kenar listesini, çizime uygun özniteliklere sahip bir kenar listesine dönüştürmektir.

create_cpp_edgelist, çizimde kullanacağınız bazı ek özniteliklerle bir kenar listesi oluşturur:

• sequence: her kenarı ne zaman yürüdüğümüzün sırasını kaydeder.
• visits: belirli bir kenarı kaç kez yürüdüğümüzdür.

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())

CPP kenar listesini oluşturalım:

cpp_edgelist = create_cpp_edgelist(euler_circuit)

Beklendiği gibi, kenar listeniz orijinal graftaki kenar sayısıyla aynıdır.

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

Number of edges in CPP edge list: 123

CPP kenar listesi, euler_circuit’e benzer görünür; yalnızca birkaç ek öznitelik içerir.

# 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})]

Şimdi grafı oluşturalım:

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

Görselleştirme 1: Adımları Geri İzleme

Burada, bir kez yürünmüş (gri) ve birden fazla kez yürünmüş (mavi) kenarları gösteriyorsunuz. Bu, 2.4’te oluşturulan ve tek düğüm çiftleri arasındaki naif (kuş uçuşu) bağlantıları (kırmızı) gösteren görselleştirmenin "doğru" versiyonudur. Burada, her tek derece düğüm çifti için gerçek var olan kenarlar üzerinden en kısa yolu izleyerek bu durum düzeltilmiştir.

Eğer optimizasyon iyiyse, bu mavi çizgiler mümkün olan en az mesafeyi temsil etmelidir. Özellikle, tek dereceli düğümlerin bir eşleştirmesini üretmek için gereken minimum mesafe.

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()

Görselleştirme 2: CPP Çözüm Sırası

Burada, CPP çözümüne göre patikaları hangi sıralarla yürüdüğümüzü gösteren sıra numaralarıyla açıklamalı orijinal grafı (patika haritası) çiziyorsunuz. Birden çok numara, geri dönmemiz gereken patikaları gösterir.

Sağ alttaki mavi patikada başlıyorsunuz (0. ve 157. yön).

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()

Görselleştirme 3: Film

Aşağıda baştan sona Euler çevrimini izleyen film gömülüdür. Kenarlar ilk kez yüründüğünde siyah, ikinci kez yüründüğünde kırmızı renge boyanır.

Bu gif’in, başka bir kenarla üst üste binen veya doğru şekilde görselleştirmek için çok küçük kalan kenarlara tam görsel adaleti sağlayamadığına dikkat edin. Graphviz gibi daha sağlam bir görselleştirme kütüphanesi, düğümler arasında düz çizgiler yerine spline’lar çizerek bunu ele alabilir.

Onu oluşturan kod, referans olarak aşağıda sunulmuştur.

Önce, CPP çözümündeki her yönerge (yürünmüş kenar) için bir PNG görsel üretilir.

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()

Ardından bu PNG görselleri birleştirilerek yukarıdaki küçük gif yapılır.

Önce PNG’ler 0’dan 157’ye sırada dizilir. Sonra imageio kullanılarak saniyede 3 kare hızında gif oluşturmak için birleştirilirler.

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)

Sonraki Adımlar

Tebrikler, Python’da Çinli Postacı Problemini çözen bu eğitimi tamamladınız. Bu eğitimde çok yol kat ettiniz (tam olarak 33,6 mil patika). Ağ temellerine daha derin bir dalış için, temel kavramların daha kapsamlı bir işlenişini sunan Datacamp’in Python’da Ağ Analizine Giriş kursu ilginizi çekebilir.

Bu karmaşık ağları nasıl oluşturacağınız, yöneteceğiniz ve geçeceğiniz hakkında daha fazla bilgi için NetworkX dokümantasyonuna bakmaktan çekinmeyin. Dokümanlar kapsamlıdır; iyi sayıda örnek ve bir dizi eğitim içerir.

CPP’yi kendi grafınız üzerinde çözmekle ilgileniyorsanız, bu eğitimdeki işlevselliği postman_problems Python paketine ekledim. Farklı bir kenar ve düğüm listesiyle bu eğitimdeki kod bloklarını da bir araya getirebilirsiniz; fakat postman_problems paketi muhtemelen sizi daha hızlı ve daha temiz bir şekilde sonuca ulaştırır.

Bir gün, CPP’nin uzantılarını (Kırsal ve Rüzgarlı Postacı Problemi) burada da uygulamayı planlıyorum. Ayrıca bu uzantılar ve patikalarda rotaları test etme deneyimlerim hakkında blogumda burada yazma gibi büyük hedeflerim var. Keza başka bir uygulama olarak, Garmin saatime adım adım yol tarifi göndermek için enlem/boylam koordinatlarını dahil etmeyi de keşfetmeyi ve yazmayı planlıyorum.

Ve elbette son bir sonraki adım: dışarı çıkıp rotayı koşmak!

Python’da Ağlar hakkında daha fazla bilgi edinmek isterseniz şu DataCamp kurslarına göz atın:

Python’da Ağ Analizine Giriş

Python’da Orta Düzey Ağ Analizi

Kaynaklar

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. Cilt 18, No. 1: 23-38.