Algorithms and data structures for graph analysis
This work proposes an implementation of adjacency lists for graph structures using a hash table with arrays, where the arrays indicate edges to vertices, and proposes dedicated objects for both vertices and edges, allowing for easily adding information to both vertice and edges.
Abstract
Introduction Software implementations for graph structures can represent a graph as an adjacency list or a sparse adjacency matrix. There are no standards regarding the implementation details of adjacency list or adjacency matrix structures. Notable parties propose different implementations for adjacency lists [1]. Guido van Rossum suggests using a hash table with arrays, where the arrays indicate edges to vertices. Cormen et al. [2] suggest using an array of singly linked lists. Goodrich and Tamassia propose dedicated objects for both vertices and edges, allowing for easily adding information to both vertices and edges. Each of the implementation suggestions has advantages and disadvantages. One can easily come up with more variations, but their trade-offs in the context of graph applications are not clear.