วิธีค้นหา Edge ที่เชื่อมต่อจากรายการ Edge ใน 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