#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

extern const char *__progname;

typedef struct node NODE;
typedef struct link LINK;

struct node {
  NODE *link;
  char *name;
  LINK *links;
  int live;
  double x;
  double y;
  double fx;
  double fy;
  } ;

struct link {
  NODE *a;
  NODE *b;
  LINK *alink;
  LINK *blink;
  } ;

static NODE *nodes;

static LINK *follow_link(LINK *l, NODE *n)
{
 if (n == l->a) return(l->alink);
 if (n == l->b) return(l->blink);
 abort();
}

static LINK **follow_linkp(LINK *l, NODE *n)
{
 if (n == l->a) return(&l->alink);
 if (n == l->b) return(&l->blink);
 abort();
}

static NODE *other_node(LINK *l, NODE *n)
{
 if (n == l->a) return(l->b);
 if (n == l->b) return(l->a);
 abort();
}

static void init(void)
{
 nodes = 0;
 srandom(time(0));
}

static NODE *find_node(const char *name)
{
 NODE *n;

 for (n=nodes;n;n=n->link) if (! strcmp(n->name,name)) return(n);
 n = malloc(sizeof(NODE));
 n->name = strdup(name);
 n->links = 0;
 n->link = nodes;
 nodes = n;
 return(n);
}

static void link_up(const char *name1, const char *name2)
{
 NODE *n1;
 NODE *n2;
 LINK *l;

 n1 = find_node(name1);
 n2 = find_node(name2);
 if (n1 == n2) return;
 for (l=n1->links;l;l=follow_link(l,n1))
  { if ( ((l->a == n1) && (l->b == n2)) ||
	 ((l->b == n1) && (l->a == n2)) ) return;
  }
 l = malloc(sizeof(LINK));
 l->a = n1;
 l->b = n2;
 l->alink = n1->links;
 n1->links = l;
 l->blink = n2->links;
 n2->links = l;
}

static void link_down(const char *name1, const char *name2)
{
 NODE *n1;
 NODE *n2;
 LINK *f;
 LINK *l;
 LINK **lp;

 n1 = find_node(name1);
 n2 = find_node(name2);
 if (n1 == n2) return;
 lp = &n1->links;
 while (1)
  { f = *lp;
    if (! f) return;
    if ( ((f->a == n1) && (f->b == n2)) ||
	 ((f->b == n1) && (f->a == n2)) )
     { *lp = follow_link(f,n1);
       break;
     }
    lp = follow_linkp(f,n1);
  }
 lp = &n2->links;
 while (1)
  { l = *lp;
    if (! l) abort();
    if (l == f)
     { *lp = follow_link(l,n2);
       free(f);
       return;
     }
    lp = follow_linkp(l,n2);
  }
}

static void read_net(void)
{
 int errs;
 char line[256];
 char s1[256];
 char s2[256];

 errs = 0;
 while (fgets(&line[0],sizeof(line)-1,stdin))
  { if (sscanf(&line[0],"link up %s %s",&s1[0],&s2[0]) == 2)
     { link_up(&s1[0],&s2[0]);
     }
    else if (sscanf(&line[0],"link down %s %s",&s1[0],&s2[0]) == 2)
     { link_down(&s1[0],&s2[0]);
     }
    else
     { fprintf(stderr,"%s: bad line: %s\n",__progname,&line[0]);
       errs = 1;
     }
  }
 if (errs) exit(1);
}

static void anneal(void)
{
 NODE *nextnode;
 NODE *n;
 LINK *l;
 NODE *o;
 double d;
 double x;
 double y;
 int i;

 for (n=nodes;n;n=n->link) n->live = 0;
 nodes->live = 1;
 nodes->x = 0;
 nodes->y = 0;
 for (nextnode=nodes->link;nextnode;nextnode=nextnode->link)
  { nextnode->live = 1;
    i = 0;
    x = 0;
    y = 0;
    for (l=nextnode->links;l;l=follow_link(l,nextnode))
     { o = other_node(l,nextnode);
       if (o->live)
	{ x += o->x;
	  y += o->y;
	  i ++;
	}
     }
    if (i == 0)
     { nextnode->x = ((random() & 0xffffff) / 1677721.5) - 5;
       nextnode->y = ((random() & 0xffffff) / 1677721.5) - 5;
     }
    else if (i == 1)
     { d = hypot(x,y);
       nextnode->x = x + (x / d);
       nextnode->y = y + (y / d);
     }
    else
     { nextnode->x = x / i;
       nextnode->y = y / i;
     }
    nextnode->x += ((random() & 0xffffff) / 167772150.0) - .05;
    nextnode->y += ((random() & 0xffffff) / 167772150.0) - .05;
    printf("\n%% placing %s at (%g,%g)\n",nextnode->name,nextnode->x,nextnode->y);
    for (i=100;i>0;i--)
     { printf("\n");
       for (n=nodes;n;n=n->link) if (n->live) printf("%% %s %g %g\n",n->name,n->x,n->y);
       printf("\n");
       for (n=nodes;n;n=n->link)
	{ if (! n->live) continue;
	  n->fx = 0;
	  n->fy = 0;
	  for (l=n->links;l;l=follow_link(l,n))
	   { o = other_node(l,n);
	     if (! o->live) continue;
	     x = o->x - n->x;
	     y = o->y - n->y;
	     d = hypot(x,y);
	     if (d > 1)
	      { x = (x/d) * (d-1);
		y = (y/d) * (d-1);
		n->fx += x;
		n->fy += y;
		printf("%% link %s %s -> (%g,%g) -> (%g,%g)\n",
			n->name, o->name,
			x, y,
			n->fx, n->fy );
	      }
	   }
	  for (o=nodes;o;o=o->link)
	   { if (!o->live || (o == n)) continue;
	     x = n->x - o->x;
	     y = n->y - o->y;
	     d = hypot(x,y);
	     if (d < 1)
	      { if (d < .5)
		 { x /= 2 * d;
		   y /= 2 * d;
		 }
		else
		 { x *= (1 - d) / d;
		   y *= (1 - d) / d;
		 }
		n->fx += x;
		n->fy += y;
		printf("%% any %s %s -> (%g,%g) -> (%g,%g)\n",
			n->name, o->name,
			x, y,
			n->fx, n->fy );
	      }
	   }
	  if (n->x > 0) n->fx -= .1; else if (n->x < 0) n->fx += .1;
	  if (n->y > 0) n->fy -= .1; else if (n->y < 0) n->fy += .1;
	}
       for (n=nodes;n;n=n->link)
	{ if (! n->live) continue;
	  n->x += i * n->fx / 1000;
	  n->y += i * n->fy / 1000;
	  printf("%% move %s -> (%g,%g) -> (%g,%g)\n",
		n->name, n->fx, n->fy, n->x, n->y);
	}
     }
  }
}

static void dump(void)
{
 double minx;
 double maxx;
 double miny;
 double maxy;
 NODE *n;
 LINK *l;
 double s;

 minx = nodes->x;
 maxx = nodes->x;
 miny = nodes->y;
 maxy = nodes->y;
 for (n=nodes->link;n;n=n->link)
  { if (n->x < minx) minx = n->x;
    if (n->x > maxx) maxx = n->x;
    if (n->y < miny) miny = n->y;
    if (n->y > maxy) maxy = n->y;
  }
 minx -= 1;
 maxx += 1;
 miny -= 1;
 maxy += 1;
 s = maxx - minx;
 if (maxy-miny > s) s = maxy - miny;
 printf("%% x=[%g,%g] y=[%g,%g] s=%g\n",minx,maxx,miny,maxy,s);
 minx = (minx + maxx - s) / 2;
 maxx = minx + s;
 miny = (miny + maxy - s) / 2;
 maxy = miny + s;
 printf("%% x=[%g,%g] y=[%g,%g]\n",minx,maxx,miny,maxy);
 printf("/Helvetica findfont 10 scalefont setfont\n");
 printf("[0 0 0 0 0 0] currentmatrix\n");
 printf("56 146 translate\n");
 printf("0 0 moveto 500 0 rlineto 0 500 rlineto -500 0 rlineto closepath\n");
 printf("%g dup scale\n",500/s);
 printf("%g %g translate\n",-minx,-miny);
 for (n=nodes;n;n=n->link)
  { printf("%g %g moveto %g %g %g 0 360 arc closepath\n",n->x+(s/100),n->y,n->x,n->y,s/100);
    for (l=n->links;l;l=follow_link(l,n))
     { printf("%g %g moveto %g %g lineto\n",l->a->x,l->a->y,l->b->x,l->b->y);
     }
  }
 printf("gsave dup setmatrix stroke grestore newpath\n");
 for (n=nodes;n;n=n->link)
  { printf("%g %g transform gsave 2 index setmatrix itransform moveto 10 -4 rmoveto (%s) show grestore\n",n->x,n->y,n->name);
  }
 printf("pop showpage\n");
}

int main(void);
int main(void)
{
 init();
 read_net();
 anneal();
 dump();
 exit(0);
}