src/netartic.c

   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 #include <config.h>
  26
  27 #include "debug.h"
  28 #include "cavern.h"
  29 #include "filename.h"
  30 #include "listpos.h"
  31 #include "message.h"
  32 #include "netartic.h"
  33 #include "netbits.h"
  34 #include "netskel.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
  44 typedef struct articulation {
  45    struct articulation *next;
  46    node *stnlist;
  47 } articulation;
  48
  49 typedef struct component {
  50    struct component *next;
  51    articulation *artic;
  52 } component;
  53
  54 static component *component_list;
  55
  56 static articulation *articulation_list;
  57
  58 static node *artlist;
  59
  60 static node *fixedlist;
  61
  62 static 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 */
  71 static unsigned long cMaxVisits;
  72
  73 static unsigned char *dirn_stack = NULL;
  74 static long *min_stack = NULL;
  75
  76 static unsigned long
  77 visit(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
  87 iter:
  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;
 106 uniter:
 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
 198 extern void
 199 articulate(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       /* Any stations still in stnlist are unfixed, which is means we have
 370        * one or more hanging surveys.
 371        *
 372        * The cause of the problem is pretty likely to be a typo, so run the
 373        * checks which report errors and warnings about issues which such a
 374        * typo is likely to result in.
 375        */
 376       check_node_stats();
 377
 378       bool fNotAttached = false;
 379       /* TRANSLATORS: At the end of processing (or if a *SOLVE command is used)
 380        * cavern will issue this warning if there are any sections of the survey
 381        * network which are hanging. */
 382       warning(/*Survey not all connected to fixed stations*/45);
 383       FOR_EACH_STN(stn, stnlist) {
 384          prefix *name = find_non_anon_stn(stn)->name;
 385          if (TSTBIT(name->sflags, SFLAGS_HANGING)) {
 386              /* Already reported this name as hanging. */
 387              continue;
 388          }
 389          name->sflags |= BIT(SFLAGS_HANGING);
 390          if (name->ident) {
 391             if (!fNotAttached) {
 392                fNotAttached = true;
 393                /* TRANSLATORS: Here "station" is a survey station, not a train
 394                 * station. */
 395                puts(msg(/*The following survey stations are not attached to a fixed point:*/71));
 396             }
 397             printf("%s:%d: %s: ", name->filename, name->line, msg(/*info*/485));
 398             print_prefix(name);
 399             putnl();
 400          }
 401       }
 402       stnlist = NULL;
 403       hanging_surveys = true;
 404    }
 405
 406    {
 407       component *comp = component_list;
 408
 409 #ifdef DEBUG_ARTIC
 410       printf("\nDump of %d components:\n", cComponents);
 411 #endif
 412       while (comp) {
 413          node *list = NULL, *listend = NULL;
 414          articulation *art;
 415          component * old_comp;
 416 #ifdef DEBUG_ARTIC
 417          printf("Component:\n");
 418 #endif
 419          SVX_ASSERT(comp->artic);
 420          art = comp->artic;
 421          while (art) {
 422             articulation * old_art;
 423 #ifdef DEBUG_ARTIC
 424             printf("  Articulation (%p):\n", art->stnlist);
 425 #endif
 426             SVX_ASSERT(art->stnlist);
 427             if (listend) {
 428                listend->next = art->stnlist;
 429                art->stnlist->prev = listend;
 430             } else {
 431                list = art->stnlist;
 432             }
 433
 434             FOR_EACH_STN(stn, art->stnlist) {
 435 #ifdef DEBUG_ARTIC
 436                printf("    %d %p (", stn->colour, stn);
 437                print_prefix(stn->name);
 438                printf(")\n");
 439 #endif
 440                listend = stn;
 441             }
 442             old_art = art;
 443             art = art->next;
 444             osfree(old_art);
 445          }
 446 #ifdef DEBUG_ARTIC
 447          putnl();
 448          FOR_EACH_STN(stn, list) {
 449             printf("MX: %c %p (", fixed(stn)?'*':' ', stn);
 450             print_prefix(stn->name);
 451             printf(")\n");
 452          }
 453 #endif
 454          solve_matrix(list);
 455 #ifdef DEBUG_ARTIC
 456          putnl();
 457          FOR_EACH_STN(stn, list) {
 458             printf("%c %p (", fixed(stn)?'*':' ', stn);
 459             print_prefix(stn->name);
 460             printf(")\n");
 461          }
 462 #endif
 463          listend->next = stnlist;
 464          if (stnlist) stnlist->prev = listend;
 465          stnlist = list;
 466
 467          old_comp = comp;
 468          comp = comp->next;
 469          osfree(old_comp);
 470       }
 471 #ifdef DEBUG_ARTIC
 472       printf("done articulating\n");
 473 #endif
 474    }
 475
 476 #ifdef DEBUG_ARTIC
 477    /* test articulation */
 478    FOR_EACH_STN(stn, stnlist) {
 479       int d;
 480       int f;
 481       if (stn->name->ident && TSTBIT(stn->name->sflags, SFLAGS_FIXED)) {
 482          stn->colour = 1;
 483       } else {
 484          stn->colour = 0;
 485       }
 486       f = 0;
 487       for (d = 0; d < 3; d++) {
 488          if (stn->leg[d]) {
 489             if (f) {
 490                printf("awooga - gap in legs\n");
 491             }
 492             if (stn->leg[d]->l.reverse & FLAG_ARTICULATION) {
 493                if (!(reverse_leg(stn->leg[d])->l.reverse & FLAG_ARTICULATION)) {
 494                   printf("awooga - bad articulation (one way art)\n");
 495                }
 496             } else {
 497                if (reverse_leg(stn->leg[d])->l.reverse & FLAG_ARTICULATION) {
 498                   printf("awooga - bad articulation (one way art)\n");
 499                }
 500             }
 501          } else {
 502             f = 1;
 503          }
 504       }
 505    }
 506
 507    colour = 2;
 508
 509    while (1) {
 510       int c;
 511       int f;
 512       do {
 513          c = 0;
 514          FOR_EACH_STN(stn, stnlist) {
 515             int d;
 516             f = 0;
 517             for (d = 0; d < 3; d++) {
 518                if (stn->leg[d]) {
 519                   node *stn2 = stn->leg[d]->l.to;
 520                   if (f) {
 521                      printf("awooga - gap in legs\n");
 522                   }
 523                   if (stn2->colour) {
 524                      if (!(stn->leg[d]->l.reverse & FLAG_ARTICULATION)) {
 525                         if (stn->colour == 0) {
 526                            stn->colour = stn2->colour;
 527                            c++;
 528                         }
 529                      }
 530                   }
 531                } else {
 532                   f = 1;
 533                }
 534             }
 535          }
 536       } while (c);
 537
 538       /* colour bits */
 539       FOR_EACH_STN(stn, stnlist) {
 540          if (stn->colour == 0) break;
 541       }
 542       if (!stn) break; /* all coloured */
 543
 544       stn->colour = colour++;
 545    }
 546
 547    FOR_EACH_STN(stn, stnlist) {
 548       int d;
 549       int f;
 550       f = 0;
 551       for (d = 0; d < 3; d++) {
 552          if (stn->leg[d]) {
 553             if (f) {
 554                printf("awooga - gap in legs\n");
 555             }
 556 #ifdef DEBUG_ARTIC
 557             if (stn->leg[d]->l.reverse & FLAG_ARTICULATION) {
 558                node *stn2 = stn->leg[d]->l.to;
 559                printf("art: %ld %ld [%p] ", stn->colour, stn2->colour, stn);
 560                print_prefix(stn->name);
 561                printf(" - [%p] ", stn2);
 562                print_prefix(stn2->name);
 563                printf("\n");
 564             }
 565 #endif
 566          } else {
 567             f = 1;
 568          }
 569       }
 570    }
 571 #endif
 572    FOR_EACH_STN(stn, stnlist) {
 573       SVX_ASSERT(fixed(stn));
 574    }
 575 }