Jamgreen - 1 year ago 80
Javascript Question

# Traversing graph using while loop iteration

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.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?

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)
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download