CODEWITHSUNDEEP
matlabmatrixgraph
StamDad
StamDad

Reputation: 135

distinguish between paths starting from different nodes

I have the foolowing graph pf size (i,j) with two types of nodes : i is the number of nodes of type S and j is the 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 dfsearch results starting from all nodes of type 'O' simultaneously . My question is the following : Is there any way to distinguish between the results , I mean to distinguish between the results of 'O1' and those of 'O2' and goes on ?

Upvotes: 3

Views: 69

Answers (1)

rahnema1
rahnema1

Reputation: 15867

You can make a block diagonal matrix from nNodeCol copies of the adjacency matrix (corresponding to O1 O2 ...) and a dummy element ,so the new graph will have nNodeCol*(nNodeCol+nNodeLine)+1 nodes. Then you can connect the first element of the first block , second element of the second block... to the end ,dummy, node. Starting the search from the end element all subgraphs starting from O elements can be found.

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 related to each subgraph.

Upvotes: 1

Related Questions