I'll have to think about this. I would like to find a small example of the problem to put into a unit test!

I know that I worked pretty hard on this algorithm

Yeah, it shows. It's great to work on code like this!

I wish there was a small counter-example too, I’ll try to work on that. I think that would help narrow down where the actual problem is.

Here's a simple one:

  using point_t = int;
  using linestring_t = std::vector<point_t>;

  std::vector<std::pair<linestring_t, bool>> paths = {
    {{1, 0}, false},
    {{2, 0}, false},
    {{1, 2}, true},
  };
  auto euler_paths = eulerian_paths::get_eulerian_paths<point_t, linestring_t>(paths);

No points are considered must_start, so only the final step does anything. It starts at point 1, makes a path {1, 0}, then stitch_loops tries to stitch in {1, 2, 0}, making {1, 2, 0, 0}, which is not a valid result. With the change it returns {1, 0} and {1, 2, 0}.

It would be good to find one where the first call to stitch_loops fails, maybe tomorrow.

I've got a good idea how to fix this, just thinking about the right way to implement it.

Working on it in #736 . @tomjnixon Really good find that the bug is in eulerian paths. I wouldn't have guessed!

I was able to fix the error that you found here. I didn't think through the logic correctly and I thought that it was possible to stitch loops early. It works like this:

In a normal example with all bi-directional edges, you can know for sure that every intersection of points that has an odd number of edges must be the start/end of a path. So you go to one of those and then you make a path on edges as long as you can until you reach a vertex where you cannot continue because there are no more untraveled edges out of it. Then you find another vertex that still has an odd number of edges and you follow that until you hit a dead end. Do that until there are no more vertices with dead-ends.

After that, now you can take a path that you have already created and walk along it looking for any vertices with untraveled edges. Any path from there must eventually return there because after you traverse from it, there will only be one more vertex that could have a dead-end, and it is the same one. That is a loop and you stitch it into your path. You then keep doing that on the path until you get all the loops done. Do it for all paths.

Finally, do it for all nodes that aren't a part of any path and you're done.

The issue is with directional edges. We can only treat a node as having an even number of nodes if it could be even. That comes from the number of out edges matching the number of in edges where some of the bi-directional edges could be used as out or in.

My error was that I didn't realize that not only do we have to take care of nodes that have a combination of in, out, and bidi edges that require them to be a starting point, we are also reaching situations where nodes have a combination of in/out/bidi that require them to be end points.

I'm now handling that and this solved some of the problems but not all of them.

So far, in #736, I have some progress and some of the errors went away, but not all. I'm going to write some code that checks the inputs against the output of the algorithm, and will print out the buggy input/output pair. Then I can put it into the unit test and work against that, which will be faster. I hope that the error case will not be too big.

Possibly fixed in #743. Reopen this if the bug is not fixed.

Nice, thank you. I'll give it a go with my random test generator.

I think I was wrong to say that there isn't a boost-geometry-related issue though. I've got a test case where the buffer operation goes wrong, causing some traces to be missing from the SegmentTree; i'll open a new issue with that when I've tidied it up.