BFS search example

findPath.ts

const findPath = (targetNode, startNode = startWord, graph = wordlist ) => {
          // source: https://books.google.com/books?id=GSBKDwAAQBAJ&pg=PA187&lpg=PA187&dq=bfs+lodash&source=bl&ots=FmkF1thzTu&sig=XjRtFH5vZH-mSRfIYowlwDdtIzM&hl=en&sa=X&ved=2ahUKEwjol-HZwbXdAhUDNd8KHW81Ao8Q6AEwCHoECAIQAQ#v=onepage&q=bfs%20lodash&f=false

          // initialize the path to traverse
          let travelledPath = [];

          // mark the nodes that need to be visited breadthwise
          let nodesToVisit = [];

          // mark all visited nodes
          let visitedNodes = {};

          // current node being visited
          let currentNode;

          // add start node to the to-be-visited path
          nodesToVisit.push(startNode);

          // mark starting node as visited node
          visitedNodes[startNode] = true;

          //while there are more nodes to goto
          while (nodesToVisit.length) {

            // get the first one in the list to visit
            currentNode = nodesToVisit.shift();

            // if it is the target
            if (_.isEqual(currentNode, targetNode)) {
              // add to result, backtrack steps taken based on path taken
              let result = [targetNode];

              // while target is not source
              while (!_.isEqual(targetNode, startNode)) {
                //extract how we got to this node
                targetNode = travelledPath[targetNode];

                // add it to result
                result.push(targetNode);
              }

              // extract the relationship between the edges and return the value
              //  this is where we'd apply an interpretation function
              return result.reverse();
            }

            // if result not found, set the next node to visit by traversing
            //  breadth-first
            _.forOwn(graph, (connections, name) => {
              // if not current node, is connected to current node
              //  and not already visited
              if (!_.isEqual(name, currentNode)
                  && _.includes(graph[name], currentNode)
                  && !visitedNodes[name]) {
                    // we will be visiting new node from current node
                    travelledPath[name] = currentNode;

                    // set the visited flag
                    visitedNodes[name] = true;

                    // push nodes to visit
                    nodesToVisit.push(name);
                  }
            });
          }

          // nothing found
          return [];
          // return null;
        }