/*  File   : tree2dot.c
    Author : Richard A. O'Keefe
    Updated: %G%
    Purpose: Take "Newick" trees and plot them using 'dot'.

    Requires:
	dot from GraphViz.

    Method:
	cc -o tree2dot tree2dot.c
	yourprog <characters.dat >yourprog.tree
	./tree2dot <yourprog.tree >yourprog.dot
	dot -Tps yourprog.dot >yourprog.ps
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct Node *Tree;
struct Node {
    struct Node *left, *right;
    int datum;
    int label;
};

static Tree read_tree(void) {
    int c;
    Tree t = malloc(sizeof *t);

    if (t == 0) abort();
    c = getchar();
    if (c == '(') {
	Tree x, y;

	x = read_tree();
	c = getchar();
	if (c != ',') abort();
	y = read_tree();
	c = getchar();
	if (c != ')') abort();
	
	if (x->datum <= y->datum) {
	    t->left = x, t->right = y, t->datum = x->datum;
	} else {
	    t->left = y, t->right = x, t->datum = y->datum;
	}
    } else {
	int n = 0;

	while ('0' <= c && c <= '9') {
	    n = n*10 + (c-'0');
	    c = getchar();
	}
	ungetc(c, stdin);
	t->left = t->right = 0;
	t->datum = n;
    }
    return t;
}

static int n = 0;

static void number_tree(Tree t) {
    if (t->left != 0) {
	number_tree(t->left);
	t->datum = ++n;
	number_tree(t->right);
    }
}

static void print_tree(Tree t) {
    if (t->left != 0) {    
	printf("    H%d[shape = box];\n", t->datum);
	printf("    H%d -> %s%d;\n    H%d -> %s%d;\n",
	    t->datum,
	    t->left->left == 0 ? "" : "H",
	    t->left->datum,
	    t->datum,
	    t->right->left == 0 ? "" : "H",
	    t->right->datum);
	print_tree(t->left);
	print_tree(t->right);
    }
}

int main(void) {
    Tree t = read_tree();

    n = 0;
    number_tree(t);
    printf("digraph Phylogeny {\n");
    printf("    paper = \"8.25,11.6;\"\n");
    printf("    size  = \"10,8\";\n");
    printf("    rotate = 90;\n");
    print_tree(t);
    printf("}\n");
    return 0;
}