Re: [igraph] Chinese Postman Problem with igraph?

[Victor Snesarev]

Sounds like you're describing the Hierholzer's algorithm.

Thank you, Tamas! That answers my question.

Out of curiosity... There is an extensive set of functions in igraph dealing with paths but not with circuits. Why is that? Is it simply because circuits are not very useful for problems people use igraph to solve?

-SD

On Tue, Jan 8, 2019 at 6:05 AM Tamas Nepusz <address@hidden> wrote:

> 6: Modify the graph by adding all the edges that  have been found in step 5.
> SD: igraph_add_vertices()
igraph_add_edges(), most likely

> 8: Print Euler Circuit of the modified graph. This Euler Circuit is Chinese Postman Tour.
> SD: I cannot find any functions that, given a starting vertex, calculate a circuit, a tour, or a closed path. Recommendations?
There is no such function, but if there is an Euler circuit in the
graph, all you need to do is to start from anywhere, and keep on
following any unvisited edge going outwards from the current vertex,
marking the edge as "visited" while doing so. If you get stuck
somewhere, then you have found the Euler circuit of the connected
component containing the start vertex. (If there are multiple
connected components, proceed with the next one).

T.

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help