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! P.S. Steps are copied from https://www.geeksforgeeks.org/chinese-postman-route-inspection-set-1-introduction/
_______________________________________________ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
