2 * Split up network at articulation points
3 * Copyright (C) 1993-2003,2005,2012,2014,2015 Olly Betts
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.
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.
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
21 # define DEBUG_INVALID 1
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
45 typedef struct articulation
{
46 struct articulation
*next
;
50 typedef struct component
{
51 struct component
*next
;
55 static component
*component_list
;
57 static articulation
*articulation_list
;
61 static node
*fixedlist
;
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.
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
;
74 static unsigned char *dirn_stack
= NULL
;
75 static long *min_stack
= NULL
;
78 visit(node
*stn
, int back
)
82 unsigned long tos
= 0;
83 SVX_ASSERT(dirn_stack
&& min_stack
);
85 printf("visit(%p, %d) called\n", stn
, back
);
89 min_colour
= stn
->colour
= ++colour
;
91 printf("visit: stn [%p] ", stn
);
92 print_prefix(stn
->name
);
93 printf(" set to colour %ld -> min\n", colour
);
95 for (i
= 0; i
<= 2 && stn
->leg
[i
]; i
++) {
97 node
*to
= stn
->leg
[i
]->l
.to
;
98 long col
= to
->colour
;
100 SVX_ASSERT(tos
< cMaxVisits
);
101 dirn_stack
[tos
] = back
;
102 min_stack
[tos
] = min_colour
;
104 back
= reverse_leg_dirn(stn
->leg
[i
]);
110 i
= reverse_leg_dirn(stn
->leg
[back
]);
112 stn
= to
->leg
[back
]->l
.to
;
113 back
= dirn_stack
[tos
];
114 if (min_stack
[tos
] < min_colour
) min_colour
= min_stack
[tos
];
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");
125 remove_stn_from_list(&stnlist
, to
);
126 add_stn_to_list(&artlist
, to
);
128 if (to
->colour
<= min_colour
) {
131 min_colour
= to
->colour
;
133 /* FIXME: note down leg (<-), remove and replace:
135 * [fixed point(s)] *-* -> [..] )
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
;
143 /* start new articulation */
144 art
= osnew(articulation
);
145 art
->stnlist
= artlist
;
146 art
->next
= articulation_list
;
147 articulation_list
= art
;
151 printf("Articulate *-");
152 print_prefix(stn
->name
);
154 print_prefix(to
->name
);
161 /* we've found a fixed point */
165 /* Removing this solves Graham Mullan's problem and makes more
166 * sense since it means we'll recheck this point for further
169 printf("Putting FOUND FIXED stn ");
170 print_prefix(to
->name
);
171 printf(" on artlist\n");
173 remove_stn_from_list(&fixedlist
, to
);
174 add_stn_to_list(&artlist
, to
);
178 if (col
< min_colour
) min_colour
= col
;
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);
187 if (tos
> 0) goto uniter
;
190 printf("Putting stn ");
191 print_prefix(stn
->name
);
192 printf(" on artlist\n");
194 remove_stn_from_list(&stnlist
, stn
);
195 add_stn_to_list(&artlist
, stn
);
202 node
*stn
, *stnStart
;
206 component_list
= NULL
;
207 articulation_list
= NULL
;
211 /* find articulation points and components */
215 FOR_EACH_STN(stn
, stnlist
) {
217 remove_stn_from_list(&stnlist
, stn
);
218 add_stn_to_list(&fixedlist
, stn
);
220 stn
->colour
= -colour
;
222 printf("Putting stn ");
223 print_prefix(stn
->name
);
224 printf(" on fixedlist\n");
231 dirn_stack
= osmalloc(cMaxVisits
);
232 min_stack
= osmalloc(cMaxVisits
* sizeof(long));
234 /* fixedlist can be NULL here if we've had a *solve followed by survey
235 * which is all hanging. */
239 stnStart
= fixedlist
;
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) {
246 printf("new component\n");
248 stn
->colour
= -stn
->colour
; /* fixed points are negative until we colour from them */
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) */
258 art
= osnew(articulation
);
259 art
->stnlist
= artlist
;
260 art
->next
= articulation_list
;
261 articulation_list
= art
;
264 comp
= osnew(component
);
265 comp
->next
= component_list
;
266 comp
->artic
= articulation_list
;
267 component_list
= comp
;
268 articulation_list
= NULL
;
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
);
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
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)
291 * FIXME: this is a "fixed point cut-line" case where we could
292 * start a new component.
294 long col
= visit(stn2
, reverse_leg_dirn(stn
->leg
[i
]));
296 print_prefix(stn
->name
);
298 print_prefix(stn2
->name
);
299 printf(" col %d cFixed %d\n", 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
;
314 /* had to colour in 2 or 3 directions from start point */
315 case 3: case 5: case 6: case 7:
317 print_prefix(stn
->name
);
318 printf(" is a special case start articulation point [%d]\n", c
);
320 for (i
= 0; i
<= 2 && stn
->leg
[i
]; i
++) {
322 /* flag leg as an articulation for loop error reporting */
323 stn
->leg
[i
]->l
.reverse
|= FLAG_ARTICULATION
;
325 print_prefix(stn
->leg
[i
]->l
.to
->name
);
328 reverse_leg(stn
->leg
[i
])->l
.reverse
|= FLAG_ARTICULATION
;
334 printf("Putting FIXED stn ");
335 print_prefix(stn
->name
);
336 printf(" on artlist\n");
338 remove_stn_from_list(&fixedlist
, stn
);
339 add_stn_to_list(&artlist
, stn
);
341 if (stnStart
->colour
== 1) {
343 printf("%ld components\n",cComponents
);
355 articulation
*art
= osnew(articulation
);
356 art
->stnlist
= artlist
;
357 art
->next
= articulation_list
;
358 articulation_list
= art
;
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
;
370 /* Any stations still in stnlist are unfixed, which is means we have
371 * one or more hanging surveys.
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.
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...
383 bool fNotAttached
= false;
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.
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.
399 /* SVX_ASSERT(!TSTBIT(stn->name->sflags, SFLAGS_ANON)); */
400 if (stn
->name
->ident
) {
403 /* TRANSLATORS: Here "station" is a survey station, not a train
405 puts(msg(/*The following survey stations are not attached to a fixed point:*/71));
407 puts(sprint_prefix(stn
->name
));
414 component
*comp
= component_list
;
417 printf("\nDump of %d components:\n", cComponents
);
420 node
*list
= NULL
, *listend
= NULL
;
422 component
* old_comp
;
424 printf("Component:\n");
426 SVX_ASSERT(comp
->artic
);
429 articulation
* old_art
;
431 printf(" Articulation (%p):\n", art
->stnlist
);
433 SVX_ASSERT(art
->stnlist
);
435 listend
->next
= art
->stnlist
;
436 art
->stnlist
->prev
= listend
;
441 FOR_EACH_STN(stn
, art
->stnlist
) {
443 printf(" %d %p (", stn
->colour
, stn
);
444 print_prefix(stn
->name
);
455 FOR_EACH_STN(stn
, list
) {
456 printf("MX: %c %p (", fixed(stn
)?'*':' ', stn
);
457 print_prefix(stn
->name
);
464 FOR_EACH_STN(stn
, list
) {
465 printf("%c %p (", fixed(stn
)?'*':' ', stn
);
466 print_prefix(stn
->name
);
470 listend
->next
= stnlist
;
471 if (stnlist
) stnlist
->prev
= listend
;
479 printf("done articulating\n");
484 /* test articulation */
485 FOR_EACH_STN(stn
, stnlist
) {
488 if (stn
->name
->ident
&& TSTBIT(stn
->name
->sflags
, SFLAGS_FIXED
)) {
494 for (d
= 0; d
< 3; d
++) {
497 printf("awooga - gap in legs\n");
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");
504 if (reverse_leg(stn
->leg
[d
])->l
.reverse
& FLAG_ARTICULATION
) {
505 printf("awooga - bad articulation (one way art)\n");
521 FOR_EACH_STN(stn
, stnlist
) {
524 for (d
= 0; d
< 3; d
++) {
526 node
*stn2
= stn
->leg
[d
]->l
.to
;
528 printf("awooga - gap in legs\n");
531 if (!(stn
->leg
[d
]->l
.reverse
& FLAG_ARTICULATION
)) {
532 if (stn
->colour
== 0) {
533 stn
->colour
= stn2
->colour
;
546 FOR_EACH_STN(stn
, stnlist
) {
547 if (stn
->colour
== 0) break;
549 if (!stn
) break; /* all coloured */
551 stn
->colour
= colour
++;
554 FOR_EACH_STN(stn
, stnlist
) {
558 for (d
= 0; d
< 3; d
++) {
561 printf("awooga - gap in legs\n");
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
);
579 FOR_EACH_STN(stn
, stnlist
) {
580 SVX_ASSERT(fixed(stn
));