Skip to content

Neighbourhood

Bases: ABC, Generic[IndexType]

Neighbourhood interface.

This class abstracts away getting the neighbours of a region. It allows to get the neighbours at a certain distance or up to a certain distance. It is worth noting, that the distance here is not a metric distance, but a number of hops. This definition makes most sense semantically for grid systems such as H3 or S2 but should work for arbitrary neighbourhoods as well.

The subclasses only need to implement the get_neighbours method, but can also override the get_neighbours_up_to_distance and get_neighbours_at_distance methods for performance reasons. See the H3Neighbourhood class for an example.

Source code in srai/neighbourhoods/_base.py 
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
class Neighbourhood(ABC, Generic[IndexType]):
    """
    Neighbourhood interface.

    This class abstracts away getting the neighbours of a region. It allows to get the neighbours at
    a certain distance or up to a certain distance. It is worth noting, that the distance here is
    not a metric distance, but a number of hops. This definition makes most sense semantically for
    grid systems such as H3 or S2 but should work for arbitrary neighbourhoods as well.

    The subclasses only need to implement the `get_neighbours` method, but can also override the
    `get_neighbours_up_to_distance` and `get_neighbours_at_distance` methods for performance
    reasons. See the `H3Neighbourhood` class for an example.
    """

    @abstractmethod
    def get_neighbours(self, index: IndexType) -> Set[IndexType]:
        """
        Get the direct neighbours of a region using its index.

        Args:
            index (IndexType): Unique identifier of the region.
                Dependant on the implementation.

        Returns:
            Set[IndexType]: Indexes of the neighbours.
        """

    def get_neighbours_up_to_distance(self, index: IndexType, distance: int) -> Set[IndexType]:
        """
        Get the neighbours of a region up to a certain distance.

        Args:
            index (IndexType): Unique identifier of the region.
                Dependant on the implementation.
            distance (int): Maximum distance to the neighbours.

        Returns:
            Set[IndexType]: Indexes of the neighbours.
        """
        neighbours_with_distances = self._get_neighbours_with_distances(index, distance)
        neighbours: Set[IndexType] = seq(neighbours_with_distances).map(lambda x: x[0]).to_set()
        neighbours.discard(index)
        return neighbours

    def get_neighbours_at_distance(self, index: IndexType, distance: int) -> Set[IndexType]:
        """
        Get the neighbours of a region at a certain distance.

        Args:
            index (IndexType): Unique identifier of the region.
                Dependant on the implementation.
            distance (int): Distance to the neighbours.

        Returns:
            Set[IndexType]: Indexes of the neighbours.
        """
        neighbours_up_to_distance = self._get_neighbours_with_distances(index, distance)
        neighbours_at_distance: Set[IndexType] = (
            seq(neighbours_up_to_distance)
            .filter(lambda x: x[1] == distance)
            .map(lambda x: x[0])
            .to_set()
        )
        neighbours_at_distance.discard(index)
        return neighbours_at_distance

    def _get_neighbours_with_distances(
        self, index: IndexType, distance: int
    ) -> Set[Tuple[IndexType, int]]:
        visited_indexes: Dict[IndexType, int] = {}
        to_visit: Queue[Tuple[IndexType, int]] = Queue()

        to_visit.put((index, 0))
        while not to_visit.empty():
            current_index, current_distance = to_visit.get()

            visited_indexes[current_index] = min(
                current_distance, visited_indexes.get(current_index, distance)
            )
            if current_distance < distance:
                current_neighbours = self.get_neighbours(current_index)
                for neighbour in current_neighbours:
                    if neighbour not in visited_indexes:
                        to_visit.put((neighbour, current_distance + 1))

        return set(visited_indexes.items())

get_neighbours abstractmethod 

get_neighbours(index: IndexType) -> Set[IndexType]

Get the direct neighbours of a region using its index.

PARAMETER DESCRIPTION
index

Unique identifier of the region. Dependant on the implementation.

TYPE: IndexType

RETURNS DESCRIPTION
Set[IndexType]

Set[IndexType]: Indexes of the neighbours.
Source code in srai/neighbourhoods/_base.py 
26
27
28
29
30
31
32
33
34
35
36
37
@abstractmethod
def get_neighbours(self, index: IndexType) -> Set[IndexType]:
    """
    Get the direct neighbours of a region using its index.

    Args:
        index (IndexType): Unique identifier of the region.
            Dependant on the implementation.

    Returns:
        Set[IndexType]: Indexes of the neighbours.
    """

get_neighbours_at_distance 

get_neighbours_at_distance(index: IndexType, distance: int) -> Set[IndexType]

Get the neighbours of a region at a certain distance.

PARAMETER DESCRIPTION
index

Unique identifier of the region. Dependant on the implementation.

TYPE: IndexType

distance

Distance to the neighbours.

TYPE: int

RETURNS DESCRIPTION
Set[IndexType]

Set[IndexType]: Indexes of the neighbours.
Source code in srai/neighbourhoods/_base.py 
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
def get_neighbours_at_distance(self, index: IndexType, distance: int) -> Set[IndexType]:
    """
    Get the neighbours of a region at a certain distance.

    Args:
        index (IndexType): Unique identifier of the region.
            Dependant on the implementation.
        distance (int): Distance to the neighbours.

    Returns:
        Set[IndexType]: Indexes of the neighbours.
    """
    neighbours_up_to_distance = self._get_neighbours_with_distances(index, distance)
    neighbours_at_distance: Set[IndexType] = (
        seq(neighbours_up_to_distance)
        .filter(lambda x: x[1] == distance)
        .map(lambda x: x[0])
        .to_set()
    )
    neighbours_at_distance.discard(index)
    return neighbours_at_distance

get_neighbours_up_to_distance 

get_neighbours_up_to_distance(index: IndexType, distance: int) -> Set[IndexType]

Get the neighbours of a region up to a certain distance.

PARAMETER DESCRIPTION
index

Unique identifier of the region. Dependant on the implementation.

TYPE: IndexType

distance

Maximum distance to the neighbours.

TYPE: int

RETURNS DESCRIPTION
Set[IndexType]

Set[IndexType]: Indexes of the neighbours.
Source code in srai/neighbourhoods/_base.py 
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def get_neighbours_up_to_distance(self, index: IndexType, distance: int) -> Set[IndexType]:
    """
    Get the neighbours of a region up to a certain distance.

    Args:
        index (IndexType): Unique identifier of the region.
            Dependant on the implementation.
        distance (int): Maximum distance to the neighbours.

    Returns:
        Set[IndexType]: Indexes of the neighbours.
    """
    neighbours_with_distances = self._get_neighbours_with_distances(index, distance)
    neighbours: Set[IndexType] = seq(neighbours_with_distances).map(lambda x: x[0]).to_set()
    neighbours.discard(index)
    return neighbours