Cyclical Direct Inversion Algorithms (JavaScript)

Question

I have a connected, directed, circular graph. The task is to detect each node in the graph without falling into an infinite loop, as a normal tree traversal algorithm does.

It can be assumed that I already know why to start a node in order to reach all the points in a directed graph, and that for each node I have a function that will return the nodes to which it directs. Is there a known algorithm for finding all nodes?

The main problem is to avoid loops, and I would love it if there was a way to do this without tracking every node and comparing it with a list of nodes already passed.

If you need more information, the urgent task is to get a list of each named function in JavaScript, including functions that are properties of other objects. So I tried something like the following, since I thought that the JS object references to each other made a tree (but of course it is not):

function __findFunctions(obj){
  for (var f in obj){
    // for special case of edge with self
    if (obj === obj[f]){
      continue
    }
    if (typeof obj[f] === 'function' &&
        obj.hasOwnProperty(f) &&
          // exclude native functions, we only want user-defined ones
        !(/\[(native\scode|object\sfunction)\]/i).test(obj[f].toString()) &&
          // exclude functions with __ prefix
        !(/^\s*function\s*__/).test(obj[f].toString())
       ){
      document.write(f + "<br/>" + obj[f].toString() + "<hr/>");
    }
    //alert(typeof obj[f] + "\n" + obj + "\n" + obj[f] + "\n" + f)
    __findFunctions(obj[f]);
  }
}
__findFunctions(window);

The problem with this code is that it gets stuck in loops.

Answer 1

I would really like it if there was a way to do this without tracking each node and comparing it with a list of nodes that have already passed.

, . node :

// psuedo
id=0;
for each node
    node.id = id++;

.

node ID :

var alreadyTraversed = {};

// Traversing a node:
alreadyTraversed[node.id] = true;

, , :

if (node.id in alreadyTraversed) // It already been traversed...

---

, , , :

node._traversed = true;

// Later:
if (someNode._traversed) // already traversed.

Answer 2

, .

.

__findFunctions(obj, visited) as your signature
at start do an "in array" test for current obj and return if so.
at start add obj to the visited for subsequent traversals.