Saturday, October 26, 2013

C program to find Euler path or Euler Circuit



Reason to write this


            I was searched for C program to find the euler path/circuit in Google, but I am not able to find any C implementation for this. So I have decided to write a C program to find euler path/circuit. I written, compiled and published here. I hope it will helpful for some persons like me who are looking for C program to find the euler path/circuit.

EULER CIRCUIT PROBLEM

Consider the three figures in Figure below. A popular puzzle is to reconstruct these figures using a pen, drawing each line exactly once. The pen may not be lifted from the paper while the drawing is being performed. As an extra challenge, make the pen finish at the same point at which it started. This puzzle has a surprisingly simple solution.

The first figure can be drawn only if the starting point is the lower left- or right-hand corner, and it is not possible to finish at the starting point. The second figure is easily drawn with the finishing point the same as the starting point, but the third figure cannot be drawn at all within the parameters of the puzzle.
             We can convert this problem to a graph theory problem by assigning a vertex to each intersection.Then the edges can be assigned in the natural manner, as shown in below.
After this conversion is performed, we must find a path in the graph that visits every edge exactly once. If we are to solve the "extra challenge," then we must find a cycle that visits every edge exactly once. This graph problem was solved in 1736 by Euler and marked the beginning of graph theory. The problem is thus commonly referred to as an Euler path (sometimes Euler touror Euler circuit problem, depending on the specific problem statement. The Euler tour and Euler circuit problems, though slightly different, have the same basic solution. Thus, we will consider the Euler circuit problem

EULER PATH
In graph theory Euler path is a path that visits each edge from the graph exactly once.
EULER CYCLE/EULER CIRCUIT
            Euler cycle is a Euler path that starts and ends with the same node.
EULER GRAPH
            Euler graph is a graph with graph which contains Euler cycle.
EULERS THEOREM
Connected undirected graph is Euler graph if and only if every node in the graph is of even degree (has even number of  edges starting from that node).

HIERHOLZER’S ALGORITHM
This is an algorithm to find an Eulerian circuit in a connected graph in which every vertex has even degree.
1. Choose any vertex v and push it onto a stack. Initially all edges are unmarked.
2. While the stack is nonempty, look at the top vertex, u, on the stack. If u has an unmarked incident edge, say, to a vertex w, then push w onto the stack and mark the edge uw. On the other hand, if u has no unmarked incident edge, then pop u off the stack and print it.                
                 When the stack is empty, you will have printed a sequence of vertices that correspond to an Eulerian circuit

HIERHOLZER’S ALGORITHM - Example
We will use two stacks in this example: tempPath and finalPath in order to be able to combine the simple cycles we’ve found into one big cycle (the searched Euler’s cycle).

1.Lets start with edge 0 (arbitrary choice)
Adding 0 to the tempPath stack.
tempPath:0
finalPath:<empty>
2.Lets choose edge  0->1 (arbitrary choice).
Erasing the edge and adding 1 to tempPath stack
tempPath:0 1
finalPath:<empty>


3.Lets choose edge  1->2 (arbitrary choice).
Erasing the edge and adding 2 to tempPath stack
tempPath:0 1 2
finalPath:<empty>
4.Lets choose edge  2->3 (arbitrary choice).

Erasing the edge and adding 3 to tempPath stack
tempPath:0 1 2 3
finalPath:<empty>
5.Lets choose edge  3->0 (only possible choice).

Erasing the edge and adding 0 to tempPath stack
tempPath:0 1 2 3 0
finalPath:<empty>
We’ve created a simple cycle and there is nowhere to go, but there are still unvisited edges! Go back to vertex with unvisited edge, moving elements from tempPath to finalPath.

tempPath:0 1 2 3 0
finalPath:<empty>
6.Move back from o to 3.
Move o from tempPath to finalPath.
tempPath:0 1 2 3
finalPath:0
7.Move back from 3 to 2.

Move 3 from tempPath to finalPath.
tempPath:0 1 2
finalPath:0 3
8.Lets choose edge  2->4 (arbitrary choice).

Erasing the edge and adding 4 to tempPath stack
tempPath:0 1 2 4
finalPath:0 3
9.Lets choose edge  4->1 (only possible choice).

Erasing the edge and adding 1 to tempPath stack
tempPath:0 1 2 4 1
finalPath:0 3
10.Lets choose edge  1->5 (only possible choice).

Erasing the edge and adding 5 to tempPath stack
tempPath:0 1 2 4 1 5
finalPath:0 3
11.Lets choose edge  5->2 (only possible choice).

Erasing the edge and adding 2 to tempPath stack
tempPath:0 1 2 4 1 5 2
finalPath:0 3
So we have passed through all the edges! Now all we have to do is move elements from tempPath stack to finalPath stack!

tempPath:0 1 2 4 1 5 2
finalPath:0 3
The result sequence in finalPath stack is an Euler’s cycle!

tempPath:0 1 2 4 1 5 2         
finalPath:0 3
to
tempPath:<empty>
finalPath:0 3 2 5 1 4 2 1 0

C Program to find EULER Circuit/ EULER Path using Hierholzer’s Algorithm  


//Written and Compiled by M.Karuppasamy Pandiyan
#include<stdio.h>
#include<conio.h>
char stack[20];
int top=-1, n;
char b[20],finalPath[20];
char ajMat[20][20];
int fp=0,count;

//Push into Stack Operation
void push(char val)
{
top=top+1;
stack[top]=val;
}

//Pop from Stack Operation
char pop()
{
return stack[top--];
}

//To check weather all adjecent vertices/nodes are visited 
//or not
int allVisited(int i)
{
    int j;
    for(j=0;j<n;j++)
    {
       if(ajMat[i][j]=='y')
       return 0;
    }
    return 1;
}

//To get the current index of node in the array b[] of nodes
int getNo(char c)
{
    int l=0;
    while(c!=b[l])
    l++;
    return l;

}

//Display the Euler circuit/path
void displayPath()
{
     int i;
     for(i=0;i<fp;i++)
     {
       printf("%c ->",finalPath[i]);
     }
}

//To find the Euler circuit/path and store it in finalPath[] array
void eularFind(int root)
{
     int l,j;
     //push root into the stack
    push(b[root]);
    //Run upto stock becomes empty i.e top=-1
    while(top!=-1)
    {
      
      //get the array index of top of the stack
      l=getNo(stack[top]);
      //If all adjacent nodes are already visited
      //pop element from stack and store it in finalpath[] array
      if(allVisited(l))
      {
        finalPath[fp++]=pop();
        
      }
      //If any unvisited node available push that node into stack
      //mark that edge as already visited by marking 'n' in adjMat[][]
      //break the iteration
      else
      {
        for(j=0;j<n;j++)
        {
        if(ajMat[l][j]=='y')
        {
            
             ajMat[l][j]='n';
             ajMat[j][l]='n';
             push(b[j]);
            
             break;
           
        }
        }
       }
     }
}

//To get the degree of node i.e no of edges currently connected to the node
int getDegree(int i)
{
    int j,deg=0;
    for(j=0;j<n;j++)
    {
      if(ajMat[i][j]=='y') deg++;
    }
    return deg;
}

//To assign the root of the graph
//Condition 1: If all Nodes have even degree, there should be a euler Circuit/Cycle
//We can start path from any node
//Condition 2: If exactly 2 nodes have odd degree, there should be euler path.
//We must start from node which has odd degree
//Condition 3: If more than 2 nodes or exactly one node have odd degree, euler path/circuit not possible.

//findRoot() will return 0 if euler path/circuit not possible
//otherwise it will return array index of any node as root
int findRoot()
{
     
     int i,cur=1;//Assume root as 1
     for(i=0;i<n;i++)
     {
        if(getDegree(i)%2!=0)
        {
           count++;
           cur=i;//Store the node which has odd degree to cur variable
        }
     }
     //If count is not exactly 2 then euler path/circuit not possible so return 0
     if(count!=0 && count!=2)
     {
        return 0;
     }
     else return cur;// if exactly 2 nodes have odd degree, it will return one of those node as root otherwise return 1 as root  as assumed
}

int main()
{
    char v;
    int i,j,l;
    printf("Enter the number of nodes in a graph\n");
    scanf("%d",&n);
    printf("Enter the value of node of graph\n");
    for( i=0; i<n; i++)
    {
     scanf("%s",&b[i]);//store the nodes in b[] array
    }
    
    //Get the Graph details by using adjacency matrix
    printf("Enter the value in adjancency matrix in from of 'Y' or 'N'\n");
    printf("\nIf there is an edge between the two vertices then enter 'Y' or 'N'\n");
    for( i=0; i<n; i++)
    printf(" %c ",b[i]);
    for( i=0;i<n; i++)
    {
     printf("\n%c ",b[i]);
     for( j=0; j<n; j++)
     {
      printf("%c ",v=getch());
      ajMat[i][j]=v;
     }
      printf("\n\n");
    }
    
//findRoot() will return 0 if euler path/circuit not possible
//otherwise it will return array index of any node as root
    int root;
    if(root=findRoot())
    {
      if(count) printf("Available Euler Path is\n");
      else printf("Available Euler Circuit is\n");
      eularFind(root);
      displayPath();
    }
    else printf("Euler path or circuit not available\n");
    getch();
}

Example1: Input  Graph
Output
Example2: Input  Graph
Output:

Exmple 3:Input Graph
Output:






Reference:
       1. Data Structures and Algorithm Analysis in C by Mark Allen Weiss.
       2. Euler Graphs Power point Presentation by Deyan Yosifov, Telerik Corporation.

Goto Data Structure Concepts






12 comments:

  1. The only article on the web that has exactly what I wanted. Thank you!

    ReplyDelete
  2. Thank you so much for nice description

    ReplyDelete
  3. Great work! Thanks for the excellent article, it really helped me understand Eulerian algorithms. I will take your advice and donate to someone in need!

    ReplyDelete
  4. "EULER PATH
    In graph theory Euler path is a path that visits each **node** from the graph exactly once."
    Its a typo ... should be edge!

    ReplyDelete
    Replies
    1. Thanks for pointing it out. I updated the same.

      Delete