001package algs42; 002 003import java.util.Iterator; 004import java.util.LinkedList; 005import algs13.Queue; 006import stdlib.*; 007 008public class MyEuler { 009 // local copy of the graph 010 private Queue<Integer>[] adj; 011 private int E; 012 private boolean isEulerian = true; 013 014 @SuppressWarnings("unchecked") 015 public MyEuler(Digraph G) { 016 // create local copy of graph 017 adj = new Queue[G.V()]; 018 for (int v = 0; v < G.V(); v++) { 019 adj[v] = new Queue<>(); 020 for (int w : G.adj(v)) 021 adj[v].enqueue(w); 022 } 023 // get initial number of edges 024 E = G.E (); 025 if (E == 0) { 026 isEulerian = true; 027 return; 028 } 029 // find starting vertex with at least one edge 030 int s = 0; 031 while (adj[s].isEmpty ()) 032 s++; 033 034 // TODO 035 } 036 public Iterable<Integer> tour() { 037 // TODO 038 return null; 039 } 040 public boolean isEulerian() { 041 return isEulerian; 042 } 043 044 public static boolean isTour(Digraph G, Iterable<Integer> tour) { 045 @SuppressWarnings("unchecked") 046 LinkedList<Integer>[] adj = new LinkedList[G.V()]; 047 int E = G.E (); 048 for (int v = 0; v < G.V(); v++) { 049 adj[v] = new LinkedList<>(); 050 for (int w : G.adj(v)) 051 adj[v].add(w); 052 } 053 if (tour == null) 054 return E == 0; 055 Iterator<Integer> it = tour.iterator (); 056 if (!it.hasNext()) 057 return E == 0; 058 int s = it.next(); 059 int v = s; 060 while (it.hasNext()) { 061 int w = it.next(); 062 if (adj[v].contains(w)) { 063 adj[v].remove((Integer) w); 064 E--; 065 v = w; 066 } else { 067 throw new Error(); 068 } 069 } 070 if (v != s) throw new Error(); 071 if (E != 0) throw new Error(); 072 return (v == s) && (E == 0); 073 } 074 075 public static Digraph inOutEqual (int V, int E) { 076 // random graph of V vertices and approximately E edges 077 // with indegree[v] = outdegree[v] for all vertices 078 Digraph G = new Digraph(V); 079 int[] indegree = new int[V]; 080 int[] outdegree = new int[V]; 081 int deficit = 0; 082 for (int i = 0; i < E - deficit/2; i++) { 083 int v = StdRandom.uniform(V); 084 int w = StdRandom.uniform(V); 085 if (v == w) { i--; continue; } 086 G.addEdge(v, w); 087 if (outdegree[v] >= indegree[v]) deficit++; 088 else deficit--; 089 outdegree[v]++; 090 if (indegree[w] >= outdegree[w]) deficit++; 091 else deficit--; 092 indegree[w]++; 093 } 094 while (deficit > 0) { 095 int v = StdRandom.uniform(V); 096 int w = StdRandom.uniform(V); 097 if (v == w) continue; 098 if (outdegree[v] >= indegree[v]) continue; 099 if (indegree[w] >= outdegree[w]) continue; 100 G.addEdge(v, w); 101 if (outdegree[v] >= indegree[v]) deficit++; 102 else deficit--; 103 outdegree[v]++; 104 if (indegree[w] >= outdegree[w]) deficit++; 105 else deficit--; 106 indegree[w]++; 107 } 108 return G; 109 } 110 public static void main(String[] args) { 111 //args = new String[] { "data/tinyDG.txt" }; // NO 112 //args = new String[] { "data/tinyCG.txt" }; // NO 113 //args = new String[] { "data/tinyDGeuler9.txt" }; // YES 114 //args = new String[] { "data/tinyDGeuler2.txt" }; // YES 115 //args = new String[] { "data/tinyDGeuler3.txt" }; // YES 116 //args = new String[] { "data/tinyDGeuler4.txt" }; // YES 117 //args = new String[] { "data/tinyDGeuler5.txt" }; // NO 118 //args = new String[] { "data/tinyDGeuler6.txt" }; // YES 119 //args = new String[] { "data/tinyDGeuler7.txt" }; // NO 120 //args = new String[] { "data/tinyDGeuler8.txt" }; // YES 121 //args = new String[] { "data/tinyDGeuler9.txt" }; // YES 122 args = new String[] { "20", "40" }; 123 124 Digraph G; 125 if (args.length == 1) { 126 In in = new In(args[0]); 127 G = DigraphGenerator.fromIn(in); 128 } else { 129 int V = Integer.parseInt(args[0]); 130 int E = Integer.parseInt(args[1]); 131 while (true) { 132 G = inOutEqual(V,E); 133 if (new KosarajuSharirSCC(G).count () == 1) 134 break; 135 } 136 } 137 StdOut.println(G); 138 YEuler euler0 = new YEuler(G, 1); 139 if (euler0.isEulerian()) { 140 for (int v : euler0.tour()) 141 StdOut.print(v + " "); 142 StdOut.println(); 143 } else { 144 StdOut.println("Not eulerian"); 145 } 146 if (!isTour(G,euler0.tour())) StdOut.println("Not a tour"); 147 YEuler euler1 = new YEuler(G, 2); 148 if (euler1.isEulerian()) { 149 for (int v : euler1.tour()) 150 StdOut.print(v + " "); 151 StdOut.println(); 152 } else { 153 StdOut.println("Not eulerian"); 154 } 155 if (!isTour(G,euler1.tour())) StdOut.println("Not a tour"); 156 } 157}