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 #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
  45 typedef struct articulation {
  46    struct articulation *next;
  47    node *stnlist;
  48 } articulation;
  49
  50 typedef struct component {
  51    struct component *next;
  52    articulation *artic;
  53 } component;
  54
  55 static component *component_list;
  56
  57 static articulation *articulation_list;
  58
  59 static node *artlist;
  60
  61 static node *fixedlist;
  62
  63 static 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 */
  72 static unsigned long cMaxVisits;
  73
  74 static unsigned char *dirn_stack = NULL;
  75 static long *min_stack = NULL;
  76
  77 static unsigned long
  78 visit(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
  88 iter:
  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;
 107 uniter:
 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
 199 extern void
 200 articulate(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 }