Adjacency Matrix to Directory Path
Posted: Sun Oct 05, 2008 2:02 am
Hello,
I am essentially using an adjacency matrix in a database to represent a directory structure.
pid represents the parent folder of for that particular "directory_name." So the 'Downloads' directory is a sub-directory of 'Home' and Audio is a sub-directory of 'Downloads.' I am trying to write an algorithm to go through the database and construct the full path to that directory. In other words I would expect to see:
I have written a piece of code that does just this, but I cannot help to think it can be more optimal and elegant (especially with the presence of two while loops). So I seek your advice. I feel recursion would be of an ideal use, unfortunately I can't really make sense of it.
Thank you,
John
I am essentially using an adjacency matrix in a database to represent a directory structure.
Code: Select all
+----+-----+----------------+
| id | pid | directory_name |
+----+-----+----------------+
| 1 | 0 | / |
| 2 | 1 | Home |
| 3 | 2 | Downloads |
| 4 | 2 | Videos |
| 5 | 2 | Audio |
| 6 | 2 | Applications |
| 7 | 5 | Artists |
+----+-----+----------------+
Code: Select all
/
/Home
/Home/Downloads
/Home/Downloads/Videos
/Home/Downloads/Audio
/Home/Downloads/Applications
/Home/Downloads/Audio/ArtistsCode: Select all
$result = mysql_query("SELECT * FROM `directories` ORDER BY `pid`");
while($rows = mysql_fetch_assoc($result)) {
if($rows['directory_name'] != "/") {
echo $root . constructPath($rows['id']) . "<br />";
}
}
function constructPath($id) {
$result = mysql_query("SELECT * FROM `directories` WHERE `id` = '$id'");
$rows = mysql_fetch_assoc($result);
$dirs = array();
array_push($dirs, $rows['directory_name']);
$pid = $rows['pid'];
while($pid != 1) {
$result = mysql_query("SELECT * FROM `directories` WHERE `id` = '$pid'");
$rows = mysql_fetch_assoc($result);
array_push($dirs, $rows['directory_name']);
$pid = $rows['pid'];
}
array_reverse($dirs);
while(sizeof($dirs) != 0) {
$path .= array_pop($dirs) . "/";
}
return $path;
}John