|
|
| Κωδικός Πόρου |
000449964 |
| Τίτλος |
Analysis and visualization of hierarchical graphs |
| Άλλος τίτλος |
Ανάλυση και οπτικοποίηση ιεραρχικών γράφων |
|
Συγγραφέας
|
Κρητικάκης, Γεώργιος
|
|
Σύμβουλος διατριβής
|
Τόλλης, Ιωάννης
|
|
Μέλος κριτικής επιτροπής
|
Πρατικάκης, Πολύβιος
Τσαμαρδινός, Ιωάννης
|
| Περίληψη |
Σε αυτό το έργο εξερευνήσαμε αλγορίθμους αιχμής για διάσπαση γράφων σε
μονοπάτια και κανάλια. Οι αλγόριθμοι μας είναι γραμμικοί ή σχεδόν γραμμικοί, και
τα αποτελέσματα τους είναι πολύ κοντά στο βέλτιστο. Επιπρόσθετα, αναπτύξαμε ένα
πλαίσιο οπτικοποίησης ιεραρχικών γραφημάτων που βασίζεται στην διάσπαση σε
μονοπάτια και κανάλια και μας βοηθάει να αποκαλύψουμε κρίσιμες πτυχές των
ιεραρχιών ενός γράφου.
Ακριβέστερα, θα δείξουμε πώς να δημιουργήσουμε μια υποβέλτιστη διάσπαση σε
κανάλια ενός άκυκλου κατευθυνόμενου γραφήματος σε σχεδόν γραμμικό χρόνο. Ο
αριθμός των καναλιών που δημιουργεί ο αλγόριθμος μας, τα οποία δεν μοιράζονται
κοινούς κόμβους, είναι πολύ κοντά στο ελάχιστο. Η χρονική πολυπλοκότητα του
αλγορίθμου μας είναι Ο(|E|+c*l), όπου c είναι ο αριθμός των καναλιών και l o
αριθμός της μεγαλύτερης διαδρομής του γράφου. Θα δώσουμε αναλυτική εξήγηση
στα επόμενα κεφάλαια. Αυτή η θεμελιώδης έννοια έχει ένα ευρύ φάσμα εφαρμογών.
Θα επικεντρωθούμε σε μερικές από αυτές. Θα περιγράψουμε εκτενώς πώς να
λύσουμε το πρόβλημα της μεταβατικής κλειστότητας και πώς να απαντάμε
ερωτήματα σε σταθερό χρόνο δημιουργώντας ένα γνωστό σχήμα από δείκτες. Η
μέθοδος μας χρειάζεται O(kc*|Ered|) χρόνο και Ο(kc*|V|) χώρο. Ο όρος kc είναι το
μέγεθος μιας υποβέλτιστης διάσπασης καναλιών, ο όρος Ered είναι το σύνολο των
μη-μεταβατικών ακμών του γράφου, και ο όρος |V| υποδηλώνει τον αριθμό των
κόμβων. Επιπλέον θα δείξουμε πως το |Εred| φράζεται, |Εred|≤width*|V|, και θα
περιγράψουμε πως μπορούμε να βρούμε ένα υποσύνολο του Etr (σύνολο
μεταβατικών ακμών) χωρίς να υπολογίσουμε τη μεταβατική κλειστότητα. Οι
μεθοδολογίες μας συνοδεύονται από εκτενής πειράματα. Τα πειράματα μας
δείχνουν ότι οι αλγόριθμοι μας δεν είναι απλώς αποδοτικοί στη θεωρία. Στη πράξη η
απόδοση είναι ακόμα ποιο μεγάλη.
Ακόμη, έχουμε αναπτύξει το Path-based-Framework (PBF). Το PBF είναι ένα
πρόσφατο πλαίσιο οπτικοποίησης ιεραρχικών γραφημάτων που μοιάζει αλλά επίσης
διαφέρει από το κλασικό πλαίσιο τεσσάρων φάσεων του Sugiyama. Το PBF βασίζεται
στη ιδέα της διάσπασης του γράφου σε κανάλια και μονοπάτια. Επεκτείναμε αυτή
την ιδέα. Ζωγραφίζουμε όλες τις ακμές, εφαρμόζουμε επικάλυψη ακμών,
ελαχιστοποιούμε το ύψος, και μειώνουμε το πλάτος του γραφήματος εφαρμόζοντας
τεχνικές όμοιες με αυτές του χρονο-προγραμματισμού εργασιών. Ως εκ τούτου,
παρουσιάζουμε ένα γενικό μοντέλο οπτικοποίησης ιεραρχικών γραφημάτων.
Τρέξαμε μια έρευνα χρήστη προκειμένου να μετρήσουμε την ευχρηστία και την
αναγνωσιμότητα του. Βάλαμε ερωτήσεις σε γράφους που οπτικοποιήθηκαν από το
δικό μας πλαίσιο, και συγκρίναμε την επίδοση των χρηστών σε σχέση με την
οπτικοποίηση της βιβλιοθήκης OGDF που χρησιμοποιεί το πλαίσιο του Sygiyama. Τα
αποτελέσματα μας φανέρωσαν ένα ξεκάθαρο πλεονέκτημα του PBF σε σχέση με το
OGDF σε αυτά τα ερωτήματα.
|
| Φυσική περιγραφή |
vi, 53 σ. : σχεδ., πιν., εικ. ; 30 εκ. |
| Γλώσσα |
Αγγλικά |
| Θέμα |
Channel decomposition |
|
Compressed transitive closure |
|
DAG |
|
Data structures |
|
Experimental study |
|
Graph algorithms |
|
Graph hierarchies |
|
Hierarchical graph drawings |
|
Indexing schemes |
|
Path concatenation |
|
Path decomposition |
|
Performance |
|
Query processing |
|
Transitive closure |
|
Transitive reduction |
|
Άκυκλοι γράφοι |
|
Αλγόριθμοι γράφων |
|
Απόδοση |
|
Διάσπαση γράφου σε κανάλια |
|
Διάσπαση γράφου σε μονοπάτια |
|
Διαχείριση ερωτημάτων |
|
Δομές δεδομένων |
|
Ιεραρχίες γράφων |
|
Ιεραρχικά γραφήματα |
|
Μεταβατική αφαίρεση |
|
Πειραματική εργασία |
|
Συμπιεσμένη μεταβατική κλειστότητα |
|
Συνένωση μονοπατιών |
|
Σχήμα δεικτών |
| Ημερομηνία έκδοσης |
2022-03-18 |
| Συλλογή
|
Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
|
|
|
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
|
| Εμφανίσεις |
1711 |
Analysis and visualization of hierarchical graphs
