समय जागरूक सामाजिक ग्राफ डीएस/प्रश्न

Question

क्लासिक सोशल नेटवर्क को ग्राफ़/मैट्रिक्स के रूप में प्रदर्शित किया जा सकता है। > बी

सामान्य आँकड़े (पारस्परिकता, औसत कनेक्टिविटी, आदि)

आदि -

एक ग्राफ/मैट्रिक्स के साथ

एक आसानी से एक से

2 के बीच
• कम से कम पथ प्रतिभागियों
• गम्यता गणना कर सकता है

क्या कोई आदर्श डेटा संरचना (या ग्राफ/मैट्रिक्स में संशोधन) है जो आसान गणना को सक्षम बनाता है o समय के बारे में जागरूक होने पर उपरोक्त एफ?

उदाहरण के लिए,

इनपुट

t = 0 ... 100

• एक < -> बी (जबकि t = 0 ... 10)
• बी < -> सी (जबकि टी = 5 ... 100)
• सी < -> ए (जबकि टी = 50 ... 100)

नमूना क्वेरीज़

• एक किसी भी समय बी के साथ जुड़े है? (हाँ)
• बी बी से जुड़ा हुआ है जबकि बी सी से जुड़ा हुआ है? (हाँ। @t = 5 ... 10)
• सी कभी एक से पहुंचा जा सकता है (हाँ। @ टी = 5)

Answer 1

क्या आप देख रहे हैं एक स्पष्ट लगातार डेटा संरचना है। इस पर साहित्य का एक उचित निकाय है, लेकिन यह ज्ञात नहीं है। क्रिस ओकासाकी ने इस विषय पर एक बहुत ही महत्वपूर्ण पुस्तक लिखी। this question पर मेरा उत्तर देखें।

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

मुझे लगता है कि संभवतः कम से कम एक प्रकाशन मूल्य के अनगिनत क्षेत्र के लायक है, जिसमें लगातार ग्राफ पर दिलचस्प प्रश्न कैसे करें, यदि अधिक नहीं है।