finding paths in a graph

Question

stam dadi 2017-7-11

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/348289-finding-paths-in-a-graph

评论： Christine Tobler 2017-7-12

I have the following code to generate a graph of size (i,j) with two type of nodes 'S' and 'O'

i=input('i:');
j=input('j:');
B=randi([0 1], i*2,j); 
nNodeCol = size(B,2);                            % one node for each column of B
nNodeLine = size(B,1)/2;                         % one node for every two lines of B
% First the column nodes, then the line nodes:
nodeNames = [cellstr(strcat('O',num2str((1:size(B,2))'))) ; cellstr(strcat('S',num2str((1:size(B,1)/2)')))];
% Adjacency matrix adj, adj(i,j)=1 means there is an edge from node#i to node#j:
adj = zeros(nNodeCol+nNodeLine);                 % square matrix which size is the number of nodes
adj(1:nNodeCol, nNodeCol+1:end) = B(1:2:end,:)'; % edge from a column node to a line node is added for all the 1 in the first line of the node in the matrix
adj(nNodeCol+1:end, 1:nNodeCol) = B(2:2:end,:);  % edge from the line node to a column node is added for all the 1 in the second line of the node in the matrix
% Creation of the graph:
G = digraph(adj,nodeNames);

now i use the following to get all the paths from a node O1 for example :

v = dfsearch(G,'O1');

my problem is that I want to get a tree regrouping all the paths of the nodes of type 'O' ; for example : if I search for the paths from a node O1 , in the instant that an another node of type 'O' (O2 for example) is found , I call the dfssearch for the found node (O2) , and I repeat the following untill all the nodes are found ; i dont do that if the node have been already processed Is that any way to do that ? Thanks.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Christine Tobler 2017-7-11

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/348289-finding-paths-in-a-graph#answer_273773

I'm afraid I don't completely understand your question. In the strictest sense, what you describe is already done by dfsearch. However, dfsearch is called recursively whether or not a node is of type 'O': Whenever any successor node is found that has not been visited yet, dfsearch is restarted from that node.

Also, by paths do you mean shortest paths between two 'O' nodes, or any kind of path that connects two nodes of type 'O'?

2 个评论
显示无隐藏无

stam dadi 2017-7-12

In other word , I want to execute dfsearch for every 'O' node in my graph simultanily and then plot the result in a single plot . for example : if my graph has two nodes 'O1' and 'O2' , I want to do dfsearch for both of them in the same time and plot the result with distinguishing betwwen the two results . By path i mean any kind of path .

Christine Tobler 2017-7-12

在 MATLAB Online 中打开

Here's an example of doing dfsearch on node 'O1':

figure;
e = dfsearch(G, 'O1', 'edgetonew');
p = plot(G);
highlight(p, e(:,1), e(:,2), 'EdgeColor', 'red');
highlight(p, 'O1', 'NodeColor', 'red', 'MarkerSize', 6)

The two plots are the result of running the above code using node 'O1' and 'O2'. The graph is constructed by setting i and j to 3 in your code above.

This only highlights those edges that are touched by dfsearch and are pointing to a node that has not been visited yet in the traversal of the tree.

I'm still not sure what outputs you are looking for when trying to run dfsearch from both nodes at the same time. How would the two searches sync up with each other? Would a node that is discovered in one dfsearch be counted as discovered in the other search?

If you could describe what you are looking for as an output for the example graph here, I think that would be very helpful for my understanding.

请先登录，再进行评论。