CODEWITHSUNDEEP
matlabmatrixgraph
StamDad
StamDad

Reputation: 135

Regroup paths from nodes in a single tree

I have the following code to generate a graph of size (i,j) with two type of nodes 'S' and 'O'. all the nodes are stored in the cell array nodeNames

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 dfssearch function to get all the paths from a node O1 for example :

v = dfsearch(G,'O1');

The result is a tree of all the nodes reachable from O1 of type 'O' and 'S'. I want to do the following; get a tree regrouping all the paths of the nodes of type 'O' ; for example : if I do dfsearch(G,'O1') , in the moment that an another node of type 'O' (O2 for example) is found , I call the dfssearch for the found node (O2) dfsearch(G,'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.

Upvotes: 2

Views: 39

Answers (1)

beaker
beaker

Reputation: 16811

The trick is to augment your graph with a dummy starting node that has an edge to each of the O nodes. Then you can start your search from the new dummy node and the search will continue for all of the O nodes not previously visited.

...
% 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 taken care of, 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*
...

From here you can create the digraph and run dfsearch:

v = dfsearch(G,'X');

The resulting vertex list will start at X (which can easily be removed) and will contain all of the O nodes.

Note: The first line of each of the code blocks is unchanged from the original code and is only there to give you a reference point as to where to place the new code.

Upvotes: 3

Related Questions