Plans for cookbook 2

[JohnCoconut]

BGL has quite a number of alogorithms. It will take sometime to cover all of them.

To keep things going on, I am going to create a to_do_list file to:

1. write down all algorithms we are going to cover
2. track the progress so we don'f feel lost and keep motivated

We need good examples for algorithms, or even better, real world examples. For example,

1. Depth first search to solve maze puzle
2. Use shortest path to find network problem (find the minimum delay between too hosts in the internet)

Fortunately, wikipedia has a Applications section for algorithms. We will steal examples from it, and make them more descriptive.

[JohnCoconut]

Use dot file to import graph

Unlike book 1, we will use dot file to import graphs. To illustrate the algorithm, a svg file will be shown in the tutorial for a relative simple graph.

One problem with complexed graph is how to do testing properly.

1. We cannot check the result just by counting visually
2. We cannot check the result with our own algorithm

I haven't got an idea on how to deal with testing. Do you have any idea, @richelbilderbeek ?

[richelbilderbeek]

Well, book 1 does use .dot files to import graphs, for the same reasons as you listed. The functions are called load_[type]_graph_from_dot. I guess that is what you needed?

[JohnCoconut]

Oh, my question is not about the dot file importing. It's about how to do testing properly.

If we have a very complicated example(a large graph), how do we know our algorithm is correct?

[richelbilderbeek]

I always follow these steps:

• Create an input
• Create an expected result
• Create the actual result from a function
• Compare expected and actual result

In my tests, one can see I do so for graphs of increasing complexity. I do Test-Driven Development to write exactly as much tests as needed.

[JohnCoconut]

Create an expected result

https://upload.wikimedia.org/wikipedia/commons/3/3f/Horizontally_Influenced_Depth-First_Search_Generated_Maze.png

That's the difficult part. I mean, for a maze like this, how do you get expected result?

I joined Robert Sedgewick's Algorithm in coursera in the past. His course has good coverage on tests. The course has a repo on github, and it's licensed under GPL-3.0. See https://github.com/kevin-wayne/algs4.

Maybe we don't want to just copy his tests to our repo, but we can use his tests to verify the correctness of our algorithm first, and create new tests by hand.

But I have to go through his course again. It's written in Java, and I haven't touched Java for quite some time.

[richelbilderbeek]

That's the difficult part. I mean, for a maze like this, how do you get expected result?

There may be even better ways, but I always setup the expected results by hand. Yes, this is tedious, but there is AFAIK no other way to properly test code. Also with mazes, I'd go up in complexity gradually. And of course re-use mazes (and their results).

[richelbilderbeek]

... and I volunteer to wrote those tests as well.

When we both have found our ways within Cookbook 2 (I take great effort to strip everything except the most relevant), I volunteer to prove your function works.

[JohnCoconut]

We will see how it goes.

I like SedgeWick's example. It has graph as small as 10 edges, and as large as 700K edges. His algorithm has been verified by millions of people. I want to use it as a start.

[JohnCoconut]

Of course, I am happy to accept whatever tests you come up with. More tests are definitely better.

[richelbilderbeek]

Sounds like a solid plan. I can but guess what algorithms you plan to create, so assign me to create tests when your algorithms are in place. OK?

[JohnCoconut]

Yeah. Sure.

[Becheler]

Hi!
Any updates on an algorithms-dedicated cookbook? :)