diff options
author | Andreas Scherer <andreas_tex@freenet.de> | 2023-06-20 19:43:32 +0000 |
---|---|---|
committer | Andreas Scherer <andreas_tex@freenet.de> | 2023-06-20 19:43:32 +0000 |
commit | f754b336d197f04dbca7b2664b0d72d54c445b80 (patch) | |
tree | 3119d3383ff24c050898dadaacd827e1b01cd5d4 /Build/source | |
parent | 45ad44f1f1e6a06556bfbe72bfe081ba5956d036 (diff) |
[CWEB] Provide a comprehensive test for CTWILL.
The material comes from https://github.com/ascherer/cwebtest and was
pre-processed with
$ ctwill ham ham # (twice), producing ham.{aux,idx,ref,scn,tex}
$ tex ham # producing ham.{dvi,log}
$ ctwill-refsort < ham.ref > ham.sref
plus for "proofing"
$ ctwill-proofsort ham.tex > ham-sorted.tex
Note that the fonal step is not active in ctwill.test.
git-svn-id: svn://tug.org/texlive/trunk@67417 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source')
-rw-r--r-- | Build/source/texk/web2c/cwebdir/ChangeLog | 2 | ||||
-rwxr-xr-x | Build/source/texk/web2c/cwebdir/ctwill.test | 52 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/gb_graph.hux | 54 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/gb_save.hux | 29 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/gb_types.w | 8 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/ham-sorted.tex | 364 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/ham.aux | 29 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/ham.bux | 2 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/ham.ch | 112 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/ham.idx | 43 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/ham.ref | 47 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/ham.scn | 23 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/ham.sref | 47 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/ham.tex | 366 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/ham.w | 163 | ||||
-rw-r--r-- | Build/source/texk/web2c/cwebdir/tests/system.bux | 41 |
16 files changed, 1344 insertions, 38 deletions
diff --git a/Build/source/texk/web2c/cwebdir/ChangeLog b/Build/source/texk/web2c/cwebdir/ChangeLog index a58efbcd741..e8a17244348 100644 --- a/Build/source/texk/web2c/cwebdir/ChangeLog +++ b/Build/source/texk/web2c/cwebdir/ChangeLog @@ -4,6 +4,8 @@ * ctwill-mini.ch, * ctwill-w2c.ch, * ctwill.bux: Use 'kpse_find_file' for '*.bux' files. + * ctwill.test, + * tests/: Comprehensive test of CTWILL and its utilities. 2023-06-18 Karl Berry <karl@freefriends.org> diff --git a/Build/source/texk/web2c/cwebdir/ctwill.test b/Build/source/texk/web2c/cwebdir/ctwill.test index 8e6c5ee6047..c52725bc5ab 100755 --- a/Build/source/texk/web2c/cwebdir/ctwill.test +++ b/Build/source/texk/web2c/cwebdir/ctwill.test @@ -3,53 +3,29 @@ # Copyright 2023 Andreas Scherer <tex-live@tug.org> # You may freely use, modify and/or distribute this file. +testdir=$srcdir/cwebdir/tests + # # (1) Test the "classic" CTWILL procedure # -TEXMFCNF=$srcdir/../kpathsea \ - CWEBINPUTS=$srcdir/cwebdir ./ctie -m ctwill.w \ - cweave.w ctwill-w2c.ch ctwill-mini.ch || exit 1 - # Prime the pump by running CTWILL twice -TEXMFCNF=$srcdir/../kpathsea \ - CWEBINPUTS=$srcdir/cwebdir: ./ctwill +lpdf ctwill.w || exit 1 - -TEXMFCNF=$srcdir/../kpathsea \ - CWEBINPUTS=$srcdir/cwebdir: ./ctwill +lpdf ctwill.w || exit 1 - -exit 0 - -# (can't) run TeX for the first time -#TEXMFCNF=$srcdir/../kpathsea \ -# TEXINPUTS=$srcdir/cwebdir//: tex ctwill.tex || exit 1 +CWEBINPUTS=$testdir ./ctwill +lpdf ham ham || exit 1 +CWEBINPUTS=$testdir ./ctwill +lpdf ham ham || exit 1 # Test CTWILL-REFSORT -TEXMFCNF=$srcdir/../kpathsea \ - ./ctwill-refsort < ctwill.ref > ctwill.sref || exit 1 - -# Run TeX for the second time -- NOT! -#TEXMFCNF=$srcdir/../kpathsea \ - #TEXINPUTS=$srcdir/cwebdir//: tex ctwill.tex || exit 1 +./ctwill-refsort < $testdir/ham.ref > ham.sref || exit 1 +diff ham.sref $testdir/ham.sref || exit 1 # # (2) Test the "proofing" CTWILL procedure # -TEXMFCNF=$srcdir/../kpathsea \ - CWEBINPUTS=$srcdir/cwebdir ./ctie -m ctwill.w \ - cweave.w ctwill-w2c.ch ctwill-mini.ch \ - ctwill-hint.ch || exit 1 - -# Running CTWILL once again, but with options +P +lpdf -TEXMFCNF=$srcdir/../kpathsea \ - CWEBINPUTS=$srcdir/cwebdir: ./ctwill +P +lpdf ctwill.w || exit 1 - -# Test CTWILL-PROOFSORT -TEXMFCNF=$srcdir/../kpathsea \ - $srcdir/cwebdir/ctwill-proofsort ctwill.tex > ctwill-sorted.tex || exit 1 -#mv ctwill-sorted.tex ctwill.tex || exit 1 # -- NOT! - -# Run pdfTeX once -- NOT! -#TEXMFCNF=$srcdir/../kpathsea \ - #TEXINPUTS=$srcdir/cwebdir//: pdftex ctwill.tex || exit 1 +CWEBINPUTS=$testdir ./ctwill +P +lpdf ham ham || exit 1 +CWEBINPUTS=$testdir ./ctwill +P +lpdf ham ham || exit 1 + +# Test CTWILL-PROOFSORT---NOT! +# First, it doesn't show up in Work/texk/web2c/ and +# second, Perl complains about the unresolved $Revision$ and §Date$. +#./ctwill-proofsort ham.tex > ham-sorted.tex || exit 1 +#diff ham-sorted.tex $testdir/ham-sorted.tex || exit 1 exit 0 diff --git a/Build/source/texk/web2c/cwebdir/tests/gb_graph.hux b/Build/source/texk/web2c/cwebdir/tests/gb_graph.hux new file mode 100644 index 00000000000..2fc45ab5d21 --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/gb_graph.hux @@ -0,0 +1,54 @@ +@$util {GB\_\,GRAPH}8 =\&{union}@> +@$V {GB\_\,GRAPH}8 \&{Vertex} ${}{*}{}$@> +@$A {GB\_\,GRAPH}8 \&{Arc} ${}{*}{}$@> +@$G {GB\_\,GRAPH}8 \&{Graph} ${}{*}{}$@> +@$S {GB\_\,GRAPH}8 \&{char} ${}{*}{}$@> +@$I {GB\_\,GRAPH}8 \&{long}@> + +@$Vertex {GB\_\,GRAPH}9 =\&{struct}@> +@$arcs {GB\_\,GRAPH}9 \&{Arc} ${}{*}{}$@> +@$name {GB\_\,GRAPH}9 \&{char} ${}{*}{}$@> +@$u {GB\_\,GRAPH}9 \&{util}@> +@$v {GB\_\,GRAPH}9 \&{util}@> +@$w {GB\_\,GRAPH}9 \&{util}@> +@$x {GB\_\,GRAPH}9 \&{util}@> +@$y {GB\_\,GRAPH}9 \&{util}@> +@$z {GB\_\,GRAPH}9 \&{util}@> + +@$Arc {GB\_\,GRAPH}10 =\&{struct}@> +@$tip {GB\_\,GRAPH}10 \&{Vertex} ${}{*}{}$@> +@$next {GB\_\,GRAPH}10 \&{Arc} ${}{*}{}$@> +@$len {GB\_\,GRAPH}10 \&{long}@> +@$a {GB\_\,GRAPH}10 \&{util}@> +@$b {GB\_\,GRAPH}10 \&{util}@> + +@$gb_typed_alloc {GB\_\,GRAPH}11 =macro (\,)@> + +@$Graph {GB\_\,GRAPH}20 =\&{struct}@> +@$vertices {GB\_\,GRAPH}20 \&{Vertex} ${}{*}{}$@> +@$n {GB\_\,GRAPH}20 \&{long}@> +@$m {GB\_\,GRAPH}20 \&{long}@> +@$uu {GB\_\,GRAPH}20 \&{util}@> +@$vv {GB\_\,GRAPH}20 \&{util}@> +@$ww {GB\_\,GRAPH}20 \&{util}@> +@$xx {GB\_\,GRAPH}20 \&{util}@> +@$yy {GB\_\,GRAPH}20 \&{util}@> +@$zz {GB\_\,GRAPH}20 \&{util}@> + +@$n_1 {GB\_\,GRAPH}22 =\\{uu}.\|I@> + +@$arcs_per_block {GB\_\,GRAPH}29 =\T{102}@> + +@$gb_new_graph {GB\_\,GRAPH}31 =macro@> +@$gb_new_arc {GB\_\,GRAPH}31 =macro@> +@$gb_new_edge {GB\_\,GRAPH}31 =macro@> + +@$siz_t {GB\_\,GRAPH}34 =\&{unsigned} \&{long}@> + +@$string_block_size {GB\_\,GRAPH}35 =\T{1016}@> + +@$hash_link {GB\_\,GRAPH}43 =\|u.\|V@> +@$hash_head {GB\_\,GRAPH}43 =\|v.\|V@> + +@$HASH_MULT {GB\_\,GRAPH}45 =\T{314159}@> +@$HASH_PRIME {GB\_\,GRAPH}45 =\T{516595003}@> diff --git a/Build/source/texk/web2c/cwebdir/tests/gb_save.hux b/Build/source/texk/web2c/cwebdir/tests/gb_save.hux new file mode 100644 index 00000000000..86bb6fa5269 --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/gb_save.hux @@ -0,0 +1,29 @@ +@$MAX_SV_STRING {GB\_\,SAVE}1 =\T{4095}@> +@$MAX_SV_ID {GB\_\,SAVE}1 =\T{154}@> + +@$restore_graph {GB\_\,SAVE}4 \&{Graph} ${}{*}(\,){}$@> + +@$panic {GB\_\,SAVE}5 =macro (\,)@> + +@$fillin {GB\_\,SAVE}7 =macro (\,)@> + +@$buffer {GB\_\,SAVE}13 =macro@> + +@$bad_type_code {GB\_\,SAVE}19 =\T{\^1}@> +@$string_too_long {GB\_\,SAVE}19 =\T{\^2}@> +@$addr_not_in_data_area {GB\_\,SAVE}19 =\T{\^4}@> +@$addr_in_mixed_block {GB\_\,SAVE}19 =\T{\^8}@> +@$bad_string_char {GB\_\,SAVE}19 =\T{\^10}@> +@$ignored_data {GB\_\,SAVE}19 =\T{\^20}@> + +@$unk {GB\_\,SAVE}21 =\T{0}@> +@$ark {GB\_\,SAVE}21 =\T{1}@> +@$vrt {GB\_\,SAVE}21 =\T{2}@> +@$mxt {GB\_\,SAVE}21 =\T{3}@> +@$block_rep {GB\_\,SAVE}21 =\&{struct}@> + +@$lookup {GB\_\,SAVE}25 =macro (\,)@> + +@$append_comma {GB\_\,SAVE}37 =macro@> + +@$trans {GB\_\,SAVE}39 =macro (\,)@> diff --git a/Build/source/texk/web2c/cwebdir/tests/gb_types.w b/Build/source/texk/web2c/cwebdir/tests/gb_types.w new file mode 100644 index 00000000000..7b533f348ca --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/gb_types.w @@ -0,0 +1,8 @@ +@q This file makes CWEAVE treat Graph, Arc, Vertex, etc. as reserved words. @> + +@s Graph int +@s Arc int +@s Vertex int +@s Area int +@s util int +@s siz_t int diff --git a/Build/source/texk/web2c/cwebdir/tests/ham-sorted.tex b/Build/source/texk/web2c/cwebdir/tests/ham-sorted.tex new file mode 100644 index 00000000000..30668f582ed --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/ham-sorted.tex @@ -0,0 +1,364 @@ +\input ctwimac +\datethis +\def\title{HAM} + + + + +\N{1}{1} +Hamiltonian cycles. This program finds all Hamiltonian cycles of +an undirected graph. [It's a slight revision of the program published +in my paper ``Mini-indexes for literate programs,'' {\sl Software---Concepts +and Tools\/ \bf15} (1994), 2--11.] The input graph should be in +Stanford GraphBase format, and should be named on the command line +as, for example, \.{foo.gb}. An optional second command-line parameter +is a modulus \PB{\|m}, which causes every $m$th solution to be printed. + +We use a utility field to record the vertex degrees. + +\Y\B\4\D$\\{deg}$ \5 +$\|u.{}$\|I\par +\Y\B\8\#\&{include} \.{"gb\_graph.h"}\C{ the GraphBase data structures }\6 +\8\#\&{include} \.{"gb\_save.h"}\C{ \PB{\\{restore\_graph}} }\7 +\1\1\&{int} \\{main}(\&{int} \\{argc}${},\39{}$\&{char} ${}{*}\\{argv}[\,])\2% +\2{}$\6 +${}\{{}$\1\6 +\&{Graph} ${}{*}\|g;{}$\6 +\&{Vertex} ${}{*}\|x,\39{*}\|y,\39{*}\|z,\39{*}\\{tmax};{}$\6 +\&{register} \&{Vertex} ${}{*}\|t,\39{*}\|u,\39{*}\|v;{}$\6 +\&{register} \&{Arc} ${}{*}\|a,\39{*}\\{aa};{}$\6 +\&{register} \&{int} \|d;\6 +\&{Arc} ${}{*}\|b,\39{*}\\{bb};{}$\6 +\&{int} \\{count}${}\K\T{0};{}$\6 +\&{int} \\{dmin}${},\39\\{modulus};{}$\7 +\X2:Process the command line, inputting the graph\X;\6 +\X3:Prepare \PB{\|g} for backtracking, and find a vertex \PB{\|x} of minimum +degree\X;\6 +\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$ +${}\|v\PP){}$\1\5 +${}\\{printf}(\.{"\ \%ld"},\39\|v\MG\\{deg});{}$\2\6 +\\{printf}(\.{"\\n"});\C{ TEMPORARY CHECK }\6 +\&{if} ${}(\|x\MG\\{deg}<\T{2}){}$\5 +${}\{{}$\1\6 +${}\\{printf}(\.{"The\ minimum\ degree\ }\)\.{is\ \%ld\ (vertex\ \%s)!\\}\)% +\.{n"},\39\|x\MG\\{deg},\39\|x\MG\\{name});{}$\6 +\&{return} ${}{-}\T{1};{}$\6 +\4${}\}{}$\2\6 +\&{for} ${}(\|b\K\|x\MG\\{arcs};{}$ ${}\|b\MG\\{next};{}$ ${}\|b\K\|b\MG% +\\{next}){}$\1\6 +\&{for} ${}(\\{bb}\K\|b\MG\\{next};{}$ \\{bb}; ${}\\{bb}\K\\{bb}\MG\\{next}){}$% +\5 +${}\{{}$\1\6 +${}\|v\K\|b\MG\\{tip};{}$\6 +${}\|z\K\\{bb}\MG\\{tip};{}$\6 +\X4:Find all simple paths of length \PB{$\|g\MG\|n-\T{2}$} from \PB{\|v} to % +\PB{\|z}, avoiding \PB{\|x}\X;\6 +\4${}\}{}$\2\2\6 +${}\\{printf}(\.{"Altogether\ \%d\ solut}\)\.{ions.\\n"},\39\\{count});{}$\6 +\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$ +${}\|v\PP){}$\1\5 +${}\\{printf}(\.{"\ \%ld"},\39\|v\MG\\{deg});{}$\2\6 +\\{printf}(\.{"\\n"});\C{ TEMPORARY CHECK, SHOULD AGREE WITH FORMER VALUES }\6 +\4${}\}{}$\2\par +\mini +\]{GB\_\,GRAPH}10 \&{Arc} =\&{struct} +\]{GB\_\,GRAPH}9 \\{arcs} \&{Arc} ${}{*}{}$ +\]{GB\_\,GRAPH}20 \&{Graph} =\&{struct} +\]{GB\_\,GRAPH}8 \|{I} \&{long} +\]{GB\_\,GRAPH}20 \|{m} \&{long} +\]{GB\_\,GRAPH}20 \|{n} \&{long} +\]{GB\_\,GRAPH}9 \\{name} \&{char} ${}{*}{}$ +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\]"<stdio.h>" \\{printf} \zip +\]{GB\_\,SAVE}4 \\{restore\_graph} \&{Graph} ${}{*}(\,){}$ +\]{GB\_\,GRAPH}10 \\{tip} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \|{u} \&{util} +\]{GB\_\,GRAPH}9 \&{Vertex} =\&{struct} +\]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ +}\FI + +\shortpage +\M{2} +\B\X2:Process the command line, inputting the graph\X${}\E{}$\6 +\&{if} ${}(\\{argc}>\T{1}){}$\1\5 +${}\|g\K\\{restore\_graph}(\\{argv}[\T{1}]){}$;\5 +\2\&{else}\1\5 +${}\|g\K\NULL;{}$\2\6 +\&{if} ${}(\\{argc}<\T{3}\V\\{sscanf}(\\{argv}[\T{2}],\39\.{"\%d"},\39{\AND}% +\\{modulus})\I\T{1}){}$\1\5 +${}\\{modulus}\K\T{1000000000};{}$\2\6 +\&{if} ${}(\R\|g\V\\{modulus}\Z\T{0}){}$\5 +${}\{{}$\1\6 +${}\\{fprintf}(\\{stderr},\39\.{"Usage:\ \%s\ foo.gb\ [m}\)\.{odulus]\\n"},\39% +\\{argv}[\T{0}]);{}$\6 +${}\\{exit}({-}\T{1});{}$\6 +\4${}\}{}$\2\par +\U1. +\mini +\[1 \\{argc} \&{int} +\[1 \\{argv} \&{char} ${}{*}[\,]{}$ +\]"<stdlib.h>" \\{exit} \zip +\]"<stdio.h>" \\{fprintf} \zip +\[1 \|{g} \&{Graph} ${}{*}{}$ +\[1 \\{modulus} \&{int} +\]{GB\_\,SAVE}4 \\{restore\_graph} \&{Graph} ${}{*}(\,){}$ +\]"<stdio.h>" \\{sscanf} \zip +\]"<stdio.h>" \\{stderr} \zip +}\FI + +\M{3} +Vertices that have already appeared in the path are ``taken,'' and +their \PB{\\{taken}} field is nonzero. Initially we make all those fields zero. + +\Y\B\4\D$\\{taken}$ \5 +$\|v.{}$\|I\par +\Y\B\4\X3:Prepare \PB{\|g} for backtracking, and find a vertex \PB{\|x} of +minimum degree\X${}\E{}$\6 +$\\{dmin}\K\|g\MG\|n;{}$\6 +\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$ +${}\|v\PP){}$\5 +${}\{{}$\1\6 +${}\|v\MG\\{taken}\K\T{0};{}$\6 +${}\|d\K\T{0};{}$\6 +\&{for} ${}(\|a\K\|v\MG\\{arcs};{}$ \|a; ${}\|a\K\|a\MG\\{next}){}$\1\5 +${}\|d\PP;{}$\2\6 +${}\|v\MG\\{deg}\K\|d;{}$\6 +\&{if} ${}(\|d<\\{dmin}){}$\1\5 +${}\\{dmin}\K\|d,\39\|x\K\|v;{}$\2\6 +\4${}\}{}$\2\par +\U1. +\mini +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \\{arcs} \&{Arc} ${}{*}{}$ +\[1 \|{d} \&{register} \&{int} +\[1 \\{deg} =\|u.\|I +\[1 \\{dmin} \&{int} +\[1 \|{g} \&{Graph} ${}{*}{}$ +\]{GB\_\,GRAPH}8 \|{I} \&{long} +\]{GB\_\,GRAPH}20 \|{n} \&{long} +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\[1 \|{v} \&{register} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ +\[1 \|{x} \&{Vertex} ${}{*}{}$ +}\FI + +\N{1}{4} +The data structures. I use one simple rule to cut off unproductive +branches of the search tree: If one of the vertices we could move to next +is adjacent to only one other unused vertex, we must move to it now. + +The moves will be recorded in the vertex array of \PB{\|g}. More precisely, the +\PB{\|k}th vertex of the path will be \PB{$\|t\MG\\{vert}$} when \PB{\|t} is +the \PB{\|k}th vertex of +the graph. If the move was not forced, \PB{$\|t\MG\\{ark}$} will point to the +Arc +record representing the edge from \PB{$\|t\MG\\{vert}$} to \PB{$(\|t+\T{1})\MG% +\\{vert}$}; otherwise +\PB{$\|t\MG\\{ark}$} will be \PB{$\NULL$}. + +This program is a typical backtrack program. I am more comfortable doing +it with labels and goto statements than with while loops, but some day +I may learn my lesson. + +\Y\B\4\D$\\{vert}$ \5 +$\|w.{}$\|V\par +\B\4\D$\\{ark}$ \5 +$\|x.{}$\|A\par +\Y\B\4\X4:Find all simple paths of length \PB{$\|g\MG\|n-\T{2}$} from \PB{\|v} +to \PB{\|z}, avoiding \PB{\|x}\X${}\E{}$\6 +$\|t\K\|g\MG\\{vertices}{}$;\5 +${}\\{tmax}\K\|t+\|g\MG\|n-\T{1};{}$\6 +${}\|x\MG\\{taken}\K\T{1}{}$;\5 +${}\|t\MG\\{vert}\K\|x{}$;\5 +${}\|t\MG\\{ark}\K\NULL;{}$\6 +\4\\{advance}:\5 +\X5:Increase \PB{\|t} and update the data structures to show that vertex \PB{% +\|v} is now taken; \PB{\&{goto} \\{backtrack}} if no further moves are possible% +\X;\6 +\4\\{try\_next}:\5 +\X7:Look at edge \PB{\|a} and its successors, advancing if it is a valid move% +\X;\6 +\4\\{restore}:\5 +\X6:Downdate the data structures to the state they were in when level \PB{\|t} +was entered\X;\6 +\4\\{backtrack}:\5 +\X8:Decrease \PB{\|t}, if possible, and try the next possibility; or \PB{% +\&{goto} \\{done}}\X;\6 +\\{done}:\par +\U1. +\mini +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +\]{GB\_\,GRAPH}8 \|{A} \&{Arc} ${}{*}{}$ +\[1 \|{g} \&{Graph} ${}{*}{}$ +\]{GB\_\,GRAPH}20 \|{n} \&{long} +\[1 \|{t} \&{register} \&{Vertex} ${}{*}{}$ +\[3 \\{taken} =\|v.\|I +\[1 \\{tmax} \&{Vertex} ${}{*}{}$ +\[1 \|{v} \&{register} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}8 \|{V} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \|{w} \&{util} +\]{GB\_\,GRAPH}9 \|{x} \&{util} +\[1 \|{z} \&{Vertex} ${}{*}{}$ +}\FI + +\M{5} +\B\X5:Increase \PB{\|t} and update the data structures to show that vertex \PB{% +\|v} is now taken; \PB{\&{goto} \\{backtrack}} if no further moves are possible% +\X${}\E{}$\6 +$\|t\PP;{}$\6 +${}\|t\MG\\{vert}\K\|v;{}$\6 +${}\|v\MG\\{taken}\K\T{1};{}$\6 +\&{if} ${}(\|v\E\|z){}$\5 +${}\{{}$\1\6 +\&{if} ${}(\|t\E\\{tmax}){}$\1\5 +\X9:Record a solution\X;\2\6 +\&{goto} \\{backtrack};\6 +\4${}\}{}$\2\6 +\&{for} ${}(\\{aa}\K\|v\MG\\{arcs},\39\|y\K\NULL;{}$ \\{aa}; ${}\\{aa}\K\\{aa}% +\MG\\{next}){}$\5 +${}\{{}$\1\6 +${}\|u\K\\{aa}\MG\\{tip};{}$\6 +${}\|d\K\|u\MG\\{deg}-\T{1};{}$\6 +\&{if} ${}(\|d\E\T{1}\W\|u\MG\\{taken}\E\T{0}){}$\5 +${}\{{}$\1\6 +\&{if} (\|y)\1\5 +\&{goto} \\{restore};\C{ restoration will stop at \PB{\\{aa}} }\2\6 +${}\|y\K\|u;{}$\6 +\4${}\}{}$\2\6 +${}\|u\MG\\{deg}\K\|d;{}$\6 +\4${}\}{}$\2\6 +\&{if} (\|y)\5 +${}\{{}$\1\6 +${}\|t\MG\\{ark}\K\NULL;{}$\6 +${}\|v\K\|y;{}$\6 +\&{goto} \\{advance};\6 +\4${}\}{}$\2\6 +${}\|a\K\|v\MG\\{arcs}{}$;\par +\U4. +\mini +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +\[1 \\{aa} \&{register} \&{Arc} ${}{*}{}$ +\[4 \\{advance} label +\]{GB\_\,GRAPH}9 \\{arcs} \&{Arc} ${}{*}{}$ +\[4 \\{ark} =\|x.\|A +\[4 \\{backtrack} label +\[1 \|{d} \&{register} \&{int} +\[1 \\{deg} =\|u.\|I +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\[4 \\{restore} label +\[1 \|{t} \&{register} \&{Vertex} ${}{*}{}$ +\[3 \\{taken} =\|v.\|I +\]{GB\_\,GRAPH}10 \\{tip} \&{Vertex} ${}{*}{}$ +\[1 \\{tmax} \&{Vertex} ${}{*}{}$ +\[1 \|{u} \&{register} \&{Vertex} ${}{*}{}$ +\[1 \|{v} \&{register} \&{Vertex} ${}{*}{}$ +\[4 \\{vert} =\|w.\|V +\[1 \|{y} \&{Vertex} ${}{*}{}$ +\[1 \|{z} \&{Vertex} ${}{*}{}$ +}\FI + +\M{6} +\B\X6:Downdate the data structures to the state they were in when level \PB{% +\|t} was entered\X${}\E{}$\6 +\&{for} ${}(\|a\K\|t\MG\\{vert}\MG\\{arcs};{}$ ${}\|a\I\\{aa};{}$ ${}\|a\K\|a% +\MG\\{next}){}$\1\5 +${}\|a\MG\\{tip}\MG\\{deg}\PP{}$;\2\par +\U4. +\mini +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +\[1 \\{aa} \&{register} \&{Arc} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \\{arcs} \&{Arc} ${}{*}{}$ +\[1 \\{deg} =\|u.\|I +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\[1 \|{t} \&{register} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}10 \\{tip} \&{Vertex} ${}{*}{}$ +\[4 \\{vert} =\|w.\|V +}\FI + +\M{7} +\B\X7:Look at edge \PB{\|a} and its successors, advancing if it is a valid move% +\X${}\E{}$\6 +\&{while} (\|a)\5 +${}\{{}$\1\6 +${}\|v\K\|a\MG\\{tip};{}$\6 +\&{if} ${}(\|v\MG\\{taken}\E\T{0}){}$\5 +${}\{{}$\1\6 +${}\|t\MG\\{ark}\K\|a;{}$\6 +\&{goto} \\{advance};\6 +\4${}\}{}$\2\6 +${}\|a\K\|a\MG\\{next};{}$\6 +\4${}\}{}$\2\6 +\4\\{restore\_all}:\5 +${}\\{aa}\K\NULL{}$;\C{ all moves tried; we fall through to \PB{\\{restore}} }% +\par +\U4. +\mini +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +\[1 \\{aa} \&{register} \&{Arc} ${}{*}{}$ +\[4 \\{advance} label +\[4 \\{ark} =\|x.\|A +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\[4 \\{restore} label +\[1 \|{t} \&{register} \&{Vertex} ${}{*}{}$ +\[3 \\{taken} =\|v.\|I +\]{GB\_\,GRAPH}10 \\{tip} \&{Vertex} ${}{*}{}$ +\[1 \|{v} \&{register} \&{Vertex} ${}{*}{}$ +}\FI + +\M{8} +\B\X8:Decrease \PB{\|t}, if possible, and try the next possibility; or \PB{% +\&{goto} \\{done}}\X${}\E{}$\6 +$\|t\MG\\{vert}\MG\\{taken}\K\T{0};{}$\6 +${}\|t\MM;{}$\6 +\&{if} ${}(\|t\MG\\{ark}){}$\5 +${}\{{}$\1\6 +${}\|a\K\|t\MG\\{ark}\MG\\{next};{}$\6 +\&{goto} \\{try\_next};\6 +\4${}\}{}$\2\6 +\&{if} ${}(\|t\E\|g\MG\\{vertices}){}$\1\5 +\&{goto} \\{done};\2\6 +\&{goto} \\{restore\_all};\C{ the move was forced }\par +\U4. +\mini +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +\[4 \\{ark} =\|x.\|A +\[4 \\{done} label +\[1 \|{g} \&{Graph} ${}{*}{}$ +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\[7 \\{restore\_all} label +\[1 \|{t} \&{register} \&{Vertex} ${}{*}{}$ +\[3 \\{taken} =\|v.\|I +\[4 \\{try\_next} label +\[4 \\{vert} =\|w.\|V +\]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ +}\FI + +\M{9} +\B\X9:Record a solution\X${}\E{}$\6 +${}\{{}$\1\6 +${}\\{count}\PP;{}$\6 +\&{if} ${}(\\{count}\MOD\\{modulus}\E\T{0}){}$\5 +${}\{{}$\1\6 +${}\\{printf}(\.{"\%d:\ "},\39\\{count});{}$\6 +\&{for} ${}(\|u\K\|g\MG\\{vertices};{}$ ${}\|u\Z\\{tmax};{}$ ${}\|u\PP){}$\1\5 +${}\\{printf}(\.{"\%s\ "},\39\|u\MG\\{vert}\MG\\{name});{}$\2\6 +\\{printf}(\.{"\\n"});\6 +\4${}\}{}$\2\6 +\4${}\}{}$\2\par +\U5. +\mini +\[1 \\{count} \&{int} +\[1 \|{g} \&{Graph} ${}{*}{}$ +\[1 \\{modulus} \&{int} +\]{GB\_\,GRAPH}9 \\{name} \&{char} ${}{*}{}$ +\]"<stdio.h>" \\{printf} \zip +\[1 \\{tmax} \&{Vertex} ${}{*}{}$ +\[1 \|{u} \&{register} \&{Vertex} ${}{*}{}$ +\[4 \\{vert} =\|w.\|V +\]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ +}\FI + +\inx +\fin +\con diff --git a/Build/source/texk/web2c/cwebdir/tests/ham.aux b/Build/source/texk/web2c/cwebdir/tests/ham.aux new file mode 100644 index 00000000000..f7e08b75c58 --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/ham.aux @@ -0,0 +1,29 @@ +@$deg {HAM}1 =\|u.\|I@> +@$argc {HAM}1 \&{int}@> +@$argv {HAM}1 \&{char} ${}{*}[\,]{}$@> +@$main {HAM}1 \&{int} (\,)@> +@$g {HAM}1 \&{Graph} ${}{*}{}$@> +@$x {HAM}1 \&{Vertex} ${}{*}{}$@> +@$y {HAM}1 \&{Vertex} ${}{*}{}$@> +@$z {HAM}1 \&{Vertex} ${}{*}{}$@> +@$tmax {HAM}1 \&{Vertex} ${}{*}{}$@> +@$t {HAM}1 \&{register} \&{Vertex} ${}{*}{}$@> +@$u {HAM}1 \&{register} \&{Vertex} ${}{*}{}$@> +@$v {HAM}1 \&{register} \&{Vertex} ${}{*}{}$@> +@$a {HAM}1 \&{register} \&{Arc} ${}{*}{}$@> +@$aa {HAM}1 \&{register} \&{Arc} ${}{*}{}$@> +@$d {HAM}1 \&{register} \&{int}@> +@$b {HAM}1 \&{Arc} ${}{*}{}$@> +@$bb {HAM}1 \&{Arc} ${}{*}{}$@> +@$count {HAM}1 \&{int}@> +@$dmin {HAM}1 \&{int}@> +@$modulus {HAM}1 \&{int}@> +@$taken {HAM}3 =\|v.\|I@> +@$vert {HAM}4 =\|w.\|V@> +@$ark {HAM}4 =\|x.\|A@> +@$advance {HAM}4 label@> +@$try_next {HAM}4 label@> +@$restore {HAM}4 label@> +@$backtrack {HAM}4 label@> +@$done {HAM}4 label@> +@$restore_all {HAM}7 label@> diff --git a/Build/source/texk/web2c/cwebdir/tests/ham.bux b/Build/source/texk/web2c/cwebdir/tests/ham.bux new file mode 100644 index 00000000000..85f62380ec3 --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/ham.bux @@ -0,0 +1,2 @@ +@i gb_graph.hux +@i gb_save.hux diff --git a/Build/source/texk/web2c/cwebdir/tests/ham.ch b/Build/source/texk/web2c/cwebdir/tests/ham.ch new file mode 100644 index 00000000000..52871477779 --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/ham.ch @@ -0,0 +1,112 @@ +Limbo. + +@x l.1 +\datethis +@s try x +@y +\datethis +\def\title{HAM} +@z + +Section 1. + +@x l.15 +@d deg u.I +@y +@d deg u.I +@-deg@> +@$deg {HAM}1 =\|u.\|I@> +@% +@$u {GB\_\,GRAPH}9 \&{util}@> +@z + +@x l.21 +main(int argc,char *argv[]) +@y +@#@;@q Fix a bug in CWEB/CTWILL 4.3 @> +int main(int argc,char *argv[]) +@z + +@x l.33 + for (v=g->vertices;v<g->vertices+g->n;v++) printf(" %d",v->deg); +@y + for (v=g->vertices;v<g->vertices+g->n;v++) printf(" %ld",v->deg); +@z + +@x l.36 + printf("The minimum degree is %d (vertex %s)!\n",x->deg,x->name); +@y + printf("The minimum degree is %ld (vertex %s)!\n",x->deg,x->name); +@z + +@x l.46 + for (v=g->vertices;v<g->vertices+g->n;v++) printf(" %d",v->deg); +@y + for (v=g->vertices;v<g->vertices+g->n;v++) printf(" %ld",v->deg); +@z + +Section 2. + +@x l.50 +@ @<Process the command line, inputting the graph@>= +@y +@r @ @<Process the command line, inputting the graph@>= +@z + +Section 3. + +@x +@ Vertices that have already appeared in the path are ``taken,'' and +@y +@ Vertices that have already appeared in the path are ``taken,'' and +@-taken@> +@$taken {HAM}3 =\|v.\|I@> +@% +@$v {HAM}1 \&{register} \&{Vertex} ${}{*}{}$@> +@$v {GB\_\,GRAPH}9 \&{util}@> +@$I {GB\_\,GRAPH}8 \&{long}@> +@z + +Section 4. + +@x l.85 +I may learn my lesson. +@y +I may learn my lesson. +@-k@> +@-vert@> +@-ark@> +@$vert {HAM}4 =\|w.\|V@> +@$ark {HAM}4 =\|x.\|A@> +@% +@$w {GB\_\,GRAPH}9 \&{util}@> +@$x {GB\_\,GRAPH}9 \&{util}@> +@$x {HAM}1 \&{register} \&{Vertex} ${}{*}{}$@> +@z + +@x l.92 +x->taken=1;@+t->vert=x; +@y +x->taken=1;@+t->vert=x;@+ +@z + +@x l.97 +try: @<Look at edge |a| and its successors, advancing if it is a valid move@>; +@y +try_next: @<Look at edge |a| and its successors, advancing if it is a valid move@>; +@z + +Section 8. + +@x l.148 + goto try; +@y + goto try_next; +@z + +Section 10. + +@x l.163 +@*Index. +@y +@z diff --git a/Build/source/texk/web2c/cwebdir/tests/ham.idx b/Build/source/texk/web2c/cwebdir/tests/ham.idx new file mode 100644 index 00000000000..bee85184c3e --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/ham.idx @@ -0,0 +1,43 @@ +\I\|{a}, \[1]. +\I\\{aa}, \[1], 5, 6, 7. +\I\\{advance}, \[4], 5, 7. +\I\&{Arc}, 1. +\I\\{arcs}, 1, 3, 5, 6. +\I\\{argc}, \[1], 2. +\I\\{argv}, \[1], 2. +\I\\{ark}, \[4], 5, 7, 8. +\I\|{b}, \[1]. +\I\\{backtrack}, \[4], 5. +\I\\{bb}, \[1]. +\I\\{count}, \[1], 9. +\I\|{d}, \[1]. +\I\\{deg}, \[1], 3, 5, 6. +\I\\{dmin}, \[1], 3. +\I\\{done}, \[4], 8. +\I\\{exit}, 2. +\I\\{fprintf}, 2. +\I\|{g}, \[1]. +\I\&{Graph}, 1. +\I\\{main}, \[1]. +\I\\{modulus}, \[1], 2, 9. +\I\\{name}, 1, 9. +\I\\{next}, 1, 3, 5, 6, 7, 8. +\I\\{printf}, 1, 9. +\I\\{restore}, \[4], 5, 7. +\I\\{restore_all}, \[7], 8. +\I\\{restore_graph}, 1, 2. +\I\\{sscanf}, 2. +\I\\{stderr}, 2. +\I\|{t}, \[1]. +\I\\{taken}, \[3], 4, 5, 7, 8. +\I\\{tip}, 1, 5, 6, 7. +\I\\{tmax}, \[1], 4, 5, 9. +\I\\{try_next}, \[4], 8. +\I\|{u}, \[1]. +\I\|{v}, \[1]. +\I\\{vert}, \[4], 5, 6, 8, 9. +\I\&{Vertex}, 1. +\I\\{vertices}, 1, 3, 4, 8, 9. +\I\|{x}, \[1]. +\I\|{y}, \[1]. +\I\|{z}, \[1]. diff --git a/Build/source/texk/web2c/cwebdir/tests/ham.ref b/Build/source/texk/web2c/cwebdir/tests/ham.ref new file mode 100644 index 00000000000..f628122b0e1 --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/ham.ref @@ -0,0 +1,47 @@ +!3 ++ \]{GB\_\,GRAPH}9 \|{u} \&{util} ++ \]{GB\_\,GRAPH}10 \\{tip} \&{Vertex} ${}{*}{}$ ++ \]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ ++ \]{GB\_\,GRAPH}9 \\{arcs} \&{Arc} ${}{*}{}$ ++ \]{GB\_\,GRAPH}9 \\{name} \&{char} ${}{*}{}$ ++ \]"<stdio.h>" \\{printf} \zip ++ \]{GB\_\,GRAPH}20 \|{n} \&{long} ++ \]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ ++ \]{GB\_\,GRAPH}10 \&{Arc} =\&{struct} ++ \]{GB\_\,GRAPH}9 \&{Vertex} =\&{struct} ++ \]{GB\_\,GRAPH}20 \&{Graph} =\&{struct} ++ \]{GB\_\,SAVE}4 \\{restore\_graph} \&{Graph} ${}{*}(\,){}$ ++ \]{GB\_\,GRAPH}8 \|{I} \&{long} ++ \]{GB\_\,GRAPH}20 \|{m} \&{long} ++ \]"<stdlib.h>" \\{exit} \zip ++ \]"<stdio.h>" \\{stderr} \zip ++ \]"<stdio.h>" \\{fprintf} \zip ++ \]"<stdio.h>" \\{sscanf} \zip ++ \]{GB\_\,GRAPH}9 \|{v} \&{util} +!5 ++ \[1 \|{x} \&{register} \&{Vertex} ${}{*}{}$ ++ \[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ ++ \[1 \|{z} \&{Vertex} ${}{*}{}$ ++ \[1 \|{v} \&{register} \&{Vertex} ${}{*}{}$ ++ \[3 \\{taken} =\|v.\|I ++ \[1 \\{tmax} \&{Vertex} ${}{*}{}$ ++ \[1 \|{t} \&{register} \&{Vertex} ${}{*}{}$ ++ \[1 \|{g} \&{Graph} ${}{*}{}$ ++ \[1 \\{deg} =\|u.\|I ++ \[1 \|{d} \&{register} \&{int} ++ \[1 \|{u} \&{register} \&{Vertex} ${}{*}{}$ ++ \[1 \|{y} \&{Vertex} ${}{*}{}$ ++ \[1 \\{aa} \&{register} \&{Arc} ${}{*}{}$ ++ \[1 \\{modulus} \&{int} ++ \[1 \\{count} \&{int} ++ \]{GB\_\,GRAPH}9 \|{x} \&{util} ++ \]{GB\_\,GRAPH}9 \|{w} \&{util} ++ \]{GB\_\,GRAPH}20 \|{n} \&{long} ++ \]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ ++ \]{GB\_\,GRAPH}8 \|{A} \&{Arc} ${}{*}{}$ ++ \]{GB\_\,GRAPH}8 \|{V} \&{Vertex} ${}{*}{}$ ++ \]{GB\_\,GRAPH}10 \\{tip} \&{Vertex} ${}{*}{}$ ++ \]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ ++ \]{GB\_\,GRAPH}9 \\{arcs} \&{Arc} ${}{*}{}$ ++ \]{GB\_\,GRAPH}9 \\{name} \&{char} ${}{*}{}$ ++ \]"<stdio.h>" \\{printf} \zip diff --git a/Build/source/texk/web2c/cwebdir/tests/ham.scn b/Build/source/texk/web2c/cwebdir/tests/ham.scn new file mode 100644 index 00000000000..ba6d99d45f4 --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/ham.scn @@ -0,0 +1,23 @@ +\I\X8:Decrease \PB{\|t}, if possible, and try the next possibility; or \PB{% +\&{goto} \\{done}}\X +\U4. +\I\X6:Downdate the data structures to the state they were in when level \PB{% +\|t} was entered\X +\U4. +\I\X4:Find all simple paths of length \PB{$\|g\MG\|n-\T{2}$} from \PB{\|v} to % +\PB{\|z}, avoiding \PB{\|x}\X +\U1. +\I\X5:Increase \PB{\|t} and update the data structures to show that vertex \PB{% +\|v} is now taken; \PB{\&{goto} \\{backtrack}} if no further moves are possible% +\X +\U4. +\I\X7:Look at edge \PB{\|a} and its successors, advancing if it is a valid move% +\X +\U4. +\I\X3:Prepare \PB{\|g} for backtracking, and find a vertex \PB{\|x} of minimum +degree\X +\U1. +\I\X2:Process the command line, inputting the graph\X +\U1. +\I\X9:Record a solution\X +\U5. diff --git a/Build/source/texk/web2c/cwebdir/tests/ham.sref b/Build/source/texk/web2c/cwebdir/tests/ham.sref new file mode 100644 index 00000000000..60732fec54c --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/ham.sref @@ -0,0 +1,47 @@ +\]{GB\_\,GRAPH}10 \&{Arc} =\&{struct} +\]{GB\_\,GRAPH}9 \\{arcs} \&{Arc} ${}{*}{}$ +\]"<stdlib.h>" \\{exit} \zip +\]"<stdio.h>" \\{fprintf} \zip +\]{GB\_\,GRAPH}20 \&{Graph} =\&{struct} +\]{GB\_\,GRAPH}8 \|{I} \&{long} +\]{GB\_\,GRAPH}20 \|{m} \&{long} +\]{GB\_\,GRAPH}20 \|{n} \&{long} +\]{GB\_\,GRAPH}9 \\{name} \&{char} ${}{*}{}$ +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\]"<stdio.h>" \\{printf} \zip +\]{GB\_\,SAVE}4 \\{restore\_graph} \&{Graph} ${}{*}(\,){}$ +\]"<stdio.h>" \\{sscanf} \zip +\]"<stdio.h>" \\{stderr} \zip +\]{GB\_\,GRAPH}10 \\{tip} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \|{u} \&{util} +\]{GB\_\,GRAPH}9 \|{v} \&{util} +\]{GB\_\,GRAPH}9 \&{Vertex} =\&{struct} +\]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ +\donewithpage3 +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +\]{GB\_\,GRAPH}8 \|{A} \&{Arc} ${}{*}{}$ +\[1 \\{aa} \&{register} \&{Arc} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \\{arcs} \&{Arc} ${}{*}{}$ +\[1 \\{count} \&{int} +\[1 \|{d} \&{register} \&{int} +\[1 \\{deg} =\|u.\|I +\[1 \|{g} \&{Graph} ${}{*}{}$ +\[1 \\{modulus} \&{int} +\]{GB\_\,GRAPH}20 \|{n} \&{long} +\]{GB\_\,GRAPH}9 \\{name} \&{char} ${}{*}{}$ +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\]"<stdio.h>" \\{printf} \zip +\[1 \|{t} \&{register} \&{Vertex} ${}{*}{}$ +\[3 \\{taken} =\|v.\|I +\]{GB\_\,GRAPH}10 \\{tip} \&{Vertex} ${}{*}{}$ +\[1 \\{tmax} \&{Vertex} ${}{*}{}$ +\[1 \|{u} \&{register} \&{Vertex} ${}{*}{}$ +\[1 \|{v} \&{register} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}8 \|{V} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \|{w} \&{util} +\[1 \|{x} \&{register} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \|{x} \&{util} +\[1 \|{y} \&{Vertex} ${}{*}{}$ +\[1 \|{z} \&{Vertex} ${}{*}{}$ +\donewithpage5 diff --git a/Build/source/texk/web2c/cwebdir/tests/ham.tex b/Build/source/texk/web2c/cwebdir/tests/ham.tex new file mode 100644 index 00000000000..923e90aa6e0 --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/ham.tex @@ -0,0 +1,366 @@ +\input ctwimac +\datethis +\def\title{HAM} + + + + +\N{1}{1} +Hamiltonian cycles. This program finds all Hamiltonian cycles of +an undirected graph. [It's a slight revision of the program published +in my paper ``Mini-indexes for literate programs,'' {\sl Software---Concepts +and Tools\/ \bf15} (1994), 2--11.] The input graph should be in +Stanford GraphBase format, and should be named on the command line +as, for example, \.{foo.gb}. An optional second command-line parameter +is a modulus \PB{\|m}, which causes every $m$th solution to be printed. + +We use a utility field to record the vertex degrees. + +\Y\B\4\D$\\{deg}$ \5 +$\|u.{}$\|I\par +\Y\B\8\#\&{include} \.{"gb\_graph.h"}\C{ the GraphBase data structures }\6 +\8\#\&{include} \.{"gb\_save.h"}\C{ \PB{\\{restore\_graph}} }\7 +\1\1\&{int} \\{main}(\&{int} \\{argc}${},\39{}$\&{char} ${}{*}\\{argv}[\,])\2% +\2{}$\6 +${}\{{}$\1\6 +\&{Graph} ${}{*}\|g;{}$\6 +\&{Vertex} ${}{*}\|x,\39{*}\|y,\39{*}\|z,\39{*}\\{tmax};{}$\6 +\&{register} \&{Vertex} ${}{*}\|t,\39{*}\|u,\39{*}\|v;{}$\6 +\&{register} \&{Arc} ${}{*}\|a,\39{*}\\{aa};{}$\6 +\&{register} \&{int} \|d;\6 +\&{Arc} ${}{*}\|b,\39{*}\\{bb};{}$\6 +\&{int} \\{count}${}\K\T{0};{}$\6 +\&{int} \\{dmin}${},\39\\{modulus};{}$\7 +\X2:Process the command line, inputting the graph\X;\6 +\X3:Prepare \PB{\|g} for backtracking, and find a vertex \PB{\|x} of minimum +degree\X;\6 +\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$ +${}\|v\PP){}$\1\5 +${}\\{printf}(\.{"\ \%ld"},\39\|v\MG\\{deg});{}$\2\6 +\\{printf}(\.{"\\n"});\C{ TEMPORARY CHECK }\6 +\&{if} ${}(\|x\MG\\{deg}<\T{2}){}$\5 +${}\{{}$\1\6 +${}\\{printf}(\.{"The\ minimum\ degree\ }\)\.{is\ \%ld\ (vertex\ \%s)!\\}\)% +\.{n"},\39\|x\MG\\{deg},\39\|x\MG\\{name});{}$\6 +\&{return} ${}{-}\T{1};{}$\6 +\4${}\}{}$\2\6 +\&{for} ${}(\|b\K\|x\MG\\{arcs};{}$ ${}\|b\MG\\{next};{}$ ${}\|b\K\|b\MG% +\\{next}){}$\1\6 +\&{for} ${}(\\{bb}\K\|b\MG\\{next};{}$ \\{bb}; ${}\\{bb}\K\\{bb}\MG\\{next}){}$% +\5 +${}\{{}$\1\6 +${}\|v\K\|b\MG\\{tip};{}$\6 +${}\|z\K\\{bb}\MG\\{tip};{}$\6 +\X4:Find all simple paths of length \PB{$\|g\MG\|n-\T{2}$} from \PB{\|v} to % +\PB{\|z}, avoiding \PB{\|x}\X;\6 +\4${}\}{}$\2\2\6 +${}\\{printf}(\.{"Altogether\ \%d\ solut}\)\.{ions.\\n"},\39\\{count});{}$\6 +\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$ +${}\|v\PP){}$\1\5 +${}\\{printf}(\.{"\ \%ld"},\39\|v\MG\\{deg});{}$\2\6 +\\{printf}(\.{"\\n"});\C{ TEMPORARY CHECK, SHOULD AGREE WITH FORMER VALUES }\6 +\4${}\}{}$\2\par +\mini +\]{GB\_\,GRAPH}9 \|{u} \&{util} +\]{GB\_\,GRAPH}10 \\{tip} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \\{arcs} \&{Arc} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \\{name} \&{char} ${}{*}{}$ +\]"<stdio.h>" \\{printf} \zip +\]{GB\_\,GRAPH}20 \|{n} \&{long} +\]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}10 \&{Arc} =\&{struct} +\]{GB\_\,GRAPH}9 \&{Vertex} =\&{struct} +\]{GB\_\,GRAPH}20 \&{Graph} =\&{struct} +\]{GB\_\,SAVE}4 \\{restore\_graph} \&{Graph} ${}{*}(\,){}$ +\]{GB\_\,GRAPH}8 \|{I} \&{long} +\]{GB\_\,GRAPH}20 \|{m} \&{long} +}\FI + +\shortpage +\M{2} +\B\X2:Process the command line, inputting the graph\X${}\E{}$\6 +\&{if} ${}(\\{argc}>\T{1}){}$\1\5 +${}\|g\K\\{restore\_graph}(\\{argv}[\T{1}]){}$;\5 +\2\&{else}\1\5 +${}\|g\K\NULL;{}$\2\6 +\&{if} ${}(\\{argc}<\T{3}\V\\{sscanf}(\\{argv}[\T{2}],\39\.{"\%d"},\39{\AND}% +\\{modulus})\I\T{1}){}$\1\5 +${}\\{modulus}\K\T{1000000000};{}$\2\6 +\&{if} ${}(\R\|g\V\\{modulus}\Z\T{0}){}$\5 +${}\{{}$\1\6 +${}\\{fprintf}(\\{stderr},\39\.{"Usage:\ \%s\ foo.gb\ [m}\)\.{odulus]\\n"},\39% +\\{argv}[\T{0}]);{}$\6 +${}\\{exit}({-}\T{1});{}$\6 +\4${}\}{}$\2\par +\U1. +\mini +\]"<stdlib.h>" \\{exit} \zip +\]"<stdio.h>" \\{stderr} \zip +\]"<stdio.h>" \\{fprintf} \zip +\[1 \\{modulus} \&{int} +\]"<stdio.h>" \\{sscanf} \zip +\[1 \\{argv} \&{char} ${}{*}[\,]{}$ +\]{GB\_\,SAVE}4 \\{restore\_graph} \&{Graph} ${}{*}(\,){}$ +\[1 \|{g} \&{Graph} ${}{*}{}$ +\[1 \\{argc} \&{int} +}\FI + +\M{3} +Vertices that have already appeared in the path are ``taken,'' and +their \PB{\\{taken}} field is nonzero. Initially we make all those fields zero. + +\Y\B\4\D$\\{taken}$ \5 +$\|v.{}$\|I\par +\Y\B\4\X3:Prepare \PB{\|g} for backtracking, and find a vertex \PB{\|x} of +minimum degree\X${}\E{}$\6 +$\\{dmin}\K\|g\MG\|n;{}$\6 +\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$ +${}\|v\PP){}$\5 +${}\{{}$\1\6 +${}\|v\MG\\{taken}\K\T{0};{}$\6 +${}\|d\K\T{0};{}$\6 +\&{for} ${}(\|a\K\|v\MG\\{arcs};{}$ \|a; ${}\|a\K\|a\MG\\{next}){}$\1\5 +${}\|d\PP;{}$\2\6 +${}\|v\MG\\{deg}\K\|d;{}$\6 +\&{if} ${}(\|d<\\{dmin}){}$\1\5 +${}\\{dmin}\K\|d,\39\|x\K\|v;{}$\2\6 +\4${}\}{}$\2\par +\U1. +\mini +\]{GB\_\,GRAPH}8 \|{I} \&{long} +\]{GB\_\,GRAPH}9 \|{v} \&{util} +\[1 \|{v} \&{register} \&{Vertex} ${}{*}{}$ +\[1 \|{x} \&{Vertex} ${}{*}{}$ +\[1 \\{deg} =\|u.\|I +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \\{arcs} \&{Arc} ${}{*}{}$ +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +\[1 \|{d} \&{register} \&{int} +\]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}20 \|{n} \&{long} +\[1 \|{g} \&{Graph} ${}{*}{}$ +\[1 \\{dmin} \&{int} +}\FI + +\N{1}{4} +The data structures. I use one simple rule to cut off unproductive +branches of the search tree: If one of the vertices we could move to next +is adjacent to only one other unused vertex, we must move to it now. + +The moves will be recorded in the vertex array of \PB{\|g}. More precisely, the +\PB{\|k}th vertex of the path will be \PB{$\|t\MG\\{vert}$} when \PB{\|t} is +the \PB{\|k}th vertex of +the graph. If the move was not forced, \PB{$\|t\MG\\{ark}$} will point to the +Arc +record representing the edge from \PB{$\|t\MG\\{vert}$} to \PB{$(\|t+\T{1})\MG% +\\{vert}$}; otherwise +\PB{$\|t\MG\\{ark}$} will be \PB{$\NULL$}. + +This program is a typical backtrack program. I am more comfortable doing +it with labels and goto statements than with while loops, but some day +I may learn my lesson. + +\Y\B\4\D$\\{vert}$ \5 +$\|w.{}$\|V\par +\B\4\D$\\{ark}$ \5 +$\|x.{}$\|A\par +\Y\B\4\X4:Find all simple paths of length \PB{$\|g\MG\|n-\T{2}$} from \PB{\|v} +to \PB{\|z}, avoiding \PB{\|x}\X${}\E{}$\6 +$\|t\K\|g\MG\\{vertices}{}$;\5 +${}\\{tmax}\K\|t+\|g\MG\|n-\T{1};{}$\6 +${}\|x\MG\\{taken}\K\T{1}{}$;\5 +${}\|t\MG\\{vert}\K\|x{}$;\5 +${}\|t\MG\\{ark}\K\NULL;{}$\6 +\4\\{advance}:\5 +\X5:Increase \PB{\|t} and update the data structures to show that vertex \PB{% +\|v} is now taken; \PB{\&{goto} \\{backtrack}} if no further moves are possible% +\X;\6 +\4\\{try\_next}:\5 +\X7:Look at edge \PB{\|a} and its successors, advancing if it is a valid move% +\X;\6 +\4\\{restore}:\5 +\X6:Downdate the data structures to the state they were in when level \PB{\|t} +was entered\X;\6 +\4\\{backtrack}:\5 +\X8:Decrease \PB{\|t}, if possible, and try the next possibility; or \PB{% +\&{goto} \\{done}}\X;\6 +\\{done}:\par +\U1. +\mini +\[1 \|{x} \&{register} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \|{x} \&{util} +\]{GB\_\,GRAPH}9 \|{w} \&{util} +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +\[1 \|{z} \&{Vertex} ${}{*}{}$ +\[1 \|{v} \&{register} \&{Vertex} ${}{*}{}$ +\[3 \\{taken} =\|v.\|I +\]{GB\_\,GRAPH}20 \|{n} \&{long} +\[1 \\{tmax} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}8 \|{A} \&{Arc} ${}{*}{}$ +\]{GB\_\,GRAPH}8 \|{V} \&{Vertex} ${}{*}{}$ +\[1 \|{t} \&{register} \&{Vertex} ${}{*}{}$ +\[1 \|{g} \&{Graph} ${}{*}{}$ +}\FI + +\M{5} +\B\X5:Increase \PB{\|t} and update the data structures to show that vertex \PB{% +\|v} is now taken; \PB{\&{goto} \\{backtrack}} if no further moves are possible% +\X${}\E{}$\6 +$\|t\PP;{}$\6 +${}\|t\MG\\{vert}\K\|v;{}$\6 +${}\|v\MG\\{taken}\K\T{1};{}$\6 +\&{if} ${}(\|v\E\|z){}$\5 +${}\{{}$\1\6 +\&{if} ${}(\|t\E\\{tmax}){}$\1\5 +\X9:Record a solution\X;\2\6 +\&{goto} \\{backtrack};\6 +\4${}\}{}$\2\6 +\&{for} ${}(\\{aa}\K\|v\MG\\{arcs},\39\|y\K\NULL;{}$ \\{aa}; ${}\\{aa}\K\\{aa}% +\MG\\{next}){}$\5 +${}\{{}$\1\6 +${}\|u\K\\{aa}\MG\\{tip};{}$\6 +${}\|d\K\|u\MG\\{deg}-\T{1};{}$\6 +\&{if} ${}(\|d\E\T{1}\W\|u\MG\\{taken}\E\T{0}){}$\5 +${}\{{}$\1\6 +\&{if} (\|y)\1\5 +\&{goto} \\{restore};\C{ restoration will stop at \PB{\\{aa}} }\2\6 +${}\|y\K\|u;{}$\6 +\4${}\}{}$\2\6 +${}\|u\MG\\{deg}\K\|d;{}$\6 +\4${}\}{}$\2\6 +\&{if} (\|y)\5 +${}\{{}$\1\6 +${}\|t\MG\\{ark}\K\NULL;{}$\6 +${}\|v\K\|y;{}$\6 +\&{goto} \\{advance};\6 +\4${}\}{}$\2\6 +${}\|a\K\|v\MG\\{arcs}{}$;\par +\U4. +\mini +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +\[4 \\{advance} label +\[4 \\{ark} =\|x.\|A +\[4 \\{restore} label +\[1 \\{deg} =\|u.\|I +\[1 \|{d} \&{register} \&{int} +\]{GB\_\,GRAPH}10 \\{tip} \&{Vertex} ${}{*}{}$ +\[1 \|{u} \&{register} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\[1 \|{y} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \\{arcs} \&{Arc} ${}{*}{}$ +\[1 \\{aa} \&{register} \&{Arc} ${}{*}{}$ +\[4 \\{backtrack} label +\[1 \\{tmax} \&{Vertex} ${}{*}{}$ +\[1 \|{z} \&{Vertex} ${}{*}{}$ +\[3 \\{taken} =\|v.\|I +\[1 \|{v} \&{register} \&{Vertex} ${}{*}{}$ +\[4 \\{vert} =\|w.\|V +\[1 \|{t} \&{register} \&{Vertex} ${}{*}{}$ +}\FI + +\M{6} +\B\X6:Downdate the data structures to the state they were in when level \PB{% +\|t} was entered\X${}\E{}$\6 +\&{for} ${}(\|a\K\|t\MG\\{vert}\MG\\{arcs};{}$ ${}\|a\I\\{aa};{}$ ${}\|a\K\|a% +\MG\\{next}){}$\1\5 +${}\|a\MG\\{tip}\MG\\{deg}\PP{}$;\2\par +\U4. +\mini +\[1 \\{deg} =\|u.\|I +\]{GB\_\,GRAPH}10 \\{tip} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\[1 \\{aa} \&{register} \&{Arc} ${}{*}{}$ +\]{GB\_\,GRAPH}9 \\{arcs} \&{Arc} ${}{*}{}$ +\[4 \\{vert} =\|w.\|V +\[1 \|{t} \&{register} \&{Vertex} ${}{*}{}$ +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +}\FI + +\M{7} +\B\X7:Look at edge \PB{\|a} and its successors, advancing if it is a valid move% +\X${}\E{}$\6 +\&{while} (\|a)\5 +${}\{{}$\1\6 +${}\|v\K\|a\MG\\{tip};{}$\6 +\&{if} ${}(\|v\MG\\{taken}\E\T{0}){}$\5 +${}\{{}$\1\6 +${}\|t\MG\\{ark}\K\|a;{}$\6 +\&{goto} \\{advance};\6 +\4${}\}{}$\2\6 +${}\|a\K\|a\MG\\{next};{}$\6 +\4${}\}{}$\2\6 +\4\\{restore\_all}:\5 +${}\\{aa}\K\NULL{}$;\C{ all moves tried; we fall through to \PB{\\{restore}} }% +\par +\U4. +\mini +\[4 \\{restore} label +\[1 \\{aa} \&{register} \&{Arc} ${}{*}{}$ +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\[4 \\{advance} label +\[4 \\{ark} =\|x.\|A +\[1 \|{t} \&{register} \&{Vertex} ${}{*}{}$ +\[3 \\{taken} =\|v.\|I +\]{GB\_\,GRAPH}10 \\{tip} \&{Vertex} ${}{*}{}$ +\[1 \|{v} \&{register} \&{Vertex} ${}{*}{}$ +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +}\FI + +\M{8} +\B\X8:Decrease \PB{\|t}, if possible, and try the next possibility; or \PB{% +\&{goto} \\{done}}\X${}\E{}$\6 +$\|t\MG\\{vert}\MG\\{taken}\K\T{0};{}$\6 +${}\|t\MM;{}$\6 +\&{if} ${}(\|t\MG\\{ark}){}$\5 +${}\{{}$\1\6 +${}\|a\K\|t\MG\\{ark}\MG\\{next};{}$\6 +\&{goto} \\{try\_next};\6 +\4${}\}{}$\2\6 +\&{if} ${}(\|t\E\|g\MG\\{vertices}){}$\1\5 +\&{goto} \\{done};\2\6 +\&{goto} \\{restore\_all};\C{ the move was forced }\par +\U4. +\mini +\[7 \\{restore\_all} label +\[4 \\{done} label +\]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ +\[1 \|{g} \&{Graph} ${}{*}{}$ +\[4 \\{try\_next} label +\]{GB\_\,GRAPH}10 \\{next} \&{Arc} ${}{*}{}$ +\[1 \|{a} \&{register} \&{Arc} ${}{*}{}$ +\[4 \\{ark} =\|x.\|A +\[3 \\{taken} =\|v.\|I +\[4 \\{vert} =\|w.\|V +\[1 \|{t} \&{register} \&{Vertex} ${}{*}{}$ +}\FI + +\M{9} +\B\X9:Record a solution\X${}\E{}$\6 +${}\{{}$\1\6 +${}\\{count}\PP;{}$\6 +\&{if} ${}(\\{count}\MOD\\{modulus}\E\T{0}){}$\5 +${}\{{}$\1\6 +${}\\{printf}(\.{"\%d:\ "},\39\\{count});{}$\6 +\&{for} ${}(\|u\K\|g\MG\\{vertices};{}$ ${}\|u\Z\\{tmax};{}$ ${}\|u\PP){}$\1\5 +${}\\{printf}(\.{"\%s\ "},\39\|u\MG\\{vert}\MG\\{name});{}$\2\6 +\\{printf}(\.{"\\n"});\6 +\4${}\}{}$\2\6 +\4${}\}{}$\2\par +\U5. +\mini +\]{GB\_\,GRAPH}9 \\{name} \&{char} ${}{*}{}$ +\[4 \\{vert} =\|w.\|V +\[1 \\{tmax} \&{Vertex} ${}{*}{}$ +\]{GB\_\,GRAPH}20 \\{vertices} \&{Vertex} ${}{*}{}$ +\[1 \|{g} \&{Graph} ${}{*}{}$ +\[1 \|{u} \&{register} \&{Vertex} ${}{*}{}$ +\]"<stdio.h>" \\{printf} \zip +\[1 \\{modulus} \&{int} +\[1 \\{count} \&{int} +}\FI + +\inx +\fin +\con diff --git a/Build/source/texk/web2c/cwebdir/tests/ham.w b/Build/source/texk/web2c/cwebdir/tests/ham.w new file mode 100644 index 00000000000..eb4990bba9c --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/ham.w @@ -0,0 +1,163 @@ +\datethis +@s try x +@i gb_types.w + +@*Hamiltonian cycles. This program finds all Hamiltonian cycles of +an undirected graph. [It's a slight revision of the program published +in my paper ``Mini-indexes for literate programs,'' {\sl Software---Concepts +and Tools\/ \bf15} (1994), 2--11.] The input graph should be in +Stanford GraphBase format, and should be named on the command line +as, for example, \.{foo.gb}. An optional second command-line parameter +is a modulus |m|, which causes every $m$th solution to be printed. + +We use a utility field to record the vertex degrees. + +@d deg u.I + +@c +#include "gb_graph.h" /* the GraphBase data structures */ +#include "gb_save.h" /* |restore_graph| */ + +main(int argc,char *argv[]) +{ + Graph *g; + Vertex *x,*y,*z, *tmax; + register Vertex *t,*u,*v; + register Arc *a,*aa; + register int d; + Arc *b,*bb; + int count=0; + int dmin,modulus; + @<Process the command line, inputting the graph@>; + @<Prepare |g| for backtracking, and find a vertex |x| of minimum degree@>; + for (v=g->vertices;v<g->vertices+g->n;v++) printf(" %d",v->deg); + printf("\n"); /* TEMPORARY CHECK */ + if (x->deg<2) { + printf("The minimum degree is %d (vertex %s)!\n",x->deg,x->name); + return -1; + } + for (b=x->arcs;b->next;b=b->next) for (bb=b->next;bb;bb=bb->next) { + v=b->tip; + z=bb->tip; + @<Find all simple paths of length |g->n-2| from |v| to |z|, + avoiding |x|@>; + } + printf("Altogether %d solutions.\n",count); + for (v=g->vertices;v<g->vertices+g->n;v++) printf(" %d",v->deg); + printf("\n"); /* TEMPORARY CHECK, SHOULD AGREE WITH FORMER VALUES */ +} + +@ @<Process the command line, inputting the graph@>= +if (argc>1) g=restore_graph(argv[1]);@+ else g=NULL; +if (argc<3 || sscanf(argv[2],"%d",&modulus)!=1) modulus=1000000000; +if (!g || modulus<=0) { + fprintf(stderr,"Usage: %s foo.gb [modulus]\n",argv[0]); + exit(-1); +} + +@ Vertices that have already appeared in the path are ``taken,'' and +their |taken| field is nonzero. Initially we make all those fields zero. + +@d taken v.I + +@<Prepare |g| for backtracking, and find a vertex |x| of minimum degree@>= +dmin=g->n; +for (v=g->vertices;v<g->vertices+g->n;v++) { + v->taken=0; + d=0; + for (a=v->arcs;a;a=a->next) d++; + v->deg=d; + if (d<dmin) dmin=d,x=v; +} + +@*The data structures. I use one simple rule to cut off unproductive +branches of the search tree: If one of the vertices we could move to next +is adjacent to only one other unused vertex, we must move to it now. + +The moves will be recorded in the vertex array of |g|. More precisely, the +|k|th vertex of the path will be |t->vert| when |t| is the |k|th vertex of +the graph. If the move was not forced, |t->ark| will point to the Arc +record representing the edge from |t->vert| to |(t+1)->vert|; otherwise +|t->ark| will be |NULL|. + +This program is a typical backtrack program. I am more comfortable doing +it with labels and goto statements than with while loops, but some day +I may learn my lesson. + +@d vert w.V +@d ark x.A + +@<Find all simple paths of length |g->n-2|...@>= +t=g->vertices;@+tmax=t+g->n-1; +x->taken=1;@+t->vert=x; +t->ark=NULL; +advance: @<Increase |t| and update the data structures to show that + vertex |v| is now taken; |goto backtrack| if no further + moves are possible@>; +try: @<Look at edge |a| and its successors, advancing if it is a valid move@>; +restore: @<Downdate the data structures to the state they were in when + level |t| was entered@>; +backtrack: @<Decrease |t|, if possible, and try the next possibility; + or |goto done|@>; +done: + +@ @<Increase |t| and update the data structures...@>= +t++; +t->vert=v; +v->taken=1; +if (v==z) { + if (t==tmax) @<Record a solution@>; + goto backtrack; +} +for (aa=v->arcs,y=NULL;aa;aa=aa->next) { + u=aa->tip; + d=u->deg-1; + if (d==1 && u->taken==0) { + if (y) goto restore; /* restoration will stop at |aa| */ + y=u; + } + u->deg=d; +} +if (y) { + t->ark=NULL; + v=y; + goto advance; +} +a=v->arcs; + +@ @<Downdate the data structures to the state they were in when + level |t| was entered@>= +for (a=t->vert->arcs;a!=aa;a=a->next) a->tip->deg++; + +@ @<Look at edge |a| and its successors, advancing if it is a valid move@>= +while (a) { + v=a->tip; + if (v->taken==0) { + t->ark=a; + goto advance; + } + a=a->next; +} +restore_all: aa=NULL; /* all moves tried; we fall through to |restore| */ + +@ @<Decrease |t|, if possible...@>= +t->vert->taken=0; +t--; +if (t->ark) { + a=t->ark->next; + goto try; +} +if (t==g->vertices) goto done; +goto restore_all; /* the move was forced */ + +@ @<Record a solution@>= +{ + count++; + if (count%modulus==0) { + printf("%d: ",count); + for (u=g->vertices;u<=tmax;u++) printf("%s ",u->vert->name); + printf("\n"); + } +} + +@*Index. diff --git a/Build/source/texk/web2c/cwebdir/tests/system.bux b/Build/source/texk/web2c/cwebdir/tests/system.bux new file mode 100644 index 00000000000..6bf53f045e3 --- /dev/null +++ b/Build/source/texk/web2c/cwebdir/tests/system.bux @@ -0,0 +1,41 @@ +@$memcmp "<string.h>" \zip@> +@$strcat "<string.h>" \zip@> +@$strcmp "<string.h>" \zip@> +@$strcpy "<string.h>" \zip@> +@$strlen "<string.h>" \zip@> +@$strncmp "<string.h>" \zip@> +@$strncpy "<string.h>" \zip@> + +@$BUFSIZ "<stdio.h>" \zip@> +@$fclose "<stdio.h>" \zip@> +@$feof "<stdio.h>" \zip@> +@$fflush "<stdio.h>" \zip@> +@$fopen "<stdio.h>" \zip@> +@$fprintf "<stdio.h>" \zip@> +@$fputs "<stdio.h>" \zip@> +@$fread "<stdio.h>" \zip@> +@$fwrite "<stdio.h>" \zip@> +@$printf "<stdio.h>" \zip@> +@$putc "<stdio.h>" \zip@> +@$putchar "<stdio.h>" \zip@> +@$puts "<stdio.h>" \zip@> +@$rename "<stdio.h>" \zip@> +@$remove "<stdio.h>" \zip@> +@$sprintf "<stdio.h>" \zip@> +@$sscanf "<stdio.h>" \zip@> +@$stdout "<stdio.h>" \zip@> +@$stderr "<stdio.h>" \zip@> + +@$exit "<stdlib.h>" \zip@> + +@$isalpha "<ctype.h>" \zip@> +@$isdigit "<ctype.h>" \zip@> +@$islower "<ctype.h>" \zip@> +@$isspace "<ctype.h>" \zip@> +@$isupper "<ctype.h>" \zip@> +@$isxdigit "<ctype.h>" \zip@> +@$tolower "<ctype.h>" \zip@> +@$toupper "<ctype.h>" \zip@> + +@$gettext "<libintl.h>" \zip@> +@$textdomain "<libintl.h>" \zip@> |