#### Computational Science Technical Note CSTN-043

#
Exploring Data Structures and Tools for Computations on Graphs and Networks

##
K. A. Hawick

###
Archived August 2007, Revised August 2009

**Abstract**

Many important applications problems can be formulated in terms of network or graph models. There are several well known approaches
to storing and manipulating graph data using conventional data structures such as adjacency matrices and edge list arrays. Some new
powerful possibilities are available using associative and other sophisticated data structures that are built-in to some modern
programming languages. This article reviews these ideas and their use in a library and an associated toolset for measuring graph
and network properties on small and large scale networks from sources including: computer networks; biological networks; socio-nets;
physical models; and other simulated systems. Directed graph networks pose particular problems of their own for efficient storage
and traversal algorithms. Some techniques of interest such as graph colouring; reachability analysis; enumerating circuits and
loops; and eigen-spectral analysis are computationally expensive but have different tradeoffs for optimal efficiency. A primary
``neighbours'' data structure of ``to-arcs'' is used, coupled with various support data structures and routines for conversion
between different sparse and dense network data storage mechanisms. A collection of algorithms and prototype implementations are
given alongwith a discussion of design and implementation issues for these libraries and program tools that use them.

**Keywords:**
graphs; networks; data structures; metrics.

**Full Document Text:**
PDF version.

**Citation Information:** BiBTeX database for CSTN Notes.

**BiBTeX reference:**

@TECHREPORT{CSTN-043,
author = {K.A. Hawick},
title = {Exploring Data Structures and Tools for Computations on Graphs and
Networks},
institution = {Computer Science, Massey University},
year = {2007},
number = {CSTN-043},
month = {August},
timestamp = {2008.10.21},
url = {http://www.massey.ac.nz/~kahawick/cstn/043/cstn-043.pdf}
}

[
CSTN Index |
CSTN BiBTeX
]