quiver.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 <stddef.h>
  20 #include <stdint.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24
  25 #include "macros.h"
  26 #include "quiver.h"
  27
  28 #define MAX_SUPPORTED_EDGE_NUM           (((size_t) -1) >> 2)
  29 #define MAX_SUPPORTED_VERTEX_NUM         (((size_t) -1) >> 2)
  30
  31 /* Primes for reducing fractions */
  32 static uint32_t primes[] = {
  33         /* */
  34         2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
  35         71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
  36         149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
  37         227, 229, 233, 239, 241, 251
  38 };
  39
  40 /* GCD */
  41 static int
  42 gcd(uint_fast8_t x, uint_fast8_t y)
  43 {
  44         uint_fast8_t r = 0;
  45
  46         if (!x &&
  47             !y) {
  48                 return 1;
  49         }
  50
  51         while (y) {
  52                 r = x % y;
  53                 x = y;
  54                 y = r;
  55         }
  56
  57         return x;
  58 }
  59
  60 /* Attempt to store a fraction in out, reducing if possible */
  61 static int
  62 reduce_fraction(int_fast32_t n, uint_fast32_t d, struct rational *out, const
  63                 char **out_errstr)
  64 {
  65         if (!n &&
  66             d) {
  67                 *out = (struct rational) { .p = 0, .q = 1 };
  68
  69                 return 0;
  70         }
  71
  72         /* We special-case 1-3 since, in those cases, this actually needs to go fast */
  73         if (d == 1) {
  74                 goto calculated;
  75         } else if (d == 2) {
  76                 if (n % 2) {
  77                 } else {
  78                         n /= 2;
  79                         d = 1;
  80                 }
  81
  82                 goto calculated;
  83         } else if (d == 3) {
  84                 if (n % 3) {
  85                 } else {
  86                         n /= 3;
  87                         d = 1;
  88                 }
  89
  90                 goto calculated;
  91         }
  92
  93         for (size_t j = 0; j < ((sizeof primes) / (sizeof primes[0])); ++j) {
  94                 uint32_t p = primes[j];
  95
  96                 if (j &&
  97                     p > d) {
  98                         break;
  99                 }
 100
 101                 while (n % p == 0 &&
 102                        d % p == 0) {
 103                         n = n / p;
 104                         d = d / p;
 105                 }
 106         }
 107
 108 calculated:
 109
 110         if (n > INT_FAST8_MAX ||
 111             n < INT_FAST8_MIN ||
 112             d == 0 ||
 113             d > UINT_FAST8_MAX) {
 114                 IF_NZ_SET(out_errstr, L("unrepresentable fraction"));
 115
 116                 return EDOM;
 117         }
 118
 119         *out = (struct rational) { .p = n, .q = d };
 120
 121         return 0;
 122 }
 123
 124 /* out += a/b */
 125 static int
 126 add_to_fraction(int_fast8_t a, uint_fast8_t b, struct rational *out, const
 127                 char **out_errstr)
 128 {
 129         int_fast32_t n = a * out->q + out->p * b;
 130         uint_fast32_t d = b * out->q;
 131
 132         return reduce_fraction(n, d, out, out_errstr);
 133 }
 134
 135 /* Add an arrow of weight a/b from i -> j, affecting e(i,j) and e(j,i) */
 136 int
 137 quiver_add_to_edge(struct quiver *q, size_t i, size_t j, int_fast8_t a,
 138                    uint_fast8_t b, const char **out_errstr)
 139 {
 140         int ret = 0;
 141
 142         if (!q) {
 143                 IF_NZ_SET(out_errstr, L("nonexistant quiver"));
 144
 145                 return EINVAL;
 146         }
 147
 148         if (i >= q->v_num ||
 149             j >= q->v_num) {
 150                 IF_NZ_SET(out_errstr, L("edge includes nonexistant vertex"));
 151
 152                 return EINVAL;
 153         }
 154
 155         if (i == j) {
 156                 IF_NZ_SET(out_errstr, L("loops are not allowed"));
 157
 158                 return EINVAL;
 159         }
 160
 161         struct rational *eij = &(q->e[i * q->v_len + j]);
 162         struct rational *eji = &(q->e[j * q->v_len + i]);
 163         uint_fast8_t d = gcd(q->v[i].fatness, q->v[j].fatness);
 164
 165         if ((ret = add_to_fraction(a * q->v[j].fatness, b * d, eij,
 166                                    out_errstr))) {
 167                 return ret;
 168         }
 169
 170         if ((ret = add_to_fraction(-1 * a * q->v[i].fatness, b * d, eji,
 171                                    out_errstr))) {
 172                 return ret;
 173         }
 174
 175         return 0;
 176 }
 177
 178 /* Add a vertex with a name and weight */
 179 int
 180 quiver_add_vertex(struct quiver *q, size_t *out_i, const char *name,
 181                   uint_fast16_t fatness, int x, int y, uint32_t argb, const
 182                   char **out_errstr)
 183 {
 184         void *newmem = 0;
 185         char *newname;
 186         size_t len = 0;
 187
 188         if (!q) {
 189                 IF_NZ_SET(out_errstr, L("invalid quiver"));
 190
 191                 return EINVAL;
 192         }
 193
 194         if (!name) {
 195                 len = snprintf(0, 0, "%zu", q->v_num);
 196
 197                 if (len + 1 < len) {
 198                         IF_NZ_SET(out_errstr, L("overflow"));
 199
 200                         return EOVERFLOW;
 201                 }
 202
 203                 if (!(newname = malloc(len + 1))) {
 204                         int sv_err = errno;
 205
 206                         IF_NZ_SET(out_errstr, L("malloc"));
 207
 208                         return sv_err;
 209                 }
 210
 211                 sprintf(newname, "%zu", q->v_num);
 212         } else {
 213                 /*
 214                  * Should be no need to check overflow, either name
 215                  * was malloc'd, or came from a file which was read
 216                  * in with a length cap.
 217                  */
 218                 if (!(newname = malloc(strlen(name) + 1))) {
 219                         int sv_err = errno;
 220
 221                         IF_NZ_SET(out_errstr, L("malloc"));
 222
 223                         return sv_err;
 224                 }
 225
 226                 strcpy(newname, name);
 227         }
 228
 229         if (q->v_num >= q->v_len) {
 230                 size_t newlen = q->v_len + 8;
 231
 232                 if (newlen >= ((size_t) -1) / newlen ||
 233                     (newlen * newlen) / newlen != newlen) {
 234                         IF_NZ_SET(out_errstr, L("too many vertices"));
 235
 236                         return EDOM;
 237                 }
 238
 239                 if (!(newmem = calloc(newlen * newlen, sizeof (*q->e)))) {
 240                         int sv_err = errno;
 241
 242                         IF_NZ_SET(out_errstr, L("too many vertices"));
 243
 244                         return sv_err;
 245                 }
 246
 247                 for (size_t j = 0; j < q->v_num; ++j) {
 248                         for (size_t k = 0; k < q->v_num; ++k) {
 249                                 ((struct rational *) newmem)[j * newlen + k] =
 250                                         q->e[j * q->v_len + k];
 251                         }
 252
 253                         for (size_t k = q->v_num; k < newlen; ++k) {
 254                                 ((struct rational *) newmem)[j * newlen + k] =
 255                                         (struct rational) { .p = 0, .q = 1 };
 256                         }
 257                 }
 258
 259                 for (size_t j = q->v_num; j < newlen; ++j) {
 260                         for (size_t k = 0; k < newlen; ++k) {
 261                                 ((struct rational *) newmem)[j * newlen + k] =
 262                                         (struct rational) { .p = 0, .q = 1 };
 263                         }
 264                 }
 265
 266                 if (q->e) {
 267                         free(q->e);
 268                 }
 269
 270                 q->e = newmem;
 271
 272                 if (!(newmem = (realloc(q->v, newlen * sizeof (*q->v))))) {
 273                         int sv_err = errno;
 274
 275                         IF_NZ_SET(out_errstr, L("too many vertices"));
 276
 277                         return sv_err;
 278                 }
 279
 280                 q->v = newmem;
 281                 q->v_len = newlen;
 282         }
 283
 284         for (size_t k = 0; k <= q->v_num; ++k) {
 285                 q->e[k * q->v_len + q->v_num] = (struct rational) { .p = 0, .q =
 286                                                                             1 };
 287                 q->e[q->v_num * q->v_len + k] = (struct rational) { .p = 0, .q =
 288                                                                             1 };
 289         }
 290
 291         q->v[q->v_num] = (struct vertex) { /* */
 292                 .name = newname, .fatness = fatness, .x = x, .y = y, .r =
 293                         (argb & 0xff0000) >> 16, .g = (argb & 0xff00) >> 8, .b =
 294                         (argb &
 295                          0xff),
 296         };
 297
 298         if (out_i) {
 299                 *out_i = q->v_num;
 300         }
 301
 302         q->v_num++;
 303
 304         return 0;
 305 }
 306
 307 /* Increase or decrease the fatness of a vertex, readjusting edges as well */
 308 int
 309 quiver_adjust_fatness(struct quiver *q, size_t i, int_fast8_t fatness_adj, const
 310                       char **out_errstr)
 311 {
 312         int ret = 0;
 313
 314         if (i >= q->v_num) {
 315                 IF_NZ_SET(out_errstr, L("invalid vertex"));
 316
 317                 return EINVAL;
 318         }
 319
 320         int new_fatness = q->v[i].fatness + fatness_adj;
 321
 322         if (new_fatness <= 0 ||
 323             new_fatness > UINT_FAST8_MAX) {
 324                 IF_NZ_SET(out_errstr, L("invalid new fatness"));
 325
 326                 return EINVAL;
 327         }
 328
 329         for (size_t j = 0; j < q->v_num; ++j) {
 330                 if (i == j) {
 331                         continue;
 332                 }
 333
 334                 uint_fast8_t d_orig = gcd(q->v[i].fatness, q->v[j].fatness);
 335                 uint_fast8_t d_new = gcd(new_fatness, q->v[j].fatness);
 336                 size_t k = i * q->v_len + j;
 337
 338                 if ((ret = reduce_fraction(q->e[k].p * d_orig, q->e[k].q *
 339                                            d_new, &(q->e[k]), out_errstr))) {
 340                         return ret;
 341                 }
 342
 343                 k = j * q->v_len + i;
 344
 345                 if ((ret = reduce_fraction(q->e[k].p * d_orig * q->v[i].fatness,
 346                                            q->e[k].q * d_new * new_fatness,
 347                                            &(q->e[k]), out_errstr))) {
 348                         return ret;
 349                 }
 350         }
 351
 352         q->v[i].fatness = new_fatness;
 353
 354         return ret;
 355 }
 356
 357 /* Free all memory used by this quiver, resetting it to { 0 } */
 358 int
 359 quiver_clean(struct quiver *q)
 360 {
 361         if (!q) {
 362                 return 0;
 363         }
 364
 365         for (size_t j = 0; j < q->v_num; ++j) {
 366                 free(q->v[j].name);
 367         }
 368
 369         free(q->v);
 370         free(q->e);
 371         *q = (struct quiver) { 0 };
 372
 373         return 0;
 374 }
 375
 376 /* Delete a vertex (and all associated edges) */
 377 int
 378 quiver_delete_vertex(struct quiver *q, size_t i, const char **out_errstr)
 379 {
 380         if (i >= q->v_num) {
 381                 IF_NZ_SET(out_errstr, L("invalid vertex"));
 382
 383                 return EINVAL;
 384         }
 385
 386         if (q->v_num == 1) {
 387                 q->v_num = 0;
 388                 free(q->v[0].name);
 389                 q->v[0].name = 0;
 390
 391                 return 0;
 392         }
 393
 394         /* First, shift everything over to the left */
 395         for (size_t j = 0; j < q->v_num; ++j) {
 396                 for (size_t k = i + 1; k < q->v_num; ++k) {
 397                         q->e[q->v_len * j + k - 1] = q->e[q->v_len * j + k];
 398                 }
 399         }
 400
 401         /* Second, shift everything below row i up */
 402         for (size_t j = i + 1; j < q->v_num; ++j) {
 403                 for (size_t k = 0; k < q->v_num; ++k) {
 404                         q->e[q->v_len * (j - 1) + k] = q->e[q->v_len * j + k];
 405                 }
 406         }
 407
 408         /* Now shift the vertex names/lengths over */
 409         free(q->v[i].name);
 410         q->v[i].name = 0;
 411
 412         for (size_t j = i + 1; j < q->v_num; ++j) {
 413                 q->v[j - 1] = q->v[j];
 414         }
 415
 416         q->v_num--;
 417         q->v[q->v_num] = (struct vertex) { 0 };
 418
 419         return 0;
 420 }
 421
 422 /* Return σ_{ij} */
 423 int
 424 quiver_get_sigma(const struct quiver * const q, size_t i, size_t j, struct
 425                  rational *out_s)
 426 {
 427         size_t idx = 0;
 428         int d = 0;
 429
 430         /* No errstr here. This is in a tight loop upstairs */
 431         if (!q ||
 432             !out_s ||
 433             i >= q->v_num ||
 434             j >= q->v_num) {
 435                 return EINVAL;
 436         }
 437
 438         idx = i * q->v_len + j;
 439         const struct rational * const e = &(q->e[idx]);
 440
 441         out_s->p = e->p;
 442         out_s->q = e->q;
 443         out_s->p *= gcd(q->v[i].fatness, q->v[j].fatness);
 444         out_s->q *= q->v[j].fatness;
 445         d = gcd(out_s->p, out_s->q);
 446         out_s->p /= d;
 447         out_s->q /= d;
 448
 449         return 0;
 450 }
 451
 452 /* Read quiver from file */
 453 int
 454 quiver_load_from_file(struct quiver *q, FILE *f, const char **out_errstr)
 455 {
 456         if (!q) {
 457                 IF_NZ_SET(out_errstr, L("invalid quiver"));
 458
 459                 return EINVAL;
 460         }
 461
 462         int ret = 0;
 463
 464         for (size_t k = 0; k < q->v_num; ++k) {
 465                 struct vertex *v = &(q->v[k]);
 466
 467                 free(v->name);
 468                 v->name = 0;
 469         }
 470
 471         q->v_num = 0;
 472         size_t new_vnum = 0;
 473         char *p = 0;
 474
 475         if (fscanf(f, "%zu Vertices\n", &new_vnum) != 1) {
 476                 IF_NZ_SET(out_errstr, L("Invalid file (|V| unspecified)"));
 477
 478                 return EINVAL;
 479         }
 480
 481         for (size_t k = 0; k < new_vnum; ++k) {
 482                 size_t j = 0;
 483                 size_t fatness = 0;
 484                 int x = 0;
 485                 int y = 0;
 486                 unsigned int argb = 0;
 487                 size_t len = 0;
 488
 489                 if (fscanf(f, " v[%zu] f:%zu x:%d y:%d c:0x%x l:%zu n:", &j,
 490                            &fatness, &x, &y, &argb, &len) != 6) {
 491                         IF_NZ_SET(out_errstr, L("Invalid file"));
 492
 493                         return EINVAL;
 494                 } else if (j != k) {
 495                         IF_NZ_SET(out_errstr, L(
 496                                           "Invalid file (vertices out of order)"));
 497
 498                         return EINVAL;
 499                 } else if (fatness >= UINT_FAST16_MAX) {
 500                         IF_NZ_SET(out_errstr, L(
 501                                           "Invalid file (fatness unsupported)"));
 502
 503                         return EINVAL;
 504                 }
 505
 506                 if (p) {
 507                         free(p);
 508                         p = 0;
 509                 }
 510
 511                 if (!len) {
 512                         IF_NZ_SET(out_errstr, L(
 513                                           "Invalid file (nameless vertex)"));
 514
 515                         return EINVAL;
 516                 }
 517
 518                 if (len > 1024) {
 519                         IF_NZ_SET(out_errstr, L(
 520                                           "Invalid file (vertex with name too large)"));
 521
 522                         return EINVAL;
 523                 }
 524
 525                 if (!(p = malloc(len + 1))) {
 526                         ret = errno;
 527                         perror(L("malloc"));
 528                         IF_NZ_SET(out_errstr, L("malloc error"));
 529
 530                         return ret;
 531                 }
 532
 533                 if (fread(p, sizeof *p, len, f) != (sizeof *p) * len) {
 534                         IF_NZ_SET(out_errstr, L(
 535                                           "Invalid file (short vertex name)"));
 536
 537                         return EINVAL;
 538                 }
 539
 540                 p[len] = '\0';
 541
 542                 if ((ret = quiver_add_vertex(q, 0, p, (uint_fast16_t) fatness,
 543                                              x, y, (uint32_t) argb,
 544                                              out_errstr))) {
 545                         goto done;
 546                 }
 547         }
 548
 549         while (!feof(f)) {
 550                 size_t i = 0;
 551                 size_t j = 0;
 552                 long n = 0;
 553                 size_t d = 0;
 554
 555                 if (fscanf(f, " e[%zu][%zu] %ld/%zu ", &i, &j, &n, &d) != 4) {
 556                         IF_NZ_SET(out_errstr, L(
 557                                           "Invalid file (bad edge line)"));
 558                         ret = EINVAL;
 559                         goto done;
 560                 }
 561
 562                 if (i >= q->v_num ||
 563                     j >= q->v_num) {
 564                         IF_NZ_SET(out_errstr, L(
 565                                           "Invalid file (edge between nonexistent vertices)"));
 566                         ret = EINVAL;
 567                         goto done;
 568                 }
 569
 570                 struct rational *e = &(q->e[i * q->v_len + j]);
 571
 572                 if (n <= INT_FAST32_MIN ||
 573                     n >= INT_FAST32_MAX ||
 574                     d > UINT_FAST32_MAX) {
 575                         IF_NZ_SET(out_errstr, L(
 576                                           "Invalid file (edge weight out of range)"));
 577                         ret = EINVAL;
 578                         goto done;
 579                 }
 580
 581                 if ((ret = reduce_fraction((int_fast32_t) n, (uint_fast32_t) d,
 582                                            e, out_errstr))) {
 583                         goto done;
 584                 }
 585         }
 586
 587         ret = 0;
 588 done:
 589         free(p);
 590
 591         return ret;
 592 }
 593
 594 /* Rename a vertex */
 595 int
 596 quiver_rename_vertex(struct quiver *q, size_t i, const char *new_name, const
 597                      char **out_errstr)
 598 {
 599         void *newmem = 0;
 600         int ret = 0;
 601
 602         if (!q) {
 603                 IF_NZ_SET(out_errstr, L("invalid quiver"));
 604
 605                 return EINVAL;
 606         }
 607
 608         if (i >= q->v_num) {
 609                 IF_NZ_SET(out_errstr, L("vertex out of range"));
 610
 611                 return EINVAL;
 612         }
 613
 614         if (!(newmem = strdup(new_name))) {
 615                 ret = errno;
 616                 IF_NZ_SET(out_errstr, L("cannot strdup()"));
 617                 goto done;
 618         }
 619
 620         free(q->v[i].name);
 621         q->v[i].name = newmem;
 622 done:
 623
 624         return ret;
 625 }
 626
 627 /* Set color of a vertex */
 628 int
 629 quiver_color_vertex(struct quiver *q, size_t i, uint32_t argb, const
 630                     char **out_errstr)
 631 {
 632         if (!q) {
 633                 IF_NZ_SET(out_errstr, L("invalid quiver"));
 634
 635                 return EINVAL;
 636         }
 637
 638         if (i >= q->v_num) {
 639                 IF_NZ_SET(out_errstr, L("vertex out of range"));
 640
 641                 return EINVAL;
 642         }
 643
 644         q->v[i].r = (argb & 0x00ff0000) >> 16;
 645         q->v[i].g = (argb & 0x0000ff00) >> 8;
 646         q->v[i].b = (argb & 0x000000ff) >> 0;
 647
 648         return 0;
 649 }
 650
 651 /* Serialize the quiver */
 652 int
 653 quiver_save_to_file(struct quiver *q, FILE *f, const char **out_errstr)
 654 {
 655         if (!q) {
 656                 IF_NZ_SET(out_errstr, L("invalid quiver"));
 657
 658                 return EINVAL;
 659         }
 660
 661         int ret = 0;
 662
 663         if (fprintf(f, "%zu Vertices\n", q->v_num) < 0) {
 664                 ret = errno;
 665                 IF_NZ_SET(out_errstr, L("write failed"));
 666                 goto done;
 667         }
 668
 669         for (size_t k = 0; k < q->v_num; ++k) {
 670                 struct vertex *v = &(q->v[k]);
 671                 unsigned int argb = (v->r << 16) | (v->g << 8) | v->b;
 672
 673                 if (fprintf(f, "v[%zu] f:%zu x:%d y:%d c:0x%06x l:%zu n:%s\n",
 674                             k, (size_t) v->fatness, v->x, v->y, argb, strlen(
 675                                     v->name),
 676                             v->name) < 0) {
 677                         ret = errno;
 678                         IF_NZ_SET(out_errstr, L("write failed"));
 679                         goto done;
 680                 }
 681         }
 682
 683         for (size_t i = 0; i < q->v_num; ++i) {
 684                 for (size_t j = 0; j < q->v_num; ++j) {
 685                         struct rational *e = &(q->e[i * q->v_len + j]);
 686
 687                         if (!e->p) {
 688                                 continue;
 689                         }
 690
 691                         if (fprintf(f, "e[%zu][%zu] %d/%u\n", i, j, (int) e->p,
 692                                     (unsigned) e->q) < 0) {
 693                                 ret = errno;
 694                                 IF_NZ_SET(out_errstr, L("write failed"));
 695                                 goto done;
 696                         }
 697                 }
 698         }
 699
 700         if (fflush(f)) {
 701                 ret = errno;
 702                 IF_NZ_SET(out_errstr, L("flush failed"));
 703         }
 704
 705 done:
 706
 707         return ret;
 708 }
 709
 710 /* Set threshold: if quiver_mutate() creates an edge above, warn_out is set */
 711 int
 712 quiver_set_warning_threshold(struct quiver *q, unsigned int warn_threshold,
 713                              const char **out_errstr)
 714 {
 715         if (!q) {
 716                 IF_NZ_SET(out_errstr, L("invalid quiver"));
 717
 718                 return EINVAL;
 719         }
 720
 721         q->edge_weight_threshold = warn_threshold;
 722
 723         return 0;
 724 }
 725
 726 /* Mutate the quiver at vertex k */
 727 int
 728 quiver_mutate(struct quiver *q, size_t k, int *out_warn, const
 729               char **out_errstr)
 730 {
 731         int ret = 0;
 732
 733         if (!q) {
 734                 IF_NZ_SET(out_errstr, L("invalid quiver"));
 735
 736                 return EINVAL;
 737         }
 738
 739         /* Step one: complete all triangles */
 740         for (size_t i = 0; i < q->v_num; ++i) {
 741                 if (i == k) {
 742                         continue;
 743                 }
 744
 745                 struct rational *eik = &(q->e[i * q->v_len + k]);
 746
 747                 for (size_t j = 0; j < q->v_num; ++j) {
 748                         if (j == k ||
 749                             j == i) {
 750                                 continue;
 751                         }
 752
 753                         struct rational *eij = &(q->e[i * q->v_len + j]);
 754                         struct rational *ekj = &(q->e[k * q->v_len + j]);
 755
 756                         if (eik->p * ekj->p <= 0) {
 757                                 continue;
 758                         }
 759
 760                         if ((ret = add_to_fraction(abs(eik->p) * ekj->p,
 761                                                    eik->q * ekj->q, eij,
 762                                                    out_errstr))) {
 763                                 return ret;
 764                         }
 765
 766                         if (out_warn &&
 767                             q->edge_weight_threshold &&
 768                             eij->q * q->edge_weight_threshold <= (unsigned
 769                                                                   int) abs(
 770                                     eij->p)) {
 771                                 *out_warn = 1;
 772                         }
 773                 }
 774         }
 775
 776         /* Step two: invert all edges that touch k */
 777         for (size_t i = 0; i < q->v_num; ++i) {
 778                 if (i == k) {
 779                         continue;
 780                 }
 781
 782                 struct rational *eik = &(q->e[i * q->v_len + k]);
 783                 struct rational *eki = &(q->e[k * q->v_len + i]);
 784
 785                 eik->p = -eik->p;
 786                 eki->p = -eki->p;
 787         }
 788
 789         return 0;
 790 }