I'm working on finding an Euler circuit for an indoor geographical 2D grid. when abstracting the grid as a an undirected graph, all nodes in the graph are connected (i.e, there is a path between every node in the graph). The graph could be huge (more than 100,000) nodes. The requirements are simple :
1- The generated path has to pass by every edge in the graph in both directions.
2- I need to minimize the number of times any edge appears in the generated path, such that the Optimal solution is a path that would include each edge ONLY once for each direction.
I abstracted the problem as an undirected graph, for which I have to find an Euler circuit in one direction. I did so for simplicity. If I was able to produce a path that would include every edge in one direction, I could simply reverse that path and hence meet the requirement of generating a path that covers the edges of the graph in both directions. Since I was looking for an optimal solution (minimizing the number of edges after including them at-least once), I planned the following steps:
1- 10 percent of the nodes had an odd degree (about 10,000 nodes!), therefore, I had to employ a matching algorithm to find the shortest mutually disjoint paths between pairs of odd nodes such that the sum of the distance between pairs is minimized. In other words, using a variation of blossom algorithm http://web.eecs.umich.edu/~pettie/matching/Edmonds-Johnson-chinese-postman.pdf
2- After adding the artificial edges between odd pairs, the nodes of the graph are all of even degree. Find the Euler circuit for the graph.
3- Include a reverse version of the generated path to the final solution.
Issues with first approach
Understanding and Implementing J.Edmond's algorithm (blossom algorithm) is a tedious task. More importantly, the solution is still not optimal (several edges are covered more than once due to pairing of odd nodes).
1- Abstracting the grid as a directed graph, simply by doubling the edges of each node of the graph (i.e, one edge from node A->B and the other B->A). Hence, guaranteeing that all nodes are of even degree, such that the number of incoming edges of every node is equal to the number of outgoing edges.
2- Finding an Euler Circuit for the directed graph. The optimal solution (which is an Euler circuit that exists) is in this case double the summation of all edges.
My question is simple. Before I get too excited, are there any shortcomings to the second approach ?. Does the second approach (directed graph) meet the requirements of an Euler circuit ?