Eulerian path

[claudiogeop]

Hello everyone, I'm having problems performing the routing of the road base that I have. I need to route this cartographic base so that it passes through all the edges. At first determining an initial vertex and after going through all the edges my router will end up at that same vertex. Has anyone worked with this Eulerian graphic model?

[agila5]

Hi! Could you please add more details and, possibly, an example of input data and desired output? I've never worked on Eulerian graphic models but, my intuition is that there is no general solution unless you add some conditions or hypothesis regarding the structure of the linear network.

[claudiogeop]

Hello, I have these cartographic bases at the national level, let's go to the layers:
The 'Teresina' point will be our point of departure and arrival, later I would like to have the possibility of inserting another point for arrival, but at first the idea would be this, arrival and departure. The layer in black is our route 01 and must be completely traversed, with the possibility of inserting impedances. We also have the dotted blue layer which are the other routes, but it should serve as a support in some situations to improve routing.
Thanks for the help!

[agila5]

IMO that looks like a problem related to the TSP. Did you check the sfnetworks vignettes?

[claudiogeop]

I believe it is more related to the Chinese postman problem. Does sfnetworks already have something developed in this regard? In python we have the application using the NetworkX library, I have been using it however it would be highly beneficial if we have something developed for the R language.

[agila5]

AFAIK, there is no built-in routine that can be used to solve the Chinese postman problem. See also here for a discussion.

[claudiogeop]

Alright, I'll take a look...

[luukvdmeer]

Igraph has functions for finding Eulerian paths and cycles, but not sure if this exactly does what you need: https://rdrr.io/cran/igraph/man/has_eulerian_path.html