पाइथन

Question

के लिए फास्ट मैक्स-फ्लो मिन-कट लाइब्रेरी एल्गोरिदम के कार्यान्वयन के साथ एक विश्वसनीय और अच्छी तरह से प्रलेखित पायथन लाइब्रेरी है जो निर्देशित ग्राफ में अधिकतम प्रवाह और न्यूनतम कटौती पाती है?

pygraph.algorithms.minmax.maximum_flowpython-graph से समस्या हल करती है लेकिन यह दर्दनाक रूप से धीमी है: 4000 नोड्स और 11000 किनारों जैसे कुछ निर्देशित ग्राफ में अधिकतम प्रवाह और न्यूनतम कटौती> 1 मिनट लगती है। मैं ऐसा कुछ ढूंढ रहा हूं जो कम से कम तीव्रता का क्रम है।

बाउंटी: मैं इस प्रश्न पर एक बक्षीस की पेशकश कर रहा हूं कि यह सवाल देखने के बाद स्थिति बदल गई है या नहीं। बोनस पॉइंट्स यदि आपके पास लाइब्रेरी के साथ व्यक्तिगत अनुभव है तो आप अनुशंसा करते हैं!

Answer 1

मैंने इसी तरह के कार्यों के लिए graph-tool का उपयोग किया है।

ग्राफ-टूल ग्राफिक्स (ए.के.ए. नेटवर्क) के हेरफेर और सांख्यिकीय विश्लेषण के लिए एक कुशल पायथन मॉड्यूल है। उनके पास max-flow algorithms के बारे में शानदार दस्तावेज़ीकरण भी है।

वर्तमान में ग्राफ उपकरण दिया समर्थन करता है एल्गोरिदम:

• एडमंड्स-कार्प - एडमंड्स-कार्प एल्गोरिथ्म के साथ ग्राफ पर अधिकतम प्रवाह की गणना।
• पुश रिलाबेल - पुश-रिसाबेल एल्गोरिदम के साथ ग्राफ पर अधिकतम प्रवाह की गणना करें।
• बॉयकोव कोल्मोगोरोव - बॉयकोव-कोल्मोगोरोव एल्गोरिदम के साथ ग्राफ पर अधिकतम प्रवाह की गणना करें।

उदाहरण डॉक्स से लिया: find maxflow using Boykov-Kolmogorov:

>>> g = gt.load_graph("flow-example.xml.gz") #producing example is in doc 
>>> cap = g.edge_properties["cap"] 
>>> src, tgt = g.vertex(0), g.vertex(1) 
>>> res = gt.boykov_kolmogorov_max_flow(g, src, tgt, cap) 
>>> res.a = cap.a - res.a # the actual flow 
>>> max_flow = sum(res[e] for e in tgt.in_edges()) 
>>> print max_flow 
6.92759897841 
>>> pos = g.vertex_properties["pos"] 
>>> gt.graph_draw(g, pos=pos, pin=True, penwidth=res, output="example-kolmogorov.png") 

मैं यादृच्छिक निर्देशित ग्राफ (नोड = 4000, कोने = 23,964) के साथ इस उदाहरण मार डाला, सभी प्रक्रिया अभी 11seconds ले लिया।

विकल्प पुस्तकालयों:

• igraph - मुख्य रूप से सी में लागू है, लेकिन अजगर है और आर इंटरफ़ेस
• Sage wiki में विषय "Python packages for graph theory"
• या अन्य का चयन ग्राफ उपकरण लिंक्ड।

Answer 2

मुझे नहीं पता कि यह तेज़ है या नहीं, आपको इसकी जांच करनी होगी, लेकिन आपने networkx को आजमाया है? ऐसा लगता है कि यह functionality प्रदान करता है जो आप देख रहे हैं और मेरे अनुभव से यह आलेखों को संभालने के लिए लाइब्रेरी का उपयोग करना बहुत आसान है।

Answer 3

वास्तव में अच्छा प्रदर्शन के लिए, आप एक इंटीजर लीनियर प्रोग्राम के रूप में अपनी समस्या को दोबारा सुधारने का प्रयास कर सकते हैं, मानक आईएलपी उपकरण में से कोई भी आपको पर्याप्त प्रदर्शन से अधिक देना चाहिए।

विकिपीडिया में ऐसे वाणिज्यिक और खुले स्रोत tools दोनों की एक अच्छी सूची है, जिनमें से कई में पाइथन बाइंडिंग लगती है। सबसे प्रसिद्ध में CPLEX और lp_solve हैं।

मैंने पिछले कुछ वर्षों में व्यक्तिगत रूप से एलपी_सोल्व को काफी हद तक उपयोग किया है और इसे plain text files के रूप में lp_solve में इनपुट लिखने के लिए पर्याप्त पाया है और खोल का उपयोग करके lp_solve को आमंत्रित किया है। वापस सोचकर, शायद मुझे आधिकारिक पायथन बाइंडिंग को lp_solve काम करने के लिए थोड़ा और प्रयास करना चाहिए था।