bfzIII.c

   1 /*
   2  * Copyright (c) 2018, S. Gilles <sgilles@math.umd.edu>
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software
   5  * for any purpose with or without fee is hereby granted, provided
   6  * that the above copyright notice and this permission notice appear
   7  * in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
  10  * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
  11  * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
  12  * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
  13  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
  14  * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
  15  * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  16  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18 #include <errno.h>
  19 #include <limits.h>
  20 #include <stdint.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <unistd.h>
  25
  26 #include "macros.h"
  27 #include "quiver.h"
  28
  29 /*
  30  * This is an implementation of the algorithm of Berenstein, Fomin,
  31  * and Zelevinsky from "Cluster Algebras III", which produces quivers
  32  * for the double Bruhat cell G^{u,v}.
  33  */
  34
  35 #define zabs(x)    (((x) < 0) ? -(x) : (x))
  36 #define zabsdiff(x, y) ((x) < (y) ? ((y) - (x)) : ((x) - (y)))
  37 #define zmin(x, y) (((x) < (y)) ? (x) : (y))
  38 #define zmax(x, y) (((x) > (y)) ? (x) : (y))
  39 #define zsgn(x) ((x) < 0 ? -1 : (x) > 0 ? 1 : 0)
  40
  41 /* Which of the Lie classifications we're looking at */
  42 enum dynkin { INVALID, An, Bn, Cn, Dn, G2, F4, E6, E7, E8 };
  43
  44 /* Cartan matrix entry a_{i,j}, given dynkin type. 1-based. */
  45 static int
  46 aij(enum dynkin typ, size_t n, size_t i, size_t j)
  47 {
  48         i--;
  49         j--;
  50         size_t max_idx = (i > j) ? i : j;
  51         size_t k = 0;
  52
  53         switch (typ) {
  54         case INVALID:
  55
  56                 return INT_MAX;
  57                 break;
  58         case An:
  59
  60                 if (max_idx >= n) {
  61                         return INT_MAX;
  62                 } else if (i == j) {
  63                         return 2;
  64                 } else if (zabsdiff(i, j) == 1) {
  65                         return -1;
  66                 }
  67
  68                 return 0;
  69                 break;
  70         case Bn:
  71         case Cn:
  72
  73                 /* TODO: do you have Bn and Cn switched? You always do that */
  74                 if (max_idx >= n) {
  75                         return INT_MAX;
  76                 } else if (i == j) {
  77                         return 2;
  78                 } else if (zabsdiff(i, j) == 1) {
  79                         if (typ == Bn &&
  80                             i == n - 2 &&
  81                             j == n - 1) {
  82                                 return -2;
  83                         } else if (typ == Cn &&
  84                                    i == n - 1 &&
  85                                    j == n - 2) {
  86                                 return -2;
  87                         }
  88
  89                         return -1;
  90                 }
  91
  92                 return 0;
  93                 break;
  94         case Dn:
  95
  96                 if (max_idx >= n) {
  97                         return INT_MAX;
  98                 } else if (i == j) {
  99                         return 2;
 100                 } else if (zabsdiff(i, j) == 1 &&
 101                            i <= n - 2 &&
 102                            j <= n - 2) {
 103                         return -1;
 104                 } else if ((i == n - 3 &&
 105                             j == n - 1) ||
 106                            (i == n - 1 &&
 107                             j == n - 3)) {
 108                         return -1;
 109                 }
 110
 111                 return 0;
 112                 break;
 113         case G2:
 114
 115                 if (max_idx >= 2) {
 116                         return INT_MAX;
 117                 } else if (i == j) {
 118                         return 2;
 119                 } else if (i == 0 &&
 120                            j == 1) {
 121                         return -3;
 122                 } else if (i == 1 &&
 123                            j == 0) {
 124                         return -1;
 125                 }
 126
 127                 return 0;
 128                 break;
 129         case F4:
 130
 131                 if (max_idx >= 4) {
 132                         return INT_MAX;
 133                 } else if (i == j) {
 134                         return 2;
 135                 } else if (i == 1 &&
 136                            j == 2) {
 137                         return -2;
 138                 } else if (zabsdiff(i, j) == 1) {
 139                         return -1;
 140                 }
 141
 142                 return 0;
 143                 break;
 144         case E6:
 145         case E7:
 146         case E8:
 147                 k = (typ == E6) ? 6 : (typ == E7) ? 7 : 8;
 148
 149                 if (max_idx >= k) {
 150                         return INT_MAX;
 151                 } else if (i == j) {
 152                         return 2;
 153                 } else if (zabsdiff(i, j) == 1 &&
 154                            zmax(i, j) >= 3) {
 155                         return -1;
 156                 } else if (zabsdiff(i, j) == 2 &&
 157                            zmin(i, j) <= 1) {
 158                         return -1;
 159                 }
 160
 161                 return 0;
 162                 break;
 163         }
 164
 165         return INT_MAX;
 166 }
 167
 168 const int x_mult = 25;
 169 const int y_mult = 25;
 170
 171 /* Given vertex idx of k, return vertex idx of k⁺ */
 172 static int
 173 find_plus(int k, size_t *u, size_t lu, size_t *v, size_t lv)
 174 {
 175         size_t vk = (size_t) -1;
 176
 177         if (k < 0) {
 178                 vk = -1 * (k + 1);
 179
 180                 for (int j = 1; j <= (int) (lu + lv); ++j) {
 181                         size_t vj = (size_t) -1;
 182
 183                         vj = (j <= (int) lu) ? u[j - 1] : v[j - 1 - lu];
 184
 185                         if (vk == vj) {
 186                                 return j;
 187                         }
 188                 }
 189         } else if (1 <= k &&
 190                    k <= (int) lu) {
 191                 vk = u[k - 1];
 192
 193                 for (int j = k + 1; j <= (int) (lu + lv); ++j) {
 194                         size_t vj = (size_t) -1;
 195
 196                         vj = (j <= (int) lu) ? u[j - 1] : v[j - 1 - lu];
 197
 198                         if (vk == vj) {
 199                                 return j;
 200                         }
 201                 }
 202         } else if ((int) lu + 1 <= k &&
 203                    k <= (int) (lu + lv)) {
 204                 vk = v[k - 1 - lu];
 205
 206                 for (int j = k + 1; j <= (int) (lu + lv); ++j) {
 207                         size_t vj = v[j - 1 - lu];
 208
 209                         if (vk == vj) {
 210                                 return j;
 211                         }
 212                 }
 213         }
 214
 215         return lu + lv + 1;
 216 }
 217
 218 /* Given k in { -1, ..., -r } U { 1, 2, ..., l(u) + l(v) }, return the vertex idx for it */
 219 static size_t
 220 v_of(int k, int r, size_t lu, size_t lv)
 221 {
 222         if (-1 >= k &&
 223             k >= -r) {
 224                 return (-1 * k) - 1;
 225         } else if (1 <= k &&
 226                    k <= (int) (lu + lv)) {
 227                 return k - 1 + r;
 228         }
 229
 230         return (size_t) -1;
 231 }
 232
 233 /* [BFZIII] */
 234 static int
 235 run_bfzIII(struct quiver *qq, enum dynkin typ, size_t r, size_t *u, size_t lu,
 236            size_t *v, size_t lv, int ymult)
 237 {
 238         int ret = -1;
 239         size_t nl = 1 + snprintf(0, 0, "%d%zu", -1 * (int) r, lu + lv);
 240         char *nbuf = 0;
 241         const char *errstr = 0;
 242         size_t x = 0;
 243         int *i = 0;
 244         int *e = 0;
 245         uint32_t c_froz = 0x4ce7ff;
 246         uint32_t c_nonf = 0xad7fa8;
 247         int need_fatness_run = 1;
 248
 249         if (!(nbuf = malloc(nl))) {
 250                 goto done;
 251         }
 252
 253         if (!(i = calloc(r + lu + lv + 1, sizeof *i))) {
 254                 goto done;
 255         }
 256
 257         if (!(e = calloc(r + lu + lv + 1, sizeof *e))) {
 258                 goto done;
 259         }
 260
 261         /* First, add { -1, -2, ..., -r } */
 262         for (int k = -1; k >= -1 * (int) r; k--) {
 263                 size_t vv = v_of(k, r, lu, lv);
 264
 265                 i[vv] = -1 * k;
 266                 sprintf(nbuf, "%d", k);
 267
 268                 if (quiver_add_vertex(qq, 0, nbuf, 1, 50 * x, ymult * 50 *
 269                                       i[vv], c_froz, &errstr) < 0) {
 270                         fprintf(stderr, "%s\n", errstr);
 271                         fprintf(stderr, L("quiver_add_vertex failed\n"));
 272                         goto done;
 273                 }
 274
 275                 x++;
 276         }
 277
 278         /* Now add { 1, 2, ..., u_seq_len + v_seq_len } */
 279         for (int k = 1; k <= (int) (lu + lv); ++k) {
 280                 size_t vv = v_of(k, r, lu, lv);
 281                 int kplus = find_plus(k, u, lu, v, lv);
 282                 uint32_t c = (kplus <= (int) (lu + lv)) ? c_nonf : c_froz;
 283
 284                 i[vv] = 1 + ((k <= (int) lu) ? u[k - 1] : v[k - lu - 1]);
 285                 sprintf(nbuf, "%d", k);
 286
 287                 if (quiver_add_vertex(qq, 0, nbuf, 1, 50 * x, ymult * 50 *
 288                                       i[vv], c, &errstr) < 0) {
 289                         fprintf(stderr, "%s\n", errstr);
 290                         fprintf(stderr, L("quiver_add_vertex failed\n"));
 291                         goto done;
 292                 }
 293
 294                 x++;
 295         }
 296
 297         /* Now add edges by remark 2.4 */
 298         for (int k = -r; k <= (int) (lu + lv); ++k) {
 299                 int kplus = find_plus(k, u, lu, v, lv);
 300                 size_t vk = v_of(k, r, lu, lv);
 301
 302                 if (k == 0) {
 303                         continue;
 304                 }
 305
 306                 for (int l = -r; l <= (int) (lu + lv); ++l) {
 307                         int lplus = find_plus(l, u, lu, v, lv);
 308                         int p = zmax(k, l);
 309                         int eip = (1 <= p &&
 310                                    p <= (int) lu) ? -1 : 1;
 311                         int q = zmin((int) kplus, (int) lplus);
 312                         int eiq = (1 <= q &&
 313                                    q <= (int) lu) ? -1 : 1;
 314                         size_t vl = v_of(l, r, lu, lv);
 315                         size_t idx = vk * qq->v_len + vl;
 316                         struct rational *e = &qq->e[idx];
 317
 318                         if (l == 0 ||
 319                             (k < 0 &&
 320                              l < 0)) {
 321                                 continue;
 322                         }
 323
 324                         if (p == q) {
 325                                 e->p = zsgn(k - l) * eip;
 326                                 e->q = 1;
 327                         } else if (p < q &&
 328                                    eip * eiq * (k - l) * (kplus - lplus) > 0) {
 329                                 e->p = zsgn(k - l) * eip * aij(typ, r, i[vk],
 330                                                                i[vl]);
 331                                 e->q = 1;
 332                         }
 333                 }
 334         }
 335
 336         /*
 337          * Now modify the fatness of various vertices to normalize |sigma|.
 338          *
 339          * We could just compute this by looking at the y-position
 340          * and the Dynkin type, but this serves as a nice sanity check.
 341          */
 342         while (need_fatness_run) {
 343                 need_fatness_run = 0;
 344
 345                 for (size_t j = 0; j < qq->v_num; ++j) {
 346                         struct vertex *v = &qq->v[j];
 347
 348                         for (size_t k = 0; k < qq->v_num; ++k) {
 349                                 struct vertex *w = &qq->v[k];
 350                                 struct rational *e = &qq->e[j * qq->v_len + k];
 351                                 struct rational *f = &qq->e[k * qq->v_len + j];
 352
 353                                 if (zabs(e->p * v->fatness) > zabs(f->p *
 354                                                                    w->fatness))
 355                                 {
 356                                         w->fatness++;
 357                                         need_fatness_run = 1;
 358                                 } else if (zabs(e->p * v->fatness) < zabs(f->p *
 359                                                                           w->
 360                                                                           fatness))
 361                                 {
 362                                         v->fatness++;
 363                                         need_fatness_run = 1;
 364                                 }
 365                         }
 366                 }
 367         }
 368
 369         quiver_save_to_file(qq, stdout, 0);
 370         ret = 0;
 371 done:
 372         free(nbuf);
 373         free(i);
 374         free(e);
 375
 376         return ret;
 377 }
 378
 379 /* "e" -> { }, "1,2" -> { 1, 2 } */
 380 static int
 381 parse_word(const char *s, size_t n, size_t **out_word, size_t *out_len)
 382 {
 383         size_t *seq = 0;
 384         size_t len = 1;
 385         size_t j = 0;
 386         int ret = -1;
 387         char *err = 0;
 388
 389         if (!(strcmp(s, "e"))) {
 390                 *out_word = 0;
 391                 *out_len = 0;
 392
 393                 return 0;
 394         }
 395
 396         for (const char *p = s; *p; p++) {
 397                 len += (*p == ',');
 398         }
 399
 400         if (!(seq = calloc(len, sizeof *seq))) {
 401                 perror(L("calloc"));
 402                 goto done;
 403         }
 404
 405         seq[j] = strtoll(s, 0, 0) - 1;
 406
 407         if (seq[j] >= n ||
 408             errno) {
 409                 goto done;
 410         }
 411
 412         j++;
 413
 414         for (const char *p = s; *p; p++) {
 415                 if (*p != ',') {
 416                         continue;
 417                 }
 418
 419                 errno = 0;
 420                 seq[j] = strtoll(p + 1, &err, 0) - 1;
 421
 422                 if (seq[j] >= n ||
 423                     errno) {
 424                         goto done;
 425                 }
 426
 427                 j++;
 428         }
 429
 430         ret = 0;
 431 done:
 432
 433         if (ret < 0) {
 434                 free(seq);
 435         } else {
 436                 *out_word = seq;
 437                 *out_len = len;
 438         }
 439
 440         return ret;
 441 }
 442
 443 static void
 444 usage(char *argv0)
 445 {
 446         printf(
 447                 "Usage: %s -c <Dynkin classification> [ -u <word>]  [-v <word>] [ -U ]\n",
 448                 argv0);
 449         printf(
 450                 "       Dynkin classification: Something like \u2018F4\u2019; permitted are\n");
 451         printf("           A\u2081, A\u2082, A\u2083, \u2026\n");
 452         printf("           B\u2081, B\u2082, B\u2083, \u2026\n");
 453         printf("           C\u2081, C\u2082, C\u2083, \u2026\n");
 454         printf("           D\u2081, D\u2082, D\u2083, \u2026\n");
 455         printf("           G\u2082, F\u2084, E\u2086, E\u2087, E\u2088\n");
 456         printf(
 457                 "       Word: something like \u20181,2,1,2\u2019 (\u2018e\u2019 is permitted)\n");
 458         printf("             if none given, \u2018e\u2019 is assumed\n");
 459         printf("\n");
 460         printf("        With -U, -r is above -1. Without, -1 is above -r\n");
 461 }
 462
 463 /* Run the thing */
 464 int
 465 main(int argc, char **argv)
 466 {
 467         int ret = 0;
 468         int opt = 0;
 469         enum dynkin typ = INVALID;
 470         int n = -1;
 471         char *p = 0;
 472         char *uword = "e";
 473         char *vword = "e";
 474         int ymult = 1;
 475         size_t *u_seq = 0;
 476         size_t *v_seq = 0;
 477         size_t u_seq_len = 0;
 478         size_t v_seq_len = 0;
 479         struct quiver q = { 0 };
 480
 481         while ((opt = getopt(argc, argv, "hUc:u:v:")) != -1) {
 482                 switch (opt) {
 483                 case 'h':
 484                         usage(argv[0]);
 485                         ret = 0;
 486                         goto done;
 487                 case 'u':
 488                         uword = optarg;
 489                         break;
 490                 case 'v':
 491                         vword = optarg;
 492                         break;
 493                 case 'U':
 494                         ymult = -1;
 495                         break;
 496                 case 'c':
 497
 498                         switch (optarg[0]) {
 499                         case 'a':
 500                         case 'A':
 501                                 typ = An;
 502                                 n = strtoll(optarg + 1, &p, 0);
 503                                 break;
 504                         case 'b':
 505                         case 'B':
 506                                 typ = Bn;
 507                                 n = strtoll(optarg + 1, &p, 0);
 508                                 break;
 509                         case 'c':
 510                         case 'C':
 511                                 typ = Cn;
 512                                 n = strtoll(optarg + 1, &p, 0);
 513                                 break;
 514                         case 'd':
 515                         case 'D':
 516                                 typ = Dn;
 517                                 n = strtoll(optarg + 1, &p, 0);
 518                                 break;
 519                         case 'e':
 520                         case 'E':
 521                                 n = strtoll(optarg + 1, &p, 0);
 522
 523                                 switch (n) {
 524                                 case 6:
 525                                         typ = E6;
 526                                         break;
 527                                 case 7:
 528                                         typ = E7;
 529                                         break;
 530                                 case 8:
 531                                         typ = E8;
 532                                         break;
 533                                 default:
 534                                         fprintf(stderr,
 535                                                 "Type E may only be E\u2086, E\u2087, or E\u2088\n");
 536                                         n = -1;
 537                                         break;
 538                                 }
 539
 540                                 break;
 541                         case 'f':
 542                         case 'F':
 543
 544                                 if (optarg[1] == '4' &&
 545                                     optarg[2] == 0) {
 546                                         typ = F4;
 547                                         n = 4;
 548                                 } else {
 549                                         fprintf(stderr,
 550                                                 "Type F may only be F\u2084\n");
 551                                 }
 552
 553                                 break;
 554                         case 'g':
 555                         case 'G':
 556
 557                                 if (optarg[1] == '2' &&
 558                                     optarg[2] == 0) {
 559                                         typ = G2;
 560                                         n = 2;
 561                                 } else {
 562                                         fprintf(stderr,
 563                                                 "Type G may only be G\u2082\n");
 564                                 }
 565
 566                                 break;
 567                         default:
 568                                 fprintf(stderr,
 569                                         "Invalid Dynkin classification: \u2018%s\u2019\n",
 570                                         optarg);
 571                                 goto done;
 572                                 break;
 573                         }
 574
 575                         if (n <= 0 ||
 576                             (p &&
 577                              *p)) {
 578                                 fprintf(stderr, "Invalid n: \u2018%s\u2019\n",
 579                                         optarg + 1);
 580                                 ret = EINVAL;
 581                                 goto done;
 582                         }
 583                 }
 584         }
 585
 586         switch (typ) {
 587         case INVALID:
 588                 fprintf(stderr,
 589                         "Dynkin classification is required (ex: \u2018-c F4\u2019)\n");
 590                 ret = EINVAL;
 591                 goto done;
 592                 break;
 593         default:
 594                 break;
 595         }
 596
 597 #if 0
 598
 599         for (size_t i = 0; i < n; ++i) {
 600                 printf("  [ ");
 601
 602                 for (size_t j = 0; j < n; ++j) {
 603                         printf("%3d ", bij(typ, n, i, j));
 604                 }
 605
 606                 printf("]");
 607                 printf("\n");
 608         }
 609
 610         goto done;
 611 #endif
 612
 613         if (parse_word(uword, n, &u_seq, &u_seq_len) < 0) {
 614                 fprintf(stderr, "Invalid u-word: \u2018%s\u2019\n", uword);
 615                 ret = EINVAL;
 616                 goto done;
 617         }
 618
 619         if (parse_word(vword, n, &v_seq, &v_seq_len) < 0) {
 620                 fprintf(stderr, "Invalid v-word: \u2018%s\u2019\n", vword);
 621                 ret = EINVAL;
 622                 goto done;
 623         }
 624
 625         if ((ret = run_bfzIII(&q, typ, n, u_seq, u_seq_len, v_seq, v_seq_len,
 626                               ymult)) < 0) {
 627                 fprintf(stderr, "BFZIII algorithm failed\n");
 628                 goto done;
 629         }
 630
 631 done:
 632         quiver_clean(&q);
 633         free(u_seq);
 634         free(v_seq);
 635
 636         return ret;
 637 }