Add runtime chart for examples in data dir

[ivoysey]

I'd love to know the expected wall-clock runtime (so not asymptotic analysis) for the included examples. I've been horsing around with this and it works on the small examples but just heats up my lap really well on the longer ones. I can run pacific_spirit and see nothing more than

Loading graph: pacific_spirit
153 edges
Converting to Eularian path...
	Doubling dead_ends
	Building possible odd node pairs
		(1128 pairs)
	Finding pair solutions
		(2256 solutions)
	Building path sets
	Finding cheapest route

for about 10 minutes. A table mapping the examples to number of seconds of runtime on a particular reference system might be helpful.

I'm wondering if this is what you've seen as well or if maybe my system isn't configured correctly and it's hanging for some reason.

[supermitch]

Hi ivoysey,

I have found that pacific spirit is unsolvable for me too... and I've left it running overnight. I think that there needs to be some pruning of "silly but possible" solutions, I just haven't really explored ways to do that. As an example, are there solutions with new odd paths that cross others? Is that reasonable?

I can add some additional logging (feel free to pull request) so we can check to see how progress is going. My gut feel is that it's just way too big of a network for a rudimentary solver.

I can try to generate a table of time vs. nodes for you too. I'll need an app to build networks...

[ivoysey]

That's reassuring in its own way! I was implementing a toy solver much like yours and tried to run it on a reasonably medium example and it just hung (or ran out of memory).

I was using your tool to see if I was totally nuts or more or less on track --- I guess it seems like I might not be nuts because my example hangs in your tool as well. If pacific_spirit worked for you, I'd be puzzled.

It would definitely be interesting to see a table anyway, although obviously not urgently. My understanding is that the interesting asymptotic behaivour is going to be a function of the number of vertices of odd degree in the input graph -- because they are the things stopping it from being Eulerian. It would be interesting to see how large that number can get in practice before the naïve approach breaks down!

[ivoysey]

So Kolmogorov---yes, that one---seems to have more or less done this for us. The hard part of this is efficiently finding the matching; the rest is all pretty obviously poly time.

Specifically in http://pub.ist.ac.at/~vnk/papers/BLOSSOM5.html he offers the appropriate proofs and an implementation in C++ http://pub.ist.ac.at/~vnk/software.html#BLOSSOM5 of his algorithm for an efficient minimum cost perfect matching algorithm. I'm currently messing around with just making a system call to his binary instead of trying to redo it myself.

[supermitch]

Very cool. I will have to take a look. Thanks for the messages!