Gabriel network

Navigation:  Network and Location Analysis > Network Construction, Optimal Routes and Optimal Tours >

Gabriel network

Previous pageReturn to chapter overviewNext page

A form of network that is a super-set of the MST and has a variety of uses is known as the Gabriel network, named after its principal originator, K R Gabriel (see Gabriel and Sokal (1969) for more details). The Gabriel network for a point set, such as that shown in Figure 7‑4A, is created by adding edges between pairs of points in the source set iff there are no other points from the set contained within a circle whose diameter passes through the two points (see Figure 7‑5A — black circles). In this example the green circle shown encloses another point from the set so a link between the two points used to create this circle is not included in the final solution (the straight lines). The process continues until all point pairs have been examined in this manner and linked where the condition holds (Figure 7‑5B).

Figure 7‑5 Gabriel network construction

A. Gabriel network construction

B. Gabriel network

clip0356

clip0357.zoom65

The Gabriel network provides a form of network that contains more links than a MST and hence provides greater connectivity especially between nearby points that are not actually nearest neighbors. It was introduced as one means of uniquely defining contiguity for a point set such that no other point could be regarded as lying ‘between’ connected pairs. It has been used in a variety of applications, most notably in genetic studies of populations (human and other). Examples include the research of Sokal et al. (1986) into the genetic makeup of the Yanomama Amerindian villages and the research by Arnaud et al. (1999) into land snail genetics. In each case the Gabriel network was judged to be a meaningful description of connectivity, with the option of binary or edge weighted measurement. The measure was then used to determine the spatial weights matrix in autocorrelation analyses. The MST can be produced as a subset of the Gabriel network as follows:

(i) construct an initial subset of the Gabriel network in which the additional constraint is applied that no other points may lie within the area of intersection defined by circles placed at each Gabriel network node with radius equal to the inter-node separation (see Figure 7‑6B). The resulting network is called a Relative Neighborhood Network (Figure 7‑6C, e.g. see implementations in Manifold GIS and PASSaGE spatial ecology software); (ii) remove the longest link in the relative network that does not break overall network connectivity; (iii) repeat step (ii) until no further reduction in overall length is achieved (see Figure 7‑6D — the line identified by the arrow is the only edge requiring removal).

Figure 7‑6 Relative neighborhood network and related constructions

A. Point set (nodes or vertices)

B. Relative neighborhood construction

clip0358.zoom50

clip0359.zoom50

C. Relative neighborhood network

D. Minimum spanning tree

clip0360.zoom50

clip0361.zoom50

Although not specifically described in detail, this appears to be the general procedure adopted in the Manifold GIS for creating an MST. As opposed to the construction approached described earlier, this method commences with a promising solution that is a superset of the MST and reduces it until the MST is determined. A variant of the procedure is sometimes described as the k-MST problem, in which an MST is sought for a given subset, k<=n vertices, with the remaining vertices either connected via an existing set of edges or not connected.

The various networks described so far have involved construction using Euclidean straight lines and the Euclidean metric (L2). Solutions to problems such as determining the MST and many of those that are discussed in the following subsections may also be sought using other metrics. Extensive research exists into solutions that apply for the L1 metric, not merely because this may provide a more meaningful measure for street patterns in many cities, but also because in unrelated areas, such as electronic circuit design and utility infrastructure planning, such metrics are often more appropriate. Examples of solutions for alternative metrics will be provided later in this chapter.