converting adjacency matrix into a tree

[Oleg Ogurok]

Hi all,

I'm looking for a fast algorithm to do the following:
A DataTable has the following columns: ID, ParentID, Title, Body, etc. It
represents webforum conversation threads. ParentID points to the ID of the
parent post.
I'm trying to convert this into a tree structure in memory (e.g. XML).

I understand this can be done with recursion but my algorithm seems to be
too slow, i.e. there are too many loops. Does anyone have an example of a
better algorithm?

Thanks.

Mine is (pseudocode):

For each row in table
{
if parent == 0 // top element
{
row.visited = true;
AttachToTree()
RecursivelySearchForChildRen(row)
}
}

method RecursivelySearchForChildRen(parent)
{
Foreach row in table // TODO need to eliminate this extra loop, too
much iterating
{
if row.visited == false && row.parent == parent
{
row.visited = true;
AttachToParent()
RecursivelySearchForChildRen(row) // call itself again
}
}
}

-Oleg.

 

[Brad Williams]

This probably has small chance of working without me implementing and
testing it, but it's a welcome break from writing specs for me, and I hope
it helps. It should perform better than O(n^2). By the way, if your
data is already in a friendly order (parents before children or vice versa)
you could write something very simple that would be wicked fast.

// "map" is an object that maps from an int id to a node object
// "node" is a class holds a row object and a parent node object
foreach row in table
{
if (!map.Exists(row.id))
{
// create parent placeholder node if necessary
if (!map.Exists(row.parentid))
map[row.parentid] = new node(null, null);

// create new node with row and link to parent node
map[row.id] = new node(row, map[row.parentid]);
}
else if (map[row.id].row is null) // node was created as mere
placeholder earlier?
{
// create parent placeholder node if necessary
if (!map.Exists(row.parentid))
map[row.parentid] = new node(null, null);

// fill in this node now with row and link to parent node
map[row.id].row = row;
map[row.id].parentnode = map[row.parentid]
}
}

Brad Williams

 

[Oleg Ogurok]

This is not bad at all. I've tested it.
However, in my scenario, I need to convert ID-ParentID rows of a DataTable
into a Row-ChildrenCollection.
In other words, here's the class structure:

class Node
{
int id;
string name;
NodeCollection subnodes;
}

Your code produces a list of leaves with the ability of walking up to the
top element.
I'm trying to write the opposite, e.g. to get a list of top nodes. Each node
has a pointer to all its children.
Thanks,

-Oleg.