#!/bin/sh
# version 2007.09.24
# D. J. Bernstein
# Public domain.

original-awk -F: '
  function sort(x,y,n, i,j,p,q,t,u) {
    i = int(n / 2) + 1
    j = n
    while (j > 1) {
      if (i > 1) { --i; t = x[i]; u = y[i] }
      else { t = x[j]; u = y[j]; x[j] = x[1]; y[j] = y[1]; --j }
      q = i
      while ((p = q * 2) <= j) {
        if (p < j) if (x[p + 1] >= x[p]) ++p
        x[q] = x[p]; y[q] = y[p]; q = p
      }
      while (q > i) {
        p = int(q / 2)
        if (t < x[p]) break
        x[q] = x[p]; y[q] = y[p]; q = p
      }
      x[q] = t; y[q] = u
    }
  }
  BEGIN {
    v[0] = 0
  }
  {
    if ($1 == "vertex" && $3 == "label") {
      vnum = vnum + 1
      v[vnum] = $2
      print
    } else if ($1 == "vertex" && $3 == "y") {
      vy[$2] = -$4
      if (!ymax || vy[$2] > ymax) ymax = vy[$2]
      if (!ymin || vy[$2] < ymin) ymin = vy[$2]
      print
    } else if ($1 == "vertex" && $3 == "x") {
      vx[$2] = $4
    } else if ($1 == "edge") {
      enum = enum + 1
      estart[enum] = $2
      eend[enum] = $3
      print
    }
  }
  END {
    for (i = 1;i <= enum;++i) {
      targetnum[estart[i]] += 1
      target[estart[i]"/"targetnum[estart[i]]] = eend[i]
      sourcenum[eend[i]] += 1
      source[eend[i]"/"sourcenum[eend[i]]] = estart[i]
    }
    for (i = 1;i <= vnum;++i) {
      ++yvnum[vy[v[i]]]
      yv[vy[v[i]]"/"yvnum[vy[v[i]]]] = v[i]
    }
    for (loop = 0;loop < 5;++loop) {
      for (y = ymax;y >= ymin;--y) {
        anum = 0
        for (i = 1;i <= yvnum[y];++i) {
          u = yv[y"/"i]
          total = vx[u]
          if (targetnum[u]) {
            bnum = 0
            for (j = 1;j <= targetnum[u];++j) {
              ++bnum
              b[bnum] = vx[target[u"/"j]]
            }
            sort(b,b,bnum)
            if (bnum % 2)
              total = b[int((bnum + 1) / 2)]
            else
              total = 0.5 * (b[bnum / 2] + b[(bnum + 2) / 2])
          }
          ++anum
          a[anum] = total * 0.95
          av[anum] = u
        }
        sort(a,av,anum)
        j = int((anum + 1) / 2)
        x = a[j]
        for (i = j;i <= anum;++i) {
          if (x < a[i]) x = a[i]
          vx[av[i]] = x
          x += 1
        }
        x = a[j]
        for (i = j;i >= 1;--i) {
          if (x > a[i]) x = a[i]
          vx[av[i]] = x
          x -= 1
        }

	productive2 = 1
        for (loop2 = 0;productive2 && loop2 < 3;++loop2) {
	  productive2 = 0
          anum = 0
          for (i = 1;i <= yvnum[y];++i) {
            u = yv[y"/"i]
            ++anum;
            a[anum] = vx[u]
            av[anum] = u
          }
          sort(a,av,anum)
          for (i = 1;i < anum;++i) {
            u1 = av[i]
            u2 = av[i + 1]
            wantswap = 0
            for (j = 1;j <= targetnum[u1];++j)
              for (k = 1;k <= targetnum[u2];++k) {
                if (vx[target[u1"/"j]] > vx[target[u2"/"k]]) ++wantswap
                if (vx[target[u1"/"j]] < vx[target[u2"/"k]]) --wantswap
              }
            if (wantswap) {
	      productive2 = 1
              t = vx[u1]
              vx[u1] = vx[u2]
              vx[u2] = t
              av[i] = u2
              av[i + 1] = u1
            }
          }
          for (i = anum - 1;i >= 1;--i) {
            u1 = av[i]
            u2 = av[i + 1]
            wantswap = 0
            for (j = 1;j <= targetnum[u1];++j)
              for (k = 1;k <= targetnum[u2];++k) {
                if (vx[target[u1"/"j]] > vx[target[u2"/"k]]) ++wantswap
                if (vx[target[u1"/"j]] < vx[target[u2"/"k]]) --wantswap
              }
            if (wantswap) {
	      productive2 = 1
              t = vx[u1]
              vx[u1] = vx[u2]
              vx[u2] = t
              av[i] = u2
              av[i + 1] = u1
            }
          }
        }

      }
      for (y = ymin;y <= ymax;++y) {
        anum = 0
        for (i = 1;i <= yvnum[y];++i) {
          u = yv[y"/"i]
          total = vx[u]
          if (sourcenum[u]) {
            bnum = 0
            for (j = 1;j <= sourcenum[u];++j) {
              ++bnum
              b[bnum] = vx[source[u"/"j]]
            }
            sort(b,b,bnum)
            if (bnum % 2)
              total = b[int((bnum + 1) / 2)]
            else
              total = 0.5 * (b[bnum / 2] + b[(bnum + 2) / 2])
          }
          ++anum
          a[anum] = total * 0.95
          av[anum] = u
        }
        sort(a,av,anum)
        j = int((anum + 1) / 2)
        x = a[j]
        for (i = j;i <= anum;++i) {
          if (x < a[i]) x = a[i]
          vx[av[i]] = x
          x += 1
        }
        x = a[j]
        for (i = j;i >= 1;--i) {
          if (x > a[i]) x = a[i]
          vx[av[i]] = x
          x -= 1
        }

	productive2 = 1
        for (loop2 = 0;productive2 && loop2 < 3;++loop2) {
	  productive2 = 0
          anum = 0
          for (i = 1;i <= yvnum[y];++i) {
            u = yv[y"/"i]
            ++anum;
            a[anum] = vx[u]
            av[anum] = u
          }
          sort(a,av,anum)
          for (i = 1;i < anum;++i) {
            u1 = av[i]
            u2 = av[i + 1]
            wantswap = 0
            for (j = 1;j <= sourcenum[u1];++j)
              for (k = 1;k <= sourcenum[u2];++k) {
                if (vx[source[u1"/"j]] > vx[source[u2"/"k]]) ++wantswap
                if (vx[source[u1"/"j]] < vx[source[u2"/"k]]) --wantswap
              }
            if (wantswap) {
	      productive2 = 1
              t = vx[u1]
              vx[u1] = vx[u2]
              vx[u2] = t
              av[i] = u2
              av[i + 1] = u1
            }
          }
          for (i = anum - 1;i >= 1;--i) {
            u1 = av[i]
            u2 = av[i + 1]
            wantswap = 0
            for (j = 1;j <= sourcenum[u1];++j)
              for (k = 1;k <= sourcenum[u2];++k) {
                if (vx[source[u1"/"j]] > vx[source[u2"/"k]]) ++wantswap
                if (vx[source[u1"/"j]] < vx[source[u2"/"k]]) --wantswap
              }
            if (wantswap) {
	      productive2 = 1
              t = vx[u1]
              vx[u1] = vx[u2]
              vx[u2] = t
              av[i] = u2
              av[i + 1] = u1
            }
          }
        }


      }
    }
    for (i = 1;i <= vnum;++i) {
      if (v[i] in vx) print "vertex:"v[i]":x:"vx[v[i]]":"
    }
  }
'