source: cpp/frams/canvas/nn_smart_layout.cpp @ 135

Last change on this file since 135 was 135, checked in by sz, 8 years ago

neuron layout algorithm (for schematic drawing), usage example in frams/_demos/neuro_layout_test.cpp

  • Property svn:eol-style set to native
File size: 8.3 KB
Line 
1#include "nn_layout.h"
2#include <vector>
3#include "common/nonstd_stl.h"
4
5#define DB(x)
6
7#if DB(1)+0
8#include <assert.h>
9#endif
10
11class block;
12
13/** Information about a single element (neuron). There are N einfo objects in an array called "einfo" */
14struct einfo
15{
16        /** Element's owner */
17        class block *block;
18
19        /** Integer coordinates (neurons are simply placed in a grid, (x,y) is a grid cell) */
20        int x, y;
21};
22
23/** Array[0..N-1] - one einfo for each neuron */
24static struct einfo* einfo;
25
26/** Array[0..N-1] - initially each neuron resides in its own block. The algorithm merges blocks until one single block is created */
27static block **blocks;
28
29/** N = number of neurons */
30static int N;
31
32/** Provides neuron connections information and receives the layout result */
33static NNLayoutState *nn;
34
35static char *JEDEN = (char*)"1";
36
37/** Block is a group of neurons.
38        After "blocking" some neurons, their relative location will not change. */
39class block
40{
41public:
42
43        /** Block's id is its index in the "blocks" array */
44        int id;
45
46        /** Block members (neurons), or actually neuron indexes (0..N-1 ints)  */
47        std::vector<int> elementy;
48
49        /** Block's bounding box (a rectangle containing all elemens)
50                w=maxx-minx+1; h=maxy-miny+1;
51                */
52        int w, h;
53        int minx, miny, maxx, maxy;
54
55        /** 2d array, w*h cells, indicating if a given (x,y) location is taken.
56                This speeds up checking if neurons from two blocks overlap.
57                */
58        char *map;
59
60        /** Creating an initial block consisting of a single neuron */
61        block(int nr) : id(nr), w(1), h(1), minx(0), miny(0), maxx(0), maxy(0)
62        {
63                DB(printf("new block(%d)\n", nr));
64                dodajelement(nr, 0, 0);
65                blocks[id] = this;
66                map = JEDEN;
67        }
68
69        ~block()
70        {
71                DB(printf("~ block(%d)\n", id));
72                blocks[id] = 0;
73                zwolnijmape();
74        }
75
76        void zwolnijmape(void)
77        {
78                if (map)
79                {
80                        if (map != JEDEN) free(map);
81                        map = 0;
82                }
83        }
84
85        void potrzebnamapa(void)
86        {
87                if (map) return;
88                odtworzmape();
89        }
90
91        void odtworzmape(void)
92        {
93                zwolnijmape();
94                w = maxx - minx + 1;
95                h = maxy - miny + 1;
96                map = (char*)calloc(1, w*h);
97                int i, e;
98                DB(printf("mapa bloku #%ld\n", id));
99                for (i = 0; i < elementy.size(); i++)
100                {
101                        e = elementy[i];
102                        map[w*(einfo[e].y - miny) + (einfo[e].x - minx)] = 1;
103                }
104                DB(for (i = 0; i < h; i++){ for (e = 0; e < w; e++)printf("%c", map[w*i + e] ? '*' : '.'); printf("\n"); })
105        }
106
107        /** Add a neuron to a block at location(x,y) */
108        void dodajelement(int nr, int x, int y)
109        {
110                elementy.push_back(nr);
111                einfo[nr].x = x;
112                einfo[nr].y = y;
113                einfo[nr].block = this;
114        }
115};
116
117static int moznadolaczyc(block *b, block *b2, int dx, int dy)
118{
119        /* Check if block b2 can be merged with b with b2 shifted by (dx,dy) so no overlap occurs.
120           All coordinates are relative to b->minx/miny
121           */
122        int x1, y1, x2, y2; // union rectangle
123        x1 = max(0, b2->minx - b->minx + dx);
124        x2 = min(b->maxx - b->minx, -b->minx + dx + b2->maxx);
125        if (x1 > x2) return 1;
126        y1 = max(0, b2->miny - b->miny + dy);
127        y2 = min(b->maxy - b->miny, -b->miny + dy + b2->maxy);
128        if (y1 > y2) return 1;
129        int x, y;
130        dx += b2->minx - b->minx; //dx,dy relative to minx,miny
131        dy += b2->miny - b->miny;
132        b->potrzebnamapa();
133        b2->potrzebnamapa();
134        for (y = y1; y <= y2; y++)
135        {
136                for (x = x1; x <= x2; x++)
137                        if (b->map[b->w*y + x] && b2->map[b2->w*(y - dy) + (x - dx)]) return 0;
138        }
139        return 1;
140}
141
142/** Merge b2 with b shifting b2 by (dx,dy) - adds all b2's neurons to b and deletes b2 */
143static int dolaczblock(block *b, block *b2, int dx, int dy)
144{ // return 1 if successful
145        if (!moznadolaczyc(b, b2, dx, dy)) return 0; // merging causes no collision
146        DB(printf("#%ld(%ld,%ld,%ld,%ld) + #%ld(%ld,%ld,%ld,%ld)<%ld,%ld>", b->id, b->minx, b->miny, b->maxx, b->maxy, b2->id, b2->minx, b2->miny, b2->maxx, b2->maxy, dx, dy));
147
148        b->zwolnijmape();
149        int i, e;
150        for (i = 0; i < b2->elementy.size(); i++)
151        {
152                e = b2->elementy[i];
153                b->dodajelement(e, einfo[e].x + dx, einfo[e].y + dy);
154        }
155        b->minx = min(b->minx, dx + b2->minx);
156        b->miny = min(b->miny, dy + b2->miny);
157        b->maxx = max(b->maxx, dx + b2->maxx);
158        b->maxy = max(b->maxy, dy + b2->maxy);
159
160        DB(printf(" -> (%ld,%ld,%ld,%ld)\n", b->minx, b->miny, b->maxx, b->maxy));
161
162        DB(printf(" ...#%ld...(%ld)...", b->id, b->elementy.size()));
163        for (i = 0; i < b->elementy.size(); i++)
164        {
165                e = b->elementy[i];
166                DB(assert(einfo[e].x >= b->minx);)
167                        DB(assert(einfo[e].x <= b->maxx);)
168                        DB(assert(einfo[e].y >= b->miny);)
169                        DB(assert(einfo[e].y <= b->maxy);)
170                        DB(printf("(%ld)%ld,%ld ", e, einfo[e].x, einfo[e].y));
171        }
172
173        DB(printf("\n"));
174
175        delete b2;
176        return 1;
177}
178
179/** e2 neuron will be connected to e neuron's input:
180        - e and e2 belong to different blocks: shift/merge the blocks so e2 is to the left of e
181        - same block: nothing can be done
182        */
183static void polaczjakowejscie(int e, int e2)
184{
185        block *b, *b2;
186        b = einfo[e].block;
187        if (!einfo[e2].block) new block(e2);
188        b2 = einfo[e2].block;
189        if (b == b2)
190        {
191                DB(printf("--- b==b2 -> cancel\n"));
192                return;
193        }
194        int dx, dy;
195        dx = einfo[e].x - einfo[e2].x;
196        dy = einfo[e].y - einfo[e2].y;
197        DB(printf("  elem.%ld (%ld,%ld@%ld) + elem.%ld (%ld,%ld@%ld)...\n", e, einfo[e].x, einfo[e].y, b->id, e2, einfo[e2].x, einfo[e2].y, b2->id));
198        if (dolaczblock(b, b2, dx - 1, dy)) return;
199        int proba; // retry - increasing the y offset (keeps x offset at -1)
200        for (proba = 1;; proba++)
201        {
202                if (dolaczblock(b, b2, dx - 1, dy - proba)) return;
203                if (dolaczblock(b, b2, dx - 1, dy + proba)) return;
204        }
205}
206
207/** Retrieve the information about neuron e inputs and place the input neurons accordingly
208        unless they are already processed
209        */
210static void ustawelement(int e)
211{
212        if (einfo[e].block)
213        {
214                DB(printf("block#%ld exists\n", e));
215                return;
216        }
217        new block(e);
218        int we;
219        int n = nn->GetInputs(e);
220        for (we = 0; we < n; we++)
221        {
222                int e2 = nn->GetLink(e, we);
223                if (e2 < 0) continue;
224                if (e == e2) continue;
225                ustawelement(e2);
226                polaczjakowejscie(e, e2);
227        }
228}
229
230/**
231   The algorithm:
232   1. Phase one
233    - for each neuron, place its input neurons to the left
234      (at relative location (-1,dy), where dy is any number, ideally 0)
235    - the neuron's location in a block is never changed after the initial assignment
236    - which means that any further connections within a given block are ignored (neurons are already fixed in place)
237    - foreign block connections cause block merges, shifting the blocks so the (-1,dy) condition is met
238      (which also affects all neurons in the other block, since their relative positions are fixed)
239    - the final result is a set of blocks corresponding to the "islands" in the neural network
240   2. Phase two
241    - "islands" are merged into one final block. Any relative offsets can be used, as their neurons
242      are not connected anyway. Here a simple method is used: placing the islands in a vertical stack.
243 */
244void smartlayout(NNLayoutState *nnlayout)
245{
246        DB(printf("\n >>>>>>>>> smartlayout <<<<<<<<<<<\n"));
247        nn = nnlayout;
248        N = nn->GetElements();
249        einfo = (struct einfo*)calloc(N, sizeof(struct einfo));
250        blocks = (class block**)calloc(N, sizeof(class block*));
251
252        int el;
253        for (el = 0; el < N; el++) ustawelement(el);
254
255        DB(printf(" - - merging blocks - -\n"));
256
257        block *first;
258        for (el = 0; el < N; el++) if (blocks[el]) { first = blocks[el]; el++; break; }
259        while (el<N)
260        {
261                if ((first->maxx - first->minx)>(first->maxy - first->miny))
262                {
263                        int y = first->maxy + 2;
264                        int x = first->minx;
265                        int ex = first->maxx;
266                        while (el<N)
267                        {
268                                if (blocks[el])
269                                {
270                                        int dx = blocks[el]->maxx - blocks[el]->minx + 2;
271                                        dolaczblock(first, blocks[el], x - blocks[el]->minx, y - blocks[el]->miny);
272                                        x += dx;
273                                        if (x>ex) break;
274                                }
275                                el++;
276                        }
277                }
278                else
279                {
280                        int x = first->maxx + 2;
281                        int y = first->miny;
282                        int ey = first->maxy;
283                        while (el<N)
284                        {
285                                if (blocks[el])
286                                {
287                                        int dy = blocks[el]->maxy - blocks[el]->miny + 2;
288                                        dolaczblock(first, blocks[el], x - blocks[el]->minx, y - blocks[el]->miny);
289                                        y += dy;
290                                        if (y>ey) break;
291                                }
292                                el++;
293                        }
294                }
295        }
296        /*
297        for (;el<N;el++)
298        if (blocks[el])
299        dolaczblock(first,blocks[el],first->minx-blocks[el]->minx,first->maxy-blocks[el]->miny+1);
300        */
301        if (first) // at this stage we have a single block containing all neurons
302        {
303                DB(printf(" - - setting coordinates - -\n"));
304                int i;
305                DB(first->odtworzmape());
306                for (i = 0; i < first->elementy.size(); i++)
307                {
308                        el = first->elementy[i];
309                        nn->SetXYWH(el, einfo[el].x * 70, -einfo[el].y * 70, 50, 50);
310                }
311                delete first;
312        }
313
314        free(blocks);
315        free(einfo);
316        DB(printf("--------------------------------\n\n"));
317}
Note: See TracBrowser for help on using the repository browser.