BUG: relative neighbourhood depends on the order of observations

[martinfleis]

The graph coming from the relative neighbourhood depends on the order of observations in the df. I guess that should not happen.

import geodatasets
import geopandas

from libpysal.graph._triangulation import _relative_neighborhood

stores = geopandas.read_file(geodatasets.get_path("geoda liquor_stores")).explode(
    index_parts=False
)
stores_unique = stores.drop_duplicates(subset="geometry")

for _ in range(5):
    data = stores_unique.sample(frac=1)
    head, tail, weight = _relative_neighborhood(data)
    print(head.shape)

(3360,)
(3338,)
(3360,)
(3346,)
(3342,)

This issue is also present in the implementation in weights, not only the new one.

for _ in range(5):
    data = stores_unique.sample(frac=1)
    W = weights.Relative_Neighborhood.from_dataframe(data)
    print(W.to_adjlist().shape)

(3352, 3)
(3350, 3)
(3340, 3)
(3344, 3)
(3352, 3)

[ljwolf]

Wow indeed should not happen.

I will get a look next week.

[ljwolf]

I think the issue is that the dkmax search (the inner loop if filter_relativehood) has to iterate over all pairs, rather than terminating early.