JSON object how to match key to value pairs in Javascript

Question

I have the following object:

{ apple: 'banana',
  banana: [ 'pear', 'apple' ],
  melon: 'apple',
  grapes: 'peach',
  carrot: 'apple',
  peach: 'grapes' }

I am basically tying to find any 'circular references', for example:

apple: 'banana',
banana: ['apple']

and

grapes: 'peach',
peach: 'grapes'

I've spent ages and have tried a number of different approaches, including copying the key and values into a new array, sorting and trying to match - now I'm not even sure what the best way to tackle this is.

Edit: Thanks to everyone for their help. I think it wasn't quite clear with my original question. I was only wanting to identify the case where there exists a reference in both directions. So apple->banana, banana<-apple and grapes->peach, peach<-grapes should match. But melon->apple, banana->apple and carrot->apple should not match at all.

I've got it working with the following (fairly disgraceful) code:

var data = { apple: 'banana',
  banana: ['test', 'apple'],
  melon: 'apple',
  grapes: 'peach',
  carrot: 'apple',
  peach: 'grapes' };

var arr = [], arr2 = [], u = {} 

//Iterate over object 'data' and create an array of arrays - sorted alphabetically
for (var item in data) {
    var val = data[item];
      if (Array.isArray(val)) {
        for (var i = 0; i < val.length; ++i) {
          arr.push(new Array(item, val[i]).sort())
        }
    } else {
      arr.push(new Array(item, val).sort())
    }
}

//Iterate of arr and look for any matches..
for(var i = 0, l = arr.length; i < l; ++i){
  if(u.hasOwnProperty(arr[i])) {
         arr2.push(arr[i]);
      }
      u[arr[i]] = 1;
}

console.log('Matches found: ' + arr2)
//prints: 'Matches found: [ [ 'apple', 'banana' ], [ 'grapes', 'peach' ] ]

What do you want to do with the circular references after you found them? Maybe you only need to check if there are circular references, this would make things easier. Btw your "JSON" is not valid, it is a JavaScript object. — Pyfisch, Jul 04 '15 at 07:53
possible duplicate of [Finding all cycles in undirected graphs](http://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs) — stdob--, Jul 04 '15 at 07:57
I basically need to iterate over the object (yes, sorry you're correct it is actually just a JavaScript object - originally extracted from JSON) and just return true if there are any circular dependencies. The object will never have further levels of nesting than the example above - so a recursive function shouldn't be necessary . — Ajeas X, Jul 04 '15 at 08:04

jfriend00 · Answer 1 · 2015-07-04T08:18:59.417

Here's one approach in a working snippet:

var data = { apple: 'banana',
  banana: [ 'pear', 'apple' ],
  melon: 'apple',
  grapes: 'peach',
  carrot: 'apple',
  peach: 'grapes' };

for (var item in data) {
    var val = data[item];
    if (Array.isArray(val)) {
        for (var i = 0; i < val.length; i++) {
            if (val[i] in data) {
                document.write("circular reference for '" + val[i] + "' in " + item + ":[" + val[i] + "]<br>" );
            }
        }
    } else {
        if (val in data) {
            document.write("circular reference for '" + val + "' in " + item + ":" + val + "<br>");
        }
    }
}

It generates this output:

circular reference for 'banana' in apple:banana
circular reference for 'apple' in banana:[apple]
circular reference for 'apple' in melon:apple
circular reference for 'peach' in grapes:peach
circular reference for 'apple' in carrot:apple
circular reference for 'grapes' in peach:grapes

score 0 · Answer 2 · answered Jul 04 '15 at 08:02

Do you just want direct links? Just check to see if any of the values are keys and if so, if they point to the original key.

 _.mapObject(fruit, function(key, val) {
    if(fruit[val] && (fruit[val] === key || fruit[val].includes(key))){
        console.log(key + ':' + val + ' match!');
    }
 });

Do you want any circular references? You need a 'visited' array. You're essentially trying to do graph traversal so you can take a look at canonical examples like Dijkstra's.

score 0 · Answer 3 · answered Jul 04 '15 at 08:10

None language specific approach

Keep a multi-dimensional array/map of keys/values. (Outer array elements = each key name, Inner array elements = values for key)

// Psuedo-Code // Test: If any element in the outer array exists with the the inner array, check // for self within each inner key's inner array

isCircular(JSON Object) {
// Assume No Circular Reference
var isCircular = false;

// Check all the Keys for Circular references
nextKey = firstKey;
while (nextKey != null)
// Setup loop
var parent = nextKey;
var child = null;
   foreach child in parent.values {
       // Check the child.value for parent
       foreach value in child.value {
          // If parent exists, there is a circular reference
          if (value == parent) isCircular = true; // CIRCULAR REFERENCE
       }
   }
nextKey++; // Next Element
}

return isCircular;
}

JSON object how to match key to value pairs in Javascript

3 Answers3