3 @brief Data Structure: KD-Tree 4 @details Implementation based on paper @cite book::the_design_and_analysis. 6 @authors Andrei Novikov (pyclustering@yandex.ru) 8 @copyright GNU Public License 10 @cond GNU_PUBLIC_LICENSE 11 PyClustering is free software: you can redistribute it and/or modify 12 it under the terms of the GNU General Public License as published by 13 the Free Software Foundation, either version 3 of the License, or 14 (at your option) any later version. 16 PyClustering is distributed in the hope that it will be useful, 17 but WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19 GNU General Public License for more details. 21 You should have received a copy of the GNU General Public License 22 along with this program. If not, see <http://www.gnu.org/licenses/>. 35 @brief KD-tree text visualizer that provides service to diplay tree structure using text representation. 41 @brief Initialize KD-tree text visualizer. 43 @param[in] kdtree_instance (kdtree): Instance of KD-Tree that should be visualized. 54 @brief Display KD-tree to console. 56 @param[in] display (bool): If 'True' then tree will be shown in console. 58 @return (string) Text representation of the KD-tree. 65 for kdnode
in kdnodes:
75 def __print_node(self, level, kdnode):
76 if level == kdnode[0]:
85 def __get_nodes(self):
90 kdnodes.sort(key =
lambda item: item[0])
97 @brief Represents node of KD-Tree. 101 def __init__(self, data=None, payload=None, left=None, right=None, disc=None, parent=None):
105 @param[in] data (list): Data point that is presented as list of coodinates. 106 @param[in] payload (*): Payload of node (pointer to essense that is attached to this node). 107 @param[in] left (node): Node of KD-Tree that is represented left successor. 108 @param[in] right (node): Node of KD-Tree that is represented right successor. 109 @param[in] disc (uint): Index of dimension of that node. 110 @param[in] parent (node): Node of KD-Tree that is represented parent. 135 @return (string) Default representation of the node. 141 if self.
left is not None:
142 left = self.
left.data
144 if self.
right is not None:
145 right = self.
right.data
147 return "(%s: [L:'%s', R:'%s'])" % (self.
data, left, right)
151 @return (string) String representation of the node. 159 @brief Represents KD Tree that is a space-partitioning data structure for organizing points in a k-dimensional space. 160 @details In the term k-d tree, k denotes the dimensionality of the space being represented. Each data point is represented 161 as a node in the k-d tree in the form of a record of type node. 165 # Import required modules 166 from pyclustering.samples.definitions import SIMPLE_SAMPLES; 167 from pyclustering.container.kdtree import kdtree; 168 from pyclustering.utils import read_sample; 170 # Read data from text file 171 sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE3); 173 # Create instance of KD-tree and initialize (fill) it by read data. 174 tree_instance = kdtree(sample); 176 # Search for nearest point 177 search_distance = 0.3; 178 nearest_node = tree_instance.find_nearest_dist_node([1.12, 4.31], search_distance); 180 # Search for nearest point in radius 0.3 181 nearest_nodes = tree_instance.find_nearest_dist_nodes([1.12, 4.31], search_distance); 182 print("Nearest nodes:", nearest_nodes); 187 def __init__(self, data_list = None, payload_list = None):
189 @brief Create kd-tree from list of points and from according list of payloads. 190 @details If lists were not specified then empty kd-tree will be created. 192 @param[in] data_list (list): Insert points from the list to created KD tree. 193 @param[in] payload_list (list): Insert payload from the list to created KD tree, length should be equal to length of data_list if it is specified. 206 @brief Insert new point with payload to kd-tree. 208 @param[in] point (list): Coordinates of the point of inserted node. 209 @param[in] payload (any-type): Payload of inserted node. It can be identificator of the node or 210 some useful payload that belongs to the point. 212 @return (node) Inserted node to the kd-tree. 218 self.
__root =
node(point, payload,
None,
None, 0)
225 if cur_node.data[cur_node.disc] <= point[cur_node.disc]:
227 if cur_node.right
is None:
228 discriminator = cur_node.disc + 1
232 cur_node.right =
node(point, payload,
None,
None, discriminator, cur_node)
233 return cur_node.right
235 cur_node = cur_node.right
239 if cur_node.left
is None:
240 discriminator = cur_node.disc + 1
244 cur_node.left =
node(point, payload,
None,
None, discriminator, cur_node)
247 cur_node = cur_node.left
252 @brief Remove specified point from kd-tree. 253 @details It removes the first found node that satisfy to the input parameters. Make sure that 254 pair (point, payload) is unique for each node, othewise the first found is removed. 256 @param[in] point (list): Coordinates of the point of removed node. 257 @param[in] **kwargs: Arbitrary keyword arguments (available arguments: 'payload'). 259 <b>Keyword Args:</b><br> 260 - payload (any): Payload of the node that should be removed. 262 @return (node) Root if node has been successfully removed, otherwise None. 267 node_for_remove =
None 268 if 'payload' in kwargs:
271 node_for_remove = self.
find_node(point,
None)
273 if node_for_remove
is None:
276 parent = node_for_remove.parent
279 self.
__root = minimal_node
282 if minimal_node
is not None:
283 minimal_node.parent =
None 285 if parent.left
is node_for_remove:
286 parent.left = minimal_node
287 elif parent.right
is node_for_remove:
288 parent.right = minimal_node
293 def __recursive_remove(self, node_removed):
295 @brief Delete node and return root of subtree. 297 @param[in] node_removed (node): Node that should be removed. 299 @return (node) Minimal node in line with coordinate that is defined by descriminator. 304 if (node_removed.right
is None)
and (node_removed.left
is None):
307 discriminator = node_removed.disc
310 if node_removed.right
is None:
311 node_removed.right = node_removed.left
312 node_removed.left =
None 316 parent = minimal_node.parent
318 if parent.left
is minimal_node:
320 elif parent.right
is minimal_node:
323 minimal_node.parent = node_removed.parent
324 minimal_node.disc = node_removed.disc
325 minimal_node.right = node_removed.right
326 minimal_node.left = node_removed.left
329 if minimal_node.right
is not None:
330 minimal_node.right.parent = minimal_node
332 if minimal_node.left
is not None:
333 minimal_node.left.parent = minimal_node
340 @brief Find minimal node in line with coordinate that is defined by discriminator. 342 @param[in] node_head (node): Node of KD tree from that search should be started. 343 @param[in] discriminator (uint): Coordinate number that is used for comparison. 345 @return (node) Minimal node in line with descriminator from the specified node. 349 min_key =
lambda cur_node: cur_node.data[discriminator]
353 while isFinished
is False:
354 if node_head
is not None:
355 stack.append(node_head)
356 node_head = node_head.left
359 node_head = stack.pop()
360 candidates.append(node_head)
361 node_head = node_head.right
365 return min(candidates, key = min_key)
368 def __fill_tree(self, data_list, payload_list):
370 @brief Fill KD-tree by specified data and create point comparator in line with data type. 372 @param[in] data_list (array_like): Data points that should be inserted to the tree. 373 @param[in] payload_list (array_like): Data point payloads that follows data points inserted to the tree. 376 if data_list
is None or len(data_list) == 0:
379 if payload_list
is None:
381 for index
in range(0, len(data_list)):
382 self.
insert(data_list[index],
None)
385 for index
in range(0, len(data_list)):
386 self.
insert(data_list[index], payload_list[index])
391 def __create_point_comparator(self, type_point):
393 @brief Create point comparator. 394 @details In case of numpy.array specific comparator is required. 396 @param[in] type_point (data_type): Type of point that is stored in KD-node. 398 @return (callable) Callable point comparator to compare to points. 401 if type_point == numpy.ndarray:
402 return lambda obj1, obj2: numpy.array_equal(obj1, obj2)
404 return lambda obj1, obj2: obj1 == obj2
407 def __find_node_by_rule(self, point, search_rule, cur_node):
409 @brief Search node that satisfy to parameters in search rule. 410 @details If node with specified parameters does not exist then None will be returned, 411 otherwise required node will be returned. 413 @param[in] point (list): Coordinates of the point whose node should be found. 414 @param[in] search_rule (lambda): Rule that is called to check whether node satisfies to search parameter. 415 @param[in] cur_node (node): Node from which search should be started. 417 @return (node) Node if it satisfies to input parameters, otherwise it return None. 427 if cur_node.data[cur_node.disc] <= point[cur_node.disc]:
429 if search_rule(cur_node):
433 cur_node = cur_node.right
436 cur_node = cur_node.left
443 @brief Find node with specified coordinates and payload. 444 @details If node with specified parameters does not exist then None will be returned, 445 otherwise required node will be returned. 447 @param[in] point (list): Coordinates of the point whose node should be found. 448 @param[in] point_payload (any): Payload of the node that is searched in the tree. 449 @param[in] cur_node (node): Node from which search should be started. 451 @return (node) Node if it satisfies to input parameters, otherwise it return None. 455 rule_search =
lambda node, point=point, payload=point_payload: self.
__point_comparator(node.data, point)
and node.payload == payload
461 @brief Find node with coordinates that are defined by specified point. 462 @details If node with specified parameters does not exist then None will be returned, 463 otherwise required node will be returned. 465 @param[in] point (list): Coordinates of the point whose node should be found. 466 @param[in] cur_node (node): Node from which search should be started. 468 @return (node) Node if it satisfies to input parameters, otherwise it return None. 478 @brief Find nearest neighbor in area with radius = distance. 480 @param[in] point (list): Maximum distance where neighbors are searched. 481 @param[in] distance (double): Maximum distance where neighbors are searched. 482 @param[in] retdistance (bool): If True - returns neighbors with distances to them, otherwise only neighbors is returned. 484 @return (node|list) Nearest neighbor if 'retdistance' is False and list with two elements [node, distance] if 'retdistance' is True, 485 where the first element is pointer to node and the second element is distance to it. 494 nearest = min(best_nodes, key =
lambda item: item[0])
496 if retdistance
is True:
504 @brief Find neighbors that are located in area that is covered by specified distance. 506 @param[in] point (list): Coordinates that is considered as centroind for searching. 507 @param[in] distance (double): Distance from the center where seaching is performed. 509 @return (list) Neighbors in area that is specified by point (center) and distance (radius). 514 if self.
__root is not None:
520 def __recursive_nearest_nodes(self, point, distance, sqrt_distance, node_head, best_nodes):
522 @brief Returns list of neighbors such as tuple (distance, node) that is located in area that is covered by distance. 524 @param[in] point (list): Coordinates that is considered as centroind for searching 525 @param[in] distance (double): Distance from the center where seaching is performed. 526 @param[in] sqrt_distance (double): Square distance from the center where searching is performed. 527 @param[in] node_head (node): Node from that searching is performed. 528 @param[in|out] best_nodes (list): List of founded nodes. 532 if node_head.right
is not None:
533 minimum = node_head.data[node_head.disc] - distance
534 if point[node_head.disc] >= minimum:
537 if node_head.left
is not None:
538 maximum = node_head.data[node_head.disc] + distance
539 if point[node_head.disc] < maximum:
542 candidate_distance = euclidean_distance_square(point, node_head.data)
543 if candidate_distance <= sqrt_distance:
544 best_nodes.append( (candidate_distance, node_head) )
549 @brief Returns list of children of node. 551 @param[in] node_parent (node): Node whose children are required. 553 @return (list) Children of node. If node haven't got any child then None is returned. 557 if node_parent.left
is not None:
558 yield node_parent.left
559 if node_parent.right
is not None:
560 yield node_parent.right
563 def traverse(self, start_node = None, level = None):
565 @brief Traverses all nodes of subtree that is defined by node specified in input parameter. 567 @param[in] start_node (node): Node from that travering of subtree is performed. 568 @param[in, out] level (uint): Should be ignored by application. 570 @return (list) All nodes of the subtree. 574 if start_node
is None:
578 if start_node
is None:
581 items = [ (level, start_node) ]
582 for child
in self.
children(start_node):
583 if child
is not None:
584 items += self.
traverse(child, level + 1)
def find_minimal_node(self, node_head, discriminator)
Find minimal node in line with coordinate that is defined by discriminator.
def find_node(self, point, cur_node=None)
Find node with coordinates that are defined by specified point.
left
Left node successor of the node.
def traverse(self, start_node=None, level=None)
Traverses all nodes of subtree that is defined by node specified in input parameter.
def __recursive_remove(self, node_removed)
Delete node and return root of subtree.
KD-tree text visualizer that provides service to diplay tree structure using text representation...
parent
Parent node of the node.
def __find_node_by_rule(self, point, search_rule, cur_node)
Search node that satisfy to parameters in search rule.
right
Right node successor of the node.
Utils that are used by modules of pyclustering.
def __recursive_nearest_nodes(self, point, distance, sqrt_distance, node_head, best_nodes)
Returns list of neighbors such as tuple (distance, node) that is located in area that is covered by d...
def remove(self, point, kwargs)
Remove specified point from kd-tree.
def __print_node(self, level, kdnode)
Represents KD Tree that is a space-partitioning data structure for organizing points in a k-dimension...
def __init__(self, data_list=None, payload_list=None)
Create kd-tree from list of points and from according list of payloads.
def __init__(self, kdtree_instance)
Initialize KD-tree text visualizer.
Represents node of KD-Tree.
def find_node_with_payload(self, point, point_payload, cur_node=None)
Find node with specified coordinates and payload.
def find_nearest_dist_node(self, point, distance, retdistance=False)
Find nearest neighbor in area with radius = distance.
def __fill_tree(self, data_list, payload_list)
Fill KD-tree by specified data and create point comparator in line with data type.
def children(self, node_parent)
Returns list of children of node.
payload
Payload of node that can be used by user for storing specific information in the node.
def __create_point_comparator(self, type_point)
Create point comparator.
def find_nearest_dist_nodes(self, point, distance)
Find neighbors that are located in area that is covered by specified distance.
def insert(self, point, payload)
Insert new point with payload to kd-tree.
def __init__(self, data=None, payload=None, left=None, right=None, disc=None, parent=None)
data
Data point that is presented as list of coodinates.
def visualize(self, display=True)
Display KD-tree to console.