Search Notebook Visualizations

[antmarakis]

The search notebook currently has a lot of visualizations of graphs and such that are very important to get the concepts across. However, the visualization code itself is not important and the student does not need to read it. For such code we have created the Python script notebook.py, which holds the visualization code that goes in the notebooks.

It would be fantastic if we could start looking at ways to move the viz code to notebook.py, so that we could clean up the Search notebook a bit. Then, we could simply call the functions from the notebook without showing how the sausage is made.

If you would like to help on this issue, comment below. Thanks!

---

TODO:

• Move tree_search and graph_search to notebook.py. They are mostly visualization code that students don't need to read. We should also have a separate section explaining what the two techniques are, without the visualization. Just walking the student through the code like normal.

[bakerwho]

I've been noticing this particularly for search.ipynb. I am working on moving this stuff.

Apart from this, it seems that search.py is an extremely long file, with the following contents (in order of their appearance):

• define Problem and Node classes
• define a generic SimpleProblemSolvingAgentProgram
• define tree_search and graph_search and a number of implementations of search algorithms
• implement bidirectional_search
• implement astar_search
• implement EightPuzzle, a Problem
• implement a number of search algorithms like hill_climbing and simulated_annealing
• implement PeakFindingProblem
• implement OnlineDFSAgent, an Agent
• implement OnlineSearchProblem, a Problem!
• implement LRTAStarAgent, an Agent
• implement a number of functions to run genetic algorithms
• implement the Graph class and related derived classes!
• a bunch of constants
• define GraphProblem
• define NQueensProblem
• implement a number of boggle-related methods, then classes Wordlist and BoggleFinder
• a couple more boggle-related methods
• define InstrumentedProblem
• finally methods to compare searches!

This is messy! So messy! I think it might make further development difficult, and possibly lead to duplicate efforts for other problems or examples. Is this something we should be concerned about?

If I could get some insight on the dependencies (which other files import from search), that might help streamline these.

[ad71]

Three functions that should be immediately moved to notebook.py are show_map, final_map_colors and display_visual from the 'Searching Algorithms Visualization' section. Are there any more @MrDupin ?

[bakerwho]

@ad71, actually, it's a bit more complicated, as some of these functions use locally defined variables. I'm already working on this to streamline the viz functions as well as the use of networkx.

[ad71]

Great! Tell me if you need help. Also, is there any way to remove the networkx dependency altogether?

[bakerwho]

@ad71 We absolutely can! nx is actually being used just for the neat inbuilt visualisation it offers. There already exists the Graph class in search.py. We can build the required visualisations on matplotlib (what nx already uses). It can be done, it'll just be a little tedious.

Maybe we should take the nx discussion to another thread? Also, @MrDupin @norvig, I'm waiting for @ad71's fix to EightPuzzle to be merged to avoid merge conflicts with the changes I'd like to make!

[ad71]

You can copy search.py from my fork of the repository to your working directory and make your changes there. That way there won't be merge conflicts.

[bakerwho]

Erm, not sure that's such a good practice in general, but I guess it works for now.

[ad71]

It's definitely not good practice, just a workaround.

[antmarakis]

Great work, I think this makes the notebook a bit cleaner. I haven't tested it, but I assume the notebook cells work.

After these are merged, I will take a look and see if we can simplify the notebook a bit more. Also, we should start looking at ways to remove networkx, although this may be a bit difficult. If it takes too long, it would be a nice addition to GSoC proposals ;).

[goswami-rahul]

@MrDupin I too want to help in the issue. I just need an overview of which part of code is to be moved to another script.

[ad71]

@goswami-rahul this has already been taken care of by @bakerwho in #812 . The next checkpoint would be to try and remove the networkx dependency, which might be difficult. Meanwhile, you can suggest ideas to simplify the notebook a bit more.

[antmarakis]

I would also like to see tree_search and graph_search moved, since they are mostly visualization code. We should also have a separate section explaining what the two techniques are, without the visualization. Just walking the student through the code like normal.

Moving the two visualization functions to notebook is the next step, and then adding the new sections explaining in short what the two techniques do is the step after that.

[bakerwho]

@MrDupin I think these are good ideas. I also propose renaming these two functions tree_search_for_vis and graph_search_for_vis - or something along those lines - to indicate that they are not generic implementations.

Besides, there is also best_first_graph_search which is a general search method written here with a lot of clunky visualisation code. Maybe there's a better option?

[antmarakis]

@bakerwho: I like the renaming idea.

For best_first_graph_search, I am not sure what else can we do. One idea that I had is to use "building blocks" which contain basic functionality wrapped in visualization code and then the algorithms would simply call them to remove clutter. For example, a lot of search algorithm need a function to visit a new node. We could create a general function for node-visiting that returns information like "neighbors", "value" etc., while doing some visualization on the side.

I have not given it much thought, but I think this will be tricky to implement (if it is implementable at all). For now, I would prefer to have the aforementioned functions renamed and then just see the current PRs merged, and go from there.