3

I have a set of nodes arranged like the below image. Left columns are parents, right columns are children. A line denotes ancestor/descendant.

flow

When I select a node, I want to find the immediate family, and then any children-of-children and parents-of-parents. But not parents-of-children or children-of-parents.

highlighted

So in this example, I picked #7. You can see that #2 and #4 are parents so we want to select those. #8 is a child of a parent, so it is not selected. If we look in the other direction, you can see the highlighting following the children down, but it ignored the relationship between #13 and #9 because that is a parent-of-child relationship.

I only need to know who the related nodes are. It does not matter how they are related or where in the graph they are. What is the best way to do this? I don't know anything about these sorts of algorithms, so this may be a duplicate, I just don't realize it. I'll eventually be implementing this in JS if that matters at all.

  • Okay. I'm not sure what that means. Should I edit my question to better reflect the situation? – amflare Apr 13 '17 at 15:37
  • 1
    I did the edits. – FrustratedWithFormsDesigner Apr 13 '17 at 15:37
  • Do you know how your nodes/edges are implemented? This will significantly affect the complexity if nodes only know about their children for instance (e.g. if the data is stored as a set of directed edges, c.f. mapping a CSV dataset to a singly linked list/graph rather than a doubly linked list). Chances are your graph database may allow inference of bi-directional relationships in this case thus making this comment irrelevant, but not necessarily. – kwah Apr 15 '17 at 5:43
  • @kwah - Its all in a JSON object. So each sub-object knows insomuch as there is a property telling it the id of other sub-objects it is connected to. – amflare Apr 15 '17 at 5:55
  • 1
    PS: With respect to assisting further research, the type of algorithm you are looking for will be very similar to a commonly-available tree-walking algorithm, but will cover both parent and child nodes. Variations of these may be depth-first (following the chain until reaching the deepest/highest node, then moving along) or or breadth-first (searching all children/parents, then grandchildren/grandparents, then all great-grand-etc..). The other common pattern is the visitor pattern, but this will be less applicable in your case as it would involve an ancestry check when "visiting" each node. – kwah Apr 15 '17 at 5:57
5

You could implement this with two very simple recursive functions: one that finds all of the ancestors (can only travel left) and another that finds all the descendants (can only travel right).

Example pseudo-code:

get_family(node a)
{
    list family = get_ancestors(a) + get_children(a)

    return family
}

get_ancestors(node a)
{
   list ancestors

   foreach anc in a.ancestors
   {
      ancestors = ancestors + anc + get_ancestors(anc)
   }

   return ancestors
}

get_children(node a)
{
   list children

   foreach child in a.children
   {
      children = children + child + get_children(child)
   }

   return children
}

Update: as pointed out by Derek Elkins, if it is possible for two paths that diverge to join again, then you need a way to prevent nodes from being visited multiple times. Such as by marking each node as visited.

| improve this answer | |
  • Is there a way for it to travel back up the graph if it reached the end of a branch? So like if #12 had a second child, and we made it down to #20, how would it know to back up until it has another unsearched branch open to it or has already searched everything? – amflare Apr 13 '17 at 15:46
  • @amflare I think what I'm proposing would do that. See pseudo-code – user82096 Apr 13 '17 at 15:49
  • This will be more difficult if nodes are only aware of their descendants, and do not know their own ancestors. – FrustratedWithFormsDesigner Apr 13 '17 at 15:51
  • 1
    @FrustratedWithFormsDesigner - They know of both, so I think this will work. – amflare Apr 13 '17 at 15:52
  • 1
    @amflare it's simply a basic use of recursion. I'm not coming at this problem from the world of CS/math graph theory; they may have other terms for discussing the problem. – user82096 Apr 13 '17 at 15:57
2

Here's a procedural solution. I've written it in C#, but hopefully the comments make it clear what's going on even if you're not familiar with C#.

The idea behind this algorithm is that we can find all of the descendants by looking at the root node, and also looking at the children of each node that we look at. We keep a "to-do" list of nodes we still need to look at, so we don't lose our way.

(There's probably a name for this algorithm, but I don't know what it is.)

// This method defines how to find the descendants of a node "rootNode".
// It returns a set of nodes.
static HashSet<Node> FindDescendants(Node rootNode)
{
    // Let "descendants" and "descendantsToCheck" initially be
    // the set containing only rootNode.
    HashSet<Node> descendants = new HashSet<Node> { rootNode };
    HashSet<Node> descendantsToCheck = new HashSet<Node> { rootNode };

    // While there are still descendants left to check...
    while (descendantsToCheck.Count > 0)
    {
        // Let thisDescendant be an arbitrary descendant
        // which still needs to be checked. We will check this descendant.
        Node thisDescendant = descendantsToCheck.First();

        // For each child of thisDescendant...
        foreach (Node child in thisDescendant.Children)
        {
            // We have found a descendant. If it is already in our "descendants"
            // set, then we don't need to do anything, because this descendant
            // either has been checked or will be checked.

            // However, if this descendant is not in "descendants"...
            if (!descendants.Contains(child))
            {
                // We need to add this child to our set of descendants,
                // as well as our set of descendants that need to be checked.

                descendants.Add(child);
                descendantsToCheck.Add(child);
            }
        }

        // We are done checking thisDescendant,
        // so remove it from the set of descendants to check.
        descendantsToCheck.Remove(thisDescendant);
    }

    // At this point, there are no descendants left to check.
    // This means that we have found all of the descendants. Return them.
    return descendants;
}

This algorithm gives you only the descendants, not the ancestors. To find both descendants and ancestors, just use the algorithm twice: once for descendants, once for ancestors.

For finding ancestors, you have a couple of options. One option is to write a FindAncestors function that's identical to the FindDescendants function, except that it looks at parents instead of children. Another option is to modify the FindDescendants option to take a parameter indicating whether it should look at children or parents.

| improve this answer | |
  • 1
    A more abstract way of doing choosing descendants or ancestors is to take a function that given a "node" gives you the children. At this point you can make the function completely generic in the Node type. That is, HashSet<N> FindDescendants<N>(N root, Func<N,IEnumerable<N>> children) – Derek Elkins left SE Apr 13 '17 at 21:04
  • 1
    As a side note, this doesn't quite have optimal time complexity because HashSet.Contains isn't quite constant-time. This can be fixed by adding a bit to the nodes to mark visited ones, but it's probably not worth doing this as it leads to issues like needing to reset the bits and race conditions in concurrent traversals and other silliness. – Derek Elkins left SE Apr 13 '17 at 21:11
  • @derekelkins - good point. Another solution is to ensure every node has a small integer id, at which point you can use an O(1) set implementation (eg an array of booleans). – Jules Apr 14 '17 at 8:48
0

You have to do two simple graph traversals from your starting points, one which only follows the graph edges from left to right (parent-to-child direction), and a second in the opposite direction.

If you prefer to do the traversal in a depth-first or breadth-first manner is up to you, both will work, and none is "generally better" than the other as long as you do not have any additional constraints or requirements than just selecting all nodes.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.