Python में NetworkX के साथ ग्राफ़ ऑप्टिमाइज़ेशन

यह NetworkX ट्यूटोरियल आपको Python में Chinese Postman Problem हल करके ग्राफ़ ऑप्टिमाइज़ेशन करना सिखाएगा।

Andrew Brooks

अपडेट किया गया 6 अक्टू॰ 2026 · 15 मि॰ पढ़ें

AI के साथ खोजें

ChatGPT Claude Perplexity

अपना निःशुल्क खाता बनाएँ

अभ्यास और ट्रैक अपनी प्रगति को।

Google के साथ जारी रखें

जारी रखने पर, आप हमारी उपयोग की शर्तें, हमारी गोपनीयता नीति को स्वीकार करते हैं और यह भी कि आपका डेटा संयुक्त राज्य अमेरिका में संग्रहीत किया जाता है।

इस ट्यूटोरियल के साथ, आप ग्राफ़ थ्योरी की एक स्थापित समस्या Chinese Postman Problem को हल करेंगे। अल्गोरिदम के कुछ हिस्से वैचारिक रूप से सरल हैं, लेकिन संगणकीय रूप से काफ़ी सख़्त हो जाते हैं। फिर भी, इस ट्यूटोरियल के लिए केवल Python का कुछ पूर्वज्ञान आवश्यक है: कड़े गणित, कंप्यूटर विज्ञान या ग्राफ़ थ्योरी की पृष्ठभूमि की जरूरत नहीं है।

यह ट्यूटोरियल पहले ग्राफ़ के बुनियादी बिल्डिंग ब्लॉक्स (नोड्स, एजेज, पाथ्स, आदि) पर जाएगा और NetworkX लाइब्रेरी का उपयोग करके एक वास्तविक ग्राफ़ (एक स्टेट पार्क के ट्रेल नेटवर्क) पर समस्या को हल करेगा। आप कोर कॉन्सेप्ट्स और इम्प्लीमेंटेशन पर ध्यान देंगे। इच्छुक पाठकों के लिए, ऑप्टिमाइज़ेशन की बुनियादी कार्यप्रणाली पर आगे पढ़ने के लिए संदर्भ दिए गए हैं।

ग्राफ़ ऑप्टिमाइज़ेशन के लिए प्रेरणा

समस्या

आपने शायद Travelling Salesman Problem के बारे में सुना होगा, जिसमें नोड्स (जैसे, शहर) के एक सेट को जोड़ने वाला सबसे छोटा रूट (जैसे, सड़कें) ढूँढना होता है। थोड़ा कम प्रसिद्ध होने के बावजूद, Chinese Postman Problem (CPP), जिसे Route Inspection या Arc Routing समस्या भी कहा जाता है, काफ़ी समान है। CPP का उद्देश्य ऐसा सबसे छोटा पाथ ढूँढना है जो ग्राफ़ की सभी कड़ियों (सड़कें) को कम-से-कम एक बार कवर करे। अगर यह बिना किसी सड़क पर दोबारा लौटे संभव हो, तो बहुत बढ़िया; यही आदर्श स्थिति है और समस्या काफी सरल हो जाती है। लेकिन यदि कुछ सड़कों पर एक से अधिक बार जाना अनिवार्य हो, तो आपको ऐसा सबसे छोटा रूट ढूँढने के लिए कुछ गणना करनी होगी जो हर सड़क को कम-से-कम एक बार कवर करे और कुल दूरी न्यूनतम रहे।

व्यक्तिगत प्रेरणा

(निम्नलिखित एक व्यक्तिगत टिप्पणी है: थोड़ा भावुक, चुलबुला और Python में ग्राफ़ ऑप्टिमाइज़ेशन सीखने के लिए 100% आवश्यक नहीं)

मेरे पास इस समस्या को हल करने का एक वास्तविक जीवन अनुप्रयोग था: Giantmaster Marathoner का दर्जा पाना।

Giantmaster क्या है? Giantmaster वह (कुत्ता या इंसान) है जिसने अपने जीवनकाल में Hamden CT के Sleeping Giant State Park के हर ट्रेल पर हाइक किया हो (मेरे गृह-नगर Wallingford के पड़ोस में)। Giantmaster Marathoner वह है जिसने इन सभी ट्रेल्स को एक ही दिन में हाइक किया हो।

Sleeping Giant Park Association के सटीक रिकॉर्ड रखने के कारण, Giantmasters की पूरी सूची और उनकी Giantmastering का स्तर यहाँ मिल सकता है। मानना पड़ेगा कि इसने मुझे इस साइड-प्रोजेक्ट को शुरू करने और ट्रेल्स पर दौड़ने के लिए काफी प्रेरित किया। मैंने स्वयं 2006 की सर्दियों में Sleeping Giant Trail Crew का एक नवोदित स्वयंसेवक रहते हुए Giantmaster का दर्जा हासिल किया था (जिसे SG आर्काइव में दर्ज देखकर खुशी हुई), पर तब से नए चैलेंज सामने आए। 12-महीने और 4-सीजन Giantmaster श्रेणियाँ प्रभावशाली और लुभावनी हैं, पर उन्हें मेरे वर्तमान घर (DC) से मेरे शुरुआती घर (CT) तक अधिक यात्रा की आवश्यकता होगी जितना मैं यथोचित संभाल पाता... और वे ग्राफ़ ऑप्टिमाइज़ेशन के लिए उतनी दिलचस्प भी नहीं, तो फिर Giantmaster Marathon ही सही!

एक और संदर्भ के लिए, Sleeping Giant का ट्रेल मैप नीचे दिया गया है:

ग्राफ़्स का परिचय

ग्राफ़्स की अच्छी बात यह है कि इनके कॉन्सेप्ट्स और पारिभाषिक शब्द आम तौर पर सहज होते हैं। फिर भी, यहाँ कुछ बुनियादी शब्दावली दी गई है:

ग्राफ़्स वे संरचनाएँ हैं जो वस्तुओं के बीच संबंधों का मानचित्रण करती हैं। इस ट्यूटोरियल में वस्तुओं को नोड्स और उनके बीच के कनेक्शन्स को एजेज कहा गया है। ध्यान दें कि एजेज और नोड्स को आमतौर पर कई नामों से जाना जाता है जिनका अर्थ प्रायः समान ही होता है:

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

शुरुआती ग्राफ़ अनिर्देशित है। यानी आपके एजेज़ का कोई ओरिएंटेशन नहीं होता: वे द्विदिश हैं। उदाहरण: A<--->B == B<--->A।
इसके विपरीत, वह ग्राफ़ जो आप हर ट्रेल को हाइक करने के सबसे छोटे पाथ के लिए बना सकते हैं, एक डायरेक्टेड ग्राफ़ हो सकता है, जिसमें एजेज़ का क्रम और दिशा मायने रखते हैं। उदाहरण: A--->B != B--->A।

यह ग्राफ़ एक एज-वेटेड ग्राफ़ भी है, जहाँ हर आसन्न नोड-जोड़ी के बीच की दूरी (मील में) एज का वेट दर्शाती है। इसे "distance" नामक एक एज एट्रिब्यूट के रूप में हैंडल किया जाता है।

डिग्री से आशय किसी नोड को छूने वाले एजेज़ की संख्या से है। जब यह संख्या विषम होती है तो नोड्स को ऑड-डिग्री नोड्स कहा जाता है और जब सम होती है तो इवन-डिग्री।

इस CPP समस्या का समाधान एक Eulerian tour होगा: ऐसा ग्राफ़ जिसमें एक चक्र बनाया जा सके जो हर एज से ठीक एक बार होकर शुरुआती नोड से वापस उसी तक पहुँचता हो (बिना बैकट्रैकिंग)। Euler Tour को कई नामों से जाना जाता है:

Eulerian tour == Eulerian circuit == Eulerian cycle

मैचिंग एजेज़ का ऐसा सबसेट है जिसमें कोई नोड एक से अधिक बार न आता हो। मिनिमम वेट मैचिंग वह मैचिंग खोजती है जिसका कुल एज वेट संभव न्यूनतम हो।

NetworkX: ग्राफ़ मैनिपुलेशन और विश्लेषण

NetworkX ग्राफ़्स को मैनिपुलेट और विश्लेषित करने के लिए सबसे लोकप्रिय Python पैकेज है। कई पैकेज समान बुनियादी स्तर का ग्राफ़ मैनिपुलेशन ऑफर करते हैं, विशेष रूप से igraph, जिसके R और C++ के लिए भी बाइंडिंग्स हैं। हालाँकि, CPP को हल करने के लिए जिन ग्राफ़ अल्गोरिद्म्स की मुझे ज़रूरत थी, NetworkX उनमें सबसे मज़बूत लगा।

पैकेज इंस्टॉल करना

यदि आपने Python में कोई भी डेटा विश्लेषण किया है या आपके पास Anaconda डिस्ट्रीब्यूशन है, तो संभव है कि आपके पास pandas और matplotlib पहले से हों। हालाँकि, आपके पास networkx न हो। Python Standard Library के बाहर यही निर्भरताएँ आपको इस ट्यूटोरियल में चलने के लिए चाहिए होंगी। इन्हें pip से आसानी से इंस्टॉल किया जा सकता है:

pip install pandas
pip install networkx
pip install matplotlib

अभी के लिए आपको इतने पैकेज पर्याप्त होंगे। imageio और numpy को अंत में GIF एनीमेशन बनाने हेतु इम्पोर्ट किया गया है। चूँकि एनीमेशन इस पोस्ट में एम्बेड है, ये पैकेज वैकल्पिक हैं।

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

डेटा लोड करें

एज लिस्ट

एज लिस्ट एक सरल डेटा स्ट्रक्चर है जिसका उपयोग आप ग्राफ़ बनाने के लिए करेंगे। हर पंक्ति ग्राफ़ के एक एज और उसके कुछ एट्रिब्यूट्स का प्रतिनिधित्व करती है।

node1 और node2: जुड़े हुए नोड्स के नाम।
trail: प्रत्येक एज के लिए ट्रेल के संक्षिप्त नाम को दर्शाने वाला एज एट्रिब्यूट। उदाहरण: rs = red square
distance: ट्रेल की लंबाई (मील में) दर्शाने वाला एज एट्रिब्यूट।
color: प्लॉटिंग के लिए ट्रेल का रंग।
estimate: यह दर्शाने वाला एज एट्रिब्यूट कि एज की दूरी ट्रेल मैप को देखकर अनुमानित है या नहीं (1=हाँ, 0=नहीं), क्योंकि कुछ दूरियाँ उपलब्ध नहीं हैं। यह केवल संदर्भ के लिए है; विश्लेषण में प्रयुक्त नहीं होती।

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

	node1	node2	trail	distance	color
0	rs_end_north	v_rs	rs	0.30	red
1	v_rs	b_rs	rs	0.21	red
2	b_rs	g_rs	rs	0.11	red
3	g_rs	w_rs	rs	0.18	red
4	w_rs	o_rs	rs	0.21	red
5	o_rs	y_rs	rs	0.12	red
6	y_rs	rs_end_south	rs	0.39	red
7	rc_end_north	v_rc	rc	0.70	red
8	v_rc	b_rc	rc	0.04	red
9	b_rc	g_rc	rc	0.15	red

नोड लिस्ट

जब एज लिस्ट दी जाती है तो networkx और अन्य ग्राफ़ लाइब्रेरियों में नोड लिस्ट प्रायः वैकल्पिक होती है क्योंकि नोड नाम एज लिस्ट की पहली दो कॉलम्स में दिए होते हैं। लेकिन इस मामले में, हम कुछ नोड एट्रिब्यूट्स जोड़ना चाहेंगे: नोड्स (ट्रेल इंटरसेक्शन्स) के X, Y कॉर्डिनेट्स ताकि आप अपने ग्राफ़ को ट्रेल मैप के समान लेआउट में प्लॉट कर सकें।

मैंने इनको GIMP से इमेज पर ट्रेस करके एक दोपहर में मैन्युअली एनोटेट किया:

id: एज लिस्ट में node1 और node2 के अनुरूप नोड का नाम।
X: टॉप-लेफ़्ट के सापेक्ष नोड की क्षैतिज स्थिति/कोऑर्डिनेट।
Y टॉप-लेफ़्ट के सापेक्ष नोड की ऊर्ध्वाधर स्थिति/कोऑर्डिनेट।

नोड और एज लिस्ट बनाने पर टिप्पणी

नोड नाम बनाना भी कुछ मैन्युअल मेहनत का काम था। हर नोड दो या अधिक ट्रेल्स के इंटरसेक्शन को दर्शाता है। जहाँ संभव हो, नोड का नाम trail1_trail2 रखा गया है जहाँ trail1 वर्णानुक्रम में trail2 से पहले आता है।

जब वही ट्रेल्स एक-दूसरे को एक से अधिक बार काटते थे, तो चीजें थोड़ी कठिन हो गईं। उदाहरण के लिए, Orange और White ट्रेल। इन मामलों में, मैंने नोड नाम में _2 या _3 जोड़ा। उदाहरण के लिए, Orange और White के दो अलग-अलग इंटरसेक्शन्स के लिए आपके पास दो अलग नोड नाम हैं: o_w और o_w_2।

यह काम बहुत सारे ट्रायल-एंड-एरर और X,Y कॉर्डिनेट्स से बने प्लॉट्स की वास्तविक ट्रेल मैप से तुलना करते हुए हुआ।

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

	id	X	Y
0	b_bv	1486	732
1	b_bw	716	1357
2	b_end_east	3164	1111
3	b_end_west	141	1938
4	b_g	1725	771

ग्राफ़ बनाएँ

अब आप एज लिस्ट और नोड लिस्ट का उपयोग करके networkx में एक ग्राफ़ ऑब्जेक्ट बनाएँगे।

# Create empty graph
g = nx.Graph()

एज लिस्ट की पंक्तियों पर लूप चलाएँ और हर एज व उसके संबंधित एट्रिब्यूट्स को ग्राफ़ 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())

यहाँ क्या हो रहा है, इसे दर्शाने के लिए, चलिए एज लिस्ट की अंतिम पंक्ति के मान प्रिंट करते हैं जो ग्राफ़ 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}

इसी तरह, आप नोड लिस्ट की पंक्तियों पर लूप चलाकर ये नोड एट्रिब्यूट्स जोड़ते हैं।

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

यहाँ नोड लिस्ट की अंतिम पंक्ति का एक उदाहरण है:

# Node list example
print(nlrow)

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

ग्राफ़ का निरीक्षण

एजेज़

आपके ग्राफ़ के एजेज़ 3 लंबाई के ट्यूपल्स की सूची द्वारा दर्शाए जाते हैं। पहले दो तत्व एज से जुड़े नोड्स के नाम हैं। तीसरा एज एट्रिब्यूट्स की डिक्शनरी है।

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

नोड्स

इसी प्रकार, आपके नोड्स 2 लंबाई के ट्यूपल्स की सूची द्वारा दर्शाए जाते हैं। पहला तत्व नोड ID है, उसके बाद नोड एट्रिब्यूट्स की डिक्शनरी।

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

सार-सांख्यिकी

ग्राफ़ को विज़ुअलाइज़ करने से पहले कुछ सार-सांख्यिकी प्रिंट करें।

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

# of edges: 123
# of nodes: 77

ग्राफ़ का विज़ुअलाइज़ेशन

रंगों और लेआउट में बदलाव

Positions: सबसे पहले आपको ग्राफ़ से नोड पोज़ीशन्स को एक डिक्शनरी में बदलना होगा। इससे आप ग्राफ़ को उसी लेआउट में दोबारा बना सकेंगे जैसा वास्तविक ट्रेल मैप है। Y को नेगेट किया जाता है ताकि Y-अक्ष का ओरिजिन टॉप-लेफ़्ट से बॉटम-लेफ़्ट में बदल जाए।

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

Colors: अब आप ग्राफ़ से एज रंगों को एक सरल सूची में बदलते हैं ताकि ट्रेल्स को उनके रंग से विज़ुअलाइज़ कर सकें।

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

प्लॉट

अब आप एक बढ़िया प्लॉट बना सकते हैं जो 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()

यह ग्राफ़ रिप्रेजेंटेशन स्पष्ट रूप से ट्रेल्स के सभी मोड़ों और वक्रों को कैप्चर नहीं करता, पर चिंता न करें: इन्हें गणना में प्रयुक्त एज distance एट्रिब्यूट में सटीक रूप से कैप्चर किया गया है। यह दृश्य नोड्स (ट्रेल इंटरसेक्शन्स) के बीच की दूरी को सीधे रेखा के रूप में दर्शाता है, जो एक ठीक-ठाक अनुप्रयोग प्रतीत होता है।

CPP अल्गोरिद्म का अवलोकन

ठीक है, तो अब जब आपने कुछ शब्द परिभाषित कर लिए और ग्राफ़ बना लिया, तो इसके माध्यम से सबसे छोटा पाथ कैसे खोजेंगे?

Chinese Postman Problem को हल करना वैचारिक रूप से काफी सरल है:

सभी ऑड डिग्री वाले नोड्स ढूँढें (बहुत आसान)।
(वे सभी ट्रेल इंटरसेक्शन ढूँढें जहाँ उस इंटरसेक्शन को छूने वाले ट्रेल्स की संख्या विषम है)
ग्राफ़ में ऐसे एजेज़ जोड़ें कि सभी ऑड डिग्री नोड्स इवन हो जाएँ। ये जोड़े गए एजेज़ मूल ग्राफ़ के ही डुप्लिकेट होने चाहिए (इस समस्या के लिए मान लें कि कोई शॉर्टकट नहीं लिया जाएगा)। जोड़े गए एजेज़ का योग संभव न्यूनतम दूरी होना चाहिए (कठिन... सटीक रूप से कहें तो NP-hard)।
(सरल शब्दों में, ऐसे रूट पर बैकट्रैकिंग को न्यूनतम करें जो हर ट्रेल को कवर करता है)
एक शुरुआती बिंदु दिए जाने पर, ऑगमेंटेड डेटासेट पर Eulerian tour खोजें (मध्यम रूप से आसान)।
(जब हमें पता चल जाए कि किन ट्रेल्स पर दोबारा जाना होगा, तब वास्तव में शुरुआत से अंत तक रूट की गणना करें)

मान्यताएँ और सरलीकरण

नीचे दी गई मान्यताओं को शिथिल कर हम एक छोटा और अधिक सटीक पाथ बना सकते हैं, लेकिन इससे इस ट्यूटोरियल के दायरे से बाहर की जटिलता बढ़ेगी जो CPP पर केंद्रित है।

मान्यता 1: केवल आवश्यक ट्रेल्स

जैसा कि ऊपर ट्रेल मैप से दिखता है, पार्क की सीमाओं के साथ सड़कें हैं जिनका उपयोग ट्रेल्स को जोड़ने के लिए किया जा सकता है, खासकर रेड ट्रेल्स को। कुछ ट्रेल्स (Horseshoe और बिना मार्किंग वाले) भी हैं जो Giantmaster लॉग के अनुसार आवश्यक नहीं हैं, लेकिन लंबी बैकट्रैकिंग से बचने में मदद कर सकते हैं। वैकल्पिक ट्रेल्स का समावेश वास्तव में CPP का एक स्थापित वैरिएंट है जिसे Rural Postman Problem कहा जाता है। हम इस ट्यूटोरियल में वैकल्पिक ट्रेल्स को अनदेखा करते हैं और केवल आवश्यक ट्रेल्स पर ध्यान केंद्रित करते हैं।

मान्यता 2: Uphill == downhill

CPP यह मानता है कि किसी ट्रेल को चलने की लागत उसकी दूरी के बराबर है, चाहे उसे किसी भी दिशा में चला जाए। हालाँकि, कुछ ट्रेल्स काफ़ी ढलानदार हैं और ऊपर चढ़ते हुए उन्हें चलने में नीचे उतरने की तुलना में अधिक ऊर्जा लगेगी। दूरी और ऊँचाई परिवर्तन दोनों को मिलाने वाला कोई मेट्रिक डायरेक्टेड ग्राफ़ पर CPP के एक एक्सटेंशन में शामिल किया जा सकता है जिसे Windy Postman Problem कहा जाता है।

मान्यता 3: कोई समानांतर एज (ट्रेल) नहीं

हालाँकि संभव है, समानांतर एजेज़ (एक ही दो नोड्स को जोड़ने वाले कई ट्रेल्स) का समावेश गणना में जटिलता जोड़ता है। सौभाग्य से, यहाँ यह केवल दो बार होता है (Blue <=> Red Diamond और Blue <=> Tower Trail)। इसे एज लिस्ट में एक छोटे से हैक से संबोधित किया गया है: हर ट्रेल को कैप्चर करते हुए एजेज़ की विशिष्टता बनाए रखने के लिए डुप्लिकेट नोड्स को _dupe प्रत्यय के साथ शामिल किया गया है। यदि आप अपने ग्राफ़ पर, जहाँ कई समानांतर एजेज़ हों, CPP हल करना चाहते हैं, तो मेरे द्वारा लिखे गए postman_problems पैकेज में CPP का इम्प्लीमेंटेशन समानांतर एजेज़ को अधिक सुरुचिपूर्ण ढंग से मज़बूती से संभालता है।

CPP चरण 1: ऑड डिग्री वाले नोड्स खोजें

यह एक काफ़ी सीधी गिनती की गणना है। आप देखते हैं कि 76 में से 36 नोड्स की डिग्री ऑड है। ये अधिकतर डेड-एंड ट्रेल्स (डिग्री 1) और 3 ट्रेल्स के इंटरसेक्शन्स हैं। कुछ डिग्री 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

CPP चरण 2: न्यूनतम दूरी वाले पेयर्स खोजें

यह वास्तव में समस्या का मूल है। आप इसे 5 भागों में तोड़ेंगे:

ऑड डिग्री नोड्स के सभी संभव पेयर्स की गणना करें।
1. में निकले हर नोड पेयर के बीच का सबसे छोटा पाथ निकालें।
2. में निकाली गई सबसे छोटी पाथ दूरी को एट्रिब्यूट के रूप में जोड़ते हुए 1. के हर नोड पेयर को जोड़कर एक कम्प्लीट ग्राफ़ बनाएँ।
3. में बने ग्राफ़ का मिनिमम वेट मैचिंग निकालें।
(इसका सार यह है कि ऑड नोड्स को ऐसे पेयर करें कि पेयर्स के बीच की दूरी का कुल योग यथासंभव छोटा हो)।
4. में निकाले गए नोड पेयर्स के बीच के सबसे छोटे पाथ के साथ मूल ग्राफ़ को ऑगमेंट करें।

चरण 2.1: नोड पेयर्स की गणना

आप itertools combination फ़ंक्शन का उपयोग करके ऑड डिग्री नोड्स के सभी संभव पेयर्स निकालते हैं। आपका ग्राफ़ अनिर्देशित है, इसलिए क्रम मायने नहीं रखता: उदाहरण के लिए, (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

आइए नीचे दी गई संयोज्य गणना से पक्का कर लें कि पेयर्स की यह संख्या सही है। सौभाग्य से, आपको केवल 630 पेयर्स की चिंता करनी है। इस CPP उदाहरण को हल करने में आपका कंप्यूटेशन समय तुच्छ है (कुछ सेकंड)।

हालाँकि, अगर आपके पास 3,600 ऑड नोड पेयर्स होते, तो ~6.5 मिलियन पेयर्स ऑप्टिमाइज़ करने होते। इनपुट आकार में 100x वृद्धि पर आउटपुट में ~10,000x वृद्धि।

\begin{equation*} \#\;of\;pairs = n\;choose\;r = {n \choose r} = \frac{n!}{r!(n-r)!} = \frac{36!}{2! (36-2)!} = 630 \end{equation*}

चरण 2.2: नोड पेयर्स के बीच के सबसे छोटे पाथ निकालें

यह पहला चरण है जिसमें कुछ वास्तविक गणना शामिल है। सौभाग्य से networkx में Dijkstra के अल्गोरिद्म का सुविधाजनक इम्प्लीमेंटेशन है जो दो नोड्स के बीच का सबसे छोटा पाथ निकालता है। आप इस फ़ंक्शन को ऊपर odd_node_pairs में निकले हर पेयर (सभी 630) पर लागू करते हैं।

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}

चरण 2.3: कम्प्लीट ग्राफ़ बनाएँ

कम्प्लीट ग्राफ़ वह ग्राफ़ है जिसमें हर नोड हर अन्य नोड से एक अद्वितीय एज द्वारा जुड़ा होता है।

यहाँ विकिपीडिया से 7 नोड वाले कम्प्लीट ग्राफ़ का एक बुनियादी उदाहरण है जिसमें 21 (7 में से 2 का चयन) एजेज़ हैं:

जो ग्राफ़ आप नीचे बनाएँगे उसमें 36 नोड्स और 630 एजेज़ होंगे, जिनके संबंधित एज वेट (distance) होंगे।

create_complete_graph इसे निकालने के लिए परिभाषित है। flip_weights पैरामीटर distance को weight एट्रिब्यूट में बदलने के लिए इस्तेमाल होता है, जहाँ छोटे नंबर लंबी दूरी और बड़े नंबर छोटी दूरी को दर्शाते हैं। यह थोड़ा विरोधाभासी लगता है, पर चरण 2.4 के लिए ज़रूरी है जहाँ आप कम्प्लीट ग्राफ़ पर मिनिमम वेट मैचिंग निकालते हैं।

आदर्श रूप से आप सीधे मिनिमम वेट मैचिंग निकालना चाहेंगे, पर NetworkX केवल max_weight_matching फ़ंक्शन इम्प्लीमेंट करता है जो एज वेट को अधिकतम करता है, न्यूनतम नहीं। हम इसे थोड़ा हैक करते हैं: distance एट्रिब्यूट को -1 से गुणा कर नेगेट कर देते हैं और उसे weight मान लेते हैं। इससे दूरी के आधार पर क्रम और स्केल सुरक्षित रहते हैं, बस उलट जाते हैं।

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

दृश्य समर्थन के लिए, नीचे ऑड डिग्री नोड पेयर्स का पूर्ण रूप से जुड़ा ग्राफ़ प्लॉट किया गया है। ध्यान दें कि आप हर नोड के X, Y कॉर्डिनेट्स सुरक्षित रखते हैं, पर एजेज़ आवश्यक रूप से वास्तविक ट्रेल्स का प्रतिनिधित्व नहीं करते। उदाहरण के लिए, इस ग्राफ़ में दो नोड्स एक ही एज से जुड़े हो सकते हैं, लेकिन उनके बीच का सबसे छोटा पाथ इवन डिग्री नोड्स से होकर 5 हॉप्स का हो सकता है (यहाँ नहीं दिखाया गया)।

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

चरण 2.4: मिनिमम वेट मैचिंग निकालें

यह CPP का सबसे जटिल चरण है। आपको ऐसे ऑड डिग्री नोड पेयर्स ढूँढने हैं जिनके बीच की दूरियों का सम्मिलित योग यथासंभव छोटा हो। तो आपकी समस्या के लिए, यह चरण 2.3 में बने ग्राफ़ से 18 इष्टतम एजेज़ (36 ऑड डिग्री नोड्स / 2) चुनने तक सिमटती है।

इस ऑप्टिमाइज़ेशन का इम्प्लीमेंटेशन और सहज समझ इस ट्यूटोरियल के दायरे से बाहर है... जैसे कि 800+ लाइनों का कोड और इस पर अकादमिक साहित्य।

फिर भी, इच्छुक पाठकों के लिए एक त्वरित प्रसंग:

Joris van Rantwijk को बहुत-बहुत धन्यवाद जिन्होंने 2008 में अपने ब्लॉग पर मौलिक इम्प्लीमेंटेशन लिखा। मैं भी इसी तरह समस्या पर जा पहुँचा और वही इरादा था जो Joris का था। Joris की 2008 की पोस्ट से:

चूँकि मुझे maximum weighted matching के कोई Perl इम्प्लीमेंटेशन नहीं मिले, मैंने हल्के में स्वयं कुछ कोड लिखने का निर्णय लिया। पता चला कि मैंने समस्या को कम आंका था, पर जब तक मुझे अपनी गलती का एहसास हुआ, तब तक मैं समस्या के प्रति इतना आसक्त हो चुका था कि हार मानने से इनकार कर दिया।

हालाँकि, मैंने हार मान ली। सौभाग्य से Joris ने नहीं मानी।

यह Maximum Weight Matching तब से NetworkX पैकेज में शामिल और मेंटेन है। इस भारी कोडबेस को मेंटेन रखने वाले GitHub पर 10+ योगदानकर्ताओं को भी धन्यवाद।

यह एक कठिन और गहन गणना है। 1965 में पहला सफलता-प्राप्त परिणाम साबित करता है कि Maximum Matching समस्या बहुपद समय में हल की जा सकती है। Jack Edmonds द्वारा प्रकाशित, शायद अब तक के सबसे सुंदर अकादमिक पेपर शीर्षकों में से एक के साथ: "Paths, trees, and flowers" [1]। तब से इस कार्य पर साहित्य का एक शरीर बना है, जो ऑप्टिमाइज़ेशन प्रक्रिया को बेहतर बनाता है। NetworkX फ़ंक्शन max_weight_matching में इम्प्लीमेंटेड कोड Galil, Zvi (1986) [2] पर आधारित है, जो 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

मैचिंग आउटपुट (odd_matching_dupes) एक डिक्शनरी है। हालाँकि इस मैचिंग में 36 एजेज़ हैं, आपको केवल 18 चाहिए। हर एज-पेयर दो बार आता है (एक बार नोड 1 डिक्शनरी की-के रूप में और दूसरी बार नोड 2 की-के रूप में)।

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

आप इस डिक्शनरी को ट्यूपल्स की सूची में बदलते हैं क्योंकि आपका ग्राफ़ अनिर्देशित है और क्रम मायने नहीं रखता। डुप्लिकेट हटाने पर वे 18 अद्वितीय एज-पेयर्स मिलते हैं जिनका कुल योग संभव न्यूनतम दूरी है।

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

आइए इन पेयर्स को चरण 2.3 में प्लॉट किए गए कम्प्लीट ग्राफ़ पर विज़ुअलाइज़ करें। पहले की तरह, जबकि यहाँ नोड पोज़ीशन्स वास्तविक ग्राफ़ (ट्रेल मैप) को दर्शाते हैं, दिखाए गए एज डिस्टेन्स (नीली रेखाएँ) सीधे रेखा जैसे हैं। एक नोड से दूसरे तक का वास्तविक सबसे छोटा रूट कई एजेज़ से होकर जा सकता है जो मोड़ खाते हैं और दूरी काफ़ी लंबी हो सकती है।

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

यह दिखाने के लिए कि यह मूल ग्राफ़ के साथ कैसे फिट बैठता है, आप वही मिन वेट पेयर्स (नीली रेखाएँ) ट्रेल मैप (फीका) पर प्लॉट करते हैं, कम्प्लीट ग्राफ़ के बजाय। फिर से नोट करें कि नीली रेखाएँ शॉर्टकट (सीधी रेखा जैसी एजेज़, वास्तविक ट्रेल नहीं) दर्शाती हैं। आपको अभी भी चरण 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()

चरण 2.5: मूल ग्राफ़ को ऑगमेंट करें

अब आप मूल ग्राफ़ को चरण 2.4 में निकली मैचिंग के एजेज़ से ऑगमेंट करते हैं। नीचे इसे करने का एक सरल फ़ंक्शन परिभाषित है जो यह भी नोट करता है कि ये नए एजेज़ ऑगमेंटेड ग्राफ़ से आए हैं। आपको इसकी ज़रूरत 3. में पड़ेगी जब आप वास्तव में ग्राफ़ के माध्यम से Eulerian सर्किट बनाएँगे।

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

आइए पक्का करते हैं कि आपके ऑगमेंटेड ग्राफ़ में अपेक्षित संख्या (18) के एजेज़ जुड़ते हैं:

# 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

आइए यह भी जाँचे कि अब हर नोड की डिग्री इवन है:

pd.value_counts(g_aug.degree())

4    54
2    18
6     5
dtype: int64

CPP चरण 3: Eulerian सर्किट निकालें

अब जब आपके पास इवन डिग्री वाला ग्राफ़ है, तो कठिन ऑप्टिमाइज़ेशन का काम ख़त्म हो गया। जैसा कि Euler ने 1736 में Seven Bridges of Königsberg समस्या के साथ प्रसिद्ध रूप से प्रतिपादित किया, यदि सभी नोड्स की डिग्री इवन हो तो ऐसा पाथ मौजूद होता है जो हर एज को ठीक एक बार विजिट करता है। Carl Hierholzer ने 1870 के दशक में इस परिणाम को औपचारिक रूप से सिद्ध किया।

एक ही दूरी के कई Eulerian सर्किट बनाए जा सकते हैं। आप NetworkX के eulerian_circuit फ़ंक्शन से 90% काम हो जाता है। हालाँकि कुछ सीमाएँ हैं।

जो सीमाएँ आप ठीक करेंगे:

ऑगमेंटेड ग्राफ़ में ऐसे एजेज़ हो सकते हैं (और सम्भवतः होंगे) जो मूल ग्राफ़ में मौजूद नहीं थे। सर्किट (बिना शॉर्टकट) पाने के लिए, आपको इन ऑगमेंटेड एजेज़ को उन सबसे छोटे पाथ्स में तोड़ना होगा जो वास्तव में मौजूद एजेज़ से होकर जाते हैं।
eulerian_circuit केवल यह क्रम लौटाता है कि हम प्रत्येक नोड पर किस क्रम में पहुँचते हैं। यह सर्किट पूरा करने के लिए आवश्यक एज एट्रिब्यूट्स नहीं लौटाता। यह ज़रूरी है क्योंकि जब दो नोड्स के बीच कई एजेज़ हों, तब आपको यह ट्रैक रखना होगा कि कौन-से एज पहले ही चल लिए गए हैं।

जो सीमाएँ आप ठीक नहीं करेंगे:

अपनी टाँगों की बचत के लिए, आप Eulerian सर्किट की इस मान्यता को ढीला कर सकते हैं कि शुरुआत और समाप्ति एक ही नोड पर हो। एक Eulerian path (Eulerian सर्किट का सामान्य मामला) भी निकाला जा सकता है यदि ठीक दो नोड्स की डिग्री ऑड हो। इससे थोड़ी बैकट्रैकिंग बच सकती है... बशर्ते आप पार्क के दूसरे छोर से वापसी का इंतज़ाम कर सकें। हालाँकि, इस लेखन के समय, NetworkX Euler Path अल्गोरिद्म उपलब्ध नहीं कराता। eulerian_circuit का कोड बहुत बुरा नहीं है और इस मामले के लिए अपनाया जा सकता है, पर यहाँ हम चीज़ों को सरल ही रखेंगे।

साधारण (Naive) सर्किट

फिर भी, चलिए सरल पर अपूर्ण समाधान से शुरू करते हैं:

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

अपेक्षित रूप से, साधारण Eulerian सर्किट की लंबाई ऑगमेंटेड ग्राफ़ में एजेज़ की संख्या के बराबर है।

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

Length of eulerian circuit: 141

आउटपुट सिर्फ़ ट्यूपल्स की एक सूची है जो नोड पेयर्स का प्रतिनिधित्व करती है। ध्यान दें कि हर पेयर का पहला नोड, पिछले पेयर के दूसरे नोड के समान होता है।

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

सही सर्किट

अब एक फ़ंक्शन परिभाषित करते हैं जो आपको बताता है कि नोड A से नोड B तक पहुँचने के लिए मूल ग्राफ़ में किन ट्रेल्स का उपयोग किया जाए। कोड में भले ही यह विस्तृत दिखता हो, पर तर्क बहुत सरल है। आप साधारण सर्किट, जिसमें ऐसे एजेज़ भी थे जो मूल ग्राफ़ में नहीं थे, को केवल मूल ग्राफ़ के एजेज़ का उपयोग करके Eulerian सर्किट में बदल देते हैं।

आप साधारण Eulerian सर्किट (naive_euler_circuit) के प्रत्येक एज से गुजरते हैं। जहाँ भी आपको कोई ऐसा एज मिलता है जो मूल ग्राफ़ में मौजूद नहीं है, आप उसे उसके नोड्स के बीच के सबसे छोटे पाथ के एजेज़ के क्रम से बदल देते हैं, जो मूल ग्राफ़ में मौजूद हैं।

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

आप सीमा 3 को थोड़ा हैक करते हैं और Eulerian सर्किट को पार्क के सुदूर पूर्वी छोर पर ब्लू ट्रेल (नोड "b_end_east") से शुरू करते हैं। वास्तविक रूप से इस रूट को चलाते समय, आप बस अंतिम दिशा को छोड़ सकते हैं जो वापस लौटती है।

वर्बोज़ प्रिंट स्टेटमेंट्स जोड़े गए हैं ताकि दिख सके कि ऑगमेंटेड ग्राफ़ के उन एजेज़ को, जो मौजूद नहीं हैं, वास्तविक एजेज़ वाले सबसे छोटे पाथ से कैसे बदला जाता है।

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

आप देखते हैं कि Eulerian सर्किट की लंबाई साधारण सर्किट से अधिक है, जो सार्थक है।

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

Length of Eulerian circuit: 158

CPP समाधान निकालें

टेक्स्ट

यहाँ समाधान का टेक्स्ट प्रिंटआउट दिया है:

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

आप जल्दी ही समझ जाते हैं कि अल्गोरिद्म किसी विशेष ट्रेल के प्रति बहुत वफ़ादार नहीं है, बल्कि तेज़ी से एक से दूसरे पर कूदता है। इस दृष्टिकोण का एक एक्सटेंशन ऑब्जेक्टिव फ़ंक्शन में ट्रेल-निष्ठा की धारणा जोड़कर वास्तविक रूप से इस रूट को दौड़ने को और प्रबंधनीय बना सकता है।

सांख्यिकी

आइए अपने समाधान में झाँककर देखें कि यह कितना वाजिब दिखता है।
(इस वर्बोज़ कोड पर अटकना ज़रूरी नहीं, बस प्रिंटेड आउटपुट पर ध्यान दें)

# 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 समाधान का विज़ुअलाइज़ेशन

हालाँकि NetworkX ग्राफ़्स को विज़ुअलाइज़ करने की सुविधा भी देता है, पर इस विभाग में वे काफ़ी विनम्र हैं:

NetworkX ग्राफ़्स को विज़ुअलाइज़ करने के लिए बुनियादी कार्यक्षमता देता है, पर इसका मुख्य लक्ष्य ग्राफ़ विश्लेषण सक्षम करना है न कि ग्राफ़ विज़ुअलाइज़ेशन। भविष्य में, ग्राफ़ विज़ुअलाइज़ेशन कार्यक्षमता NetworkX से हटा दी जा सकती है या केवल ऐड-ऑन पैकेज के रूप में उपलब्ध हो सकती है।

उचित ग्राफ़ विज़ुअलाइज़ेशन कठिन है, और हम प्रबल रूप से अनुशंसा करते हैं कि लोग अपने ग्राफ़्स को उस कार्य के समर्पित टूल्स से विज़ुअलाइज़ करें। प्रमुख उदाहरणों में Cytoscape, Gephi, Graphviz और LaTeX टाइपसेटिंग के लिए PGF/TikZ शामिल हैं।

यह कहते हुए, matplotlib के साथ निर्मित NetworkX ड्रॉइंग फ़ंक्शनलिटी बुनियादी ग्राफ़्स को देखने-परखने और नेत्र-परीक्षण के लिए पर्याप्त शक्तिशाली है, इसलिए इस ट्यूटोरियल के लिए हम NetworkX के draw पर ही टिके रहेंगे।

मैंने अपने Python पैकेज graphviz और dot ग्राफ़ डिस्क्रिप्शन लैंग्वेज का उपयोग कर समाधान का विज़ुअलाइज़ेशन किया है: postman_problems। हालाँकि NetworkX ग्राफ़ स्ट्रक्चर को dot ग्राफ़ में बदलने में कुछ मेहनत लगी, पर इससे विज़ुअलाइज़ेशन्स पर गुणवत्ता और नियंत्रण बढ़ा।

CPP ग्राफ़ बनाएँ

आपका पहला कदम Euler सर्किट में चलने वाले एजेज़ की सूची को प्लॉट-फ्रेंडली एट्रिब्यूट्स वाली एज लिस्ट में बदलना है।

create_cpp_edgelist एक ऐसी एज लिस्ट बनाता है जिसमें कुछ अतिरिक्त एट्रिब्यूट्स होते हैं जिनका आप प्लॉटिंग में उपयोग करेंगे:

sequence: यह रिकॉर्ड करता है कि हम प्रत्येक एज को कब (किस क्रम में) चलते हैं।
visits: यह बस यह संख्या है कि किसी विशेष एज पर हम कितनी बार चलते हैं।

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 एज लिस्ट बनाएँ:

cpp_edgelist = create_cpp_edgelist(euler_circuit)

अपेक्षित रूप से, आपकी एज लिस्ट में मूल ग्राफ़ जितने ही एजेज़ हैं।

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

Number of edges in CPP edge list: 123

CPP एज लिस्ट euler_circuit जैसी दिखती है, बस कुछ अतिरिक्त एट्रिब्यूट्स के साथ।

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

अब ग्राफ़ बनाएँ:

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

विज़ुअलाइज़ेशन 1: दोबारा चले गए कदम

यहाँ आप दिखाते हैं कि कौन-से एजेज़ एक बार (ग्रे) और एक से अधिक बार (नीले) चले गए हैं। यह 2.4 में बनाए गए विज़ुअलाइज़ेशन का "सही" संस्करण है, जिसमें ऑड नोड पेयर्स के बीच की साधारण (सीधी रेखा जैसी) कनेक्शन्स (लाल) दिखाई गई थीं। यहाँ उन्हें सही किया गया है, यानी हर ऑड डिग्री नोड पेयर के लिए वास्तव में मौजूद एजेज़ से होकर जाने वाले सबसे छोटे पाथ का ट्रेस दिखाया गया है।

यदि ऑप्टिमाइज़ेशन अच्छा है, तो ये नीली रेखाएँ संभव न्यूनतम दूरी को दर्शानी चाहिए। विशेष रूप से, ऑड डिग्री नोड्स के मैचिंग को जनरेट करने के लिए आवश्यक न्यूनतम दूरी।

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

विज़ुअलाइज़ेशन 2: CPP समाधान का क्रम

यहाँ आप मूल ग्राफ़ (ट्रेल मैप) को उन क्रमांकित संख्याओं के साथ एनोटेट करके प्लॉट करते हैं जिन क्रम में हम CPP समाधान के अनुसार ट्रेल्स चलते हैं। कई संख्याएँ यह दर्शाती हैं कि हमें कुछ ट्रेल्स पर दोबारा जाना होगा।

आप नीचे-दाएँ ब्लू ट्रेल से शुरू करते हैं (0वाँ और 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()

विज़ुअलाइज़ेशन 3: मूवी

नीचे दी गई मूवी Euler सर्किट को शुरुआत से अंत तक ट्रेस करती है। एजेज़ पहली बार चलते समय काले और दूसरी बार चलते समय लाल रंगे जाते हैं।

ध्यान दें कि यह GIF उन एजेज़ के लिए पूर्ण दृश्य न्याय नहीं कर पाती जो किसी अन्य एज के ऊपर आते हैं या इतने छोटे हैं कि ठीक से विज़ुअलाइज़ न हों। graphviz जैसे अधिक सक्षम विज़ुअलाइज़ेशन लाइब्रेरी नोड्स के बीच सीधी रेखा के बजाय स्प्लाइन्स प्लॉट करके इसे बेहतर कर सकती है।

इसे बनाने वाला कोड संदर्भ के रूप में नीचे दिया गया है।

पहले CPP समाधान के हर निर्देश (चला गया एज) के लिए एक-एक PNG इमेज बनती है।

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

फिर PNG इमेजेस को जोड़कर ऊपर दिखाया गया सुंदर GIF बनाया जाता है।

पहले PNGs को 0 से 157 के क्रम में सॉर्ट किया जाता है। फिर उन्हें imageio का उपयोग करते हुए 3 फ़्रेम प्रति सेकंड पर जोड़कर 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)

अगले कदम

बधाई हो, आपने Python में Chinese Postman Problem हल करते हुए यह ट्यूटोरियल पूरा कर लिया। आपने इस ट्यूटोरियल में काफी ज़मीन कवर की (ठीक-ठीक कहें तो 33.6 मील के ट्रेल्स)। नेटवर्क की गहराई से समझ के लिए, आप Datacamp का Network Analysis in Python कोर्स देख सकते हैं, जो कोर कॉन्सेप्ट्स का अधिक विस्तृत उपचार देता है।

इन जटिल नेटवर्क्स को बनाना, बदलना और पार करना कैसे करें इस पर और जानने के लिए NetworkX डॉक्यूमेंटेशन देखना न भूलें। डॉक्यूमेंट्स व्यापक हैं, जिनमें अच्छी-खासी संख्या में उदाहरण और ट्यूटोरियल्स की श्रृंखला शामिल है।

यदि आप अपने स्वयं के ग्राफ़ पर CPP हल करने में रुचि रखते हैं, तो मैंने इस ट्यूटोरियल की कार्यक्षमता को postman_problems Python पैकेज में पैक किया है (Github पर)। आप इस ट्यूटोरियल के कोड ब्लॉक्स को किसी अन्य एज और नोड लिस्ट के साथ जोड़कर भी काम कर सकते हैं, पर postman_problems पैकेज आपको शायद और तेज़ी व साफ़-सुथरे ढंग से वहाँ पहुँचा देगा।

किसी दिन मैं यहाँ CPP के एक्सटेंशन्स (Rural और Windy Postman Problem) भी इम्प्लीमेंट करने की योजना रखता हूँ। मेरी बड़ी इच्छा है कि मैं इन एक्सटेंशन्स और ट्रेल्स पर रूट्स का परीक्षण करते हुए अपने अनुभवों के बारे में अपने ब्लॉग यहाँ लिखूँ। एक और अनुप्रयोग जिसे मैं तलाशने और लिखने की योजना बना रहा हूँ, वह है lat/long कॉर्डिनेट्स को शामिल कर कोई ऐसा मैकेनिज़्म विकसित (या उपयोग) करना जिससे टर्न-बाय-टर्न निर्देश मेरी Garmin घड़ी पर भेजे जा सकें।

और निश्चित ही एक अंतिम अगला कदम: बाहर निकलना और इस रूट पर ट्रेल रन करना!

यदि आप Python में नेटवर्क्स के बारे में और सीखना चाहते हैं, तो DataCamp के ये कोर्स देखें:

Introduction to Network Analysis in Python

Intermediate Network Analysis in Python

संदर्भ

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.

विषय

Python

डेटा साइंस

डेटा विज़ुअलाइज़ेशन