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 geo
spatial 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.