Jamgreen - 9 months ago 52

Javascript Question

I am using

`cytoscape.js`

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`

`node = rootNode;`

while (true) {

// find leaving edges

...

edgesTo.forEach(edge => {

// set new node to traverse

node = edge.target;

}

}

since I guess the

`edgesTo.forEach()`

`while`

I can see from http://js.cytoscape.org/#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?

Answer

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)
```

Source (Stackoverflow)