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

Last change on this file since 547 was 492, checked in by Maciej Komosinski, 8 years ago

emscripten compatibility

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