如何在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 

該代碼以不停止的方式在循環中運行。我覺得問題是在內循環結束時。如果再次遇到同樣的情況，我該如何跳回內循環的開始？謝謝。

編輯： 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);