source: git/src/netartic.c @ 736f7df

line_contentsstereotravis-osx
Last change on this file since 736f7df was 736f7df, checked in by Olly Betts <olly@…>, 5 years ago

lib/extract-msgs.pl,lib/survex.pot,src/: Insert "TRANSLATORS"
comments into source code.

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