Animated GIF of binary tree insertion

Question

I am trying to produce an animated gif of simple binary tree insertion using the dot and convert utilities of ubuntu. But it is not exactly working as I want. The animated gif which I get at the end does not show the complete tree and only shows the root node.

To test the program, just put some random integers and stop the input part with -1.

#include<stdio.h>
#include<stdlib.h>

struct node{
    int value;
    struct node *left,*right;
};

typedef struct node node;

node *root;
FILE *out;

node *insert(node *,int);
node *new_node(int);

int main()
{
    root = NULL;

    int temp;
    int k = 0;

    while(1)
    {
        scanf("%d",&temp);
        if( temp == -1) break;

        root = insert(root,temp);

        take_snap(k++); // this function writes the dot file and create a jpg image for the current tree
    }

    animate();
    // this function use convert utility to combine all the images made earlier and create a animated gif
    return 0;
}

node *new_node(int x)
{
    node *new = (node *) malloc(sizeof(node));
    new->left = new->right = NULL;
    new->value = x;
    return new;
}

node *insert(node *s,int temp)
{
    if( s == NULL)
        return new_node(temp);
    else if( s->value < temp )
        s->right = insert(s->right,temp);
    else if( s->value > temp )
        s->left = insert(s->left,temp);
    return s;
}

take_snap(int index)
{
    out = fopen("temp.dot","w");
    fprintf(out,"graph {\n");
    if( root )
        fprintf(out,"%d\n",root->value);
    dottify(root);
    fprintf(out,"}\n");

    fclose(out);
    char tempstr[100];
    sprintf(tempstr,"dot -Tjpg temp.dot -o image%d.jpg",index);
    system(tempstr);
}

dottify(node *s)
{
    if( s )
    {
        if(s->left)
        {
            fprintf(out,"%d -- %d\n",s->value,(s->left)->value);
            dottify(s->left);
        }

        if(s->right)
        {
            fprintf(out,"%d -- %d\n",s->value, (s->right)->value);
            dottify(s->right);
        }
    }
}


animate()
{
    //system("convert *.jpg -resize 200x200 *.jpg");
    system("convert -delay 100 -loop 0 image*.jpg animation.gif");
    system("eog ./animation.gif");
}

What am I doing wrong?

I tried using the resize operator yet I did not get what I wanted.

http://i.stack.imgur.com/e1rPD.gif

EDITED:

I have commented out the resize part, somehow it was making more than necessary jpgs.But the problem still remains.

Answer 1

There are two problems with convert *.jpg -resize 200x200 *.jpg:

• you need to add exclamation to force convert to mess aspect ratio
• convert can't do bulk conversions, just one image a time.

Like this:

for i in *.jpg ; do convert $i -resize 200x200! $i ; done

But due to scaling the result will be not very nice.

The other thing you can do is to force graphviz to generate fixed size images, just add some graph attributes: ratio=fill, size="2,2!", resolution=100.

Like this:

take_snap(int index)
{
    out = fopen("temp.dot","w");
    fprintf(out,"graph {\n");
    fprintf(out,"graph [ratio=fill, size=\"2,2!\", resolution=100];\n");

The problem is that all images will be 200x200px size, except the one for a single-node graph.
I don't know why this is the case. But you can fix this one image with convert.

convert image0.jpg -resize 200x200! image0.jpg

The result looks like this:

Answer 2

Here is my take on this: build the entire tree into memory, then output the entire .dot file for each additional node but set the attributes of 'not yet added' nodes to "invisible". Since all trees are now the same size, no resizing of individual files is necessary.

For this, the 'creation index' needs to be stored into the node as well. Note that I changed the output file format to "GIF" -- as you can see, storing such as simple image as a JPEG introduces ugly artefacting.

Entire code again (sorry, lots of little changes overall):

#include <stdio.h>
#include <stdlib.h>

struct node {
    int value;
    int index;
    struct node *left,*right;
};

typedef struct node node;

node *root;
FILE *out;

node *insert(node *,int,int);
node *new_node(int,int);

int main()
{
    root = NULL;

    int temp;
    int k = 0, i;

    while(1)
    {
        scanf("%d",&temp);
        if( temp == -1) break;

        root = insert(root,temp, k);
        k++;
    }

    for (i=0; i<k; i++)
    {
        take_snap (i);
    }

    // this function use convert utility to combine all the images made earlier and create a animated gif
    animate();
    return 0;
}

node *new_node (int x, int index)
{
    node *new = (node *) malloc(sizeof(node));
    new->left = new->right = NULL;
    new->value = x;
    new->index = index;

    return new;
}

node *insert(node *s,int temp, int index)
{
    if( s == NULL)
        return new_node(temp, index);
    else if( s->value < temp )
        s->right = insert(s->right,temp, index);
    else if( s->value > temp )
        s->left = insert(s->left,temp, index);
    return s;
}

take_snap (int index)
{
    char tempstr[100];
    sprintf (tempstr, "temp%d.dot", index);
    out = fopen(tempstr,"w");

    fprintf(out,"graph {\n");
    if( root )
    {
        fprintf(out,"%d\n",root->value);
        dottify(root, index);
    }
    fprintf(out,"}\n");

    fclose(out);

    sprintf(tempstr,"dot -Tgif temp%d.dot -o image%d.gif",index,index);
    system(tempstr);
}

dottify(node *s, int index)
{
    if( s )
    {
        if(s->left)
        {
            if (s->left->index <= index)
                fprintf(out,"%d -- %d\n",s->value,s->left->value);
            else
            {
                fprintf(out,"%d [style=invis]\n", s->left->value);
                fprintf(out,"%d -- %d [style=invis]\n", s->value, s->left->value);
            }
            dottify(s->left, index);
        }

        if(s->right)
        {
            if (s->right->index <= index)
                fprintf(out,"%d -- %d\n",s->value, s->right->value);
            else
            {
                fprintf(out,"%d [style=invis]\n", s->right->value);
                fprintf(out,"%d -- %d [style=invis]\n", s->value, s->right->value);
            }
            dottify(s->right, index);
        }
    }
}


animate()
{
    //system("convert *.jpg -resize 200x200 *.jpg");
    system("convert -delay 100 -loop 0 image*.jpg animation.gif");
    system("eog ./animation.gif");
}

and this is how it looks with the same input max taldykin used: 3 1 6 2 8 4 5 0 -2 -1

[Edit] Oh let's have some fun with coloring. Add this

if (s->left->index == index)
    fprintf(out,"%d [style=filled, color=cyan]\n", s->left->value);

and the same for right->value into the dottify routine to get this: