क्या graph coloring की समस्या के लिए एल्गोरिदम के पोर्टफोलियो के साथ कोई सी ++ (या कोई अन्य भाषा) लाइब्रेरी है?सी ++ ग्राफ वेरटेक्स रंग पुस्तकालय या स्रोत कोड
के पाठ्यक्रम अनुभवहीन लालची शिखर रंग एल्गोरिदम रहे हैं, लेकिन मैं की तरह अधिक दिलचस्प एल्गोरिदम में दिलचस्पी रखता हूँ:
- एल्गोरिदम wiki
- सन्निकटन एल्गोरिदम कि लेने की "सटीक एल्गोरिदम" खंड में वर्णित विशेष ग्राफ गुणों का लाभ जैसे ग्राफ़ planar या unit disk graph है।
- एल्गोरिदम जो ग्राफ़ के fractional coloring को ढूंढते हैं।
वह अंतिम व्यक्ति मेरे लिए विशेष महत्व है।
जो मैंने अभी तक पाया है वह this page पर सूची है, लेकिन इनमें से कोई भी उपर्युक्त एल्गोरिदम नहीं है। इसके अलावा, सबसे अच्छा Joe Culberson's Graph Coloring code है और इसे 90 के उत्तरार्ध में लागू किया गया था, इसलिए दस्तावेजीकृत एपीआई नहीं होने के मामले में बहुत पुराना है (यह नहीं कि यह सवाल क्या है इसके बारे में महत्वपूर्ण है, लेकिन मैंने सोचा कि मैं इसका उल्लेख करूंगा) ।
Koala graph coloring library है जो कि मैं जो खोज रहा हूं उसकी भावना है, लेकिन यदि आप उनके source code को देखते हैं तो यह अभी तक वादे पर नहीं पहुंचा है। यह विकास के शुरुआती चरणों में प्रतीत होता है।
this stackoverflow question में अन्य सामान्य ग्राफ पुस्तकालयों का उल्लेख किया गया है। इनमें शामिल हैं:
मैं नोट करना चाहिए कि मैं बहुत कुछ के लिए Boost Graph Library का उपयोग करें। वास्तव में, यह एक बेवकूफ vertex रंग कार्यान्वयन प्रदान करता है। जो कल्बर्सन का कोड (ऊपर वर्णित) बहुत कुछ करता है।
निम्नलिखित ग्राफ रंग कोड की एक सूची है, मैंने पाया है (और ज्यादातर मामलों में परीक्षण किया गया है) लेकिन वे अभी भी उपरोक्त तीन एल्गोरिदम कक्षाओं के मामले में अधिकतर कम हो जाते हैं।
- GraphCol - दस्तावेज़ीकरण अंग्रेजी में नहीं है, श्वास।
- Planarity - इसमें एक रंगीन एल्गोरिदम होता है जो प्लानर ग्राफ के लिए 5-रंग या बेहतर की गारंटी देता है।
- Graph-Coloring - जो कि कूलबर्सन (उपरोक्त) द्वारा पहले से लागू की गई छोटी संख्या में एल्गोरिदम का पुनः कार्यान्वयन प्रतीत होता है।
मुझे बीजीएल पसंद है, और यह वर्टेक्स रंग के लिए एक एल्गोरिदम प्रदान करता है, लेकिन यह एक बेवकूफ है और जो कूलबेर्सन कोड (प्रश्न में उल्लिखित) बहुत कुछ करता है।इसके अलावा, बीजीएल में निश्चित रूप से तीन "अधिक रोचक" एल्गोरिदम की तरह कुछ भी नहीं है जिसका मैंने उल्लेख किया है कि मैं देख रहा हूं। –