Page 1 of 1

Adjacency Matrix to Directory Path

Posted: Sun Oct 05, 2008 2:02 am
by SidewinderX
Hello,

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        |
+----+-----+----------------+
 
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:

Code: Select all

/
/Home
/Home/Downloads
/Home/Downloads/Videos
/Home/Downloads/Audio
/Home/Downloads/Applications
/Home/Downloads/Audio/Artists
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.

Code: 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;
    
}
Thank you,
John

Re: Adjacency Matrix to Directory Path

Posted: Sun Oct 05, 2008 2:53 am
by josh
SidewinderX wrote: I cannot help to think it can be more optimal and elegant
oh it can.
http://www.doctrine-project.org/documen ... hical-data

recursion is definitely one technique, but another approach is called tree traversal ( see wikipedia )