|
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.
|
|
|
|
|
PhilLenoir wrote: where would you have to stick him?
Hmmm, never thought of that
|
|
|
|
|
There are worse things; you could have been a $2.95 package of one of these[^].
Software Zen: delete this;
|
|
|
|
|
New York Times, Nov.15: "No. 1 With a Bullet: ‘Nadeshot’ Becomes a Call of Duty Star" [^].
"Matt Haag, a professional video game player, makes close to a million dollars a year sitting in a soft chair smashing buttons.
...
Three years ago, he was flipping burgers at McDonald’s. Today Mr. Haag, 22, skinny and blindingly pale, makes his living playing Call of Duty, a popular series of war games where players run around trying to shoot one another." What was that catchy refrain in that Rod Stewart hit way-back-when ... "some guys have all the luck ... some guys have all the pain" ... was that it ? Well, wait a minute, that's hardly luck that took Matt to the stars ... is it ? I mean he must have had some genes that got him out the starting gate with the reflexes of a hummingbird on PCP with maybe a chaser of OCD, but I am sure he's earned his place in whatever it is that he's ... in.
«The greater the social and cultural distances between people, the more magical the light can spring from their contact» Milan Kundera, "Testaments Trahis"
|
|
|
|
|
It's still a very low percentage shot.
People should not be making decisions based on looking at one-in-a-million successes.
|
|
|
|
|
PIEBALDconsult wrote: making decisions based on looking at one-in-a-million successes
That is an extremely good point and it may even indicate the popularity of failure.
You see, the media pushes these types of "amazing success" stories to the small-minded people in the world. Then, the small-minded people dream of this type of "success" and yet very, very few ever attain it. However, when one out of the 100 million do, the media pushes it.
And thus, the Stupid-Circle revolves.
Meanwhile, if those 100 million or so would focus on Making Something then they would be much more likely to find real success, though possibly not as flashy.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
