Algorithm to find a "recursive" item in a Javascript data structure

Question

Say I have a Javascript data structure such as:

var data = {
 id: '5551212',
  children: [
   {id: '5551213'},
    {id: '5551214'},
    {
    id: '5551215',
    children: [
     {id: '5551213'},
      {id: '5551212'}  // <--- I want to detect THIS one!  It's a recursive entry.
                        // or a similar occurrence anywhere in the tree.
    ]}
  ]
};

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

I'm looking for a general algorithm to detect a "recursive" item such as the one shown. I find that it's easy enough if the recursive item is just below the "parent" but what if the duplication can occur anywhere?

In this case these are mechanical assembly part numbers. So while it's no problem creating a data structure like this, actually building a recursive assembly is impossible. So I need to find a potential mistake on the user's part before they try to build something impossible.

When searching for algorithms, all I'm getting are recursive programming examples and discussions or here on StackOverflow most questions seem to be about how to create such a recursive structure.

I'm working in Javascript w/ JQuery but I'm looking for an applicable algorithm here, not necessarily an implementation.

Have you tried using `JSON.stringify()`? What should occur if the value is found? — guest271314, Jan 24 '18 at 19:28
@guest271314 I don't think the question is about objects with cycles. I think it's about finding property values that have been re-used in a way that violates some contract. — Pointy, Jan 24 '18 at 19:30
I think you mean "recurring" or "duplicate" not recursive. Recursive would be if you had a value for one of the members of the object set to the parent object. — Anthony, Jan 24 '18 at 19:32
@Pointy Yes, `JSON.stringify()` `replacer` function is recursive and can be used to match or remove properties from the resulting JavaScript object [remove object from nested array](https://stackoverflow.com/questions/36228492/remove-object-from-nested-array). `RegExp` could also be used to match duplicate values. It is not clear what should occur if duplicate property, value pairs occur. — guest271314, Jan 24 '18 at 19:32
Is a violating id any id referencing an ancestor? i.e. the grand-grand child of root is the father of the child of root along the same branch? — kabanus, Jan 24 '18 at 19:34
I may be wrong but from the wording of the question I think you're looking for a way to `flatten` your data based on certain constraints that are unknown to us - the solution is going to be dependent on those constraints and not the data structure itself — ppajer, Jan 24 '18 at 19:35
"You keep using that word. I do not think it means what you think it means." — Anthony, Jan 24 '18 at 19:36
If I'm using the word "recursion" improperly here, please pardon my poor usage. The problem is to find a child item that has the same "id" as any of its parent items. As I noted in the question, this is a structure of assembly part numbers and, in fact, if this scenario were to occur, it would be a "recursive" assembly. Think of it like this: Car->Body->Door->Body While I can create an assembly like the above, I cannot build a Car that contains a Body that contains a Door that contains the Body again. I need to detect this situation and flag it as an error. — jwh20, Jan 24 '18 at 19:43

score 2 · Answer 1 · answered Jan 24 '18 at 19:50

2

How to do it:

Check if parents of the current subtree contain its root id
If no, and subtree has children - check their subtrees recursively
If there are no children - return false

And here is the code:

function isRecursive(tree, parents){
    if (parents.indexOf(tree.id) !== -1){
        return true;
    } else if (tree.children) {
        return tree.children.some(child => isRecursive(child, [tree.id].concat(parents)));
    }

    return false;
}

isRecursive(data, []);

It can be improved by replacing array with set but I wanted to make it as compatible as possible.

answered Jan 24 '18 at 19:50

pwolaq

6,343
19
45

This won't work if there are duplicates in parallel branches, e.g. `children: [{id:X},{id:X}]` – georg Jan 24 '18 at 20:09
@georg, for my purposes at least, duplicates in parallel branches is OK. That's an acceptable construct. I'm only interested in duplicates where a child of the same id as any of its ancestors. – jwh20 Jan 24 '18 at 20:18

score 0 · Answer 2 · 2018-01-24T19:38:18.830

0

Use this:

var arr = []
function detectRecursive(object){
 var x
 for(x in object){
  if(arr.indexOf([x,object[x]])==-1){
   arr.push([x,object[x]])
   var tmp = {} 
  if(typeof object[x] == typeof tmp){
   detectRecursive(object[x])
  }
  }
 }
}

This loops over the keys and values of the array

edited Jan 24 '18 at 19:38

answered Jan 24 '18 at 19:29

1

?? The object in the OP can be successfully stringified as JSON. – Pointy Jan 24 '18 at 19:30
1

Try it! The question is not about actual cycles in the data structure, but about property values that violate some constraint. – Pointy Jan 24 '18 at 19:32
I tried the JSON.stringify suggestion but there is nothing "illegal" about this data structure. It stringified just fine – jwh20 Jan 24 '18 at 19:37

score 0 · Answer 3 · answered Jan 24 '18 at 19:51

You could use a Map to keep track of the "path" keyed by each id value. Then when you find an id is already in that Map, you could push this pair of paths to a results array.

Here is how that would work:

function collectDuplicates(data) {
    const map = new Map,
        dups = [];
    function recurse(data, path) {
        if (map.has(data.id)) {
            dups.push([data.id, map.get(data.id), path]);
        } else {
            map.set(data.id, path);
        }
        (data.children || []).forEach( (child, i) => {
            recurse(data.children[i], path + '.children[' + i + ']');
        })
    }
    recurse(data, 'data');
    return dups;
}

// Sample
var data = {
 id: '5551212',
    children: [
        {id: '5551213'},
        {id: '5551214'},
        {
            id: '5551215',
            children: [
                {id: '5551213'},
                {id: '5551212'}
            ]
        }
    ]
};

console.log(collectDuplicates(data));

.as-console-wrapper { max-height: 100% !important; top: 0; }

In this snippet I built the path in a notation that corresponds to the object notation to get to the two objects that have the same id property, but you could of course use a completely different notation or reference system.

Algorithm to find a "recursive" item in a Javascript data structure

3 Answers3