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

gnu_labis | Δευ, 12/29/2008 - 11:23 | 10' | 4

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

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

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

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

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

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


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

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

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

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

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

Παράδειγμα 1

Καταρχήν, εγκαταστείστε το πακέτο 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;
}

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

Παράδειγμα 2

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


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 οποίο παράγει τον εξής γράφο:

Παράδειγμα 3

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

Το αγαπημένο μου βοήθημα για το 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, σε σχέση με τα προηγούμενα παραδείγματα είναι η χρήση τίτλων σε κάποιες ακμές (τα ΝΑΙ κ ΟΧΙ στα σημεία αποφάσεων).

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

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

Δώσε αστέρια!
Σχόλια

Ενδιαφερον, μολις βρω λιγο χρονο θα το μελετησω και θα σου πω εντυπωσεις

 

[[email protected]]$uname -a | awk '{print $1, "on the ROCKS"}' | sed -e 's/on\ the\ ROCKS/ROCKS/'

 

<Ξεδιάντροπο Self-spam>:

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

</Ξεδιάντροπο Self-spam>

--

"the car's on fire and there's no driver at the wheel.
and the sewers are all muddied with a thousand lonely suicides.
and a dark wind blows."  GYBE

dimitris]

<Ξεδιάντροπο Self-spam>:

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

</Ξεδιάντροπο Self-spam>

Καλά κάνεις κ το αναφέρεις! Αφού έκανες "δουλειά" κ την κυκλοφορείς κ με GPL, φυσικά κ να ενημερώσεις τον κόσμο!

Από τα λίγα που είδα (κοινώς μόνο φωτογραφίες) το πρόγραμμα σου είναι πιο πολύ προς τη μελέτη κ τον υπολογισμό των ιδιοτήτων των γράφων, ή κάνω λάθος; Κατά πόσον μπορείς να φτιάξεις κάτι σαν το τελευταίο παράδειγμα που παρουσιάζω στο tutorial αυτό (με τη διακρίνουσα); Μπορείς να έχεις "μεγάλους" κόμβους με αρκετό κείμενο "μέσα τους";

Μπορείς να φτιάξεις κάτι ανάλογο όπως τα παρακάτω παραδείγματα;

http://www.graphviz.org/Gallery/directed/datastruct.html
http://www.graphviz.org/Gallery/directed/psg.html

-- gnu_labis

Το Linux ΔΕΝ είναι Windows!!!

gnu_labis]
dimitris]

<Ξεδιάντροπο Self-spam>:

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

</Ξεδιάντροπο Self-spam>

Από τα λίγα που είδα (κοινώς μόνο φωτογραφίες) το πρόγραμμα σου είναι πιο πολύ προς τη μελέτη κ τον υπολογισμό των ιδιοτήτων των γράφων, ή κάνω λάθος; Κατά πόσον μπορείς να φτιάξεις κάτι σαν το τελευταίο παράδειγμα που παρουσιάζω στο tutorial αυτό (με τη διακρίνουσα); Μπορείς να έχεις "μεγάλους" κόμβους με αρκετό κείμενο "μέσα τους"; Μπορείς να φτιάξεις κάτι ανάλογο όπως τα παρακάτω παραδείγματα; http://www.graphviz.org/Gallery/directed/datastruct.html http://www.graphviz.org/Gallery/directed/psg.html

 

Εχεις δίκιο. Το SocNetV είναι περισσότερο για ερευνητές-φοιτητές που μελετούν κοινωνικά δίκτυα (ή/και γράφους), και όχι για mindmapping, γι' αυτό επικεντρώνεται στη αφαιρετική δομή του γράφου και όχι στα metadata. Έτσι υποστηρίζει 4 γραφικά σχήματα στους κόμβους (κύκλος, τετράγωνο, ρόμβος, έλλειψη) χωρίς εσωτερικό κείμενο.  Μπορείς όμως να έχεις ετικέτες (labels) έξω από τα σχήματα των κόμβων, με όσο κείμενο θέλεις σε όποιο σημείο θες.

Παρόλα αυτά, μια και αυτά τα σχήματα είναι ουσιαστικά QGraphicsItem αντικείμενα, με μικρή τροποποιηση, γίνεται να επιτρέψουμε και ετικέτες μέσα στα σχήματα. Επειδή η ιδέα σου μ' αρέσει, την πρόσθεσα  στα blueprints μου για μελλοντική δουλειά. Δεν ξέρω πότε θα την υλοποιήσω, αλλά θα γίνει.

--

"the car's on fire and there's no driver at the wheel.
and the sewers are all muddied with a thousand lonely suicides.
and a dark wind blows."  GYBE