Java Program to Implement Euler Circuit Problem

This Java program is Implement Euler Circuit Problem.In graph theory, an Eulerian trail (or Eulerian path) is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail which starts and ends on the same vertex.

Here is the source code of the Java program to Implement Euler Circuit Problem. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. import java.util.InputMismatchException;
  2. import java.util.Scanner;
  3.  
  4. public class EulerCircuit
  5. {
  6.  
  7.     private int[][] adjacencyMatrix;
  8.     private int numberOfNodes; 
  9.  
  10.     public EulerCircuit (int numberOfNodes, int[][] adjacencyMatrix)
  11.     {
  12.         this.numberOfNodes = numberOfNodes;
  13.         this.adjacencyMatrix = new int[numberOfNodes + 1] [numberOfNodes + 1];
  14.         for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++)
  15.         {
  16.             for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++)
  17.             {
  18.                 this.adjacencyMatrix[sourceVertex][destinationVertex]
  19.                    = adjacencyMatrix[sourceVertex] [destinationVertex];
  20.             }
  21.         }
  22.     }
  23.  
  24.     public int degree (int vertex)
  25.     {
  26.         int degree = 0;
  27.         for (int destinationvertex = 1; destinationvertex <= numberOfNodes ; destinationvertex++)
  28.         {
  29.             if (adjacencyMatrix[vertex][destinationvertex] == 1 
  30.                    || adjacencyMatrix[destinationvertex][vertex] == 1)
  31.             {
  32.                 degree++;
  33.             }
  34.         }
  35.         return degree;
  36.     }
  37.  
  38.     public int oddDegreeVertex ()
  39.     {
  40.         int vertex = -1;
  41.         for (int node = 1; node <= numberOfNodes; node++) 
  42.         {
  43.             if ((degree(node) % 2) != 0)
  44.             {
  45.                 vertex = node;
  46.                 break;
  47.             }
  48.         }
  49.         return vertex;
  50.     }
  51.  
  52.     public void printEulerTourUtil (int vertex)
  53.     {
  54.         for (int destination = 1; destination <= numberOfNodes; destination++)
  55.         {
  56.             if(adjacencyMatrix[vertex][destination] == 1 && isVaildNextEdge(vertex, destination))
  57.             {
  58.                 System.out.println(" source : " + vertex + " destination " + destination);
  59.                 removeEdge(vertex, destination);
  60.                 printEulerTourUtil(destination);
  61.             }	
  62.         }
  63.     }
  64.  
  65.     public void printEulerTour ()
  66.     {
  67.         int vertex = 1;
  68.         if (oddDegreeVertex() != -1)
  69.         {
  70.             vertex = oddDegreeVertex();
  71.         }
  72.         printEulerTourUtil(vertex);
  73.         return;
  74.     }
  75.  
  76.     public boolean isVaildNextEdge (int source, int destination)
  77.     {
  78.         int count = 0;
  79.         for (int vertex = 1; vertex <= numberOfNodes; vertex++)
  80.         {
  81.             if (adjacencyMatrix[source][vertex] == 1)
  82.             {
  83.                 count++;
  84.             }
  85.         }
  86.  
  87.         if (count == 1 )
  88.         {   
  89.             return true;
  90.         }
  91.  
  92.         int visited[] = new int[numberOfNodes + 1];		
  93.         int count1 = DFSCount(source, visited);
  94.  
  95.         removeEdge(source, destination);
  96.         for (int vertex = 1; vertex <= numberOfNodes; vertex++)
  97.         {
  98.             visited[vertex] = 0;
  99.         }
  100.  
  101.        int count2 = DFSCount(source, visited);
  102.        addEdge(source, destination);
  103.  
  104.        return (count1 > count2 ) ? false : true;
  105.     } 
  106.  
  107.     public int DFSCount (int source, int visited[])
  108.     {
  109.         visited[source] = 1;
  110.         int count = 1;
  111.         int destination = 1;
  112.  
  113.         while (destination <= numberOfNodes)
  114.         {
  115.             if(adjacencyMatrix[source][destination] == 1 && visited[destination] == 0)
  116.             {
  117.                 count += DFSCount(destination, visited);
  118.             }
  119.             destination++;
  120.         }
  121.         return count;
  122.     }
  123.  
  124.     public void removeEdge (int source, int destination)
  125.     {
  126.         adjacencyMatrix[source][destination]  = 0;
  127.         adjacencyMatrix[destination][source] = 0;
  128.     }
  129.  
  130.     public void addEdge (int source, int destination)
  131.     {
  132.         adjacencyMatrix[source][destination] = 1;
  133.         adjacencyMatrix[destination][source] = 1;
  134.     }
  135.  
  136.     public static void main (String... arg)
  137.     {
  138.         int number_of_nodes;
  139.         Scanner scanner = null;
  140.  
  141.         try
  142.         {
  143.             // read the number of nodes
  144.             System.out.println("Enter the number of nodes in the graph");
  145.             scanner = new Scanner(System.in);
  146.             number_of_nodes = scanner.nextInt();
  147.  
  148.             // read the adjacency matrix
  149.             int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
  150.             System.out.println("Enter the adjacency matrix");
  151.             for (int i = 1; i <= number_of_nodes; i++)
  152.             {
  153.                 for (int j = 1; j <= number_of_nodes; j++)
  154.                 {	
  155.                     adjacency_matrix[i][j] = scanner.nextInt();
  156.                 }
  157.             }
  158.  
  159.             //make the graph undirected
  160.             for (int i = 1; i <= number_of_nodes; i++)
  161.             {
  162.                 for (int j = 1; j <= number_of_nodes; j++)
  163.                 {	
  164.                     if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0)
  165.                     {
  166.                         adjacency_matrix[j][i] = 1;
  167.                     }
  168.                 }
  169.             }			
  170.             System.out.println("the euler path or euler circuit is ");
  171.             // print euler path or circuit
  172.             EulerCircuit circuit = new EulerCircuit(number_of_nodes, adjacency_matrix);
  173.             circuit.printEulerTour();
  174.         } catch (InputMismatchException inputMismatch)
  175.          {
  176.              System.out.println("Wrong Input format");
  177.          }
  178.         scanner.close();
  179.     }	
  180. }


$javac EulerCircuit.java
$java EulerCircuit
Enter the number of nodes in the graph
4
Enter the adjacency matrix
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
the euler path or euler circuit is 
 source : 1 destination 2
 source : 2 destination 3
 source : 3 destination 4
 source : 4 destination 1

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.