javascript - Traversing graph using while loop iteration - Stack Overflow

admin管理员组

文章数量:1414928

I am using cytoscape.js to create a graph.

I want to travel through the nodes (with direction), but only to those nodes who are connected with a edge that contains a specific value.

I have done it with recursion like this

function traverse(node, requiredValue, visitedNodes) {
  // break if we visit a node twice
  if (visitedNodes.map(visitedNode => visitedNode.id()).includes(node.id())) {
    return visitedNodes;
  }

  // add visited node to collection
  visitedNodes.push(node);

  // select node
  node.select();

  // only travel through valid edges
  const edgesTo = node.outgoers(function () {
    return this.isEdge() && this.data('requiredValues').includes(requiredValue);
  });

  // break if no valid connected edges
  if (edgesTo.empty()) {
    return visitedNodes;
  }

  // travel through edges
  edgesTo.forEach(edge => {
    edge.select()
    return traverse(edge.target(), agent, visitedNodes);
  });
}

It seems to work, but I am not very good at algorithms, so I am not sure if this is a clever way to build it. I have read a bit about breadth first and depth first search algorithms, but I am not sure if it's those algorithms that I need.

Would it be possible to traverse a tree without using recursion? I have also tried with a while loop, but since it is a tree, I don't think I can just use

node = rootNode;

while (true) {
  // find leaving edges
  ...

  edgesTo.forEach(edge => {
    // set new node to traverse
    node = edge.target;
  }
}

since I guess the edgesTo.forEach() will finish before moving on to the next iteration in the while loop. I need it to traverse 'simultaneously' through the different branches.

I can see from that the library has multiple algorithms (including bfs and dfs), but do I need those algorithms when I want to traverse the tree without the purpose of searching for one specific node?

I am using cytoscape.js to create a graph.

I want to travel through the nodes (with direction), but only to those nodes who are connected with a edge that contains a specific value.

I have done it with recursion like this

function traverse(node, requiredValue, visitedNodes) {
  // break if we visit a node twice
  if (visitedNodes.map(visitedNode => visitedNode.id()).includes(node.id())) {
    return visitedNodes;
  }

  // add visited node to collection
  visitedNodes.push(node);

  // select node
  node.select();

  // only travel through valid edges
  const edgesTo = node.outgoers(function () {
    return this.isEdge() && this.data('requiredValues').includes(requiredValue);
  });

  // break if no valid connected edges
  if (edgesTo.empty()) {
    return visitedNodes;
  }

  // travel through edges
  edgesTo.forEach(edge => {
    edge.select()
    return traverse(edge.target(), agent, visitedNodes);
  });
}

It seems to work, but I am not very good at algorithms, so I am not sure if this is a clever way to build it. I have read a bit about breadth first and depth first search algorithms, but I am not sure if it's those algorithms that I need.

Would it be possible to traverse a tree without using recursion? I have also tried with a while loop, but since it is a tree, I don't think I can just use

node = rootNode;

while (true) {
  // find leaving edges
  ...

  edgesTo.forEach(edge => {
    // set new node to traverse
    node = edge.target;
  }
}

since I guess the edgesTo.forEach() will finish before moving on to the next iteration in the while loop. I need it to traverse 'simultaneously' through the different branches.

I can see from http://js.cytoscape/#collection/algorithms that the library has multiple algorithms (including bfs and dfs), but do I need those algorithms when I want to traverse the tree without the purpose of searching for one specific node?

• javascript
• algorithm
• tree
• graph-algorithm
• cytoscape.js

Share Improve this question Follow edited Oct 1, 2016 at 12:50 Saeid 4,26577 gold badges2929 silver badges4646 bronze badges asked Oct 1, 2016 at 11:16 JamgreenJamgreen 11.1k3232 gold badges122122 silver badges232232 bronze badges

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 4

BFS and DFS are general graph traversal algorithms. They are not only for searching for some specific node. Many algorithms have BFS and DFS as a subroutine.

Your code basically performs a DFS on the graph. You are ignoring all unwanted edges and traversing the rest of the graph in a depth-first manner.

Yes it is possible to traverse the graph without recursion using both DFS and BFS and only use some specific edges. You just have to ignore the unwanted edges.

BFS:

Breadth-First-Search(Graph, root):
     create empty queue Q       
     visited.put(root)
     Q.enqueue(root)                      
     while Q is not empty:             
        current = Q.dequeue()     
        for each edge that edge.startpoint == current:
             if current has required value AND edge.endpoint is not in visited:
                 Q.enqueue(edge.endpoint)
                 visited.put(edge.endpoint)

DFS:

procedure DFS-iterative(G,v):
      let S be a stack
      S.push(v)
      while S is not empty:
          v = S.pop()
          if v is not labeled as discovered:
              label v as discovered
              for all edges from v to w in G.adjacentEdges(v) :
                  if edge has required value:
                       S.push(w)

I'll chop my answer down to several questions you asked either explicitly or implicitly:

BFS and DFS algorithms in general

BFS and DFS are algorithms to traverse a connected graph (or a connection ponent of a graph). They allow you to visit all the connected nodes from a specific starting node (they do not search for a specific node as you hinted, although they can be used in such a manner), and differ in the order in which they traverse the graph (Breadth-Frist, meaning all the immediate neighbours of a node are visited before going into the next layer of neighbours, pared to Depth-First, meaning pursuing a branch that starts with one immediate neighbour first and going deeper, visiting all the nodes that are connected to the starting node through that particular neighbour node before continuing to the next branch, which are all the nodes connected through the next immediate neighbour).

BFS and DFS relating to your requirements

As before, both algorithms visit ALL the nodes in a connected ponent of a graph (all the nodes that can be reached from the starting node by traversing edges). As you have a different requirement (traverse using only edges of specific values) I'd suggest you implement your own alteration of either of the algorithms, adding this demand. You have actually already done that: your algorithm is a descendant/version of DFS in a sense.

BFS and DFS and recursion

BFS does not normally include recursion and uses a data structure (a queue) to achieve its traversal order.

DFS is easily implemented with recursion (and your intuitive way of implementing your algorithm is very similar to that). But you can implement DFS without recursion - using a data structure (a stack) to achieve its traversal order (essentially the recursion uses the call stack as the data structure implicitly so it isn't that different, although the recursion have more overhead to deal with the function calls and their environments). You can see a pseudocode in the wiki of DFS. Here it is for convenience:

procedure DFS-iterative(G,v):
  let S be a stack
  S.push(v)
  while S is not empty
      v = S.pop()
      if v is not labeled as discovered:
          label v as discovered
          for all edges from v to w in G.adjacentEdges(v) do
              S.push(w)

Cytoscape includes many mon graph theory algorithms out of the box. The algorithms even let you to specify which elements to include / call on.

You could re-implement the BFS traversal algorithm yourself using low-level traversal APIs like .outgoers(), but why re-invent the wheel?

BFS and DFS are built into Cytoscape:

cy.elements().stdFilter(function( ele ){
  return ele.isNode() ? includeThisNode( ele ) : includeThisEdge( ele ); // eles to include
}).bfs({
  visit: function(){ ... } // called when new ele visited
});

Specify includeThisNode() and includeThisEdge() to meet your criteria for which elements should be allowed to be traversed.

If you have a goal node with certain criteria, return true in visit() when those conditions are met.

本文标签： javascriptTraversing graph using while loop iterationStack Overflow