Computer engineering tutorial - Μέρος 2ο: Γράφοι παντού

Διαβάστε το πρώτο μέρος της σειράς εδώ.

Έπειτα από το σάλο που προκάλεσε το πρώτο μέρος, τα ενοχλητικά τηλεφωνήματα κ τις εκδηλώσεις λατρείας, η λαϊκή απαίτηση με ανάγκασε να επιστρέψω στο γραφείο μου κ να ετοιμάσω τη συνέχεια. Καλώς ήλθατε λοιπόν στο δεύτερο tutorial για μηχανικούς Η/Υ (κ όχι μόνο)!

Σε αντίθεση με το προηγούμενο tutorial, τούτο δω είναι χρήσιμο για κάθε μορφής επαγγελματία, φοιτητή, ή ακόμα κ μαθητή. Γιατί αυτή τη φορά, θα μάθουμε πώς να δημιουργούμε γράφους, φυσικά "the linux way"!

Κ πριν βιαστείτε να πείτε "τί είναι τούτο πάλι", ένας γράφος (graph) δεν είναι τίποτε άλλο από ένα διάγραμμα που αποτελείται από κόμβους (nodes) οι οποίοι ενώνονται με ακμές (edges).

Κοινώς, διάσπαρτα κουτάκια με γραμμές μεταξύ τους.

Παρότι είναι κάτι τόσο απλό, η θεωρία των γράφων αποτελεί ένα πανίσχυρο μαθηματικό όπλο, που μας έχει βοηθήσει αφάνταστα στην πρόοδο των επιστημών. Οι γράφοι βρίσκουν εφαρμογή σε πάσης φύσεως μηχανική, οικονομικά, προγραμματισμό, κ ό,τι άλλο βάλει ο νους κ η φαντασία σας.

Το πρόγραμμα που θα προσπαθήσω να παρουσιάσω αυτή τη φορά είναι το graphviz, open source υπό την άδεια Common Public Licence.

Για να πάρετε μια γρήγορη ιδέα του τί μπορεί να κάνει για εσάς, δείτε μερικά παραδείγματα εδώ.

Παρόμοια με το πρόγραμμα drawtiming που παρουσίασα στο πρώτο μέρος, το graphviz χρησιμοποιεί ένα αρχείο κειμένου (text) το οποίο περιγράφει ένα γράφο σε μια γλώσσα που το graphviz καταλαβαίνει. Το graphviz διαβάζει αυτό το αρχείο κ παράγει μια εικόνα που περιέχει την αναπαράσταση του γράφου.

Για να είμαστε πιο ακριβείς, το graphviz δεν είναι ένα πρόγραμμα, αλλά πολλά μαζί. Το πακέτο περιλαμβάνει μια σειρά από προγράμματα, το καθένα ικανό να κατασκευάσει διαφορετικού τύπου γράφους. Μακράν διασημότερο είναι το "dot", το οποίο φτιάχνει "κατευθυνόμενους" γράφους (directed graphs, ή digraphs για συντομία). Κ πριν μου πείτε πάλι "τί είναι αυτό", ένας κατευθυνόμενος γράφος είναι ότι κ ένας απλός γράφος, με τη διαφορά ότι οι ακμές δεν είναι απλές γραμμές, αλλά βελάκια. Σε αυτό το tutorial θα ασχοληθούμε μόνο με το dot, καθότι τα υπόλοιπα ακολουθούν βασικά την ίδια φιλοσοφία.

Πολύ μπλα-μπλα κ λίγη ουσία θα μου πείτε, κ έχετε δίκιο. Πάμε λοιπόν στο παράδειγμα μας. Για αρχή, θα σας δείξω πώς να φτιάξετε το ακόλουθο απλό κ παντελώς άχρηστο διάγραμμα (από κάπου πρέπει να αρχίσουμε...):

Καταρχήν, εγκαταστείστε το πακέτο graphviz στη διανομή linux που χρησιμοποιείτε. Στη συνέχεια ανοίξτε τον αγαπημένο σας editor (πχ gedit, kedit, emacs, vi, κ δεν συμμαζεύεται) κ γράψτε τα ακόλουθα:


digraph MyFirstGraph {
A->B1->Γ1;
B1->Γ2;
A->B2->Γ3;
B2->Γ4;
}

Σώστε το αρχείο με όποιο όνομα θέλετε, εγώ το ονόμασα test.dot. Στη συνέχεια ανοίξτε ένα τερματικό στο φάκελο που σώσατε το παραπάνω αρχείο κ δώστε την εντολή:


dot -Tpng test.dot -o test.png


Το -Tpng υποδηλώνει ότι το αποτέλεσμα το θέλουμε σε εικόνα png. Υπάρχουν άπειρες άλλες εναλλακτικές. Ακολουθεί το όνομα του αρχείου που φτιάξαμε, κ μετά το -ο δίνουμε το όνομα που θέλουμε να έχει η εικόνα που θα παράγει το dot για μας.

Αυτό είναι όλο. Πρέπει πλέον στον ίδιο φάκελο να έχετε κ μια εικόνα, λίγο-πολύ ίδια με αυτή του παραδείγματος.

Πάμε τώρα για μερικές επεξηγήσεις σχετικά με το αρχείο που δώσαμε στο dot σαν είσοδο. Κάθε γράφος που φτιάχνουμε περικλύεται ανάμεσα σε αγκύλες { }. Προηγείται πάντα η λέξη "digraph" κ ακολουθεί ένα όνομα για το γράφο (ό,τι θέλουμε εμείς). Μέσα στη περιγραφή του γράφου, κάθε γραμμή χωρίζεται από την άλλη με ένα ερωτηματικό. Αν μελετήσετε τον "κώδικα" κ το αποτέλεσμα του, θα δείτε ότι οι ακμές δηλώνονται με βελάκια ( -> ), κ μεταξύ τους τοποθετούνται οι κόμβοι του γράφου. Η σειρά των γραμμών δεν έχει ιδιαίτερη σημασία. Όπως βλέπετε, για να φτιάξουμε ένα δεύτερο βέλος που φεύγει από τον ίδιο κόμβο προς άλλη κατεύθυνση, απλά επαναλαμβάνουμε το όνομα του κόμβου (πχ οι γραμμές Β1->Γ2 κ Β2->Γ4 επαναχρησιμοποιούν τα Β1 κ Β2).

Ένα πρόβλημα της παραπάνω σύνταξης είναι ότι τα ονόματα των κόμβων οφείλουν να μην περιέχουν κενά. Αυτό μπορεί να γίνει ιδιαίτερα περιοριστικό, αλλά λύνεται πολύ εύκολα. Αυτό που χρειάζεται να κάνουμε είναι να αλλάξουμε τις ιδιότητες των κόμβων, κ πιο συγκεκριμένα το όνομα τους (label). Αυτό επιτυγχάνεται δηλώνοντας ξεχωριστά το κόμβο, κ στη συνέχεια τις ακμές που τον συνδέουν με άλλους κόμβους. Πχ:


digraph MySecondGraph {
Α [label="Αρχή του γράφου"];
Α->B1->Γ1;
B1->Γ2;
A->B2->Γ3;
B2->Γ4;
}


Το παραπάνω παράδειγμα δίνει το ακόλουθο αποτέλεσμα:

Οι κόμβοι έχουν κ πολλές άλλες ιδιότητες που μπορούμε να πειράξουμε, όπως σχήμα, χρώμα, γραμματοσειρά για τον τίτλο του κόμβου κλπ. Πάμε να δούμε κάποια από αυτά:


digraph MyThirdGraph {
A [label="Αρχή του γράφου", style="filled", fillcolor="red"];
B1 [shape="diamond", fontcolor="blue"];
B2 [shape="diamond", fontcolor="blue"];
A->B1->Γ1;
B1->Γ2;
A->B2->Γ3;
B2->Γ4;
}

To οποίο παράγει τον εξής γράφο:

Υπάρχουν κ άλλες ιδιότητες για τους κόμβους, κ φυσικά υπάρχουν ιδιότητες κ για τις ακμές. Επίσης, ιδιότητες έχει κ ο ίδιος ο γράφος (πχ απόσταση μεταξύ διαδοχικών κόμβων, γενικός τίτλος γράφου κλπ).

Το αγαπημένο μου βοήθημα για το dot (όχι το μοναδικό), με όλες τις διαθέσιμες ιδιότητες, είναι το κείμενο:
http://www.graphviz.org/pdf/dotguide.pdf

Πριν κλείσω κ αυτό το tutorial, θα ήθελα να δώσω ένα πιο "χρήσιμο" παράδειγμα. Θυμάμαι, σε αυτή τη κουβέντα του φόρουμ είχε προκύψει το θέμα της αλγοριθμικής αναπαράστασης της μεθόδου επίλυσης μιας δευτεροβάθμιας εξίσωσης με τη βοήθεια της "διακρίνουσας". Ορίστε λοιπόν ένα σύντομο διάγραμμα σε graphviz που αναπαριστά αυτό ακριβώς το πράγμα:


digraph SecondOrderEquation {
Begin [label="Αρχή", shape="invtriangle"];
Input [label="Είσοδος τιμών για α,β,γ", shape="parallelogram"];
D [label="υπολογισμός διακρίνουσας Δ"];
Branch1 [label="αν Δ >= 0", shape="diamond"];
Branch2 [label="αν Δ = 0", shape="diamond"];
TwoReal [label="υπολογισμός δύο πραγματικών λύσεων"];
OneReal [label="υπολογισμός μίας πραγματικής λύσης"];
Imagine [label="υπολογισμός μιγαδικών λύσεων"];
Output [label="Εκτύπωση αποτελεσμάτων στην οθόνη", shape="parallelogram"];
End [label="Τέλος", shape="octagon"];

Begin->Input->D->Branch1;
Branch1->Branch2 [label="ΝΑΙ"];
Branch1->Imagine [label="OXI"];
Branch2->TwoReal [label="ΟΧΙ"];
Branch2->OneReal [label="NAI"];
Imagine->Output;
TwoReal->Output;
OneReal->Output;
Output->End;
}


Τo μόνo νέo στοιχείo, σε σχέση με τα προηγούμενα παραδείγματα είναι η χρήση τίτλων σε κάποιες ακμές (τα ΝΑΙ κ ΟΧΙ στα σημεία αποφάσεων).

Το αποτέλεσμα του παραπάνω γράφου είναι:

Αυτά λοιπόν κ με τους γράφους στο linux. Αν κατάφερα να σας κεντρίσω το ενδιαφέρον, είμαι σίγουρος ότι θα βρείτε τα υπόλοιπα μόνοι σας. Κ φυσικά για όποιες απορίες, εδώ είμαστε. Καλά διαγράμματα!