ग्राफ संरचना को क्रमबद्ध करने के लिए कैसे?

Question

फ्लैट फाइलें और रिलेशनल डेटाबेस हमें संरचित डेटा को क्रमबद्ध करने के लिए एक तंत्र प्रदान करते हैं। एक्सएमएल गैर-संरचित पेड़ की तरह डेटा को क्रमबद्ध करने के लिए शानदार है।

लेकिन कई समस्याओं का सबसे अच्छा ग्राफ द्वारा प्रतिनिधित्व किया जाता है। एक थर्मल सिमुलेशन प्रोग्राम, उदाहरण के लिए, प्रतिरोधी किनारों के माध्यम से एक-दूसरे से जुड़े तापमान नोड्स के साथ काम करेगा।

तो ग्राफ संरचना को क्रमबद्ध करने का सबसे अच्छा तरीका क्या है? मुझे पता है कि एक्सएमएल कुछ हद तक ऐसा कर सकता है --- वैसे ही एक रिलेशनल डेटाबेस ऑब्जेक्ट्स के एक जटिल वेब को क्रमबद्ध कर सकता है: यह आमतौर पर काम करता है लेकिन आसानी से बदसूरत हो सकता है।

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

Answer 1

आप स्मृति में अपने ग्राफ का प्रतिनिधित्व कैसे करते हैं?

• an adjacency list representation
• an adjacency matrix representation

जिसमें निकटता सूची प्रतिनिधित्व सबसे अच्छा एक विरल ग्राफ के लिए इस्तेमाल किया है, और घने रेखांकन के लिए एक मैट्रिक्स प्रतिनिधित्व:
मूल रूप से आप दो (अच्छा) विकल्प हैं ।

यदि आप इस तरह के प्रस्तुतियों का उपयोग करते हैं तो आप इसके बजाय उन प्रस्तुतियों को क्रमबद्ध कर सकते हैं।

यदि यह मानव पठनीय होना है तो भी आप अपना स्वयं का क्रमिकरण एल्गोरिदम बनाने का विकल्प चुन सकते हैं।बस इतनी तरह स्तंभों और पंक्तियों, और सभी डेटा का प्रिंट आउट उस में:

1 2 3 
1 #t #f #f 
2 #f #f #t 
3 #f #t #f 

(यह एक गैर है उदाहरण के लिए आप मैट्रिक्स प्रतिनिधित्व की तरह आप किसी भी "सामान्य" मैट्रिक्स के साथ क्या करना होगा नीचे लिख सकता है अनुकूलित, गैर भारित प्रतिनिधित्व, लेकिन निर्देशित ग्राफ के लिए उपयोग किया जा सकता है)

Answer 2

एक्सएमएल बहुत वर्बोज़ है। जब भी मैं इसे करता हूं, मैं अपना खुद का रोल करता हूं। यहां 3 नोड निर्देशित विश्वकोश ग्राफ का एक उदाहरण दिया गया है। यह बहुत कॉम्पैक्ट है और सब कुछ मैं यह सब करने की ज़रूरत है: CubicTest में हम Xstream (जावा) का उपयोग करने के व एक्सएमएल से परीक्षण क्रमानुसार करने

0: foo 
1: bar 
2: bat 
---- 
0 1 
0 2 
1 2 

Answer 3

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

Answer 4

एक उदाहरण जो आप परिचित हो सकते हैं वह जावा धारावाहिक है। यह ग्राफ द्वारा क्रमशः क्रमबद्ध करता है, प्रत्येक ऑब्जेक्ट उदाहरण नोड होता है, और प्रत्येक संदर्भ किनारे पर होता है। इस्तेमाल किया गया एल्गोरिदम रिकर्सिव है, लेकिन डुप्लिकेट छोड़ रहा है। तो छद्म कोड होगा:

serialize(x): 
    done - a set of serialized objects 
    if(serialized(x, done)) then return 
    otherwise: 
     record properties of x 
     record x as serialized in done 
     for each neighbour/child of x: serialize(child) 

पाठ्यक्रम का एक अन्य तरीका नोड्स और किनारों की एक सूची है, जो XML के रूप में किया जा सकता है, या किसी अन्य वरीय क्रमबद्धता प्रारूप में, या एक निकटता मैट्रिक्स के रूप में के रूप में है।

Answer 5

एक्सएमएल में आम तौर पर संबंध माता-पिता/बाल संबंधों द्वारा दिखाए जाते हैं। एक्सएमएल ग्राफ डेटा को संभाल सकता है लेकिन इस तरह से नहीं। एक्सएमएल में ग्राफ को संभालने के लिए आपको xs:ID और xs:IDREF स्कीमा प्रकारों का उपयोग करना चाहिए।

उदाहरण में, मान लें कि नोड/@ आईडी एक एक्सएस है: आईडी प्रकार और वह लिंक/@ रेफरी एक एक्सएस है: आईडीआरईएफ प्रकार। निम्न XML तीन नोड्स 1 का चक्र चलता -> 2 -> 3 -> 1.

<data> 
    <node id="1"> 
    <link ref="2"/> 
    </node> 
    <node id="2"> 
    <link ref="3"/> 
    </node> 
    <node id="3"> 
    <link ref="1"/> 
    </node> 
</data> 

कई विकास उपकरण आईडी और IDREF भी के लिए समर्थन किया है। मैं जावा के JAXB (जावा बाइंडिंग एक्सएमएल का इस्तेमाल किया है। यह @XmlID और @XmlIDREF एनोटेशन के माध्यम से इन का समर्थन करता है। आप सादे जावा वस्तुओं का उपयोग कर अपने ग्राफ का निर्माण और फिर XML करने के लिए वास्तविक क्रमबद्धता को संभालने के लिए JAXB उपयोग कर सकते हैं।

Answer 6

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

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

vals: [0.3, 0.1, 0.1, 0.5, 0.2, 0.3] 
cols: [2, 3, 0, 0, 1, 4] 
rows: [0,  2, null, 4] 

संपीडित विरल पंक्ति प्रभावी रूप से एक निकटता सूची (स्तंभ सूचकांक समान रूप से कार्य) है, लेकिन प्रारूप ही मैट्रिक्स आपरेशन करने के लिए थोड़ा और सफाई से उधार देता है:

[[0.0, 0.0, 0.3, 0.1] 
[0.1, 0.0, 0.0, 0.0] 
[0.0, 0.0, 0.0, 0.0] 
[0.5, 0.2, 0.0, 0.3]] 

के रूप में प्रतिनिधित्व किया जा सकता है।