Graphit-db: Πρότυπο Σύστημα Διαχείρισης Δεδομένων Γράφων

Abstract

Οι γράφοι ως δομή χρησιμοποιούνται από πολύ παλιά για την μοντελοποίηση περίπλοκων δεδομένων. Η πλειοψηφία των γνωστών αλγορίθμων γράφων μπορεί να εφαρμοστεί αποδοτικά είτε σε γράφους με μικρό μέγεθος, είτε σε μη-μεταβαλλόμενους γράφους. Η παρούσα διπλωματική ασχολείται με ερωτήματα πάνω σε δεδομένα που είναι οργανωμένα σε γράφους. Η διαφορά των μεθόδων που θα παρουσιάσουμε στη συνέχεια από τις γνωστές βρίσκεται στον τρόπο αναπαράστασης των γράφων. Οι μέθοδοι που προτείνουμε, χρησιμοποιούν μια αναπαράσταση γράφων, στην οποία κάθε γράφος δίνεται ως σύνολο μονοπατιών. Για την αναπαράσταση αυτή χρησιμοποιούμε μια δομή, την οποία ονομάζουμε PATHINDEX και η οποία περιέχει για κάθε κόμβο στοιχεία, όπως τα μονοπάτια στα οποία εμφανίζεται, η θέση του σ'αυτά και οτιδήποτε άλλο μπορεί να χρειάζεται στον κάθε αλγόριθμο. Υλοποιήσαμε αλγορίθμους που χρησιμοποιούν τη δομή PATHINDEX και συγκρίναμε την απόδοσή τους με γνωστούς από τη βιβλιογραφία αλγορίθμους. Στην περίπτωση των πυκνών γράφων, η πλειοψηφία των μεθόδων που προτείνουμε είναι καλύτερες από τις γνωστές.