Clan x86

General Forums => Academic / School => Math and Other Problems => Topic started by: Camel on March 10, 2008, 02:27:13 pm

Title: Family tree width algorithm
Post by: Camel on March 10, 2008, 02:27:13 pm

I'm writing a family tree display widget for BNU; http://www.clanbnu.net/members.php

Each member, except for the clan creator, has a parent. Each member gets an HTML table tag, residing somewhere inside their parent's table. The goal of this widget is to pack as many tables in to each row as possible, without exceeding the maximum width as defined by a variable. I'm looking for an algorithm that can do this packing in an intuitive way.

My current algorithm calculates recursively the width that a table would be if each child were to appear horizontally; if it exceeds the maximum specified width, it chooses to display children vertically.

I'm using PHP, but a general algorithm will be sufficient. I start by building an array of all the members in this manner:
user : array(
    name => string,
    access => int,
    children => array<int, user>)

Here's a sample of what it might look like:

Code: [Select]

Array
(
    [name] => Camel
    [access] => 36
    [children] => Array
        (
            [3] => Array
                (
                    [name] => Sorceress
                    [access] => 35
                    [children] => Array
                        (
                            [11] => Array
                                (
                                    [name] => Avenger
                                    [access] => 25
                                    [children] => Array
                                        (
                                        )

                                )

                        )

                )

            [37] => Array
                (
                    [name] => Pestilence
                    [access] => 22
                    [children] => Array
                        (
                        )

                )

            [78] => Array
                (
                    [name] => Shfine
                    [access] => 15
                    [children] => Array
                        (
                        )

                )

            [4] => Array
                (
                    [name] => Bot
                    [access] => 3
                    [children] => Array
                        (
                        )

                )

        )

)

Any suggestions?

[edit] Source: http://www.clanbnu.net/members.php?source=1