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

Last change on this file since 272 was 247, checked in by Maciej Komosinski, 9 years ago

Sources support both 32-bit and 64-bit, and more compilers

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