File: grSimplifyBranches.m

package info (click to toggle)
octave-matgeom 1.2.4-2
  • links: PTS, VCS
  • area: main
  • in suites: forky, sid, trixie
  • size: 3,584 kB
  • sloc: objc: 469; makefile: 10
file content (175 lines) | stat: -rw-r--r-- 5,918 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
## Copyright (C) 2024 David Legland
## All rights reserved.
## 
## Redistribution and use in source and binary forms, with or without
## modification, are permitted provided that the following conditions are met:
## 
##     1 Redistributions of source code must retain the above copyright notice,
##       this list of conditions and the following disclaimer.
##     2 Redistributions in binary form must reproduce the above copyright
##       notice, this list of conditions and the following disclaimer in the
##       documentation and/or other materials provided with the distribution.
## 
## THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ''AS IS''
## AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
## IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
## ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
## ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
## DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
## SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
## CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
## OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
## OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
## 
## The views and conclusions contained in the software and documentation are
## those of the authors and should not be interpreted as representing official
## policies, either expressed or implied, of the copyright holders.

function varargout = grSimplifyBranches(nodes, edges)
%GRSIMPLIFYBRANCHES Replace branches of a graph by single edges.
%
%   [NODES2 EDGES2] = grSimplifyBranches(NODES, EDGES)
%   renvoie une version simplifiee d'un graphe, en ne gardant que les 
%   points multiples et les aretes reliant les points multiples.

% ------
% Author: David Legland 
% E-mail: david.legland@inrae.fr
% Created: 2003-08-13
% Copyright 2003-2023 INRA - TPV URPOI - BIA IMASTE

Mnodes = [];    % size Nn*2 -> nodes coordinates
Sedges = [];    % size Ne*2 -> indices of nodes
Mpoints = [];   % size Nn*1 -> indices of Multiple points 
                %     in nodes input array

branch = [];    % size Nb*2 (variable)

Nn = 0;
Ne = 0;
Nb = 0;

% look for the first multiple point
p = 1;
while length(find(edges(:,1) == p | edges(:,2) == p)) < 3
    p = p + 1;
end

Mpoints(1) = p;
Mnodes(1, 1:2) = nodes(p, 1:2);
Nn = Nn + 1;

% add the branches of the first multiple point
neighbours = find(edges(:,1)==p | edges(:,2)==p);
for b = 1:length(neighbours)
    Nb = Nb+1;
    edge = edges(neighbours(b),:);
    if edge(1) == p
        branch(Nb, 1:2) = [p edge(2)]; %#ok<AGROW>
    else
        branch(Nb, 1:2) = [p edge(1)]; %#ok<AGROW>
    end
end

% process each branch, until there is no more branch to process.
% b is index of current branch
b = 0;
while b < length(branch)
    b = b+1;
    
    % check if the branch is valid
    if branch(b, 1) == 0
        continue;
    end
    
    % initialize iteration
    pNode = branch(b, 1);
    node = branch(b,2);
    neighbours = find(edges(:,1) == node | edges(:,2) == node);
    
%     disp(sprintf('node %3d (%03d ; %03d) -> %3d (%03d ; %03d)', ... 
%         Mnode, nodes(Mnode, 1), nodes(Mnode, 2), ...
%         node, nodes(node, 1), nodes(node, 2)));
    
    while length(neighbours) < 3
        % look for the next point on the current branch
        next = 0;
        for n = 1:length(neighbours)
            edge = edges(neighbours(n), :);
            if edge(1)~= node && edge(1)~= pNode
                next = edge(1);
                break;
            end
            if edge(2)~= node && edge(2)~= pNode
                next = edge(2);
                break;
            end
        end
        
        pNode = node;
        node = next;
        neighbours = find(edges(:,1) == node | edges(:,2) == node);
    end
    
    % node is now  the next multiple point, and pNode contains the last
    % point of the branch.
    
    % check if the multiple point has already been processed
    index = find(Mpoints==node);
    if ~isempty(index)
        % find the branch starting with node, and with pNode has
        % second point, and set it to [0 0] to avoid it to be 
        % processed again
        %disp('remove branch');
        for b2 = 1:Nb
            if branch(b2, 1) == node && branch(b2, 2) == pNode
                %disp('find branch');
                branch(b2, 1:2) = 0; %#ok<AGROW>
                break;
            end
        end
        
    else
        % add the multiple point to the list of points
        %disp('add point');
        Nn = Nn+1;
        Mnodes(Nn, 1:2) = nodes(node, 1:2); %#ok<AGROW>
        index = Nn;
        Mpoints(Nn) = node; %#ok<AGROW>
        
        % add each neighbour of the new multiple point (but not
        % the neighbour containing pNode) to the list of branches
        for n = 1:length(neighbours)
            edge = edges(neighbours(n), :);
            if edge(1) ~= pNode && edge(2) ~= pNode
                %disp('add a branch');
                Nb = Nb + 1;
                if edge(1) == node
                    branch(Nb, 1:2) = [node edge(2)]; %#ok<AGROW>
                else
                    branch(Nb, 1:2) = [node edge(1)]; %#ok<AGROW>
                end
            end
        end
    end
    
    %disp('add new Edge');
    Ne = Ne + 1;
    Sedges(Ne, 1:2) = [find(Mpoints == branch(b,1)), index]; %#ok<AGROW>
end


% process output depending on how many arguments are needed
if nargout == 1
    out{1} = Mnodes;
    out{2} = Sedges;
    varargout{1} = out;
end

if nargout == 2
    varargout{1} = Mnodes;
    varargout{2} = Sedges;
end

return;