छंटाई बड़ी रेखांकन

Question

मैं एक ग्राफ लगभग 35,000 नोड्स सादे पाठ में प्रतिनिधित्व से मिलकर है:

node1 -> node35000 
node29420 -> node35000 
node2334 -> node4116 
... 

मैं नोड्स है कि एक श्रृंखला का हिस्सा कम से कम नहीं हैं को हटाने के द्वारा इसे नीचे ट्रिम करने के लिए करना चाहते हैं तीन लंबा तो अगर मैं केवल

1 -> 2; 
2 -> 3; 
3 -> 4; 
0 -> 4; 

था मैं रखने के लिए 1, 2, 3, और 4 (के बाद से 1 -> 2 -> 3 -> 4 चार नोड्स लंबा है), लेकिन 0 त्यागें, कि है, को दूर 0 -> 4 चाहते हैं।

ऐसा करने के लिए एक अच्छा तरीका है? मैंने पर्ल और शैल फ़ंक्शंस के संयोजन की कोशिश की लेकिन मुझे लगता है कि मुझे बेहतर दृष्टिकोण चाहिए। जब तक कि यह पहले से ही ऐसा करने के लिए उपकरण नहीं हैं? डेटा ग्राफ़विज़ प्रारूप में है लेकिन मुझे उस कार्य में हाथ से संबंधित उस सूट में कोई भी उपकरण नहीं दिखाई देता है।

ओह, और यदि ऐसा कुछ करने का कोई आसान तरीका है, तो मैं सुझावों के लिए खुला हूं - मुझे बिल्कुल सुझाए गए कार्य की आवश्यकता नहीं है। मैं बस बड़े clumps के आसपास के अधिकांश शोर को हटाने के लिए एक रास्ता तलाश रहा हूँ (जो दुर्लभ हैं और ज्यादातर कुछ छेड़छाड़ श्रृंखला)।

Answer 1

मान लें कि किसी भी नोड मनमाने ढंग से कई पूर्ववर्तियों या उत्तराधिकारियों, तो इन-डिग्री और बाहर डिग्री नोड्स की समस्या को हल करने के लिए अप्रासंगिक है हो सकता है।

के बाद एक सरल हे (एन + ई) एन नोड्स और ई किनारों के सभी रेखांकन के लिए एल्गोरिथ्म, पथ-लंबाई -3 कसौटी के अधीन है। इस एल्गोरिदम को आसानी से पर्ल या सी में कार्यान्वित किया जा सकता है। विधि परिभाषा और एक अनुमान पर आधारित है: किसी "नोड" को किसी भी नोड के रूप में परिभाषित करें जिसमें माता-पिता और बच्चे (पूर्ववर्ती और उत्तराधिकारी) हैं। प्रत्येक नोड जिसे रखा जाएगा वह बनाया गया नोड है या एक नोड का माता-पिता या बच्चा है।

1. एक स्थिति सरणी एस [nmax] सभी शून्यों को प्रमाणित करें। Nmax अधिकतम नोड संख्या है। अगर एनमैक्स को शुरुआत में नहीं जाना जाता है, तो सभी डेटा पढ़ें और इसे ढूंढें।

2. किनारों की दी गई सूची में पढ़ें। प्रत्येक इनपुट आइटम नोड पी से नोड क्यू तक निर्देशित किनारे (पी, क्यू) निर्दिष्ट करता है। प्रत्येक (पी, क्यू) आइटम के लिए जो पढ़ा जाता है: सेट एस [पी] एस [पी] | 1 यह इंगित करने के लिए कि पी में एक बच्चा है, और एस [क्यू] एस को [क्यू] सेट करें 2 यह इंगित करने के लिए कि q के माता-पिता हैं। (इस कदम के बाद, हर बनाया नोड n है एस [n] == 3.)

3. फिर किनारों की सूची पढ़ें। प्रत्येक (पी, क्यू) आइटम के लिए जो पढ़ा जाता है: यदि (एस [पी] == 3) या (एस [क्यू] == 3) आउटपुट एज (पी, क्यू)।

3 के अलावा अन्य पथ लंबाई कश्मीर के लिए इस विधि का विस्तार करने के लिए, स्मृति में बढ़त सूची रखने के लिए, बनाए रखने के एसपी [] और अनुसूचित जाति [] माता पिता चेन और बच्चे चेन, और प्रदर्शन K/2 अतिरिक्त गुजरता की लंबाई के साथ । समय ओ (एन + के * ई) में करना संभव हो सकता है। समस्या यह निर्दिष्ट नहीं करती है कि ग्राफ एक डीएजी (निर्देशित विश्वकोश ग्राफ) है, लेकिन दिया गया उदाहरण एक डीएजी है। के> 3 के लिए, यह एक फर्क पड़ सकता है।

अद्यतन 1 यहाँ एक कश्मीर> 3 एल्गोरिथ्म के एक और अधिक सटीक बयान है, एच [i] पी और एच [i] .q बढ़त #I, और पीसी [जे], सीसी [जे के अंतिम बिंदुओं होने के साथ ] नोड जे के बारे में पूर्ववर्ती और उत्तराधिकारी श्रृंखला की लंबाई होने के नाते। इसके अलावा, किनारों के ई = #; नोड्स के एन = #; और के = वांछित रखने के लिए वांछित न्यूनतम श्रृंखला लंबाई।

1. एच [] सरणी में ई एज डेटा प्रविष्टियां पढ़ें। सभी पीसी [जे], सीसी [जे] प्रविष्टियों को 0

2. i = 1 से ई के लिए, सीसी [एच [i] .p] = 1 और पीसी [एच [i] .q] = 1।

3. जे = 1 से के + 1 के लिए, {i = 1 से ई के लिए, {चलो पी = एच [i] .p और q = एच [i] .q। सीसी सेट करें [पी] = अधिकतम (सीसी [पी], 1 + सीसी [क्यू]) और पीसी [क्यू] = अधिकतम (पीसी [क्यू], 1 + पीसी [पी])। }}

4. i = 1 से ई के लिए, {चलो पी = एच [i] .p और q = एच [i] .q। आउटपुट बढ़त (पी, क्यू) यदि पीसी [p] + सीसी [p] +1> = कश्मीर और पीसी [क्यू] सीसी [क्यू] +1> = लालकृष्ण}

इस विधि बना सकते हैं गलतियों अगर ग्राफ एक डीएजी नहीं है और इसमें छोटे looped पथ शामिल हैं। उदाहरण के लिए, यदि ग्राफ़ किनारों में (1,2) और (2,1) शामिल हैं और कोई अन्य नोड्स 1 या 2 नोड्स से लिंक नहीं है, तो उन किनारों में से कोई भी आउटपुट होना चाहिए; लेकिन हम उन नोड्स के सीसी [] और पीसी [] के लिए के + 2 के साथ समाप्त होते हैं, इसलिए वे आउटपुट प्राप्त करते हैं।

Answer 2

Gephi visualizing और रेखांकन से छेड़छाड़ के लिए एक उत्कृष्ट खुला स्रोत GUI उपकरण है, और आप शायद बात की इस तरह ... हो सकता है कि एक डिग्री फिल्टर करना होगा के लिए वहाँ में फिल्टर के कुछ प्रकार खोजने के लिए सक्षम हो जाएगा: यह होगा उन नोड्स को हटा दें जिनमें केवल एक किनारा है। आप इन-डिग्री, आउट-डिग्री पर भी फ़िल्टर कर सकते हैं, आप पेजरैंक इत्यादि की गणना कर सकते हैं। इसे कुछ वाकई अच्छा आकार/लेबल/रंग विकल्प भी मिला है और ज़ूम इन/आउट करना आसान है।

Answer 3

उपकरण gvpr जो graphviz tools का हिस्सा है, एक ग्राफ को नियम लागू करने और संशोधित ग्राफ आउटपुट करने की अनुमति देता है।

वर्णन से:

यह प्रतियां इनपुट इसके उत्पादन, संभवतः उनके संरचना और गुण बदलने के लिए रेखांकन, नए ग्राफ़ बनाने, ...

ऐसा लगता है आपने निकालना चाहते हैं सभी नोड्स 0 से सहमत हैं और 0.

स्क्रिप्ट nostraynodes.gv का मेरा संस्करण यहां है:

BEGIN {node_t n; int candidates[]; int keepers[];} 
E{ 
    if (tail.indegree == 0 && head.outdegree == 0) 
    { 
    candidates[tail] = 1; 
    candidates[head] = 1; 
    } 
    else if (tail.indegree == 0) 
    { 
    keepers[tail] = 1; 
    } 
    else if (head.outdegree == 0) 
    { 
    keepers[head] = 1; 
    } 
} 

END_G { 
    for (candidates[n]){ 
    if (n in keepers == 0) 
    { 
     delete(NULL, n); 
    } 
    } 
} 

यहाँ स्क्रिप्ट करता है:

1. लूप सभी किनारों एक समय के माध्यम से और पॉप्युलेट दो सूचियों:

   • उम्मीदवारों - नोड्स जो हो सकता है की एक सूची हटाने के लिए, और
   • की pers - नोड्स की एक सूची जो उम्मीदवारों में समाप्त हो सकती है लेकिन इसे हटाया नहीं जाना चाहिए।

   तो किस सूची में जोड़ा जाता है?

   • कोई भी दो, एक दूसरे को जहां पूंछ नोड किसी भी भेजे किनारों और सिर नोड नहीं है किसी भी निवर्तमान किनारों नहीं है से जुड़ा नोड्स, केवल 2 नोड्स की एक श्रृंखला के रूप में है और इसलिए कर रहे हैं उम्मीदवारों होने के लिए नष्ट कर दिया; वह तब तक है जब तक कि एक ही नोड्स 2 नोड्स से अधिक की दूसरी श्रृंखला का हिस्सा न हों:
   • किसी भी आने वाले किनारों के बिना एक पूंछ नोड, लेकिन एक हेड नोड से जुड़ा हुआ जो स्वयं के किनारे किनारे किनारे से बाहर है, रखरखाव है; और किसी भी निवर्तमान किनारों के बिना
   • एक सिर नोड, लेकिन एक पूंछ नोड जो अपने आप में भेजे किनारों है, से जुड़ा भी एक कीपर है।
2. सभी उम्मीदवारोंमें नहीं रखवाले

यह समाधान है हटाएँ नहीं सामान्य और केवल प्रश्न में कहा गया है समस्या के लिए काम करता है, कि केवल जंजीरों कम से कम 3 नोड्स लंबे रखते हुए किया गया है । यह शॉर्ट लूप (एक दूसरे से जुड़े दो नोड्स) को भी हटा नहीं देगा।

आप इस निम्नलिखित लाइन का उपयोग कॉल कर सकते हैं:

gvpr -c -f .\nostraynodes.gv .\graph.dot 

अपने नमूना ग्राफ का उपयोग कर उत्पादन है:

digraph g { 
    1 -> 2; 
    2 -> 3; 
    3 -> 4; 
} 

कृपया ध्यान दें कि यह मेरी पहली gvpr स्क्रिप्ट है - वहाँ शायद बेहतर तरीके हैं इसे लिखने के लिए, और मुझे यकीन नहीं है कि यह 35000 नोड्स को कैसे संभालता है, हालांकि मुझे विश्वास है कि यह एक बड़ा सौदा नहीं होना चाहिए।

---

ग्राफ परिवर्तन का एक सरल उदाहरण के लिए भी Graphviz/Dot - how to mark all leaves in a tree with a distinctive color? देखें।