Formal description of a generic graph model with RTPA

摘要

Formal specification of abstract data types (ADTs) is important in modeling system architectures and their implementations. One of the most widely used ADTs is graph, since many problems in sciences and engineering can be formulated and solved by a graph model. In this paper, we present a formal approach to the specification of graphs as an ADT using real-time process algebra (RTPA). RTPA is a formal method that describes a software system, especially a real-time system, as a set of processes. We use RTPA to describe a generic graph model in three parts encompassing the architecture, static and dynamic behaviors. In the RTPA specification, the graph behaviors can be classified into four categories, namely: (a) basic operations (InsertNode, DeleteNode, InsertEdge, DeleteEdge, GetSize, GetNumberOfEdges, Retrieve, Update, and Search); (b) node/edge-specific operations (FindNode, FindEdge, Fanin, Fanout, FindNeighbours, and Degree); (c) pointer operations (CurrentNode and CurrentEdge); and (d) utility operations (Create, Clear, and Release). Each of the 20 operations is formally described by an RTPA processes in a unified encapsulation of graph behaviors. On the basis of the RTPA graph model, a wide range of graph-based applications can be implemented by sharing the common architecture and behaviors of the graph as a system type or class.