title: How to make a recursive function for find all Euler path in a graph?
body: <p>I'm trying to find all Euler paths in a graph. For doing this, I'm using a java code based on this: <a href="http://www.sanfoundry.com/java-program-implement-euler-circuit-problem/" rel="nofollow noreferrer">http://www.sanfoundry.com/java-program-implement-euler-circuit-problem/</a> (this example finds just one euler path).</p>
  
  <p>Basically, I made some changes in PrintEulerUtil method (below), but that brings me some problems in the algorithm, and I can't find a solution that works.</p>
  
  <p>Here is the code:</p>
  
  <pre><code>public void printEulerTourUtil(int vertex, int[][] adjacencyMatrix, String trail) {
  
          // variable that stores (in every recursive call) the values of the adj matrix
          int[][] localAdjacencyMatrix = new int[this.numberOfNodes + 1][this.numberOfNodes + 1];
          // verifies if there is some edge unvisited. if not, then the euler path is in variable "trail"
          int verificationSum = 0;
  
          // copy values of variable, not only reference
          for (int i = 0; i &lt;= numberOfNodes; i++) {
              for (int j = 0; j &lt;= numberOfNodes; j++) {
                  localAdjacencyMatrix[i][j] = adjacencyMatrix[i][j];
                  verificationSum += localAdjacencyMatrix[i][j];
              }
          }
  
          Integer destination = 1;
  
          // if verificationSum != 0, then, at least one edge is in the adj matrix
          if (verificationSum != 0) {
             // test for every destination possible if is valid (isValidNextEdge) and if has connection between the actual vertex and the destination.
              for (destination = 1; destination &lt;= numberOfNodes; destination++) {
                  if (localAdjacencyMatrix[vertex][destination] == 1 &amp;&amp; isValidNextEdge(vertex, destination, localAdjacencyMatrix)) {
                      // remove the edge for the next recursion call (and not loop the program)
                      removeEdge(vertex, destination, localAdjacencyMatrix);
                      trail = trail.concat(destination.toString());
                      // recursive call 
                      printEulerTourUtil(destination, localAdjacencyMatrix, trail);
                  }
              }
          } else {
              System.out.println("Euler path: " + trail);
          }
      }
  </code></pre>
  
  <p>The problem is: when the recursive call returns, and destination increments, the graph (adjacency matrix) suffers some changes that impossible to find new (nexts) Euler paths. It easier with an example, so:</p>
  
  <p><img src="https://i.stack.imgur.com/NHmdZ.png" alt="enter image description here"></p>
  
  <p>As you can see, for example, in the second level of the three, when destination is equals to 4, the edges 1-2 and 1-3 are already removed by previous recursive calls. Then, the graph is not the same of the beggining... which make impossible to find the Euler paths after the first one (because the graph isn't correct).</p>
  
  <p>Any thoughts? If someone wants my entire code, just ask. Any help will be very useful. Thank you so much and sorry the size of the post. </p>