source: git/src/netartic.c @ 36efb03

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

src/: Add more TRANSLATORS comments.

  • Property mode set to 100644
File size: 14.5 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      /* TRANSLATORS: At the end of processing (or if a *SOLVE command is used)
385       * cavern will issue this error if there are any sections of the survey
386       * network which are hanging. */
387      error(/*Survey not all connected to fixed stations*/45);
388      FOR_EACH_STN(stn, stnlist) {
389         /* Anonymous stations must be at the end of a trailing traverse (since
390          * the same anonymous station can't be referred to more than once),
391          * and trailing traverses have been removed at this point.
392          */
393         SVX_ASSERT(!TSTBIT(stn->name->sflags, SFLAGS_ANON));
394         if (stn->name->ident) {
395            if (!fNotAttached) {
396               fNotAttached = fTrue;
397               /* TRANSLATORS: Here "station" is a survey station, not a train
398                * station. */
399               puts(msg(/*The following survey stations are not attached to a fixed point:*/71));
400            }
401            puts(sprint_prefix(stn->name));
402         }
403      }
404      exit(EXIT_FAILURE);
405   }
406
407   {
408      component *comp;
409
410#ifdef DEBUG_ARTIC
411      printf("\nDump of %d components:\n", cComponents);
412#endif
413      for (comp = component_list; comp; comp = comp->next) {
414         node *list = NULL, *listend = NULL;
415         articulation *art;
416#ifdef DEBUG_ARTIC
417         printf("Component:\n");
418#endif
419         SVX_ASSERT(comp->artic);
420         for (art = comp->artic; art; art = art->next) {
421#ifdef DEBUG_ARTIC
422            printf("  Articulation (%p):\n", art->stnlist);
423#endif
424            SVX_ASSERT(art->stnlist);
425            if (listend) {
426               listend->next = art->stnlist;
427               art->stnlist->prev = listend;
428            } else {
429               list = art->stnlist;
430            }
431
432            FOR_EACH_STN(stn, art->stnlist) {
433#ifdef DEBUG_ARTIC
434               printf("    %d %p (", stn->colour, stn);
435               print_prefix(stn->name);
436               printf(")\n");
437#endif
438               listend = stn;
439            }
440         }
441#ifdef DEBUG_ARTIC
442         putnl();
443         FOR_EACH_STN(stn, list) {
444            printf("MX: %c %p (", fixed(stn)?'*':' ', stn);
445            print_prefix(stn->name);
446            printf(")\n");
447         }
448#endif
449         solve_matrix(list);
450#ifdef DEBUG_ARTIC
451         putnl();
452         FOR_EACH_STN(stn, list) {
453            printf("%c %p (", fixed(stn)?'*':' ', stn);
454            print_prefix(stn->name);
455            printf(")\n");
456         }
457#endif
458         listend->next = stnlist;
459         if (stnlist) stnlist->prev = listend;
460         stnlist = list;
461      }
462#ifdef DEBUG_ARTIC
463      printf("done articulating\n");
464#endif
465   }
466
467#ifdef DEBUG_ARTIC
468   /* test articulation */
469   FOR_EACH_STN(stn, stnlist) {
470      int d;
471      int f;
472      if (stn->name->ident && TSTBIT(stn->name->sflags, SFLAGS_FIXED)) {
473         stn->colour = 1;
474      } else {
475         stn->colour = 0;
476      }
477      f = 0;
478      for (d = 0; d < 3; d++) {
479         if (stn->leg[d]) {
480            if (f) {
481               printf("awooga - gap in legs\n");
482            }
483            if (stn->leg[d]->l.reverse & FLAG_ARTICULATION) {
484               if (!(reverse_leg(stn->leg[d])->l.reverse & FLAG_ARTICULATION)) {
485                  printf("awooga - bad articulation (one way art)\n");
486               }
487            } else {
488               if (reverse_leg(stn->leg[d])->l.reverse & FLAG_ARTICULATION) {
489                  printf("awooga - bad articulation (one way art)\n");
490               }
491            }
492         } else {
493            f = 1;
494         }
495      }
496   }
497
498   colour = 2;
499
500   while (1) {
501      int c;
502      int f;
503      do {
504         c = 0;
505         FOR_EACH_STN(stn, stnlist) {
506            int d;
507            f = 0;
508            for (d = 0; d < 3; d++) {
509               if (stn->leg[d]) {
510                  node *stn2 = stn->leg[d]->l.to;
511                  if (f) {
512                     printf("awooga - gap in legs\n");
513                  }
514                  if (stn2->colour) {
515                     if (!(stn->leg[d]->l.reverse & FLAG_ARTICULATION)) {
516                        if (stn->colour == 0) {
517                           stn->colour = stn2->colour;
518                           c++;
519                        }
520                     }
521                  }
522               } else {
523                  f = 1;
524               }
525            }
526         }
527      } while (c);
528
529      /* colour bits */
530      FOR_EACH_STN(stn, stnlist) {
531         if (stn->colour == 0) break;
532      }
533      if (!stn) break; /* all coloured */
534
535      stn->colour = colour++;
536   }
537
538   FOR_EACH_STN(stn, stnlist) {
539      int d;
540      int f;
541      f = 0;
542      for (d = 0; d < 3; d++) {
543         if (stn->leg[d]) {
544            if (f) {
545               printf("awooga - gap in legs\n");
546            }
547#ifdef DEBUG_ARTIC
548            if (stn->leg[d]->l.reverse & FLAG_ARTICULATION) {
549               node *stn2 = stn->leg[d]->l.to;
550               printf("art: %ld %ld [%p] ", stn->colour, stn2->colour, stn);
551               print_prefix(stn->name);
552               printf(" - [%p] ", stn2);
553               print_prefix(stn2->name);
554               printf("\n");
555            }
556#endif
557         } else {
558            f = 1;
559         }
560      }
561   }
562#endif
563   FOR_EACH_STN(stn, stnlist) {
564      SVX_ASSERT(fixed(stn));
565   }
566}
Note: See TracBrowser for help on using the repository browser.