Hi,
I am very new to graph theory, but I am interested in solving a real-world trail hiking problem using Chinese Postman Problem on a weighted undirected graph. Could someone help identify igraph functions for the steps? (especially the last one.) My guesses are on lines starting with "SD:".
Algorithm to find shortest closed path or optimal Chinese postman route in a weighted graph that may not be Eulerian.
1: If graph is Eulerian,return sum of all edge weights.Else do following steps.
SD: Check whether igraph_degree() returns even degree for every vertex in the graph.
2: We find all the vertices with odd degree
SD: use vertex degrees from step one to find vertices with odd degree.
3: List all possible pairings of odd vertices.
SD: no igraph necessary
4: For each set of pairings, find the shortest path connecting them.
SD: igraph_shortest_paths_dijkstra() for pairings from step 3.
5: Find the pairing with minimum shortest path connecting pairs.
SD: no igraph necessary
6: Modify the graph by adding all the edges that have been found in step 5.
SD: igraph_add_vertices()
7: Weight of Chinese Postman Tour is sum of all edges in the modified graph.
SD: sum all weights of all edges
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?
Thanks in advance!