trees - tree, ltree or other?

I've been porting one of our web apps from Oracle to postgres.  Chalk up
another win! :)

One part that has me a bit stumped is a fairly critical part of the system
which builds a structure from a relationships table.

Here's what I'm getting at.

CREATE TABLE "node_relationships" (
   "parent_node_id" int4 NOT NULL,
   "child_node_id" int4 NOT NULL,
   "ordinal" int4
);

Obviously there's a relationship between parent_node_id and child_node_id
which  are both FK's  to a second table not shown.

My problem is trying to find a way in postgres to emulate the sort of query
required. An example is
SELECT child_node_id, level
FROM node_relationships
CONNECT BY PRIOR child_node_id = parent_node_id
START WITH parent_node_id=247005
ORDER BY Hierarchy.Branch(level, ordinal)

From poking around the place, the ltree and tree from the GiST site
(http://www.sai.msu.su/~megera/postgres/gist) seem efficient but I'd have to
modify the table and code heavily in order to acommodate the 'tid' (to quote
the dmoz example code)

Another option is the 'Extended nested set model' used by openars
(http://openacs.org/bboard/q-and-a-fetch-msg.tcl?msg_id=0000j6&topic_id=12&t
opic=OpenACS%204.0%20Design) which appears to be a modified version of Celko
from what I've read.  While modifying the existing code appears to be less
troublesome this way, I still have to modify 68,000 odd rows construct the
l_node and r_node columns.

So I guess there are 2 questions.
Which is the better system in this situation (I'm leaning towards the
former)
What would be the best method for adding the r_node and l_node columns. I
think copying the data from one table to the other allowing the triggers to
fire and then renaming the table.

Cheers,
 Graeme