Как найти связанные ребра из списка ребер в Matlab

У меня есть список ребер следующим образом.

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. Как я могу вернуться к началу внутреннего цикла, если в конце снова выполняется одно и то же условие? Спасибо.

Изменить: Пример увеличенной матрицы ребер.


matlab graph edges connected-components
person Huá dé ní 華得尼    schedule 29.07.2017    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Если вы не рассматриваете циклические случаи и обратное соединение, это должно быть легкой проблемой.

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
Он отлично работает для примера ввода, который я опубликовал. Пробовал с большей матрицей, приложу к вопросу. Он не разделяет должным образом все связанные ребра. Спасибо. - person Huá dé ní 華得尼; 29.07.2017

arrow_upward
0
arrow_downward

Я решил это, включая циклические случаи и обратные соединения. Просто решил выложить, кому интересно.

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