jump to navigation

Usare Graphviz e DOT per stampare un albero binario 20 febbraio 2008

Posted by fripp in Algoritmi, C, C++, Debian, DOT, Gnome, GNU/Linux, Informatica, Mac OS X, Programmazione, Scripting, Sistemi Operativi, Ubuntu, Unix.
Tags: , , , , , , ,
trackback

Graphviz è un pacchetto di software open source sviluppato dagli AT&T Research Labs per la rappresentazione di grafi descritti mediante il linguaggio di scripting DOT.

DOT è un linguaggio abbastanza semplice ed immediato. Per esempio, il codice DOT che mi ha permesso di realizzare l’immagine della rotazione di un albero, presente nel post sugli alberi AVL, è il segunete:


digraph g{
    node [shape =record,height=.1];
    node0[label = "<f0> |<f1> b|<f2> "];
    node1[label = "<f0> |<f1> a|<f2> "];
    node2[label = "<f0> |<f1> 3|<f2> "];
    node3[label = "<f0> |<f1> 1|<f2> "];
    node4[label = "<f0> |<f1> 2|<f2> "];
    node0:f0 -> node1:f1;
    node0:f2 -> node2:f1;
    node1:f0 -> node3:f1;
    node1:f2 -> node4:f1;

    node00[label = "<f0> |<f1> b|<f2> "];
    node11[label = "<f0> |<f1> a|<f2> "];
    node22[label = "<f0> |<f1> 3|<f2> "];
    node33[label = "<f0> |<f1> 1|<f2> "];
    node44[label = "<f0> |<f1> 2|<f2> "];
    node11:f0 -> node33:f1;
    node11:f2 -> node00:f1;
    node00:f0 -> node44:f1;
    node00:f2 -> node22:f1;

}

Per ottenere un’immagine dell’albero come quella che ho inserito nel post, basta usare il comando dot compreso nel pacchetto graphviz:dot -Tpng -oalbero.png albero.dotDurante lo studio e l’implementazione degli alberi binari e degli alberi AVL ho implementato una funzione di visita in ampiezza dell’albero che crea un file .dot contenente la descrizione dell’albero appena visitato.Le strutture dati usate sono le stesse che ho usato nel post sugli alberi AVL; inoltre ho fatto uso della struttura dati GQueue per gestire la visita in ampiezza.Ecco il codice della visita in ampiezza con stampa (questa funzione prevede che ogni nodo mantenga un puntatore al nodo padre):


void visitaBFS(struct node *n, const char *fileName){
    GQueue *c=g_queue_new();

    FILE *dot=fopen(fileName,"w");
    fprintf(dot,"digraph g {\nnode [shape = record,height=.1];\n");

    g_queue_push_tail(c,(gpointer)n);

    while(!g_queue_is_empty(c)){

        struct node u=*((struct node*)g_queue_pop_head(c));
        printf("%d ",*((int*)u.data));

        fprintf(dot,"node%d[label = %c<f0> |<f1> %d|<f2> %c];\n",*((int*)u.data),'"',*((int*)u.data),'"');

        if(u.left){
            fprintf(dot,"node%d[label = %c<f0> |<f1> %d|<f2> %c];\n",*((int*)u.left->data),'"',*((int*)u.left->data),'"');
            fprintf(dot,"%cnode%d%c:f0 -> %cnode%d%c:f1;\n",'"',*((int*)u.left->father->data),'"','"',*((int*)u.left->data),'"');
            g_queue_push_tail(c,(gpointer)u.left);
        }
        if(u.right){
            fprintf(dot,"node%d[label = %c<f0> |<f1> %d|<f2> %c];\n",*((int*)u.right->data),'"',*((int*)u.right->data),'"');
            fprintf(dot,"%cnode%d%c:f2 -> %cnode%d%c:f1;\n",'"',*((int*)u.right->father->data),'"','"',*((int*)u.right->data),'"');
            g_queue_push_tail(c,(gpointer)u.right);
        }

    }
    g_queue_free(c);

    fprintf(dot,"}");
    fclose(dot);
}

Enjoy………

Annunci

Commenti»

1. Simo - 21 febbraio 2008

Ciao,
molto interessante il tuo post…. Hai, per caso, la stessa implementazione JAVA+DOT per la visita in ampiezza e profondità di un grafo?…
Grazie

2. fripp - 21 febbraio 2008

Non ho implementazioni in Java, ma è semplice convertire il codice C in codice Java. Se implementi delle funzioni (o dei metodi) di visita in ampiezza o di visita in profondità, devi fare in modo che queste/i ritornino l’albero di visita. Successivamente, puoi richiamare la funzione che ho implementato sull’albero di visita. Tutto dipende da come hai impostato il problema


Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: