EvilC's Hierarchical Bunching Method-Database
From Google Mapki
Contents |
The Database
To meet our needs, two tables will suffice:
Locations
This holds the information about any points, lines or polygons that will be shown.
Bunch points will have an entry in here AND the regions table.It is not hierarchically sorted, each location has:
- location_id: index for the locations table
- lat & lng: holds the location data.
- name: name of the location
- region_id: The region it is in.
- represents_region: If this is a bunch point, set to the region_id that it represents.
CREATE TABLE `locations` ( `location_id` int(10) NOT NULL auto_increment, `name` text NOT NULL, `lat` double NOT NULL default '0', `lng` double NOT NULL default '0', `region_id` int(10) NOT NULL default '0', `represents_region` int(10) NOT NULL default '0', PRIMARY KEY (`location_id`) ) AUTO_INCREMENT=12 ; INSERT INTO `locations` VALUES (1, 'The World', 0, 0, 0, 1); INSERT INTO `locations` VALUES (2, 'UK', 53.54031, -4.24072, 1, 2); INSERT INTO `locations` VALUES (3, 'England', 53.17312, -0.92285, 2, 3); INSERT INTO `locations` VALUES (4, 'Scotland', 57.00485, -4.570312, 2, 4); INSERT INTO `locations` VALUES (5, 'Northern Ireland', 54.648413, -7.168579, 2, 5); INSERT INTO `locations` VALUES (6, 'Wales', 52.254709, -3.515625, 2, 6); INSERT INTO `locations` VALUES (7, 'London', 51.49945, -0.11332, 3, 0); INSERT INTO `locations` VALUES (8, 'Manchester', 53.448807, -2.219238, 3, 0); INSERT INTO `locations` VALUES (9, 'Glasgow', 55.899956, -4.21875, 4, 0); INSERT INTO `locations` VALUES (10, 'Belfast', 54.572062, -5.888672, 5, 0); INSERT INTO `locations` VALUES (11, 'Cardiff', 51.508742, -3.164062, 6, 0);
Regions
This holds the regions for the bunch points.
- region_id: index for the regions table
- name: not needed, but useful for things such as building a menu to filter regions etc.
- lft & rgt: hold the nested (minor) set tree
- parent_id: holds the adjacency list (master) tree
- zoom: Zoom value at which this region disappears
CREATE TABLE `regions` ( `region_id` int(10) NOT NULL auto_increment, `name` text NOT NULL, `lft` int(10) default NULL, `rgt` int(10) default NULL, `parent_id` int(10) NOT NULL default '0', `zoom` int(2) NOT NULL default '17', PRIMARY KEY (`region_id`) ) AUTO_INCREMENT=7 ; INSERT INTO `regions` VALUES (1, 'The World', 1, 12, 0, 1); INSERT INTO `regions` VALUES (2, 'United Kingdom', 2, 11, 1, 5); INSERT INTO `regions` VALUES (3, 'England', 3, 4, 2, 6); INSERT INTO `regions` VALUES (4, 'Scotland', 5, 6, 2, 6); INSERT INTO `regions` VALUES (5, 'Ireland', 7, 8, 2, 7); INSERT INTO `regions` VALUES (6, 'Wales', 9, 10, 2, 7);
Setting the nested set tree up
These examples include data with the nested set lft and rgt values pre-calculated.
It is possible to modify the table yourself, as long as you understand the basic adjacency list model, just fiddle with the parent_id of a region to add a new one (Don't forget to add a corresponding location !) You can use this PHP code to rebuild the nested set tree (lft,rgt) from the adjacency list (parent_id) tree:
<?php
$host = 'localhost';
$user = 'root';
$pass = ;
$dbname = 'test';
if (!$db = mysql_connect($host, $user, $pass)) {
echo 'Could not connect to mysql';
exit;
}
if (!mysql_select_db($dbname, $db)) {
echo 'Could not select database';
exit;
}
$regctr=0;
if (mysql_query("LOCK TABLE regions WRITE")){
rebuild_tree('regions', 'region_id', 'parent_id', 1, 1);
mysql_query("UNLOCK TABLES");
}
echo "$regctr regions updated.";
// rebuilds nested set tree from adjacency list tree.
// call on the root node and it will recursively set the lft and rgt values
// you should lock the table before you do this in a multi-user environment !
//eg: rebuild_tree('regions', 'region_id', 'parent_id', 1, 1);
function rebuild_tree($table, $index_lookup, $parent_lookup, $node, $left) {
global $regctr;
$regctr++;
$right = $left+1;
$query = "SELECT * FROM $table WHERE $parent_lookup=$node";
$query = mysql_query($query);
while ($row = mysql_fetch_assoc($query)){
$right = rebuild_tree($table, $index_lookup, $parent_lookup, $row[$index_lookup], $right);
}
$query2="SELECT * FROM $table WHERE $index_lookup = '$node'";
$query2=mysql_query($query2);
$index_name=mysql_fetch_assoc($query2);
//echo $index_name['name']." ( ID: ".$index_name['region_id'].", PARENT: ".$index_name['parent_id']." ) - lft: $left, rgt: $right
";
mysql_query("UPDATE $table SET lft='$left', rgt='$right' WHERE $index_lookup='$node'");
return $right+1;
}
?>
