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}