Computational Science Technical Note CSTN-043

CSTN Home

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 ]