Matlabの

Question

のエッジのリストから、接続されたエッジを見つけるために、どのように私はエッジのリストを持っています。

75 77 
77 78 
78 79 
60 63 
61 65 
65 67 
57 62 
62 64 
67 81 
81 85 

接続エッジを次のように分割したいと思います。

75 60 61 57 
77 63 65 62 
78 67 64 
79 81 
     85 

私はMatlabに次のコードを書いています。

edges = [75 77; 77 78; 78 79; 60 63; 61 65; 65 67; 57 62; 62 64; 67 81; 81 85]; 
visited = zeros(size(edges,1),1); 
cEdges = []; 

cEdgesC = 1; 
cEdges(1,cEdgesC) = edges(1,1); 
cEdges(2,cEdgesC) = edges(1,2); 
visited(1,1) = 1; 
orgR = 1; 
orgC = 2; 

while sum(visited) <= size(visited,1) 
    cEdgesR = nnz(cEdges(:,cEdgesC)); 
    currentVertex = cEdges(cEdgesR,cEdgesC); 
    fprintf('\n%d\t%d',cEdgesR,currentVertex); 

    [foundR,foundC] = find(edges==currentVertex); 
    foundR(foundR==orgR) = []; 
    foundC(foundC==orgC) = []; 

    while isempty(foundR) 
     fmt=repmat('%d ',1,cEdgesR); 
     fprintf('\nLoop found: '); 
     fprintf(fmt,(cEdges(:,cEdgesC))'); 

     cEdgesC = cEdgesC+1; 

     orgR = find(visited==0, 1, 'first'); 
     orgC = 1; 

     cEdges(1,cEdgesC) = edges(orgR,orgC); 
     cEdges(2,cEdgesC) = edges(orgR,orgC+1); 
     visited(orgR,1) = 1; 

     cEdgesR = nnz(cEdges(:,cEdgesC)); 
     currentVertex = cEdges(2,cEdgesC); 
     fprintf('\n%d\t%d',cEdgesR,currentVertex); 

     [foundR,foundC]=find(edges==currentVertex); 
     foundR(foundR==orgR) = []; 
     foundC(foundC==orgC) = []; 

     if isempty(foundR) 
      // What to do here? 
     end 
    end 

    fprintf('\t%d\t%d',foundR,foundC); 
    orgR = foundR; 
    if foundC == 1 
     cEdges(cEdgesR+1,1) = edges(foundR,foundC+1); 
     orgC = foundC+1; 
    else 
     cEdges(cEdgesR+1,1) = edges(foundR,foundC-1); 
     orgC = foundC-1; 
    end 
    visited(foundR,1) = 1; 
end 

コードはループを停止せずに実行されます。問題は内部ループの終わりです。同じ条件が再び終わりに満たされた場合にどのように私は戻って、内側のwhileループの先頭にジャンプすることがあり？ありがとうございました。

編集： Example larger matrix of edges。

Answer 1

あなたは簡単な問題であるべき巡回例とこれよりも後方への接続を考慮していない場合。

edges = [75 77; 77 78; 78 79; 60 63; 61 65; 65 67; 57 62; 62 64; 67 81; 81 85]; 
NumEdges=size(edges,1); 
visited = false(NumEdges,1); 
List=cell(0); 
k=0; 
for i=1:NumEdges 
    if ~visited(i) 
     k=k+1; 
     List{k}=edges(i,1); 
     Idx=i; 
     while ~isempty(Idx) 
      visited(Idx)=true; 
      List{k}(end+1)=edges(Idx,2); 
      Idx=find(edges(:,1)==edges(Idx,2) & ~visited,1); 
     end 
    end 
end 
celldisp(List) 

Answer 2

私は、循環的なケースと後方接続も含めて解決しました。興味がある人のために投稿すると思っています。

edges = [75 77; 77 78; 78 79; 60 63; 61 65; 65 67; 57 62; 62 64; 67 81; 81 85]; 
visited = zeros(size(edges,1),1); 
cEdges = []; 

cEdgesC = 1; 
cEdges(1,cEdgesC) = edges(1,1); 
cEdges(2,cEdgesC) = edges(1,2); 
visited(1,1) = 1; 
orgR = 1; 
orgC = 2; 

cEdgesR = nnz(cEdges(:,cEdgesC)); 
currentVertex = cEdges(cEdgesR,cEdgesC); 

loops = 0; 

while sum(visited) < size(visited,1) 
    i=0; 
    found=0; 
    while i<size(edges,1) 
     i=i+1; 
     if edges(i,1)==currentVertex && visited(i,1)==0 
      cEdgesR = nnz(cEdges(:,cEdgesC)); 
      cEdges(cEdgesR,cEdgesC)=edges(i,1); 
      cEdges(cEdgesR+1,cEdgesC)=edges(i,2); 
      currentVertex = cEdges(cEdgesR+1,cEdgesC); 
      visited(i,1)=1; 
      i=0; 
      found=1; 
     elseif edges(i,2)==currentVertex && visited(i,1)==0 
      cEdgesR = nnz(cEdges(:,cEdgesC)); 
      cEdges(cEdgesR,cEdgesC)=edges(i,2); 
      cEdges(cEdgesR+1,cEdgesC)=edges(i,1); 
      currentVertex = cEdges(cEdgesR+1,cEdgesC); 
      visited(i,1)=1; 
      i=0; 
      found=1; 
     end 
    end 
    if found==0 
     fprintf('\nloop: '); 
     loops = loops+1; 
     loopVs = nnz(cEdges(:,loops)); 
     for j=1:loopVs 
      fprintf('\t%d',cEdges(j,loops)); 
     end 
     cEdgesT = cEdges.'; 
     cEdgesC = nnz(cEdgesT(:,1))+1; 
     cEdgesR = 1; 
     nextEi = find(visited==0, 1, 'first'); 
     cEdges(1,cEdgesC) = edges(nextEi,1); 
     cEdges(2,cEdgesC) = edges(nextEi,2); 
     visited(nextEi,1) = 1; 
     currentVertex = cEdges(2,cEdgesC); 
    end 
end 

fprintf('\nno. of loops = %d',loops);