|
In the most efficient way finding the lowest common ancestor (LCA) in a hierarchical (or tree) structure using the adjacency list model.
The adjacency list model simply means that every node has an ID and a ParentID that is pointing to the ID of the ParentNode.
The topmost nodes have null as a parent id.
The calculation/algorithm should take a list or array or similar of nodes as a parameter. (Not be limited to two nodes)
Use language of your own choice.
Wrong is evil and must be defeated. - Jeff Ello
Any organization is like a tree full of monkeys. The monkeys on top look down and see a tree full of smiling faces. The monkeys on the bottom look up and see nothing but assholes.
|
|
|
|
|
No.
It's Saturday you slave driver! 
|
|
|
|
|
I forgot to post it yesterday. 
Wrong is evil and must be defeated. - Jeff Ello
Any organization is like a tree full of monkeys. The monkeys on top look down and see a tree full of smiling faces. The monkeys on the bottom look up and see nothing but assholes.
|
|
|
|
|
Can I assume that there will be more queries so that preprocessing makes sense?
|
|
|
|
|
Didn't think of that. So for the sake of the challenge no.
But good solutions where you think forward, past the stated task, will always get plus points from me.
Wrong is evil and must be defeated. - Jeff Ello
Any organization is like a tree full of monkeys. The monkeys on top look down and see a tree full of smiling faces. The monkeys on the bottom look up and see nothing but assholes.
|
|
|
|
|
It seems a bit boring without preprocessing, that essentially bans all the cool algorithms. At least so far as I know.
With O(n) preprocessing, there's an O(m) algorithm for the LCA of m nodes.
|
|
|
|
|
Huh? What? I just woke up from a nap (18:00 here), I can't think right now.
|
|
|
|
|
Interesting problem. Do we assume that the collection of Nodes to be evaluated do have a common root-level ancestor ? So, if any two Nodes in the evaluated collection do not share the same root, then there is no GCA ?
Does each Node have a collection of pointers to its "child" Nodes ?
«The greater the social and cultural distances between people, the more magical the light can spring from their contact» Milan Kundera, "Testaments Trahis"
|
|
|
|
|
"The topmost nodes have null as a parent id." Note the plural on nodes. So your assumption is correct.
BillWoodruff wrote: Does each Node have a collection of pointers to its "child" Nodes ?
No, just a parent node, but if you want to add a ChildNodes property as a part of your solution, I'm interested to see that too. But assume that the nodes are stored in a database without childnodes and that you can't add them there, so adding them afterwards will affect total performance of the solution.
Wrong is evil and must be defeated. - Jeff Ello
Any organization is like a tree full of monkeys. The monkeys on top look down and see a tree full of smiling faces. The monkeys on the bottom look up and see nothing but assholes.
|
|
|
|
|
Jörgen Andersson wrote: if you want to add a ChildNodes property as a part of your solution, I'm interested to see that too
As the records are read from the database, a pair of Dictionary<id,List<id>> indices can be built -- one to hold ancestors, one to hold descendants. Not sure what to do with them yet, but the two ancestor Lists could be compared fairly easily.
Provided the Lists are ordered with the root first, then compare the Lists until you find the first difference, the previous ancestor is the one you want. Similarly, the Intersection of the sets of ancestors is all the common ancesters.
(It's now midnight and I've been actively working on this for an hour so so far.)
modified 16-Nov-14 19:37pm.
|
|
|
|
|
My idea was to use linked lists.
First create a dictionary for caching the nodes.
Create a linked list for every node in the ParameterCollection, check if the parentnode exists in the dictionary otherwise create it, and AddFirst() to the LinkedList. This way you get it sorted in the right direction.
Then create a collection of enumerators for these LinkedLists and enumerate them until they don't point to the same object anymore. The last common object is the LCA.
An other way is to do it already in SQL, but that's a bit quirkier. I made a tip on that subject a couple of years ago
Wrong is evil and must be defeated. - Jeff Ello
Any organization is like a tree full of monkeys. The monkeys on top look down and see a tree full of smiling faces. The monkeys on the bottom look up and see nothing but assholes.
|
|
|
|
|
My technique begins with a DataTable -- as if read from a database. Makes a Dictionary<ID,List<ID>> .
My method works pretty well.
public System.Data.SqlTypes.SqlGuid
GetLowestCommonAncestor
(
params System.Data.SqlTypes.SqlGuid[] Sought
)
Question:
Is a node its own ancestor?
So far, I don't consider a node to be its own ancestor, but it looks wrong.
If I provide only one ID, should I get that node? Or its parent?
If a nod is an ancestor of the others, should I get that node? Or its parent?
Edit:
"check if the parentnode exists in the dictionary otherwise create it"
Perhaps you're building the map only as you need it (and keeping it I hope).
I'm building the whole map all at once, but perhaps I should be lazier, in case of very large tables.
modified 16-Nov-14 16:35pm.
|
|
|
|
|
PIEBALDconsult wrote: Is a node its own ancestor?
Yeah, it'll have to be. As you've noticed yourself it becomes wrong otherwise.
The purpose is to find the Lowest Common Node that all nodes in the list inherits from. So if I only give one node that's the one I want.
Or if I give you two nodes where one inherits from the other I want the higher up node.
Another case where it becomes wrong is if I put a top node in the parameter collection, it doesn't have a parent.
PIEBALDconsult wrote: Perhaps you're building the map only as you need it (and keeping it I hope).
I'm building the whole map all at once, but perhaps I should be lazier, in case of very large tables.
Yes, but only for the sake of the challenge. In a real world scenario I can't think of a situation where I wouldn't preload the map.
Well, that's of course because my job only handles human hierarchies with less than a million nodes. If I were to work in chemistry or biology the situation could be different.
Wrong is evil and must be defeated. - Jeff Ello
Any organization is like a tree full of monkeys. The monkeys on top look down and see a tree full of smiling faces. The monkeys on the bottom look up and see nothing but assholes.
|
|
|
|
|
Jörgen Andersson wrote: it'll have to be
Small change. Done.
Also, now building the map only as needed. But still building a full index to start with.
Edit: Code more elegant if I always include Guid.Empty as the top-most parent.
modified 16-Nov-14 22:15pm.
|
|
|
|
|
Jörgen Andersson wrote: human hierarchies with less than a million nodes
Hmmm... I might actually be able to use this at work. Sometimes I have to access Active Directory -- to get information on all 400,000-plus employees and contractors. 
Now, in the tradition of !YAGNI -- let's see if it can be made generic. 
Oh, yes, generic. ![Badger | [badger,badger,badger,badger...]](https://codeproject.global.ssl.fastly.net/script/Forums/Images/badger.gif)
modified 16-Nov-14 23:32pm.
|
|
|
|
|
I don't like YAGNI. I've been forced to follow it by pure necessity, but I don't like it.
Whenever I have time to do a proper solution in beforehand (and thinking it through properly) I tend to not having to redo them, and therefore actually save time in the long run.
PIEBALDconsult wrote: Oh, yes, generic
Me likes generic.
Wrong is evil and must be defeated. - Jeff Ello
Any organization is like a tree full of monkeys. The monkeys on top look down and see a tree full of smiling faces. The monkeys on the bottom look up and see nothing but assholes.
|
|
|
|
|
Jörgen Andersson wrote: I don't like YAGNI.
Nor do I. For the same reason.
|
|
|
|
|
Jörgen Andersson wrote: Me likes generic
Oh, yes! Tested with Guid, SqlGuid, Int32, and String ! All success!
One odd discovery is that SqlGuid is IComparable, but not IComparable<T> .
Another minor problem is that default(T) for all but String yields a usable value. Not a surprise, of course, but disappointing.
P.S. SqlInt32 and SqlString also succeed!
|
|
|
|
|
|
I know.
You'll notice from my misunderstanding where my thoughts where already then.
I already have a functional implementation doing this, but I thought there might be other ways I haven't thought about.
Wrong is evil and must be defeated. - Jeff Ello
Any organization is like a tree full of monkeys. The monkeys on top look down and see a tree full of smiling faces. The monkeys on the bottom look up and see nothing but assholes.
|
|
|
|
|
It strikes me that this problem MIGHT be solved using the simplest approach, depending on the frequency of this search for LCA relative to adding or removing elements from the tree, and the efforts already taken to maintain some level of balance in the tree. Any work that's needed to maintain the ancestor lists for every node would slow down the (typically very common) task of adding and removing nodes. It could also add up to a very large amount of storage if the tree is sufficiently large.
However, the simple process starting with the two nodes and moving back up the tree a level at a time until a common ancestor is found should be relatively fast (tree depth should be relatively shallow for a balanced tree), and it requires no additional storage per node.
I realize that this question was asked as more of a "fun" thought experiment, but I think that without more information about the specific task at hand, it's not really possible to determine whether you've found "the most efficient way".
Sorry if I sound like a killjoy.
|
|
|
|
|
Michael Sisco wrote: Sorry if I sound like a killjoy.
No probs at all, your comments are valid.
The origin of the thought experiment is from my job where we are working a lot with human hierarchies. They are not changing very much, nor are they necessarily especially balanced.
But since I'm doing this a quite a lot I've "forgotten" about all the other uses.
And you're quite right about that it's impossible to find the best method since different methods are better in different circumstances.
As a general rule I can say that lists are faster for shallow trees and dictionaries are faster for deeper trees.
But that's the methods I've tested, it would be fun to see if someone could come up with something different.
Wrong is evil and must be defeated. - Jeff Ello
Any organization is like a tree full of monkeys. The monkeys on top look down and see a tree full of smiling faces. The monkeys on the bottom look up and see nothing but assholes.
|
|
|
|
|
About a month ago I got a bar code tattoo, I thought it would be funny to ask the cashier to scan me. Apparently I'm a $5.95 box of condoms, I hate my tattoo artist.
New version: WinHeist Version 2.1.0
There's a fine line between crazy and free spirited and it's usually a prescription.
I'm currently unsupervised, I know it freaks me out too but the possibilities are endless.
|
|
|
|
|
Mike Hankey wrote: box of condoms
Can I buy you? 
|
|
|
|
|
Just think about that for a moment - where would you have to stick him?
OTH it would make for very effective birth control.
Life is like a s**t sandwich; the more bread you have, the less s**t you eat.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
