Đếm các nút chưa được kích hoạt tại khoảng cách n cho mỗi nút trong biểu đồ

Question

Đối với mỗi điểm trong biểu đồ lớn, tôi đang cố gắng tạo danh sách chứa số nút không được hiển thị ở khoảng cách n từ nút khởi đầu. Một ví dụ đầu ra là: [1,3,6] có nghĩa là ở khoảng cách 0 có nút khởi động riêng của mình, ở khoảng cách 1 có 3 mới (chưa được khám phá) hạch vv

Nếu bạn chỉ có một điểm khởi đầu, điều này là khá dễ dàng: bạn chỉ cần tăng thêm một bộ đếm vỏ trên đầu của một tìm kiếm rộng đầu tiên. Vấn đề bắt đầu khi tôi phải làm điều này cho mỗi nút trong biểu đồ của tôi. Bởi vì đồ thị của tôi là lớn (> 100000 nút), nó trở nên khá chậm để thực hiện thói quen trên cho mọi điểm. Lần đầu tiên tôi cố gắng tối ưu hóa điều này là kiểm tra xem danh sách tại nút a có thể được xây dựng từ danh sách của tất cả những người hàng xóm a hay không, một phần do chu kỳ trong biểu đồ. Tôi hy vọng rằng một số bạn có thể có một số ý tưởng tốt đẹp, có thể liên quan đến một số thông tin bổ sung tôi có thể cache.

Câu hỏi của tôi: có cách nào để tối ưu hóa tìm kiếm như vậy nếu bạn biết rằng bạn sẽ phải làm điều đó cho mỗi nút?

Answer 1

Dường như không có giải pháp nào trong số ít hơn O(n*|V|^2), vì vậy đây là một cách tiếp cận bằng Python có vẻ không quá khủng khiếp.

# 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) 

Đang cố gắng nó ra với 10 nút và khoảng cách 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"] 

chúng tôi nhận

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} 

mà có vẻ đúng. Ngoài ra, việc chạy các cấu trúc liên kết đơn giản cho khoảng cách 100 với 100000 nút mất khoảng một phút trên máy tính xách tay của tôi. Tất nhiên nếu bạn có một đồ thị dày đặc (như fullE) điều này sẽ thổi lên.

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