Author Topic: Family tree width algorithm  (Read 3497 times)

0 Members and 1 Guest are viewing this topic.

Offline Camel

  • Hero Member
  • *****
  • Posts: 1703
    • View Profile
    • BNU Bot
Family tree width algorithm
« 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
« Last Edit: March 10, 2008, 02:39:35 pm by Camel »

<Camel> i said what what
<Blaze> in the butt
<Camel> you want to do it in my butt?
<Blaze> in my butt
<Camel> let's do it in the butt
<Blaze> Okay!