Please Go through the Introduction of Euler Circuit/Path to understand the Logic.
EulerCircuit is the Class which contains following Methods.
1. void GetInput()
2. int FindRoot()
3. int GetIndex(char c)
4. Boolean AllVisited(int node)
5. void FindEuler(int root)
6. int GetDegree(int i)
7. void FindEulerCircuit()
1. void GetInput()
- Get the no of nodes/vertices in Graph and store it in variable total.
- Get the names of all nodes/vertices and store it in nodeList array.
- Get the Graph edge representation and store it in 2 dimensional array GraphMatrix.
- If there is an edge between the two vertices then enter 'y' else 'n'
2. int FindRoot()
- It will return 0 or 1 or any number.
- Return 0 means: Euler path or circuit not possible for given graph.
- Return 1 means: Euler circuit available.
- Return any other nunmber means: Euler path available.
- GetDegree method used to find the no of edges connected to a node/vertex
- 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. return 1.
Condition 2: If exactly 2 nodes have odd degree, there should be euler path.We must start from node which has odd degree. return any other no.
Condition 3: If more than 2 nodes or exactly one node have odd degree, euler path/circuit not possible. return 0.
3. int GetIndex(char c)
- It will return the index of the node/vertex(c) in nodeList array.
4. Boolean AllVisited(int node)
- It will return true or false
- Return true means: All edges connected to node/vertex are already visited
- Return false means: there is at-least 1 edge connected to node/vertex not yet visited.
5. void FindEuler(int root)
- Find the Euler circuit/path with starting point as root and store it in finalPath arrayList
- push root into the stack tempPath
- If all adjacent nodes are already visited
- pop element from stack and store it in finalpath arrayList
- If any unvisited node available push that node into stack
- mark that edge as already visited by marking 'n' in GraphMatrix[][]
- break the iteration
- Loop will end when stack becomes empty.
6.int GetDegree(int i)
- Return the number of edges connected to vertex at index i of nodeList array
7.void FindEulerCircuit()
- GetInput();
- root = FindRoot()//Decide the root.
- if(root!=0)
- FindEuler(root)//Find the euler path/cycle with starting point as root
- PrintEulerCircuit()//Print the euler circuit/path.
- else euler path/circuit not possible.
C# Program::
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace Euler_Circuit_Application
{
class EulerCircuit
{
Stack tempPath = new Stack();
ArrayList finalPath = new ArrayList();//to store the final path
char[] nodeList;//to store the nodes
char[,] GraphMatrix;//to store the edge representation of Graph
int total, count;//total->total no of nodes, count->no of even degree node
//To Get the all input from user
private void GetInput()
{
Console.WriteLine("Enter the number of Nodes");
try
{//Get the number of nodes in a Graph
total = int.Parse(Console.ReadLine());
GraphMatrix = new char[total, total];
nodeList = new char[total];
Console.WriteLine("Enter the Nodes");
//To get the node/vertices to nodeList array
for (int i = 0; i < total; i++)
{
nodeList[i] = char.Parse(Console.ReadLine());
}
Console.WriteLine("Enter the Graph representattion in Matrix");
Console.WriteLine("If there is an edge between the two vertices then enter 'y' else 'n'");
//To get the edge details in a Graph
for (int i = 0; i < total; i++)
{
for (int j = 0; j < total; j++)
{
Console.Write("{0}----{1}==> ",nodeList[i],nodeList[j]);
GraphMatrix[i, j] = char.Parse(Console.ReadLine());
}
Console.WriteLine("");
}
}
catch
{
Console.WriteLine("Invalid number");
}
}
//To get the number of edges connected to vertex at index i of nodeList array
private int GetDegree(int i)
{
int j, deg = 0;
for (j = 0; j < total; j++)
{
if (GraphMatrix[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
private int FindRoot()
{
int root = 1; //Assume root as 1
count = 0;
for (int i = 0; i < total; i++)
{
if (GetDegree(i) % 2 != 0)
{
count++;
root = i;//Store the node which has odd degree to root 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 root;// 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 nodeList[] of nodes
private int GetIndex(char c)
{
int index = 0;
while (c != nodeList[index])
index++;
return index;
}
//To check weather all adjecent vertices/nodes are visited or not
private Boolean AllVisited(int node)
{
for (int l = 0; l < total; l++)
{
if (GraphMatrix[node, l] == 'y')
return false;
}
return true;
}
//To find the Euler circuit/path and store it in finalPath arrayList
private void FindEuler(int root)
{
int ind;
tempPath.Clear();
//push root into the stack
tempPath.Push(nodeList[root]);
while(tempPath.Count!=0)//until Stack going to empty
{
//get the array index of top of the stack
ind = GetIndex((char)tempPath.Peek());
if (AllVisited(ind))
{
//If all adjacent nodes are already visited
//pop element from stack and store it in finalpath arrayList
finalPath.Add(tempPath.Pop());
}
else
{
//If any unvisited node available push that node into stack
//mark that edge as already visited by marking 'n' in GraphMatrix[][]
//break the iteration
for (int j = 0; j < total; j++)
{
if (GraphMatrix[ind,j] == 'y')
{
GraphMatrix[ind, j] = 'n';
GraphMatrix[j, ind] = 'n';
tempPath.Push(nodeList[j]);
break;
}
}
}
}
}
//THis is the Main Program
public void FindEulerCircuit()
{
//Get the Graph representation from user
GetInput();
//Decide the root
int root = FindRoot();
//findRoot() will return 0 if euler path/circuit not possible
//otherwise it will return array index of any node as root
if(root!=0)
{
if(count!=0) Console.WriteLine("Available Euler Path is");
else Console.WriteLine("Available Euler circuit is");
//Find the Euler circuit
FindEuler(root);
//Print the euler Circuit
PrintEulerCircuit();
}
else
{
Console.WriteLine("Euler Path or Circuit not Possible");
}
}
public void PrintEulerCircuit()
{
for (int i = 0; i < finalPath.Count;i++ )
{
Console.Write("{0}--->", finalPath[i]);
}
}
}
class ExecuteEulerCircuit
{
static void Main(string[] args)
{
//Create oblect for EulerCircuit class and call FindEulerCircuit()
EulerCircuit ec = new EulerCircuit();
ec.FindEulerCircuit();
Console.ReadKey();
}
}
}
Example 1:Input Graph
Output:
Example 2:Input Graph:
Output::
Example 3:: Input Graph:
Output::
No comments:
Post a Comment