例えばJavaScriptの

Question

で循環参照を検出する方法：

$ node 
> var x = {} 
undefined 
> x.x = x 
{ x: [Circular] } 

構造の一種は、彼らがこれを達成するために使用している疑問に思う、それは私がちょうど何をしたかに直接エンコードされていないので。

var graph = new Graph(object) 
graph.detectCircularReferences() 

そして、それはどういうことが起こるかわかりません。それを実装する方法を学ぶことを願っています。

Answer 1

私はこの機能にコメントのアイデアを取った。これは渡されたオブジェクト（配列とオブジェクト上）を横断し、循環参照を指すパスの配列を返します。

// This function is going to return an array of paths 
 
// that point to the cycles in the object 
 
const getCycles = object => { 
 
    if (!object) { 
 
     return; 
 
    } 
 

 
    // Save traversed references here 
 
    const traversedProps = new Set(); 
 
    const cycles = []; 
 

 
    // Recursive function to go over objects/arrays 
 
    const traverse = function (currentObj, path) { 
 
     // If we saw a node it's a cycle, no need to travers it's entries 
 
     if (traversedProps.has(currentObj)) { 
 
      cycles.push(path); 
 
      return; 
 
     } 
 

 
     traversedProps.add(currentObj); 
 

 
     // Traversing the entries 
 
     for (let key in currentObj) { 
 
      const value = currentObj[key]; 
 
      // We don't want to care about the falsy values 
 
      // Only objects and arrays can produce the cycles and they are truthy 
 
      if (currentObj.hasOwnProperty(key) && value) { 
 
       if (value.constructor === Object) { 
 
        // We'd like to save path as parent[0] in case when parent obj is an array 
 
        // and parent.prop in case it's an object 
 
        let parentIsArray = currentObj.constructor === Array; 
 
        traverse(value, parentIsArray ? `${path}[${key}]` : `${path}.${key}`); 
 

 
       } else if (value.constructor === Array) { 
 
        for (let i = 0; i < value.length; i += 1) { 
 
         traverse(value[i], `${path}.${key}[${i}]`); 
 
        } 
 
       } 
 

 
       // We don't care of any other values except Arrays and objects. 
 
      } 
 
     } 
 
    } 
 

 
    traverse(object, 'root'); 
 
    return cycles; 
 
};

その後、あなたはこのようにそれをテストすることができます。

：

// Making some cycles. 
 
const x = {}; 
 
x.cycle = x; 
 
const objWithCycles = { 
 
    prop: {}, 
 
    prop2: [1, 2, [{subArray: x}]] 
 
}; 
 
objWithCycles.prop.self = objWithCycles; 
 

 
console.log(getCycles(objWithCycles));

これは、オブジェクト内のサイクルのリストで、次の出力を生成

[ 'root.prop.self', 'root.prop2[2][0].subArray.cycle' ]