source: git/src/netartic.c @ 9fcc81a

RELEASE/1.2debug-cidebug-ci-sanitiserswalls-data
Last change on this file since 9fcc81a was be4d0a0, checked in by Olly Betts <olly@…>, 9 years ago

src/netartic.c,tests/: Fix assertion if we try to identify a hanging
survey by an anonymous station.

  • Property mode set to 100644
File size: 15.0 KB
Line 
1/* netartic.c
2 * Split up network at articulation points
3 * Copyright (C) 1993-2003,2005,2012,2014,2015 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          * However, we may removed a trailing traverse back to an anonymous
394          * station.  FIXME: It's not helpful to fail to point to a station
395          * in such a case - it would be much nicer to look through the list
396          * of trailing traverses in such a case to find a relevant traverse
397          * and then report a station name from there.
398          */
399         /* SVX_ASSERT(!TSTBIT(stn->name->sflags, SFLAGS_ANON)); */
400         if (stn->name->ident) {
401            if (!fNotAttached) {
402               fNotAttached = fTrue;
403               /* TRANSLATORS: Here "station" is a survey station, not a train
404                * station. */
405               puts(msg(/*The following survey stations are not attached to a fixed point:*/71));
406            }
407            puts(sprint_prefix(stn->name));
408         }
409      }
410      exit(EXIT_FAILURE);
411   }
412
413   {
414      component *comp = component_list;
415
416#ifdef DEBUG_ARTIC
417      printf("\nDump of %d components:\n", cComponents);
418#endif
419      while (comp) {
420         node *list = NULL, *listend = NULL;
421         articulation *art;
422         component * old_comp;
423#ifdef DEBUG_ARTIC
424         printf("Component:\n");
425#endif
426         SVX_ASSERT(comp->artic);
427         art = comp->artic;
428         while (art) {
429            articulation * old_art;
430#ifdef DEBUG_ARTIC
431            printf("  Articulation (%p):\n", art->stnlist);
432#endif
433            SVX_ASSERT(art->stnlist);
434            if (listend) {
435               listend->next = art->stnlist;
436               art->stnlist->prev = listend;
437            } else {
438               list = art->stnlist;
439            }
440
441            FOR_EACH_STN(stn, art->stnlist) {
442#ifdef DEBUG_ARTIC
443               printf("    %d %p (", stn->colour, stn);
444               print_prefix(stn->name);
445               printf(")\n");
446#endif
447               listend = stn;
448            }
449            old_art = art;
450            art = art->next;
451            osfree(old_art);
452         }
453#ifdef DEBUG_ARTIC
454         putnl();
455         FOR_EACH_STN(stn, list) {
456            printf("MX: %c %p (", fixed(stn)?'*':' ', stn);
457            print_prefix(stn->name);
458            printf(")\n");
459         }
460#endif
461         solve_matrix(list);
462#ifdef DEBUG_ARTIC
463         putnl();
464         FOR_EACH_STN(stn, list) {
465            printf("%c %p (", fixed(stn)?'*':' ', stn);
466            print_prefix(stn->name);
467            printf(")\n");
468         }
469#endif
470         listend->next = stnlist;
471         if (stnlist) stnlist->prev = listend;
472         stnlist = list;
473
474         old_comp = comp;
475         comp = comp->next;
476         osfree(old_comp);
477      }
478#ifdef DEBUG_ARTIC
479      printf("done articulating\n");
480#endif
481   }
482
483#ifdef DEBUG_ARTIC
484   /* test articulation */
485   FOR_EACH_STN(stn, stnlist) {
486      int d;
487      int f;
488      if (stn->name->ident && TSTBIT(stn->name->sflags, SFLAGS_FIXED)) {
489         stn->colour = 1;
490      } else {
491         stn->colour = 0;
492      }
493      f = 0;
494      for (d = 0; d < 3; d++) {
495         if (stn->leg[d]) {
496            if (f) {
497               printf("awooga - gap in legs\n");
498            }
499            if (stn->leg[d]->l.reverse & FLAG_ARTICULATION) {
500               if (!(reverse_leg(stn->leg[d])->l.reverse & FLAG_ARTICULATION)) {
501                  printf("awooga - bad articulation (one way art)\n");
502               }
503            } else {
504               if (reverse_leg(stn->leg[d])->l.reverse & FLAG_ARTICULATION) {
505                  printf("awooga - bad articulation (one way art)\n");
506               }
507            }
508         } else {
509            f = 1;
510         }
511      }
512   }
513
514   colour = 2;
515
516   while (1) {
517      int c;
518      int f;
519      do {
520         c = 0;
521         FOR_EACH_STN(stn, stnlist) {
522            int d;
523            f = 0;
524            for (d = 0; d < 3; d++) {
525               if (stn->leg[d]) {
526                  node *stn2 = stn->leg[d]->l.to;
527                  if (f) {
528                     printf("awooga - gap in legs\n");
529                  }
530                  if (stn2->colour) {
531                     if (!(stn->leg[d]->l.reverse & FLAG_ARTICULATION)) {
532                        if (stn->colour == 0) {
533                           stn->colour = stn2->colour;
534                           c++;
535                        }
536                     }
537                  }
538               } else {
539                  f = 1;
540               }
541            }
542         }
543      } while (c);
544
545      /* colour bits */
546      FOR_EACH_STN(stn, stnlist) {
547         if (stn->colour == 0) break;
548      }
549      if (!stn) break; /* all coloured */
550
551      stn->colour = colour++;
552   }
553
554   FOR_EACH_STN(stn, stnlist) {
555      int d;
556      int f;
557      f = 0;
558      for (d = 0; d < 3; d++) {
559         if (stn->leg[d]) {
560            if (f) {
561               printf("awooga - gap in legs\n");
562            }
563#ifdef DEBUG_ARTIC
564            if (stn->leg[d]->l.reverse & FLAG_ARTICULATION) {
565               node *stn2 = stn->leg[d]->l.to;
566               printf("art: %ld %ld [%p] ", stn->colour, stn2->colour, stn);
567               print_prefix(stn->name);
568               printf(" - [%p] ", stn2);
569               print_prefix(stn2->name);
570               printf("\n");
571            }
572#endif
573         } else {
574            f = 1;
575         }
576      }
577   }
578#endif
579   FOR_EACH_STN(stn, stnlist) {
580      SVX_ASSERT(fixed(stn));
581   }
582}
Note: See TracBrowser for help on using the repository browser.