GNet: A generalized network model and its applications in qualitative spatial reasoning

A data model, named generalized network (GNet), is proposed to perform various network-tracing tasks, especially tracing conceptual proposition networks in qualitative spatial reasoning (QSR). The GNet model can be defined as a 6-tuple: (V, A, q, ⊕, ∼, L). By specifying each element in the 6-tuple, a GNet can function as a conventional network, or an activity on edge (AOE) network, etc. The algorithm for searching for the generalized optimum path weight (GOPW) between two vertices in a GNet is developed by extending the Bellman-Ford algorithm (EBFA). Based on the GNet model, this paper focuses on representing spatial knowledge, which consists of a set of binary relations. We present two applications of GNets, namely the RCC8 network and the hybrid RCC8 network involving cardinal direction relations. Both can be traced to infer new spatial knowledge using EBFA. The applications demonstrate that the GNet model provides a promising approach to dealing with proposition-based geospatial knowledge based on weak composition. We also point out that EBFA can check whether a network is algebraically closed, or path-consistent when the corresponding composition table is extensional.