您正在关注此问题

您将在关注的内容源中看到更新。
您可能会收到电子邮件，具体取决于您的通信预设项。

Is there more efficient way to find the neighbors of two nodes or more other than using a loop?

2 次查看（过去 30 天）

显示更早的评论

Waseem AL Aqqad 2021-6-17

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop

⋮

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop

编辑： KSSV 2021-6-23

在 MATLAB Online 中打开

The built in function "neighbors" accepts only scalar inputs, so I wonder if there is more efficient way than performing the following

for ii = 1:length(inActive)
    b = neighbors(G_dmg,inActive(ii)); 
end

I usually concatenate the neighbors of all nodes in one variable, but I cannot tell which nodes are neighbors to node X and which are neighbors to node Y.

b = [];
for ii = 1:length(inActive)
    b = [b, neighbors(G_dmg,inActive(ii))];
end

Your ideas would be highly appreciated.

8 个评论
显示 6更早的评论隐藏 6更早的评论

Christine Tobler 2021-6-17

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589660

⋮

链接

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589660

Could you say some more about what your next steps with variable b will be? You'd like to know for each element of b which node it was neighboring - so in which way would that be most convenient to use in the next step?

Also, here b could contain some nodes multiple times, for example if both inActive(1) and inActive(2) have the same node as a neighbor. Would this be a problem for your next steps? You could use unique(b) to remove any duplicates, but that would make it harder to also define which node any element of b was the neighbor of.

Waseem AL Aqqad 2021-6-17

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589685

⋮

链接

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589685

Exactly. This is what I noticed during debugging my code,so I used unique (b) and setdif(b, inActive,'stable').

I designed an algorithm to emulate Load-based faulty graph (Nodes fail when their Loads exceed their capacities), where I assign a -inf to failed nodes' loads without removing their links. Now, I'm trying to design a recovery algorithm, where I want to scan those inactive nodes( have -inf Load) and check if they have active neighbors, if yes, 1. rank them in a descending order, 2. take the average of their loads and 3. assign the value to the inactive node they were neighboring.

I hope this makes sense to you.

Christine Tobler 2021-6-17

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589710

⋮

链接

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589710

在 MATLAB Online 中打开

So something like this?

for ii=1:numnodes(G)
    if isinf(G.Nodes.Load(ii))
        G.Nodes.Load(ii) = mean(G.Nodes.Load(neighbors(G, ii)));
    end
end

With the difference that you want to traverse the nodes not as 1, 2, 3, ..., numnodes(G), but instead start with the node that has most active neighbors (neighbors with non-Inf value)?

That is, if the first node has all active neighbors, its load will become some value that's not Inf. Otherwise, it will stay Inf, since the mean of a set of values that contains Inf is again Inf.

Do I understand this correctly?

Waseem AL Aqqad 2021-6-17

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589755

⋮

链接

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589755

编辑：Waseem AL Aqqad 2021-6-17

>> but instead start with the node that has most active neighbors (neighbors with non-Inf value)?

I want to start with the inactive node(it's Load has negative inf) that it's neighboring nodes are using a high fraction of their capacities, say 99%. and then the inactive node that it's active neighbors using 95% of their capacities and so on until I scan all inactive nodes and see if I can recover them.

>>That is, if the first node has all active neighbors, its load will become some value that's not Inf

Correct. But the line inside the if statement in your code should exclude the neighbors with -ve Inf Loads(inactive nodes), and just take the neighboring nodes with none -ve Inf( have other values, like 800 or 200), that is, active nodes.

Do you think this is a realistic approach/ recovery process?

Thanks

Waseem AL Aqqad 2021-6-17

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589775

⋮

链接

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589775

编辑：Waseem AL Aqqad 2021-6-17

You might be wondering why did I assign negative Inf to the loads of failed nodes. It's basically because in the fault function, I added some disturbance value to the loads of some of the nodes and then compare it to a failure threshold value(capacity). if it is gt this threshold, they fail. And since I don't want my code to count those nodes more than once, I assign negative value to their loads ( whatever disturbance I add to them later, it will stay -ve inf). I'm doing this instead of removing the links of the failed nodes, hence neighbors function might count them more than once.

Christine Tobler 2021-6-17

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589810

⋮

链接

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589810

编辑：Christine Tobler 2021-6-17

在 MATLAB Online 中打开

Ran in:

All right, I think I understand it all. This seems like a realistic approach to me, yes, although I have no knowledge of load-based fault graphs.

To compute the number of neighbors with Inf loads, you can use the following code, which might be faster than a loop over all neighbors:

rng default;

G = graph(rand(5) > 0.3, 'upper', 'omitselfloop');

load = [-Inf; -Inf; 5; -Inf; 9];

p = plot(G);

highlight(p, load ~= -Inf)

A = adjacency(G);

nrActiveNeighbors = A * (load ~= -Inf)

nrActiveNeighbors = 5×1

1 1 1 2 1

nrNeighbors = degree(G)

nrNeighbors = 5×1

1 2 3 3 3

ratioActive = nrActiveNeighbors ./ nrNeighbors

ratioActive = 5×1

1.0000 0.5000 0.3333 0.6667 0.3333

You could then sort by ratioActive and do the above loop using them.

Of course, you could also consider updating the nrActiveNeighbors every time you turn a node back to active, and to then find the maximum of ratioActive given this change. Hard to say which would be better there; after all the original ratioActive is telling us the originally active nodes.

Waseem AL Aqqad 2021-6-17

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589870

⋮

链接

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1589870

编辑：Waseem AL Aqqad 2021-6-17

This is so clever and so fast in providing a solution to my problem. Knock on wood!

Thank you, Christine.

I will let you know what will happen when I update nrActiveNeighbors or when I increase numnodes(G).

Rubel Ahmed 2021-6-23

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1598890

⋮

链接

此评论的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/859025-is-there-more-efficient-way-to-find-the-neighbors-of-two-nodes-or-more-other-than-using-a-loop#comment_1598890