Biểu đồ: Lấy khoảng cách trắc địa dài nhất

Question

Câu hỏi của tôi là như sau: Xem xét biểu đồ không trực tiếp với 10000 nút và 4800 cạnh. Với đồ thị này và đưa ra một nút của đồ thị này (ví dụ, nút 1), tôi cần một lệnh trong igraph (R) để thu được khoảng cách giữa nút này 1 và nút xa nhất trong biểu đồ. Cảm ơn sự giúp đỡ của bạn! :)

Trân trọng, Ignacio.

Answer 1

Về cơ bản đó là một tìm kiếm/tìm đường.

Giả sử rằng isConnected (a, b) sẽ trả về nếu hai nút được kết nối

(Tôi viết mã trong Lua, nó không phải là khó để dịch)

function search(list) 

local i = 0 

while i < 10000 do 

i = i + 1 

if isConnected(i,list[#list]) then 

--This expression refers to the last member 

search(list ++ i) 

--Although not technically a proper operator, ++ adds the element to the end of the list 

end 

end 


submit_list(list) 
end 

submit_list là một hàm nhận danh sách và kiểm tra chúng. Nó tìm thấy danh sách được gửi dài nhất không chứa bản sao. Danh sách đó sẽ là giải pháp cho vấn đề của bạn.

Ồ, một điều khác; mã của tôi không chiếm một cái gì đó. Trong trường hợp danh sách chứa các nút trùng lặp, chức năng đó sẽ chấm dứt để nó không tái sử dụng vĩnh viễn.

Answer 2

> g <- erdos.renyi.game(100,1/20) 
> s <- c(shortest.paths(g,2)) 
> s 
    [1] 3 2 0 3 3 3 3 3 3 3 3 3 3 2 1 2 3 1 3 3 3 4 2 4 3 2 3 2 2 3 3 2 3 2 4 4 3 
[38] 3 3 2 2 3 3 4 2 3 3 2 2 4 3 2 3 3 2 1 2 4 2 2 2 2 1 2 4 3 2 2 2 4 3 4 3 3 
[75] 3 3 3 3 3 2 1 3 2 4 2 1 3 1 3 3 3 3 4 3 2 3 2 2 3 3 
> which(s == max(s)) 
[1] 22 24 35 36 44 50 58 65 70 72 84 93 
> get.shortest.paths(g,2,21) 
[[1]] 
[1] 2 55 33 50 21 

Hãy làm một đồ thị

g <- erdos.renyi.game(100,1/20) 

này sẽ tìm ra khoảng cách tới đỉnh 2

s <- c(shortest.paths(g,2)) 

Tìm chỉ số của đỉnh xa nhất (s)

which(s == max(s)) 

Hiển thị đường dẫn

get.shortest.paths(g,2,21)