User login

Representing all hierarchies as sets of linear progressions for a given point in a complex hierarchy- a C programmer's answer

[The answer is most likely here, if I could understand it.]

TwinStar01: Mornin'
I3IVIIVI: mornin... programming question, been working 24/7, 3 hours left to get code in...
I3IVIIVI: OK, so it's something really basic, and it's taken up a critical 8 or so hours... my brain keeps folding back on itself.
[10:35am] agaric: How do I create an array of all possible hierarchies for a term?
[10:37am] agaric: term A can have n parents, each of which can have n parents, etc. I keep messing with recursion and counting loops and while loops and make a mess out of all of them
TwinStar01: have each term have a linked list (double if you want) where each element is a reference to one of its parents.
I3IVIIVI: i've been reading about those solutions and not understanding what to do with them
TwinStar01: What language are we programming in?
I3IVIIVI: i have a term > parent (multiple parents) and
I3IVIIVI: php
TwinStar01: Is that anything like C/C++ at all??
I3IVIIVI: it's just one table with two columns, term and parent, and each term can have multiple parents
I3IVIIVI: yes
I3IVIIVI: I want to put it all in an array or object
I3IVIIVI: my problem is keeping track of what I've done and knowing when to stop
TwinStar01: So, your object is Term, correct?
I3IVIIVI: all we need to care about is term as a number
I3IVIIVI: term 1 has parents terms 2 and 3, parent term 2 has parent terms 4, 5, and 6 ...
I3IVIIVI: possibility of crossing and stuff
TwinStar01: So it's possible that Term 1 has parent Term 2, and Term 2 has parent Term 1.
I3IVIIVI: think so
TwinStar01: cringe That's poor programming.
I3IVIIVI: well not as a loop though
TwinStar01: oh!
TwinStar01: that's good.
TwinStar01: Do you know how to use linked lists?
I3IVIIVI: no, it's slowly dawning on me that I don't know computer programming at all
TwinStar01: lol, that's not true
TwinStar01: K, well in this case linked list is an object with two values, one is a pointer to a Term, and the other is a pointer to the next linked list element.
I3IVIIVI: ok, that's pretty much what we have
TwinStar01: Ok... what's the problem then?
I3IVIIVI: I need to pull out all the possible hierarchies
I3IVIIVI: Instead of one crazy tree, I need "n" ladders
I3IVIIVI: so to speak
TwinStar01: No, I htink the crazy tree is better
TwinStar01: (bbiab, drycleaner)
I3IVIIVI: aaaahhhhh! No, for storage, yes, for what I need to display, I NEED MY N LADDERS! sob
I3IVIIVI: 10 hours ago...
TwinStar01: I don't understand what this ladder you need is
I3IVIIVI: 1 > 3 > 5 > 9
I3IVIIVI: 1 > 2 > 6 > 8
I3IVIIVI: term 1 and it's ancestors
TwinStar01: Ok..... you get that through doing a tree traversal
I3IVIIVI: 1 > 2 > 4 > 10
I3IVIIVI: I loop, I recurse, I do everything but don't get the results I'm looking for
TwinStar01: Well I think recursion is your best bet...
I3IVIIVI: yes, but how do I put the answers it spits out somewhere?
I3IVIIVI: damnit, I know I know how to do this but my brain melted hours ago
TwinStar01: K I think I got it
TwinStar01: Ultimately, there will be terms with no parents, which is how we know to print out the list of terms, right?
I3IVIIVI: yeah, but each list may be a different length
TwinStar01: no problem
I3IVIIVI: wow
TwinStar01: what you're going to do is have a single list that updates itself while you're traveling through the terms
TwinStar01: The list keeps track of each term you've visited so far.
TwinStar01: If 'this' term has any parens, add 'this' to the list and follow the next parent
TwinStar01: If 'this' term has -no- parents, print out the list and print 'this' term.
TwinStar01: LADDER(TERM, LIST)
IF [TERM has no PARENTs] [print LIST, print TERM]
ELSEIF [next PARENT] [add TERM to LIST, LADDER(PARENT, LIST), remove last item from LIST]
I3IVIIVI: it's moving to the next parent/term that Ican't seem to get
I3IVIIVI: oh
I3IVIIVI: function cmt_get_ancestors($tid, $vid, $ancestors=array(), $thread = 0) {
static $hierarchies;
$result = db_query('SELECT t.tid, t.*, parent FROM {cmt_term_data} t INNER JOIN {cmt_term_vocab} v ON t.tid = v.tid INNER JOIN {cmt_term_hierarchy} h ON t.tid = h.tid WHERE t.tid = %d AND v.vid = %d ORDER BY weight, name', $tid, $vid);
while ($term = db_fetch_object($result)) {
$ancestors[$thread][] = $tid;
$ancestors = array_merge($ancestors, cmt_get_ancestors($term->parent, $vid, $ancestors, $thread));
$thread++;
}
return $ancestors;
}

I3IVIIVI: doesn't quite turn out right:
I3IVIIVI: Array
(
[0] ? Array
(
[0] ? 3
)

[1] ? Array
(
[0] ? 3
[1] ? 2
)

[2] ? Array
(
[0] ? 3
[1] ? 2
[2] ? 1
)

[3] ? Array
(
[0] ? 3
[1] ? 2
[2] ? 1
)

)
I3IVIIVI: oh, smiley faces just to taunt me!
TwinStar01: what does it look like it's doing
I3IVIIVI: giving me output each step
I3IVIIVI: it should only be: 3 2 1
TwinStar01: You should ONLY output if the current term has no ancestors
I3IVIIVI: can't figure how to track without outputting
TwinStar01: You track in the List.
I3IVIIVI: think i'm just figuring that out..
TwinStar01: if THIS has parents, (1) add THIS to the list, (2) loop on the next parent, and (3) remove THIS from the list. Rinse and repeat for each parent. Yes, I DO want you to add and remove THIS term each time
TwinStar01: I suppose, alternatively, you could add THIS to the list, loop on -each- parent, then remove THIS from the list once you're out of parents
I3IVIIVI: how do I keep track of the multiple lists?
TwinStar01: You don't. There's only one list that's constantly updating.
I3IVIIVI: but I need n threads, not just n items
TwinStar01: The list is only alive while you're printing out the traversal
TwinStar01: If you really really really need each item to have a list of lists, that's going to be a lot of overhead.
TwinStar01: BTW, you're Tuxing tomorrow, right?
I3IVIIVI: if i live
TwinStar01: you'll be fine

[The answer is most likely here, if I could understand it.]

TwinStar01: Mornin'
I3IVIIVI: mornin... programming question, been working 24/7, 3 hours left to get code in...
I3IVIIVI: OK, so it's something really basic, and it's taken up a critical 8 or so hours... my brain keeps folding back on itself.
[10:35am] agaric: How do I create an array of all possible hierarchies for a term?
[10:37am] agaric: term A can have n parents, each of which can have n parents, etc. I keep messing with recursion and counting loops and while loops and make a mess out of all of them
TwinStar01: have each term have a linked list (double if you want) where each element is a reference to one of its parents.
I3IVIIVI: i've been reading about those solutions and not understanding what to do with them
TwinStar01: What language are we programming in?
I3IVIIVI: i have a term > parent (multiple parents) and
I3IVIIVI: php
TwinStar01: Is that anything like C/C++ at all??
I3IVIIVI: it's just one table with two columns, term and parent, and each term can have multiple parents
I3IVIIVI: yes
I3IVIIVI: I want to put it all in an array or object
I3IVIIVI: my problem is keeping track of what I've done and knowing when to stop
TwinStar01: So, your object is Term, correct?
I3IVIIVI: all we need to care about is term as a number
I3IVIIVI: term 1 has parents terms 2 and 3, parent term 2 has parent terms 4, 5, and 6 ...
I3IVIIVI: possibility of crossing and stuff
TwinStar01: So it's possible that Term 1 has parent Term 2, and Term 2 has parent Term 1.
I3IVIIVI: think so
TwinStar01: cringe That's poor programming.
I3IVIIVI: well not as a loop though
TwinStar01: oh!
TwinStar01: that's good.
TwinStar01: Do you know how to use linked lists?
I3IVIIVI: no, it's slowly dawning on me that I don't know computer programming at all
TwinStar01: lol, that's not true
TwinStar01: K, well in this case linked list is an object with two values, one is a pointer to a Term, and the other is a pointer to the next linked list element.
I3IVIIVI: ok, that's pretty much what we have
TwinStar01: Ok... what's the problem then?
I3IVIIVI: I need to pull out all the possible hierarchies
I3IVIIVI: Instead of one crazy tree, I need "n" ladders
I3IVIIVI: so to speak
TwinStar01: No, I htink the crazy tree is better
TwinStar01: (bbiab, drycleaner)
I3IVIIVI: aaaahhhhh! No, for storage, yes, for what I need to display, I NEED MY N LADDERS! sob
I3IVIIVI: 10 hours ago...
TwinStar01: I don't understand what this ladder you need is
I3IVIIVI: 1 > 3 > 5 > 9
I3IVIIVI: 1 > 2 > 6 > 8
I3IVIIVI: term 1 and it's ancestors
TwinStar01: Ok..... you get that through doing a tree traversal
I3IVIIVI: 1 > 2 > 4 > 10
I3IVIIVI: I loop, I recurse, I do everything but don't get the results I'm looking for
TwinStar01: Well I think recursion is your best bet...
I3IVIIVI: yes, but how do I put the answers it spits out somewhere?
I3IVIIVI: damnit, I know I know how to do this but my brain melted hours ago
TwinStar01: K I think I got it
TwinStar01: Ultimately, there will be terms with no parents, which is how we know to print out the list of terms, right?
I3IVIIVI: yeah, but each list may be a different length
TwinStar01: no problem
I3IVIIVI: wow
TwinStar01: what you're going to do is have a single list that updates itself while you're traveling through the terms
TwinStar01: The list keeps track of each term you've visited so far.
TwinStar01: If 'this' term has any parens, add 'this' to the list and follow the next parent
TwinStar01: If 'this' term has -no- parents, print out the list and print 'this' term.
TwinStar01: LADDER(TERM, LIST)
IF [TERM has no PARENTs] [print LIST, print TERM]
ELSEIF [next PARENT] [add TERM to LIST, LADDER(PARENT, LIST), remove last item from LIST]
I3IVIIVI: it's moving to the next parent/term that Ican't seem to get
I3IVIIVI: oh
I3IVIIVI: function cmt_get_ancestors($tid, $vid, $ancestors=array(), $thread = 0) {
static $hierarchies;
$result = db_query('SELECT t.tid, t.*, parent FROM {cmt_term_data} t INNER JOIN {cmt_term_vocab} v ON t.tid = v.tid INNER JOIN {cmt_term_hierarchy} h ON t.tid = h.tid WHERE t.tid = %d AND v.vid = %d ORDER BY weight, name', $tid, $vid);
while ($term = db_fetch_object($result)) {
$ancestors[$thread][] = $tid;
$ancestors = array_merge($ancestors, cmt_get_ancestors($term->parent, $vid, $ancestors, $thread));
$thread++;
}
return $ancestors;
}

I3IVIIVI: doesn't quite turn out right:
I3IVIIVI: Array
(
[0] ? Array
(
[0] ? 3
)

[1] ? Array
(
[0] ? 3
[1] ? 2
)

[2] ? Array
(
[0] ? 3
[1] ? 2
[2] ? 1
)

[3] ? Array
(
[0] ? 3
[1] ? 2
[2] ? 1
)

)
I3IVIIVI: oh, smiley faces just to taunt me!
TwinStar01: what does it look like it's doing
I3IVIIVI: giving me output each step
I3IVIIVI: it should only be: 3 2 1
TwinStar01: You should ONLY output if the current term has no ancestors
I3IVIIVI: can't figure how to track without outputting
TwinStar01: You track in the List.
I3IVIIVI: think i'm just figuring that out..
TwinStar01: if THIS has parents, (1) add THIS to the list, (2) loop on the next parent, and (3) remove THIS from the list. Rinse and repeat for each parent. Yes, I DO want you to add and remove THIS term each time
TwinStar01: I suppose, alternatively, you could add THIS to the list, loop on -each- parent, then remove THIS from the list once you're out of parents
I3IVIIVI: how do I keep track of the multiple lists?
TwinStar01: You don't. There's only one list that's constantly updating.
I3IVIIVI: but I need n threads, not just n items
TwinStar01: The list is only alive while you're printing out the traversal
TwinStar01: If you really really really need each item to have a list of lists, that's going to be a lot of overhead.
TwinStar01: BTW, you're Tuxing tomorrow, right?
I3IVIIVI: if i live
TwinStar01: you'll be fine

Comments

Post new comment

The content of this field is kept private and will not be shown publicly.
  • You may post code using <code>...</code> (generic) or <?php ... ?> (highlighted PHP) tags.
  • You can use Markdown syntax to format and style the text. Also see Markdown Extra for tables, footnotes, and more.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd> <img> <blockquote> <small> <h2> <h3> <h4> <h5> <h6> <sub> <sup> <p> <br> <strike> <table> <tr> <td> <thead> <th> <tbody> <tt> <output>
  • Lines and paragraphs break automatically.

More information about formatting options

By submitting this form, you accept the Mollom privacy policy.