source: git/src/netartic.c @ ecbc6c18

RELEASE/1.1RELEASE/1.2debug-cidebug-ci-sanitisersstereowalls-data
Last change on this file since ecbc6c18 was ecbc6c18, checked in by Olly Betts <olly@…>, 14 years ago

src/: Update FSF address in licence notices.

git-svn-id: file:///home/survex-svn/survex/branches/survex-1_1@3417 4b37db11-9a0c-4f06-9ece-9ab7cdaee568

  • Property mode set to 100644
File size: 13.6 KB
Line 
1/* netartic.c
2 * Split up network at articulation points
3 * Copyright (C) 1993-2003,2005 Olly Betts
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18 */
19
20#if 0
21# define DEBUG_INVALID 1
22# define DEBUG_ARTIC
23#endif
24
25#ifdef HAVE_CONFIG_H
26# include <config.h>
27#endif
28
29#include "debug.h"
30#include "cavern.h"
31#include "filename.h"
32#include "message.h"
33#include "netartic.h"
34#include "netbits.h"
35#include "matrix.h"
36#include "out.h"
37
38/* We want to split station list into a list of components, each of which
39 * consists of a list of "articulations" - the first has all the fixed points
40 * in that component, and the others attach sequentially to produce the whole
41 * component
42 */
43
44typedef struct articulation {
45   struct articulation *next;
46   node *stnlist;
47} articulation;
48
49typedef struct component {
50   struct component *next;
51   articulation *artic;
52} component;
53
54static component *component_list;
55
56static articulation *articulation_list;
57
58static node *artlist;
59
60static node *fixedlist;
61
62static long colour;
63
64/* The goto iter/uniter avoids using recursion which could lead to stack
65 * overflow.  Instead we use 5 bytes of memory per iteration in malloc-ed
66 * blocks which will probably use an awful lot less memory on most platforms.
67 */
68
69/* This is the number of station in stnlist which is a ceiling on how
70 * deep visit will recurse */
71static unsigned long cMaxVisits;
72
73static unsigned char *dirn_stack = NULL;
74static long *min_stack = NULL;
75
76static unsigned long
77visit(node *stn, int back)
78{
79   long min_colour;
80   int i;
81   unsigned long tos = 0;
82   SVX_ASSERT(dirn_stack && min_stack);
83#ifdef DEBUG_ARTIC
84   printf("visit(%p, %d) called\n", stn, back);
85#endif
86
87iter:
88   min_colour = stn->colour = ++colour;
89#ifdef DEBUG_ARTIC
90   printf("visit: stn [%p] ", stn);
91   print_prefix(stn->name);
92   printf(" set to colour %ld -> min\n", colour);
93#endif
94   for (i = 0; i <= 2 && stn->leg[i]; i++) {
95      if (i != back) {
96         node *to = stn->leg[i]->l.to;
97         long col = to->colour;
98         if (col == 0) {
99            SVX_ASSERT(tos < cMaxVisits);
100            dirn_stack[tos] = back;
101            min_stack[tos] = min_colour;
102            tos++;
103            back = reverse_leg_dirn(stn->leg[i]);
104            stn = to;
105            goto iter;
106uniter:
107            SVX_ASSERT(tos > 0);
108            --tos;
109            i = reverse_leg_dirn(stn->leg[back]);
110            to = stn;
111            stn = to->leg[back]->l.to;
112            back = dirn_stack[tos];
113            if (min_stack[tos] < min_colour) min_colour = min_stack[tos];
114
115#ifdef DEBUG_ARTIC
116            printf("unwind: stn [%p] ", stn);
117            print_prefix(stn->name);
118            printf(" colour %d, min %d, station after %d\n", stn->colour,
119                   min_colour, to->colour);
120            printf("Putting stn ");
121            print_prefix(to->name);
122            printf(" on artlist\n");
123#endif
124            remove_stn_from_list(&stnlist, to);
125            add_stn_to_list(&artlist, to);
126
127            if (to->colour <= min_colour) {
128               articulation *art;
129
130               min_colour = to->colour;
131
132               /* FIXME: note down leg (<-), remove and replace:
133                *                 /\   /        /\
134                * [fixed point(s)]  *-*  -> [..]  )
135                *                 \/   \        \/
136                *                 stn to
137                */
138               /* flag leg as an articulation for loop error reporting */
139               to->leg[dirn_stack[tos]]->l.reverse |= FLAG_ARTICULATION;
140               stn->leg[i]->l.reverse |= FLAG_ARTICULATION;
141
142               /* start new articulation */
143               art = osnew(articulation);
144               art->stnlist = artlist;
145               art->next = articulation_list;
146               articulation_list = art;
147               artlist = NULL;
148
149#ifdef DEBUG_ARTIC
150               printf("Articulate *-");
151               print_prefix(stn->name);
152               printf("-");
153               print_prefix(to->name);
154               printf("-...\n");
155#endif
156            }
157         } else {
158            /* back edge case */
159            if (col < 0) {
160               /* we've found a fixed point */
161               col = -col;
162               to->colour = col;
163#if 0
164               /* Removing this solves Graham Mullan's problem and makes more
165                * sense since it means we'll recheck this point for further
166                * legs. */
167#ifdef DEBUG_ARTIC
168               printf("Putting FOUND FIXED stn ");
169               print_prefix(to->name);
170               printf(" on artlist\n");
171#endif
172               remove_stn_from_list(&fixedlist, to);
173               add_stn_to_list(&artlist, to);
174#endif
175            }
176
177            if (col < min_colour) min_colour = col;
178         }
179      }
180   }
181
182   SVX_ASSERT(!stn->leg[0] || stn->leg[0]->l.to->colour > 0);
183   SVX_ASSERT(!stn->leg[1] || stn->leg[1]->l.to->colour > 0);
184   SVX_ASSERT(!stn->leg[2] || stn->leg[2]->l.to->colour > 0);
185
186   if (tos > 0) goto uniter;
187
188#ifdef DEBUG_ARTIC
189   printf("Putting stn ");
190   print_prefix(stn->name);
191   printf(" on artlist\n");
192#endif
193   remove_stn_from_list(&stnlist, stn);
194   add_stn_to_list(&artlist, stn);
195   return min_colour;
196}
197
198extern void
199articulate(void)
200{
201   node *stn, *stnStart;
202   int i;
203   long cFixed;
204
205   component_list = NULL;
206   articulation_list = NULL;
207   artlist = NULL;
208   fixedlist = NULL;
209
210   /* find articulation points and components */
211   colour = 0;
212   stnStart = NULL;
213   cMaxVisits = 0;
214   FOR_EACH_STN(stn, stnlist) {
215      if (fixed(stn)) {
216         remove_stn_from_list(&stnlist, stn);
217         add_stn_to_list(&fixedlist, stn);
218         colour++;
219         stn->colour = -colour;
220#ifdef DEBUG_ARTIC
221         printf("Putting stn ");
222         print_prefix(stn->name);
223         printf(" on fixedlist\n");
224#endif
225      } else {
226         cMaxVisits++;
227         stn->colour = 0;
228      }
229   }
230   dirn_stack = osmalloc(cMaxVisits);
231   min_stack = osmalloc(cMaxVisits * sizeof(long));
232
233   /* fixedlist can be NULL here if we've had a *solve followed by survey
234    * which is all hanging. */
235   cFixed = colour;
236   while (fixedlist) {
237      int c;
238      stnStart = fixedlist;
239      stn = stnStart;
240
241      /* see if this is a fresh component - it may not be, we may be
242       * processing the other way from a fixed point cut-line */
243      if (stn->colour < 0) {
244#ifdef DEBUG_ARTIC
245         printf("new component\n");
246#endif
247         stn->colour = -stn->colour; /* fixed points are negative until we colour from them */
248         cComponents++;
249
250         /* FIXME: logic to count components isn't the same as the logic
251          * to start a new one - we should start a new one for a fixed point
252          * cut-line (see below) */
253         if (artlist) {
254             component *comp;
255             articulation *art;
256
257             art = osnew(articulation);
258             art->stnlist = artlist;
259             art->next = articulation_list;
260             articulation_list = art;
261             artlist = NULL;
262
263             comp = osnew(component);
264             comp->next = component_list;
265             comp->artic = articulation_list;
266             component_list = comp;
267             articulation_list = NULL;
268         }
269
270#ifdef DEBUG_ARTIC
271         print_prefix(stn->name);
272         printf(" [%p] is root of component %ld\n", stn, cComponents);
273         printf(" and colour = %d/%d\n", stn->colour, cFixed);
274#endif
275      }
276
277      c = 0;
278      for (i = 0; i <= 2 && stn->leg[i]; i++) {
279         node *stn2 = stn->leg[i]->l.to;
280         if (stn2->colour < 0) {
281            stn2->colour = -stn2->colour;
282         } else if (stn2->colour == 0) {
283            /* Special case to check if start station is an articulation point
284             * which it is iff we have to colour from it in more than one dirn
285             *
286             * We're looking for articulation legs - these are those where
287             * colouring from here doesn't reach a fixed point (including
288             * stn - the fixed point we've started from)
289             *
290             * FIXME: this is a "fixed point cut-line" case where we could
291             * start a new component.
292             */
293            long col = visit(stn2, reverse_leg_dirn(stn->leg[i]));
294#ifdef DEBUG_ARTIC
295            print_prefix(stn->name);
296            printf(" -> ");
297            print_prefix(stn2->name);
298            printf(" col %d cFixed %d\n", col, cFixed);
299#endif
300            if (col > cFixed) {
301                /* start new articulation - FIXME - overeager */
302                articulation *art = osnew(articulation);
303                art->stnlist = artlist;
304                art->next = articulation_list;
305                articulation_list = art;
306                artlist = NULL;
307                c |= 1 << i;
308            }
309         }
310      }
311
312      switch (c) {
313       /* had to colour in 2 or 3 directions from start point */
314       case 3: case 5: case 6: case 7:
315#ifdef DEBUG_ARTIC
316         print_prefix(stn->name);
317         printf(" is a special case start articulation point [%d]\n", c);
318#endif
319         for (i = 0; i <= 2 && stn->leg[i]; i++) {
320            if (TSTBIT(c, i)) {
321               /* flag leg as an articulation for loop error reporting */
322               stn->leg[i]->l.reverse |= FLAG_ARTICULATION;
323#ifdef DEBUG_ARTIC
324               print_prefix(stn->leg[i]->l.to->name);
325               putnl();
326#endif
327               reverse_leg(stn->leg[i])->l.reverse |= FLAG_ARTICULATION;
328            }
329         }
330      }
331
332#ifdef DEBUG_ARTIC
333      printf("Putting FIXED stn ");
334      print_prefix(stn->name);
335      printf(" on artlist\n");
336#endif
337      remove_stn_from_list(&fixedlist, stn);
338      add_stn_to_list(&artlist, stn);
339
340      if (stnStart->colour == 1) {
341#ifdef DEBUG_ARTIC
342         printf("%ld components\n",cComponents);
343#endif
344         break;
345      }
346   }
347
348   osfree(dirn_stack);
349   dirn_stack = NULL;
350   osfree(min_stack);
351   min_stack = NULL;
352
353   if (artlist) {
354      articulation *art = osnew(articulation);
355      art->stnlist = artlist;
356      art->next = articulation_list;
357      articulation_list = art;
358      artlist = NULL;
359   }
360   if (articulation_list) {
361      component *comp = osnew(component);
362      comp->next = component_list;
363      comp->artic = articulation_list;
364      component_list = comp;
365      articulation_list = NULL;
366   }
367
368   if (stnlist) {
369      /* Actually this error is fatal, but we want to list the survey
370       * stations which aren't connected, so we report it as an error
371       * and die after listing them...
372       */
373      bool fNotAttached = fFalse;
374      error(/*Survey not all connected to fixed stations*/45);
375      FOR_EACH_STN(stn, stnlist) {
376         if (stn->name->ident) {
377            if (!fNotAttached) {
378               fNotAttached = fTrue;
379               puts(msg(/*The following survey stations are not attached to a fixed point:*/71));
380            }
381            puts(sprint_prefix(stn->name));
382         }
383      }
384      exit(EXIT_FAILURE);
385   }
386
387   {
388      component *comp;
389
390#ifdef DEBUG_ARTIC
391      printf("\nDump of %d components:\n", cComponents);
392#endif
393      for (comp = component_list; comp; comp = comp->next) {
394         node *list = NULL, *listend = NULL;
395         articulation *art;
396#ifdef DEBUG_ARTIC
397         printf("Component:\n");
398#endif
399         SVX_ASSERT(comp->artic);
400         for (art = comp->artic; art; art = art->next) {
401#ifdef DEBUG_ARTIC
402            printf("  Articulation (%p):\n", art->stnlist);
403#endif
404            SVX_ASSERT(art->stnlist);
405            if (listend) {
406               listend->next = art->stnlist;
407               art->stnlist->prev = listend;
408            } else {
409               list = art->stnlist;
410            }
411
412            FOR_EACH_STN(stn, art->stnlist) {
413#ifdef DEBUG_ARTIC
414               printf("    %d %p (", stn->colour, stn);
415               print_prefix(stn->name);
416               printf(")\n");
417#endif
418               listend = stn;
419            }
420         }
421#ifdef DEBUG_ARTIC
422         putnl();
423         FOR_EACH_STN(stn, list) {
424            printf("MX: %c %p (", fixed(stn)?'*':' ', stn);
425            print_prefix(stn->name);
426            printf(")\n");
427         }
428#endif
429         solve_matrix(list);
430#ifdef DEBUG_ARTIC
431         putnl();
432         FOR_EACH_STN(stn, list) {
433            printf("%c %p (", fixed(stn)?'*':' ', stn);
434            print_prefix(stn->name);
435            printf(")\n");
436         }
437#endif
438         listend->next = stnlist;
439         if (stnlist) stnlist->prev = listend;
440         stnlist = list;
441      }
442#ifdef DEBUG_ARTIC
443      printf("done articulating\n");
444#endif
445   }
446
447#ifdef DEBUG_ARTIC
448   /* test articulation */
449   FOR_EACH_STN(stn, stnlist) {
450      int d;
451      int f;
452      if (stn->name->ident && stn->name->sflags & BIT(SFLAGS_FIXED)) {
453         stn->colour = 1;
454      } else {
455         stn->colour = 0;
456      }
457      f = 0;
458      for (d = 0; d < 3; d++) {
459         if (stn->leg[d]) {
460            if (f) {
461               printf("awooga - gap in legs\n");
462            }
463            if (stn->leg[d]->l.reverse & FLAG_ARTICULATION) {
464               if (!(reverse_leg(stn->leg[d])->l.reverse & FLAG_ARTICULATION)) {
465                  printf("awooga - bad articulation (one way art)\n");
466               }
467            } else {
468               if (reverse_leg(stn->leg[d])->l.reverse & FLAG_ARTICULATION) {
469                  printf("awooga - bad articulation (one way art)\n");
470               }
471            }
472         } else {
473            f = 1;
474         }
475      }
476   }
477
478   colour = 2;
479
480   while (1) {
481      int c;
482      int f;
483      do {
484         c = 0;
485         FOR_EACH_STN(stn, stnlist) {
486            int d;
487            f = 0;
488            for (d = 0; d < 3; d++) {
489               if (stn->leg[d]) {
490                  node *stn2 = stn->leg[d]->l.to;
491                  if (f) {
492                     printf("awooga - gap in legs\n");
493                  }
494                  if (stn2->colour) {
495                     if (!(stn->leg[d]->l.reverse & FLAG_ARTICULATION)) {
496                        if (stn->colour == 0) {
497                           stn->colour = stn2->colour;
498                           c++;
499                        }
500                     }
501                  }
502               } else {
503                  f = 1;
504               }
505            }
506         }
507      } while (c);
508
509      /* colour bits */
510      FOR_EACH_STN(stn, stnlist) {
511         if (stn->colour == 0) break;
512      }
513      if (!stn) break; /* all coloured */
514
515      stn->colour = colour++;
516   }
517
518   FOR_EACH_STN(stn, stnlist) {
519      int d;
520      int f;
521      f = 0;
522      for (d = 0; d < 3; d++) {
523         if (stn->leg[d]) {
524            if (f) {
525               printf("awooga - gap in legs\n");
526            }
527#ifdef DEBUG_ARTIC
528            if (stn->leg[d]->l.reverse & FLAG_ARTICULATION) {
529               node *stn2 = stn->leg[d]->l.to;
530               printf("art: %ld %ld [%p] ", stn->colour, stn2->colour, stn);
531               print_prefix(stn->name);
532               printf(" - [%p] ", stn2);
533               print_prefix(stn2->name);
534               printf("\n");
535            }
536#endif
537         } else {
538            f = 1;
539         }
540      }
541   }
542#endif
543   FOR_EACH_STN(stn, stnlist) {
544      SVX_ASSERT(fixed(stn));
545   }
546}
Note: See TracBrowser for help on using the repository browser.