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 tour) or 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

For C# Program to find Euler Circuit/Euler Path Click Here

Click Here for C Program implementation of Fluery's Algorithm to find euler circuit

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

Goto CSR Initiative