traverse all edges and print nodes in euler circuit

Question

I am trying to solve this question. I am able to find by seeing the degrees that the given structure can form euler circuit or not but I am unable to figure out how to find trace all path, for the given test case

5

2 1

2 2

3 4

3 1

2 4

there is one loop in the circuit at node 2, which I don't know how to trace, If I am using adjacency list representation then I'll get following list

1: 2,3

2: 1,2,2,4

3: 1,4

4: 2,3

So how to traverse every edge, I know it is euler circuit problem, but that self loop thing is making tough for me to code and I am not getting any tutorial or blog from where I can understand this thing.

I again thought to delete the nodes from adjacency list once I traverse that path( in order to maintain the property of euler(path should be traversed once)), but I am using vector for storing adjacency list and I don't know how to delete particular element from vector. I googled it and found remove command to delete from vectors but remove deletes all matching element from the vector.

I tried to solve the problem as below now, but getting WA :(

#include<iostream>
#include<cstdio>
#include<cstring>

int G[52][52];
int visited[52],n;

void printadj() {
  int i,j;
  for(i=0;i<51;i++) {
    for(j=0;j<51;j++)
      printf("%d  ",G[i][j]);
    printf("\n");
  }     
 }

 void dfs(int u){
  int v;
  for(v=0;v<51;v++){
    if(G[u][v]){
        G[u][v]--;
        G[v][u]--;
        printf("%d %d\n",u,v);       
        dfs(v);
     }                  
  }
}

bool is_euler(){
   int i,j,colsum=0,count=0;
   for(i=0;i<51;i++) {
    colsum=0;
    for(j=0;j<51;j++) {
       if(G[i][j] > 0) {
           colsum+=G[i][j];
       }
    }
     if(colsum%2!=0) count++; 
  }     
//  printf("\ncount=%d\n",count);
  if(count >0 ) return false;
  else return true;
}
void reset(){
    int i,j;
    for(i=0;i<51;i++)
      for(j=0;j<51;j++)                 
        G[i][j]=0;
}
int main(){
    int  u,v,i,t,k;
    scanf("%d",&t);
    for(k=0;k<t;k++) {
      scanf("%d",&n);
      reset();
      for(i=0;i<n;i++){
        scanf("%d%d",&u,&v);
        G[u][v]++;
        G[v][u]++;     
       }
//    printadj();
       printf("Case #%d\n",k+1);
      if(is_euler()) {
         dfs(u);
      }
      else printf("some beads may be lost\n");
      printf("\n");
  }
  return 0;
}

Dont know why getting WA :(

New Code:-

#include<iostream>
#include<cstdio>
#include<cstring>

#define max 51

int G[max][max],print_u[max],print_v[max],nodes_traversed[max],nodes_found[max];
int n,m;

void printadj() {
  int i,j;
  for(i=0;i<max;i++) {
    for(j=0;j<max;j++)
      printf("%d  ",G[i][j]);
    printf("\n");
  }
 }

void dfs(int u){
  int v;
  for(v=0;v<50;v++){
    if(G[u][v]){
        G[u][v]--;
        G[v][u]--;
        print_u[m]=u;
        print_v[m]=v;
        m++;
        dfs(v);
     }
  }
  nodes_traversed[u]=1;
}

bool is_evendeg(){
   int i,j,colsum=0,count=0;
   for(i=0;i<50;i++) {
    colsum=0;
    for(j=0;j<50;j++) {
       if(G[i][j] > 0) {
           colsum+=G[i][j];
       }
    }
     if(colsum&1) return false;
  }
  return true;
}

int count_vertices(int nodes[]){
 int i,count=0;
 for(i=0;i<51;i++) if(nodes[i]==1) count++;
 return count;
}
void reset(){
    int i,j;
    m=0;
    for(i=0;i<max;i++)
      for(j=0;j<max;j++)
        G[i][j]=0;
    memset(print_u,0,sizeof(print_u));
    memset(print_v,0,sizeof(print_v));
    memset(nodes_traversed,0,sizeof(nodes_traversed));
    memset(nodes_found,0,sizeof(nodes_found));
}

bool is_connected(int tot_nodes,int trav_nodes) {
 if(tot_nodes == trav_nodes) return true;
 else return false;
}

int main(){
    int  u,v,i,t,k,tot_nodes,trav_nodes;
    scanf("%d",&t);
    for(k=0;k<t;k++) {
      scanf("%d",&n);
      reset();
      for(i=0;i<n;i++){
        scanf("%d%d",&u,&v);
        G[u][v]++;
        G[v][u]++;
        nodes_found[u]=nodes_found[v]=1;
       }
//    printadj();
      printf("Case #%d\n",k+1);
      tot_nodes=count_vertices(nodes_found);
      if(is_evendeg()) {
        dfs(u);
        trav_nodes=count_vertices(nodes_traversed);
        if(is_connected(tot_nodes,trav_nodes)) {
          for(i=0;i<m;i++)
            printf("%d  %d\n",print_u[i],print_v[i]);
        }
        else printf("some beads may be lost\n");
      }
      else printf("some beads may be lost\n");
      printf("\n");
  }
  return 0;
}

This code is giving me runtime error there, please look into the code.

Answer 1

What you need to do is form arbitrary cycles and then connect all cycles together. You seem to be doing only one depth first traversal, which might give you a Eulerian circuit, but it also may give you a 'shortcut' of an Eulerian circuit. That is because in every vertex where the Eulerian circuit passes more then once (i.e., where it crosses itself), when the depth first traversal arrives there for the first time, it may pick the edge that leads directly back to the start of the depth first traversal.

Thus, you're algorithm should consist of two parts:

1. Find all cycles
2. Connect the cycles together

If done right, you don't even have to check that all vertices have an even degree, instead you can rely on the fact that if step 1 or 2 cannot continue anymore, there exists no Eulerian cycle.

Reference Implementation (Java)

Since there's no language tag in your question, I'm going to assume that it's fine for you that I'll give you a Java reference implementation. Furthermore, I'll use the term 'node' instead of 'vertex', but that's just personal preference (it gives shorter code ;)).

I'll use one constant in this algorithm, which I will refer to from the other classes:

public static final int NUMBER_OF_NODES = 50;

Then, we'll need an Edge class to easily construct our cycles, which are basically linked lists of edges:

public class Edge
{
    int u, v;
    Edge prev, next;

    public Edge(int u, int v)
    {
        this.u = u;
        this.v = v;
    }

    /**
     * Attaches a new edge to this edge, leading to the given node
     * and returns the newly created Edge. The node where the
     * attached edge starts doesn't need to be given, as it will
     * always be the node where this edge ends.
     * 
     * @param node The node where the attached edge ends.
     */
    public Edge attach(int node)
    {
        next = new Edge(this.v, node);
        next.prev = this;
        return next;
    }
}

Then, we'll need a Cycle class that can easily join two cycles:

public class Cycle
{
    Edge start;
    boolean[] used = new boolean[NUMBER_OF_NODES+1];

    public Cycle(Edge start)
    {
        // Store the cycle itself
        this.start = start;
        // And memorize which nodes are being used in this cycle
        used[start.u] = true;
        for (Edge e = start.next; e != start; e = e.next)
            used[e.u] = true;
    }

    /**
     * Checks if this cycle can join with the given cycle. That is
     * the case if and only if both cycles use a common node.
     * 
     * @return {@code true} if this and that cycle can be joined,
     *         {@code false} otherwise.
     */
    public boolean canJoin(Cycle that)
    {
        // Find a commonly used node
        for (int node = 1; node <= NUMBER_OF_NODES; node++)
            if (this.used[node] && that.used[node])
                return true;
        return false;
    }

    /**
     * Joins the given cycle to this cycle. Both cycles will be broken
     * at a common node and the paths will then be connected to each
     * other. The given cycle should not be used after this call, as the
     * list of used nodes is most probably invalidated, only this cycle
     * will be updated and remains valid.
     * 
     * @param that The cycle to be joined to this cycle.
     */
    public void join(Cycle that)
    {
        // Find the node where we'll join the two cycles
        int junction = 1;
        while (!this.used[junction] || !that.used[junction])
            junction++;
        // Find the join place in this cycle
        Edge joinAfterEdge = this.start;
        while (joinAfterEdge.v != junction)
            joinAfterEdge = joinAfterEdge.next;
        // Find the join place in that cycle
        Edge joinBeforeEdge = that.start;
        while (joinBeforeEdge.u != junction)
            joinBeforeEdge = joinBeforeEdge.next;
        // Connect them together
        joinAfterEdge.next.prev = joinBeforeEdge.prev;
        joinBeforeEdge.prev.next = joinAfterEdge.next;
        joinAfterEdge.next = joinBeforeEdge;
        joinBeforeEdge.prev = joinAfterEdge;
        // Update the used nodes
        for (int node = 1; node <= NUMBER_OF_NODES; node++)
            this.used[node] |= that.used[node];
    }

    @Override
    public String toString()
    {
        StringBuilder s = new StringBuilder();
        s.append(start.u).append(" ").append(start.v);
        for (Edge curr = start.next; curr != start; curr = curr.next)
            s.append("\n").append(curr.u).append(" ").append(curr.v);
        return s.toString();
    }
}

Now our utility classes are in place, we can write the actual algorithm (although technically, part of the algorithm is extending a path (Edge.attach(int node)) and joining two cycles (Cycle.join(Cycle that)).

/**
 * @param edges A variant of an adjacency matrix: the number in edges[i][j]
 *        indicates how many links there are between node i and node j. Note
 *        that this means that every edge contributes two times in this
 *        matrix: one time from i to j and one time from j to i. This is
 *        also true in the case of a loop: the link still contributes in two
 *        ways, from i to j and from j to i, even though i == j.
 */
public static Cycle solve(int[][] edges)
{
    Deque<Cycle> cycles = new LinkedList<Cycle>();
    // First, find a place where we can start a new cycle
    for (int u = 1; u <= NUMBER_OF_NODES; u++)
        for (int v = 1; v <= NUMBER_OF_NODES; v++)
            if (edges[u][v] > 0)
            {
                // The new cycle starts at the edge from u to v
                Edge first, last = first = new Edge(u, v);
                edges[last.u][last.v]--;
                edges[last.v][last.u]--;
                int curr = last.v;
                // Extend the list of edges until we're back at the start
                search: while (curr != u)
                {
                    // Find any edge that extends the last edge
                    for (int next = 1; next <= NUMBER_OF_NODES; next++)
                        if (edges[curr][next] > 0)
                        {
                            // We found an edge, attach it to the last one
                            last = last.attach(next);
                            edges[last.u][last.v]--;
                            edges[last.v][last.u]--;
                            curr = next;
                            continue search;
                        }
                    // We can't form a cycle anymore, which
                    // means there is no Eulerian cycle.
                    return null;
                }
                // Connect the end to the start
                last.next = first;
                first.prev = last;
                // Save it
                cycles.add(new Cycle(last));
                // And don't forget about the possibility that there are
                // more edges running from u to v, so v should be
                // re-examined in the next iteration.
                v--;
            }
    // Now we have put all edges into cycles,
    // we join them all together (if possible)
    merge: while (cycles.size() > 1)
    {
        // Join the last cycle with any of the previous ones
        Cycle last = cycles.removeLast();
        for (Cycle curr : cycles)
            if (curr.canJoin(last))
            {
                // Found one! Just join it and continue the merge
                curr.join(last);
                continue merge;
            }
        // No compatible cycle found, meaning there is no Eulerian cycle
        return null;
    }
    return cycles.getFirst();
}