The task of the Chinese postman. Finding the Euler cycle

At the university, they were asked to solve the problem of the Chinese postman.Here is the algorithm for solving it.

  1. We look at whether the graph is Eulerian or not. If yes, go to point (5).

  2. We construct a distance matrix for graphs with odd degrees of vertices.

  3. We build minimal matching pairs.

  4. We build imaginary paths for the found pairs.Now our graph is Eulerian.

  5. We find the Euler cycle and this will be the answer in our tasks. The problem with point 5 is if the graph was originally non-Eulerian. Outputs a path that is not clear to me. I tried to find the error myself, but nothing came out. I set the adjacency matrix as
    0 1 1 0
    1 0 1 1
    1 1 0 2
    0 2 1 0
    Where numbers greater than 0 indicate the number of paths, including imaginary ones.With this matrix, the values 01133210

     private List<Integer> eilerPath(int[][] matrixAdjacency) {
         Stack<Integer> stack = new Stack<>();
         List<Integer> list = new ArrayList<>();
         int v = 0;
         int u;
         int edge;
         stack.push(v);
         while (!stack.empty()) {
             edge = findAdjacencyVertex(matrixAdjacency, stack.peek());
             if (edge == -1) {
                 list.add(stack.pop());
             } else {
                 u = edge;
                 matrixAdjacency[stack.peek()][u]--;
                 matrixAdjacency[u][stack.peek()]--;
                 stack.push(u);
             }
         }
     return list;
     }
    
     private int findAdjacencyVertex(int[][] matrixAdjacency, int edge) {
         for (int i = 0; i < matrixAdjacency.length; i++) {
             if (matrixAdjacency[edge][i] > 0) {
                 return i;
             }
         }
         return -1;
     }
    
Author: Максим Никитин, 2020-06-16

1 answers

The algorithm is fully working. I found an error in another part of the code. The adjacency matrix with imaginary paths was not constructed quite correctly. In some places, I simply did not add them, which resulted in paths with an odd number of edges.

 0
Author: Максим Никитин, 2020-06-17 07:27:00