MATLAB Answers

how to do forward neighbor discovery in un-directed graph?

3 views (last 30 days)
Farah Mahmood
Farah Mahmood on 14 Feb 2020
Commented: Christine Tobler on 17 Feb 2020
I have an undirected graph G with 11 nodes and 15 edges. There is a source and destination node and i find neighbors of source node using
n1=neighbors(G,'Source');
next i want to find neighbors of n1 excluding 'Source'. Want to repeat it for neighbors of n1 as well. I only want to select the forward nodes and not the previous ones.

  0 Comments

Sign in to comment.

Answers (1)

Christine Tobler
Christine Tobler on 14 Feb 2020
If I understand correctly, you want to find all nodes that are direct neighbors of n1, then all nodes that connect to n1 through one other node, but aren't n1 or a direct neighbor of n1. In other words, you need all nodes at distance 1 from n1, at distance 2 from n1, and so on.
Simplest is to compute the distances of every node from n1, and to use that vector:
d = distances(G, 'Source', 'all', 'Method', 'unweighted');
directNeighbors = G.Nodes.Name(d == 1); % this is equivalent to neighbors(G, 'Source')
neighborsDistance2 = G.Nodes.Name(d == 2);
neighborsDistance3 = G.Nodes.Name(d == 3);
Note: If G does not have any edge weights (G.Edges has no variable named 'Weight'), you can also use
d = distances(G, 'Source', 'all');
as the 'Method', 'unweighted' option will have no effect in that case.

  2 Comments

Farah Mahmood
Farah Mahmood on 14 Feb 2020
I was looking for something like successors that is used for directed graphs.
Let me rephrase the problem, there is a source node and i use neighbors to find its direct neighbors. then i choose one of those neighbors (lets say n1) and find its direct neighbors other than the source node. I only want to see/display successors of n1.
Christine Tobler
Christine Tobler on 17 Feb 2020
You can use setdiff(successors(G, n1), {'Source'}), which will remove the original source node from the list of successors of n1.

Sign in to comment.


Translated by