Advertisement
Guest User

TestGraph Eulerian Detector

a guest
Dec 27th, 2017
342
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.98 KB | None | 0 0
  1. package euleriancircuits;
  2.  
  3. import java.util.Iterator;
  4.  
  5. public class TestGraph {
  6.  
  7.     public static void main(String[] args) {
  8.         /* Eulerian Path Example */
  9.         Graph g = new Graph(5);
  10.  
  11.         System.out.println("Graph:");
  12.         // add Edges
  13.         g.addEdge(0, 1);
  14.         g.addEdge(0, 2);
  15.         g.addEdge(0, 3);
  16.         g.addEdge(1, 2);
  17.         g.addEdge(3, 4);
  18.  
  19.         // print Graph
  20.         g.printGraph();
  21.  
  22.         // Eulerian Circuit Algorithm
  23.         eulerianCircuit(g);
  24.        
  25.         /* Eulerian Cycle Example */
  26.         Graph g1 = new Graph(5);
  27.  
  28.         System.out.println("\nGraph:");
  29.         // add Edges
  30.         g1.addEdge(0, 1);
  31.         g1.addEdge(0, 2);
  32.         g1.addEdge(0, 3);
  33.         g1.addEdge(1, 2);
  34.         g1.addEdge(3, 4);
  35.         g1.addEdge(4, 0); // I simply added one Edge
  36.  
  37.         // print Graph
  38.         g1.printGraph();
  39.  
  40.         // Eulerian Circuit Algorithm
  41.         eulerianCircuit(g1);
  42.     }
  43.    
  44.     // test function the main one is isEulerian()
  45.     static void eulerianCircuit(Graph g) {
  46.         int result = isEulerian(g);
  47.         if (result == 0)
  48.             System.out.println("Graph is not Eulerian");
  49.         else if (result == 1)
  50.             System.out.println("Graph contains a Euler path");
  51.         else // 2
  52.             System.out.println("Graph contains a Euler cycle");
  53.     }
  54.  
  55.     // returns 0: not eulerian, 1: euler path, 2: euler cycle
  56.     static int isEulerian(Graph g) {
  57.         // Check if all non-zero degree vertices are connected
  58.         if (isConnected(g) == false)
  59.             return 0;
  60.  
  61.         // Count vertices with odd degree
  62.         int odd = 0;
  63.         for (int i = 0; i < g.getvCount(); i++)
  64.             // check number of neighbours or degree
  65.             if (g.neighbours(i).size() % 2 != 0)
  66.                 odd++;
  67.  
  68.         // Check number of odd vertices
  69.         if (odd > 2) { // non-eulerian
  70.             return 0;
  71.         } else if (odd == 2) { // semi-eulerian
  72.             return 1;
  73.         } else { // eulerian
  74.             return 2;
  75.         }
  76.     }
  77.  
  78.     static boolean isConnected(Graph g) {
  79.         // array to store if vertices where visited
  80.         boolean visited[] = new boolean[g.getvCount()];
  81.        
  82.         // initialze all to non-visited
  83.         int i;
  84.         for (i = 0; i < g.getvCount(); i++) {
  85.             visited[i] = false;
  86.         }
  87.        
  88.         // Find vertex with non-zero degree
  89.         for (i = 0; i < g.getvCount(); i++) {
  90.             if (g.neighbours(i).size() != 0)
  91.                 break;
  92.         }
  93.        
  94.         // If there are no edges in the graph (special case) then return true
  95.         if (i == g.getvCount())
  96.             return true;
  97.  
  98.         // DFS Traversal starting from non-zero vertex
  99.         DFS(g, i, visited);
  100.  
  101.         // Check if all non-zero degree vertices are visited
  102.         for (i = 0; i < g.getvCount(); i++)
  103.             if (visited[i] == false && g.neighbours(i).size() > 0)
  104.                 return false;
  105.         // if at least one was not visited false, else we return true
  106.         return true;
  107.     }
  108.    
  109.     static void DFS(Graph g, int sourceVertex, boolean visited[]){
  110.         // Mark source node as visited
  111.         visited[sourceVertex] = true;
  112.  
  113.         // recursion for all the vertices adjacent to this one
  114.         Iterator<Integer> it = g.neighbours(sourceVertex).iterator();
  115.         while (it.hasNext())
  116.         {
  117.             int nextVertex = it.next();
  118.             if (!visited[nextVertex])
  119.                 DFS(g, nextVertex, visited);
  120.         }
  121.     }
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement