A taxonomy of graph representations

Abstract

Graphs are mathematical abstractions that are useful for solving many types of problems in computer science. In this dissertation, when we talk of graphs we refer to directed graphs (digraphs), which consist of a set of nodes and a set of edges between the nodes, where each edge has a direction. Numerous implementations of graphs exist in computer science however, there is a need for more systematic and complete categorisation of implementations together with some proof of correctness. Completeness is an issue because other studies only tend to discuss the useful implementations and completely or partially ignore the rest. There is also a need for a treatment of graph representations using triples instead pairs as the base component. In this dissertation, a solution to each of these deficiencies is presented. This dissertation is a taxonomic approach towards a comprehensive treatment of digraph representations. The difficulty of comparing implementations with each other is overcome by a creating a taxonomy of digraph implementations. Taxonomising digraph representations requires a systematic analysis of the two main building blocks of digraphs implementations namely maps and sets. The analysis presented in the first part of the dissertation includes a definition of the abstract data types to represent maps and sets together with a comprehensive and systematic collection of algorithms and data-structures required for the implementations thereof. These algorithms are then written and re-written in a common notation and are examined for any essential com¬ponents, differences, variations and common features. Based on this analysis the maps and sets taxonomies are presented. After the completion of maps and sets implementation foundations the dissertation continues with the main contribution: a systematic collection and implementation of other operators used for the manipulation of the base triple components of digraphs and the derivation of the the final taxonomy of digraphs by integrating the maps and sets implementations with the operators on the sets of triples. With the digraph taxonomy we can finally see relationships between implementations and we also can easily establish their similarities and differences. Furthermore, the taxonomy is also useful for further discussions, analysis and visualisation of the complete implementation topography of digraph implementations.