util.myr

   1 use std
   2
   3 use quiver
   4
   5 use "types"
   6 use "kc"
   7 use "roots"
   8
   9 pkg =
  10         generic vname : (i : @a, b : @b -> byte[:]) :: numeric @a, numeric @b
  11         generic wname : (i : @a, b : @b -> byte[:]) :: numeric @a, numeric @b
  12         const rename_and_move : (q1 : quiver.quiver#, q2 : quiver.quiver#, from : byte[:], to : byte[:] -> std.result(void, byte[:]))
  13
  14         /*
  15            This is what's used for verify_murot, and what should be used
  16            in the actual section 5 writeup.
  17          */
  18         const rename_according_to_rot : (kc : KC_type, q1 : quiver.quiver#, q2 : quiver.quiver# -> std.result(void, byte[:]))
  19
  20         /*
  21            This is what's used during the construction. It ignores some
  22            of the sigmaG rotations. Some.
  23          */
  24         const rename_according_to_twistingrot : (kc : KC_type, q1 : quiver.quiver#, q2 : quiver.quiver# -> std.result(void, byte[:]))
  25         const rename_according_to_twistingrotinv : (kc : KC_type, q1 : quiver.quiver#, q2 : quiver.quiver# -> std.result(void, byte[:]))
  26
  27         const rename_according_to_flip : (kc : KC_type, q1 : quiver.quiver#, q2 : quiver.quiver# -> std.result(void, byte[:]))
  28         const rename_according_to_twistingflip : (kc : KC_type, q1 : quiver.quiver#, q2 : quiver.quiver# -> std.result(void, byte[:]))
  29
  30         const get_node_xshifts : (kc : KC_type -> std.htab(weyl_reflection, int64)#)
  31 ;;
  32
  33 var node_xshifts_stored : std.htab(KC_type, std.htab(weyl_reflection, int64)#)#
  34
  35 const __init__ = {
  36         node_xshifts_stored = std.mkht()
  37 }
  38
  39 const __finit__ = {
  40         for (key, val) : std.byhtkeyvals(node_xshifts_stored)
  41                 std.htfree(val)
  42         ;;
  43         std.htfree(node_xshifts_stored)
  44 }
  45
  46 /* I keep bikeshedding this damn thing */
  47 generic vname = {i, j
  48         /*
  49            i : "y" position (simple root within G system)
  50            j : "x" position (simpl root within A_l system)
  51          */
  52         -> std.fmt("v{x};{x}", i, j)
  53 }
  54
  55 generic wname = {i, j
  56         -> std.fmt("w{x};{x}", i, j)
  57 }
  58
  59 /*
  60    Renames and moves a vertex. Specifically: assume that q2 is a
  61    duplicate of q1. Take the vertex named "from" in q1. Now take the
  62    corresponding vertex in q2 (i.e., the one with the same index as
  63    "from" has in q1). Call it "to", and move it to the x,y position that
  64    "to" occupies in q1.
  65  */
  66 const rename_and_move = {q1 : quiver.quiver#, q2 : quiver.quiver#, from : byte[:], to : byte[:]
  67         match quiver.find_vertex(q1, from)
  68         | `std.None: -> `std.Err std.fmt("cannot rename {} to {}; {} does not exist in q1", from, to, from)
  69         | `std.Some (fromj, fromp):
  70                 match quiver.find_vertex(q1, to)
  71                 | `std.None: -> `std.Err std.fmt("cannot rename {} to {}; {} does not exist in q1", from, to, to)
  72                 | `std.Some (toj, top):
  73                         std.slfree(q2.v[fromj].name)
  74                         q2.v[fromj].name = std.sldup(to)
  75                         q2.v[fromj].x_pos = top.x_pos
  76                         q2.v[fromj].y_pos = top.y_pos
  77                 ;;
  78         ;;
  79
  80         -> `std.Ok void
  81 }
  82
  83 /*
  84    Given q_pre, and q_post, which is just q_pre after applying murot,
  85    rename vertices of q_post so that q_post becomes graph-isomorphic to
  86    q_pre.
  87  */
  88 const rename_according_to_rot = {kc, q_pre, q_post
  89         var c
  90         match get_coxeter_elt(kc)
  91         | `std.Ok cc: c = cc
  92         | `std.Err e: -> `std.Err std.fmt("get_coxeter_elt({}): {}", kc, e)
  93         ;;
  94
  95         var sigmaG
  96         match get_sigmaG_permutation(kc)
  97         | `std.Ok sigmaGG: sigmaG = sigmaGG
  98         | `std.Err e: -> `std.Err std.fmt("get_sigmaG_permutation({}): {}", kc, e)
  99         ;;
 100
 101         var l = coxeter_num(kc) / 2 - 1
 102
 103         for i : c
 104                 var Ai = std.fmt("A{}", i)
 105                 var Bi = std.fmt("B{}", i)
 106                 var Ci = std.fmt("C{}", i)
 107
 108                 var AsigmaGi = std.fmt("A{}", sigmaG[i])
 109                 var BsigmaGi = std.fmt("B{}", sigmaG[i])
 110                 var CsigmaGi = std.fmt("C{}", sigmaG[i])
 111
 112                 match rename_and_move(q_pre, q_post, Bi, Ci)
 113                 | `std.Err e: -> `std.Err std.fmt("rearranging Q' failed: {}", e)
 114                 | `std.Ok void:
 115                 ;;
 116
 117                 match rename_and_move(q_pre, q_post, Ci, AsigmaGi)
 118                 | `std.Err e: -> `std.Err std.fmt("rearranging Q' failed: {}", e)
 119                 | `std.Ok void:
 120                 ;;
 121
 122                 match rename_and_move(q_pre, q_post, Ai, Bi)
 123                 | `std.Err e: -> `std.Err std.fmt("rearranging Q' failed: {}", e)
 124                 | `std.Ok void:
 125                 ;;
 126
 127                 std.slfree(Ai)
 128                 std.slfree(Bi)
 129                 std.slfree(Ci)
 130                 std.slfree(AsigmaGi)
 131                 std.slfree(BsigmaGi)
 132                 std.slfree(CsigmaGi)
 133         ;;
 134
 135         -> `std.Ok void
 136 }
 137
 138 /*
 139    murot does not quite perform a 120 degree rotation: there's an
 140    unfortunate permutation of vertices by sigma_G. When actually
 141    calculating coordinates, we have to perform the rename, undo the
 142    monomial map, and then permute by sigma_G back in the seed torus (or
 143    something like that).
 144
 145    For the purposes of constructing the quiver, however, we don't have
 146    variables yet: we simply operate on a graph level. Therefore, we
 147    combine both renamings into one step, and we do that step entirely on
 148    the graph.
 149  */
 150 const rename_according_to_twistingrot = {kc, q_pre, q_post
 151         var c
 152         match get_coxeter_elt(kc)
 153         | `std.Ok cc: c = cc
 154         | `std.Err e: -> `std.Err std.fmt("get_coxeter_elt({}): {}", kc, e)
 155         ;;
 156
 157         var sigmaG
 158         match get_sigmaG_permutation(kc)
 159         | `std.Ok sigmaGG: sigmaG = sigmaGG
 160         | `std.Err e: -> `std.Err std.fmt("get_sigmaG_permutation({}): {}", kc, e)
 161         ;;
 162
 163         var l = coxeter_num(kc) / 2 - 1
 164
 165         for i : c
 166                 for var j = 1; j <= l; ++j
 167                         var name_in_pre : byte[:] = vname(i,j)
 168                         var name_in_post : byte[:] = vname(sigmaG[i], l - j + 1)
 169
 170                         match rename_and_move(q_pre, q_post, name_in_pre, name_in_post)
 171                         | `std.Err e: -> `std.Err std.fmt("rearranging Q' failed: {}", e)
 172                         | `std.Ok void:
 173                         ;;
 174
 175                         std.slfree(name_in_pre)
 176                         std.slfree(name_in_post)
 177                 ;;
 178
 179                 var Ai = std.fmt("A{}", i)
 180                 var Bi = std.fmt("B{}", i)
 181                 var Ci = std.fmt("C{}", i)
 182
 183                 var AsigmaGi = std.fmt("A{}", sigmaG[i])
 184                 var BsigmaGi = std.fmt("B{}", sigmaG[i])
 185                 var CsigmaGi = std.fmt("C{}", sigmaG[i])
 186
 187                 match rename_and_move(q_pre, q_post, Bi, CsigmaGi)
 188                 | `std.Err e: -> `std.Err std.fmt("rearranging Q' failed: {}", e)
 189                 | `std.Ok void:
 190                 ;;
 191
 192                 match rename_and_move(q_pre, q_post, Ci, AsigmaGi)
 193                 | `std.Err e: -> `std.Err std.fmt("rearranging Q' failed: {}", e)
 194                 | `std.Ok void:
 195                 ;;
 196
 197                 match rename_and_move(q_pre, q_post, Ai, Bi)
 198                 | `std.Err e: -> `std.Err std.fmt("rearranging Q' failed: {}", e)
 199                 | `std.Ok void:
 200                 ;;
 201         ;;
 202
 203         -> `std.Ok void
 204 }
 205
 206 const rename_according_to_twistingrotinv = {kc, q_pre, q_post
 207         var c
 208         match get_coxeter_elt(kc)
 209         | `std.Ok cc: c = cc
 210         | `std.Err e: -> `std.Err std.fmt("get_coxeter_elt({}): {}", kc, e)
 211         ;;
 212
 213         var sigmaG
 214         match get_sigmaG_permutation(kc)
 215         | `std.Ok sigmaGG: sigmaG = sigmaGG
 216         | `std.Err e: -> `std.Err std.fmt("get_sigmaG_permutation({}): {}", kc, e)
 217         ;;
 218
 219         var l = coxeter_num(kc) / 2 - 1
 220
 221         for i : c
 222                 for var j = 1; j <= l; ++j
 223                         var name_in_pre : byte[:] = vname(i,j)
 224                         var name_in_post : byte[:] = vname(sigmaG[i], l - j + 1)
 225
 226                         match rename_and_move(q_pre, q_post, name_in_post, name_in_pre)
 227                         | `std.Err e: -> `std.Err std.fmt("rearranging Q' failed: {}", e)
 228                         | `std.Ok void:
 229                         ;;
 230
 231                         std.slfree(name_in_pre)
 232                         std.slfree(name_in_post)
 233                 ;;
 234
 235                 var Ai = std.fmt("A{}", i)
 236                 var Bi = std.fmt("B{}", i)
 237                 var Ci = std.fmt("C{}", i)
 238
 239                 var AsigmaGi = std.fmt("A{}", sigmaG[i])
 240                 var BsigmaGi = std.fmt("B{}", sigmaG[i])
 241                 var CsigmaGi = std.fmt("C{}", sigmaG[i])
 242
 243                 match rename_and_move(q_pre, q_post, Bi, Ai)
 244                 | `std.Err e: -> `std.Err std.fmt("rearranging Q' failed: {}", e)
 245                 | `std.Ok void:
 246                 ;;
 247
 248                 match rename_and_move(q_pre, q_post, CsigmaGi, Bi)
 249                 | `std.Err e: -> `std.Err std.fmt("rearranging Q' failed: {}", e)
 250                 | `std.Ok void:
 251                 ;;
 252
 253                 match rename_and_move(q_pre, q_post, AsigmaGi, Ci)
 254                 | `std.Err e: -> `std.Err std.fmt("rearranging Q' failed: {}", e)
 255                 | `std.Ok void:
 256                 ;;
 257         ;;
 258
 259         -> `std.Ok void
 260 }
 261
 262 /* As rename_according_to_rot, but for flip */
 263 const rename_according_to_flip = {kc, q_pre, q_post
 264         -> `std.Ok void
 265 }
 266
 267 const rename_according_to_twistingflip = {kc, q_pre, q_post
 268         var c
 269         match get_coxeter_elt(kc)
 270         | `std.Ok cc: c = cc
 271         | `std.Err e: -> `std.Err std.fmt("get_coxeter_elt({}): {}", kc, e)
 272         ;;
 273
 274         var sigmaG
 275         match get_sigmaG_permutation(kc)
 276         | `std.Ok perm: sigmaG = perm
 277         | `std.Err e: -> `std.Err std.fmt("get_sigmaG_permutation({}): {}", kc, e)
 278         ;;
 279
 280         var l = coxeter_num(kc) / 2 - 1
 281         var L = 2 * l + 1
 282
 283         for i : c
 284                 for var j = 1; j <= L; ++j
 285                         var name_in_pre : byte[:] = wname(i,j)
 286                         var iprime = i
 287                         var jprime = j
 288                         if j <= l
 289                                 jprime += l + 1
 290                         elif j > l + 1
 291                                 jprime -= l + 1
 292                         ;;
 293
 294                         var name_in_post : byte[:] = wname(iprime, jprime)
 295
 296                         match rename_and_move(q_pre, q_post, name_in_pre, name_in_post)
 297                         | `std.Err e: -> `std.Err std.fmt("rearranging Q' failed: {}", e)
 298                         | `std.Ok void:
 299                         ;;
 300
 301                         std.slfree(name_in_pre)
 302                         std.slfree(name_in_post)
 303                 ;;
 304         ;;
 305
 306         -> `std.Ok void
 307 }
 308
 309 const get_node_xshifts = {kc
 310         match std.htget(node_xshifts_stored, kc)
 311         | `std.Some stored: -> stored
 312         | `std.None:
 313         ;;
 314
 315         var node_xshifts : std.htab(weyl_reflection, int64)# = std.mkht()
 316         var dynkin_edges : (weyl_reflection, weyl_reflection)[:] = get_edges(kc)
 317         var T = get_tree_partition(kc)
 318         var c = [][:]
 319         match get_coxeter_elt(kc)
 320         | `std.Ok cc: c = cc
 321         | `std.Err e: goto done
 322         ;;
 323
 324         /* Space out the roots of the tree equally. */
 325         for var j = 0; j < T[1].len; ++j
 326                 std.htput(node_xshifts, T[1][j], j * 25)
 327         ;;
 328
 329         /*
 330            For each node, determine how many children it has, and space
 331            out the siblings accordingly.
 332          */
 333         for var i = 1; i < T.len; ++i
 334                 for si : T[i]
 335                         var this_xshift = std.htgetv(node_xshifts, si, 0)
 336                         var children = [][:]
 337                         for (a, b) : dynkin_edges
 338                                 if a == si
 339                                         std.slpush(&children, b)
 340                                 ;;
 341                         ;;
 342
 343                         var leftmost_child_x = this_xshift - (50 * (children.len - 1)) / 2
 344                         for var j = 0; j < children.len; ++j
 345                                 std.htput(node_xshifts, children[j], leftmost_child_x + 50 * j)
 346                         ;;
 347                         std.slfree(children)
 348                 ;;
 349         ;;
 350
 351 :done
 352         std.htput(node_xshifts_stored, kc, node_xshifts)
 353
 354         -> node_xshifts
 355 }