Skip to content

[chinese_postman] Finish implementation #3

@peferron

Description

@peferron

There's an unfinished implementation of the Chinese postman problem in the chinese_postman branch.

It's unfinished because solving this problem on undirected graphs is much more complicated than it looks. Specifically, one of the sub-problems it decomposes into is complicated: minimum weight perfect matching in a general undirected graph.

The right way to go would be to take care of this sub-problem first in a dedicated module—it definitely deserves it—and then go back to finish the chinese_postman module.

Note that the Chinese postman problem is much easier to solve on directed graphs: the sub-problem becomes matching in a bipartite graph, which is much simpler and has already been implemented in this repo.

Metadata

Metadata

Assignees

Labels

No labels
No labels

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions