Algorithm to find all linked objects that aren't a parent/grandparent/etc or a child/grandchild/etc

I have an object called Device. A Device can have one parent Device. A Device can also have n child Devices.

I have a drop down list that shows all the selectable Devices. I can get all the Devices in the database quite easily - db.Devices.

The hierarchy can be infinite levels deep.

I need to get all Devices that aren't above or below a given Device in the tree. Essentially I'm asking for Devices unrelated to a given Device (neither a parent/grandparent/great grandparent/etc or a child/grandchild/great grandchild/etc). I also need to exclude the given Device from t开发者_如何学JAVAhe list.

What is the best way to do this? Should I use recursion?

(I am using C# and Entity Framework with an SQL Server database, so I can use Linq To SQL or use the model itself.)

---

My approach would be first to get all of the siblings of the device D:

P = parent of the device
sibs = {all children of P that are not D}

Any descendants of any d in sibs is unrelated to D. Keep going up the family tree:

G = grandparent of the device
sibs = sibs union {all children of G that are not P}

Continuing this way, the set sibs and all their descendants is the set you're after.

In pseudocode:

D = device;
siblings = {};
while (D has parent) {
    P = parent(D);
    siblings = siblings union (children(P) \ D);
    D = P;
}
return descendants(siblings);

---

Agree with Denis - this depends on how your data is stored.

I'd suggest you implement your hierarchy using the TSQL HierarchyId datatype. You can then very easily check if a row is a descendent of another row using IsDescendent

DECLARE @searchId HierarchyId -- select your id
SELECT @searchId = HierarchyId FROM Devices WHERE DeviceId = 1

SELECT * FROM Devices 
WHERE 
    -- not children
    DeviceHierarchyId.IsDescendantOf(@seachId) = 0
    -- not parents
    AND @searchId.IsDescendantOf(DeviceHierarchyId) = 0

edit

To briefly explain the HierarchyId datatype and how this would work, consider that each item has a place in a hierarchy under a root node. (If you have multiple natural roots, you would place each root under a super-root). Each hierarchyid column stores the complete hierarchical position of item. For example

Id | ParentId | HierarchyId
1 | null | \1
2 | 1    | \1\2
3 | 1    | \1\3
4 | 3    | \1\3\4

and so on. To check whether an item is a child of another, simply check whether the hierarchyId is contained within the other row's hierarchyId - e.g. 4 is a child of 3 because the entire \1\3 is contained within it's hierarchyId \1\3\4, but 4 is not a child of 2 because \1\2 is not contained within the hierarchyId.

To see whether an itemA is a parent of itemB, check whether itemB is a child of itemA.

Finally, you don't actually need to do any comparisons. The TSQL HierarchyId type contains a number of methods, one of which is the IsDescendantOf method that I've highlighted above. So a usage like hierarcyId1.IsDescendantOf(hierarchyId2) performs the kind of check that I've described here. The hierarchyIds are binary and are compared very quickly in the database.

I would use hierarchyId whenever possible when dealing with a database hierarchy.

---

If you have an index on the parent, you could try

select * 
from devices as child 
where exists(select null 
                 from devices as parent 
                 where parent.id = child.parent)

My SQL isn't perfect, but that's the basic approach I would use.

---

My knee-jerk algorithmic solution to this is a "mark-and-sweep" type solution (from garbage collector theory).

http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Na.C3.AFve_mark-and-sweep

Basically you traverse the entire hierarchy of devices and mark the ones that are "traceable", meaning that they can be "reached" through another device (using recursion).

Anything that is un-marked, you "sweep" for GC. In your case, anything that is un-marked is the set you are looking for.

---

That depend on how you store your tree in the database. There is nested sets model which allows to do such queries directly in the database.