Saturday, April 18, 2015

C Program for Fleury's Algorithm to find euler 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 node 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).

Fleury's Algorithm.

1. Pick up a starting Vertex.
    Condition 1: If all Nodes have even degree, there should be a euler Circuit/Cycle. We can pick up any vertex as starting vertex.
    Condition 2: If exactly 2 nodes have odd degree, there should be euler path. We need to pick up any one of this two as starting vertex.
    Condition 3: If more than 2 nodes or exactly one node have odd degree, euler path/circuit not possible.
2. Get the next vertex in euler Path.
    Condition: Don't break the bridge.
        i) select the next vertex which has more than one edges.
        ii) If next vertex has only one edge,
            a) If it is last vertex, We can choose it as next vertex.
            b) otherwise dont.
3. Remove the selected edge.
4. Repeat 2 & 3 until all edges have been traversed, and you are back at the starting vertex.





















C Program::


#include<stdio.h>
#include<conio.h>

int n;
int b[100],finalPath[100];
char ajMat[100][100];
int fp=0,count=0;

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

//To get the degree of node i.e no of edges currently connected to the node
int getDegree(int node)
{
    int j,deg=0;
    int pos=getIndex(node);
    for(j=0;j<n;j++)
    {
      if(ajMat[pos][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(b[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 b[cur];// if exactly 2 nodes have odd degree, it will return one of those node as root otherwise return 1 as root  as assumed
}

//To get the current index of node in the array b[] of nodes
int getIndex(int node)
{
    int k=0;
    while(node!=b[k])
    k++;
     //printf("inside while\n");
   
    //l++;
    return k;
}

int isLastNode(int node)
{
    int i=0;
    int degSum=0;
    for(i=0;i<n;i++)
    {
     degSum=degSum+getDegree(b[i]);
    }
    if(degSum==2)
      return 1;
    else
      return 0;
}

int getNextNode(int node)
{
    int i=0;
    int pos=getIndex(node);
        
    for(i=0;i<n;i++)
    {   
      if(ajMat[pos][i]=='y')
      {        
        if(!isHasOneEdge(b[i]))
        {
          return b[i];
        }
        else
        {
            if(isLastNode(b[i]))
            return b[i];
        }
      }
    }
    return -1;
}

int isHasOneEdge(int node)
{  
    if(getDegree(node)==1)
      return 1;
    else
      return 0;
}

int isCompleted()
{
    int i=0;
    for(i=0;i<n;i++)
    {
        if(getDegree(b[i])>0)
             return 0;
    }
    return 1;
}

void removeEdge(root,eNode)
{
     int pos1=0,pos2=0;    
     pos1=getIndex(root);
     pos2=getIndex(eNode);
     ajMat[pos1][pos2]='n';
     ajMat[pos2][pos1]='n';
}

//To find the Euler circuit/path and store it in finalPath[] array
void eularFind(int root)
{   
     int eNode;
     while(!isCompleted())
     {
        eNode=getNextNode(root);   //get Next node    
        finalPath[fp++]=eNode;     //add the node to euler path
        removeEdge(root,eNode);   //remove the edge
        root=eNode; //change the root
     }
    /* printf("root=%d\n",root);
        eNode=getNextNode(root);
        printf("getNextNode=%d \n",eNode);
        finalPath[fp++]=eNode;
        removeEdge(root,eNode);
        root=eNode;*/
}

void printbArray()
{
     int i;
      for( i=0; i<n; i++)
    {
     printf("%d  ",b[i]);//store the nodes in b[] array
    }
}
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("%d",&b[i]);//store the nodes in b[] array
    }
  
   
    //Get the Graph details by using adjacency matrix
    printf("Enter the value in adjancency matrix in form of 'Y' or 'N'\n");
    printf("\nIf there is an edge between the two vertices then enter 'Y' else 'N'\n");
    for( i=0; i<n; i++)
    printf(" %d ",b[i]);
    for( i=0;i<n; i++)
    {
     printf("\n%d ",b[i]);
     for( j=0; j<n; j++)
     {
      printf("%c ",v=getch());
      ajMat[i][j]=v;
     }
      printf("\n\n");
    }
  
/*   We can manually hard code the Graph value by below. But u need to command the above one to get the edge details.
ajMat[0][0]='n';
ajMat[0][1]='y';
ajMat[0][2]='n';
ajMat[0][3]='y';
ajMat[0][4]='n';
ajMat[0][5]='n';
           
ajMat[1][0]='y';
ajMat[1][1]='n';
ajMat[1][2]='y';
ajMat[1][3]='n';
ajMat[1][4]='y';
ajMat[1][5]='y';
           
ajMat[2][0]='n';
ajMat[2][1]='y';
ajMat[2][2]='n';
ajMat[2][3]='y';
ajMat[2][4]='y';
ajMat[2][5]='y';
           
ajMat[3][0]='y';
ajMat[3][1]='n';
ajMat[3][2]='y';
ajMat[3][3]='n';
ajMat[3][4]='n';
ajMat[3][5]='n';
           
ajMat[4][0]='n';
ajMat[4][1]='y';
ajMat[4][2]='y';
ajMat[4][3]='n';
ajMat[4][4]='n';
ajMat[4][5]='n';
           
ajMat[5][0]='n';
ajMat[5][1]='y';
ajMat[5][2]='y';
ajMat[5][3]='n';
ajMat[5][4]='n';
ajMat[5][5]='n';
 */ 
    //findRoot() will return 0 if euler path/circuit not possible
    //otherwise it will return array index of any node as root

    int root,pos;
    if(root=findRoot())
    {
      if(count) printf("Available Euler Path is\n");
      else printf("Available Euler Circuit is\n");
      finalPath[fp++]=root;
      eularFind(root);
      displayPath();
    }
    else printf("Euler path or circuit not available\n");
    getch();
}


Goto Data Structure Concepts

1 comment:

  1. it was very helpful indeed and the encouragement posts also.. keep it up bro :)

    ReplyDelete