Bagaimana menemukan tepi yang terhubung dari daftar tepi di Matlab

Saya memiliki daftar tepi sebagai berikut.

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

Saya ingin memisahkan tepi yang terhubung sebagai berikut.

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

Saya menulis kode berikut di 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

Kode berjalan berulang-ulang tanpa henti. Saya merasa masalahnya ada di akhir loop while bagian dalam. Bagaimana saya bisa melompat kembali ke awal perulangan while bagian dalam jika kondisi yang sama terpenuhi lagi di akhir? Terima kasih.

Sunting: Contoh matriks tepi yang lebih besar.


matlab graph edges connected-components
person Huá dé ní 華得尼    schedule 29.07.2017    source sumber

Jawaban (2)


arrow_upward
1
arrow_downward

Jika Anda tidak mempertimbangkan kasus siklik dan koneksi mundur maka ini seharusnya menjadi masalah yang mudah.

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)
person Mendi Barel    schedule 29.07.2017
comment
Ini berfungsi dengan baik untuk contoh input yang saya posting. Saya mencoba dengan matriks yang lebih besar, akan melampirkannya ke pertanyaan. Itu tidak memisahkan semua tepi yang terhubung dengan benar. Terima kasih. - person Huá dé ní 華得尼; 29.07.2017

arrow_upward
0
arrow_downward

Saya menyelesaikannya termasuk kasus siklik dan koneksi mundur juga. Hanya berpikir untuk memposting demi siapa pun yang tertarik.

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);
person Huá dé ní 華得尼    schedule 13.08.2017