Breadth-first search exercise

Click to run World: Breadth-first search (Kevin Bacon) at Ancient Brain.

Exercise - Add to queue twice

• There is a bug: The search adds new nodes to the queue if they are not searched. But they might be on the queue already, just not searched. A node can be added multiple times to the queue. Search for "Michael Cyril Creighton" to see this.
• Exercise: Edit the code to fix this. Tips:
  1. The node is added to the queue, which is an array. Search for how to check in JavaScript if an object is already in an array. Then insert an if statement.
  2. neighbor is the object.
  3. neighbor.label is the name.
  4. graph.end is the goal object.
  5. graph.end.label is the goal name.

Exercise - Stop at goal

• We see that we discover the goal:

   adding unsearched neighbour Kevin Bacon to queue 

  but do not stop.
• We only stop some time later.
• It is in fact the same problem as in Breadth-first search (graphical). We talk about it there.
• We are inside a "for" loop which is inside an "if" statement inside a "while" loop. It needs the same solution of refactoring the code.

Exercise - Edit JSON

• What if no path found? Make it display "no path found" nicely.
• Will need an actor for which no path is found. So do this:
  1. Download JSON.
  2. Edit it to add fictional movie with two fictional actors.
  3. Upload JSON.
  4. Change code to point to that JSON.
  5. See what happens when you select the fictional actor (no path to Kevin Bacon).

Exercise - Simple visualisation

• Cosmetic code fix: Highlight the movie titles different to the actor names.

Exercise - Better visualisation

• In contrast to the binary tree, this is not an ordered tree or ordered graph. So search will take much longer. (We cannot quickly eliminate entire branches as we could with the binary tree search.)
• Also in contrast to the binary tree, we do not draw the graph here.
• In fact, the graph is complex and hard to visualise. This illustrates the point that we do not have to draw the graph to search it.

• Exercise: Can you edit the code to help visualise the graph?
  Not easy. Consider thousands of movies and actors.
  

• Juraj Kuruc has done an amazing visualisation.

Further idea: Better DB

• We could install a better movie DB.
• There is apparently a huge JSON DB at oracleofbacon.org