Rearrange paths from nodes in the same tree
I have the following code to create a plot of size (i, j) with two types of nodes 'S' and 'O'. all nodes are stored in a cell arraynodeNames
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 a function dfssearch
to get all paths from node O1 like:
v = dfsearch(G,'O1');
The result is a tree of all nodes accessible from O1 of type "O" and "S". What I want to do is: get a tree regrouped across all paths of nodes of type "O"; eg: if I do dfsearch(G,'O1')
, at the moment when another node of type "O" is found (O2, for example), I call dfssearch on the found node (O2) dfsearch(G,'O2')
and I repeat the following until all nodes are found. I don't do this if the node has already been processed. Is this any way to do it? Thank you.
source to share
The trick is to grow your graph with a dummy start node that has an edge for each of the nodes O
. Then you can start searching from a new node layout and the search will continue for all nodes O
that have not been visited previously.
...
% 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)')))];
% Add new node called 'X' that will be the starting node
nodeNames{end+1} = 'X'
...
Now that you've got the node names, add the new node to the adjacency 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
adj(end+1,end+1) = 0; % add 1 row and 1 column to adj
adj(end, 1:nNodeCol) = 1; % only outgoing edges from X to O*
...
Here you can create a digraph and run dfsearch
:
v = dfsearch(G,'X');
The resulting vertex list will start with X
(which can be easily deleted) and will contain all the nodes O
.
Note. The first line of each of the code blocks is unchanged from the source code and is only intended to give you a link to where to put the new code.
source to share