Distinguish paths starting at different nodes
I have a fooowing graph pf size (i, j) with two types of nodes: i
- number of nodes of type S and j
- number of nodes of type O
i=input('i:');
j=input('j');
B=randi([0 1], i*2,j);
nNodeCol = size(B,2); % nodes of type O
nNodeLine = size(B,1)/2; % nodes of type S
% First the 'O' nodes, then the 'S' nodes:
nodeNames = [cellstr(strcat('O',num2str((1:size(B,2))'))) ; cellstr(strcat('S',num2str((1:size(B,1)/2)')))];
nodeNames{end+1} = 'X';
% 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 'O'node to 'S' 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 'S' node to 'O' 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*
% Creation of the graph:
G = digraph(adj,nodeNames);
v = dfsearch(G,'X');
Now this code will allow me to get results dfsearch
starting from all nodes of type "O" at the same time. My question is this: is there a way to differentiate between the results, I mean distinguish between the “O1” and “O2” results and continue?
source to share
You can make a diagonal block matrix from nNodeCol
copies of the adjacency matrix (corresponding to O1 O2 ...) and a dummy element, so the new plot will have nodes nNodeCol*(nNodeCol+nNodeLine)+1
. Then you can wire the first element of the first block, the second element of the second block ... to the end, dummy, node. When you run a search from a leaf item, you can find all subgraphs that start with items O
.
n =nNodeCol+nNodeLine;
adj = zeros(n); %same as your code
adj(1:nNodeCol, nNodeCol+1:end) = B(1:2:end,:)'; %same as your code
adj(nNodeCol+1:end, 1:nNodeCol) = B(2:2:end,:); %same as your code
adj2= blkdiag(kron(eye(nNodeCol),adj),0); % block diagonal matrix of tha adjacency matrix plus a dummy element added to the end
adj2(end, 1:n+1:nNodeCol*n) = 1; % conncet the dummy element to O1, O2..
G = digraph(adj2);
v = dfsearch(G,nNodeCol*n+1); % start the seach from the end node
v = v(2:end); % exclude the dummy node from the result
categ= cumsum(ismember(v,1:n+1:nNodeCol*n)); % create categories so each subgraph can be distiguished
node_num = mod(v,n); % rescale node numbers to the original ones
categ
is a vector of categories associated with each subgraph.
source to share