単一ツリー内のノードからのパスを再編成する

Question

2つのタイプのノード「S」と「O」を持つサイズ（i、j）のグラフを生成するために、次のコードがあります。

v = dfsearch(G,'O1'); 

結果は、すべてのノードのツリーである：すべてのノードについて、iは、例えばノードO1からのすべてのパスを取得するdfssearch関数を使用するセルアレイ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); 

に格納されていますタイプ 'O'と 'S'のO1から到達可能です。 私は次のことをしたい。タイプ 'O'のノードのすべてのパスを再グループ化するツリーを取得します。たとえば、私がdfsearch(G,'O1')を実行すると、タイプ 'O'（たとえばO2）の別のノードが見つかった時点で、見つかったノード（O2）dfsearch(G,'O2')のdfssearchを呼び出し、すべてのノードまでが見つかりました。ノードがすでに処理されている場合、私はそれをしません。それはどんな方法でもできますか？おかげさまで

Answer 1

このトリックは、Oノードのそれぞれにエッジを持つダミーの開始ノードを使用してグラフを拡大することです。その後、新しいダミーノードから検索を開始することができ、以前には訪れていないOノードのすべてに対して検索が続行されます。

... 
% 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' 
... 

今、あなたが世話をノード名を持っていること、隣接行列に新しいノードを追加します。あなたは有向グラフを作成し、dfsearchを実行することができますここから

... 
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* 
... 

：

v = dfsearch(G,'X'); 

結果の頂点リストはX（簡単に削除できます）から始まり、Oノードがすべて含まれます。

---

注：コードブロックのそれぞれの最初の行は、元のコードから変更されていませんし、新しいコードを配置する場所へとあなたの基準点を与えるしかありません。