ग्राफ़

Question

में प्रत्येक नोड के लिए दूरी एन पर अवांछित नोड्स की गणना करना एक बड़े ग्राफ में प्रत्येक बिंदु के लिए मैं एक सूची बनाने की कोशिश कर रहा हूं जिसमें शुरुआती नोड से दूरी n पर अवांछित नोड्स की संख्या शामिल है। एक उदाहरण उत्पादन होता है: [1,3,6] जिसका अर्थ दूरी 0 पर शुरू नोड ही नहीं है, दूरी 1 में 3 नए (बेरोज़गार) नोड्स देखते हैं कि, आदि

आप केवल एक प्रारंभिक बिंदु है, तो यह काफी है आसान: आप केवल चौड़ाई की पहली खोज के शीर्ष पर एक शेल काउंटर बढ़ाते हैं। समस्या तब शुरू होती है जब मुझे अपने ग्राफ में प्रत्येक नोड के लिए ऐसा करना होता है। क्योंकि मेरा ग्राफ बड़ा है (> 100000 नोड्स), यह प्रत्येक बिंदु के लिए उपर्युक्त दिनचर्या करने में धीमा हो जाता है।

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

मेरा प्रश्न: क्या आपको पता है कि आपको प्रत्येक नोड के लिए ऐसा करना होगा?

Answer 1

ऐसा लगता है कि O(n*|V|^2) से कम में कोई समाधान है, इसलिए यहां पाइथन में एक दृष्टिकोण है जो बहुत भयानक नहीं लगता है।

# some basic topologies 
def lineE(N): 
    return(set((i,i+1) for i in range(N-1))) 

def ringE(N): 
    return(lineE(N).union([(0,N-1)])) 

def fullE(N): 
    return(set([(i,j) for i in range(N) for j in range(i)])) 

# propagate visitors from x to y 
def propagate(V, curr, x, y, d): 
    nexty = set() 
    for cx in curr[x]: 
    if not cx in V[y]["seen"]: 
     V[y]["seen"].add(cx) 
     V[y]["foaf"][d] = V[y]["foaf"].get(d,0) + 1 
     nexty.add(cx) 
    return(nexty) 

# run for D iterations 
def mingle(N, E, D): 
    V = dict((i, {"seen":set([i]), "foaf":{0:1}}) for i in range(N)) 
    curr = dict((i, set([i])) for i in range(N)) 
    for d in range(1, min(D+1, N)): 
    next = dict((i, set()) for i in range(N)) 
    for (h, t) in E: 
     next[t] = next[t].union(propagate(V, curr, h, t, d)) 
     next[h] = next[h].union(propagate(V, curr, t, h, d)) 
    curr = next 
    return(V) 

इसे आज़माना 10 नोड्स और दूरी 3 के साथ,

N=10 
D=3 
for (topology, E) in [("line", lineE(N)), ("ring", ringE(N)), ("full", fullE(N))]: 
    V = mingle(N, E, D) 
    print "\n", topology 
    for v in V: 
    print v, V[v]["foaf"] 

हम

line 
0 {0: 1, 1: 1, 2: 1, 3: 1} 
1 {0: 1, 1: 2, 2: 1, 3: 1} 
2 {0: 1, 1: 2, 2: 2, 3: 1} 
3 {0: 1, 1: 2, 2: 2, 3: 2} 
4 {0: 1, 1: 2, 2: 2, 3: 2} 
5 {0: 1, 1: 2, 2: 2, 3: 2} 
6 {0: 1, 1: 2, 2: 2, 3: 2} 
7 {0: 1, 1: 2, 2: 2, 3: 1} 
8 {0: 1, 1: 2, 2: 1, 3: 1} 
9 {0: 1, 1: 1, 2: 1, 3: 1} 

ring 
0 {0: 1, 1: 2, 2: 2, 3: 2} 
1 {0: 1, 1: 2, 2: 2, 3: 2} 
2 {0: 1, 1: 2, 2: 2, 3: 2} 
3 {0: 1, 1: 2, 2: 2, 3: 2} 
4 {0: 1, 1: 2, 2: 2, 3: 2} 
5 {0: 1, 1: 2, 2: 2, 3: 2} 
6 {0: 1, 1: 2, 2: 2, 3: 2} 
7 {0: 1, 1: 2, 2: 2, 3: 2} 
8 {0: 1, 1: 2, 2: 2, 3: 2} 
9 {0: 1, 1: 2, 2: 2, 3: 2} 

full 
0 {0: 1, 1: 9} 
1 {0: 1, 1: 9} 
2 {0: 1, 1: 9} 
3 {0: 1, 1: 9} 
4 {0: 1, 1: 9} 
5 {0: 1, 1: 9} 
6 {0: 1, 1: 9} 
7 {0: 1, 1: 9} 
8 {0: 1, 1: 9} 
9 {0: 1, 1: 9} 

जो सही लगता है मिलता है। साथ ही, 100000 नोड्स के साथ दूरी 100 के लिए सरल टोपोलॉजी चलाने से मेरे लैपटॉप पर लगभग एक मिनट लगते हैं। बेशक यदि आपके पास घना ग्राफ है (जैसे fullE) यह उड़ाएगा।

N=100000 
D=100 
for (topology, E) in [("line", lineE(N)), ("ring", ringE(N))]: 
    V = mingle(N, E, D)