Contents [0/1] |
Homework [1/1] |
(Click here for one slide per page)
Homework [1/1] |
Read Algorithms Section 4.4 (Shortest Paths)
Read Algorithms Section 5.1 (String Sorts) - we will cover this during the makeup class on Zoom, so make this lower priority
Read Algorithms Section 5.2 (Tries) - we will cover this during the makeup class on Zoom, so make this lower priority
Read Algorithms Section 5.5 (Data Compression) - we will cover this during week 10
Deadline extended Due Wednesday, March 6 before 5:45 PM: (hw7) Written Homework: Minimum Spanning Trees
Quiz 7 Due Wednesday, March 6 before 5:45 PM
Written Homework: Shortest Paths (hw8a) - Due Sunday, March 10 before 11:59 PM
Answer the following questions from the text:
4.4.5
4.4.6
4.4.13
4.4.21
Programming: algs42.MyDegrees
(hw8b) and algs42.MyEuler
(hw8c) Due Tuesday, March 12 before 5:45 PM
For homework, complete the following two problems, using only Digraph.java from algs42. You may copy code from other classes in algs42, but you should not use the classes themselves.
(1) The indegree of a vertex in a digraph is the number of directed edges that point to that vertex. The outdegree of a vertex in a digraph is the number of directed edges that emanate from that vertex. A vertex with outdegree 0 is called a sink. A vertex with indegree 0 is called a source. A digraph where every vertex has outdegree 1 is a map (self loops are allowed). (A digraph that is a map can be seen as a function from 0..V-1 to 0..V-1.)
Write a class called MyDegrees.java that implements the following API:
public class MyDegrees { // constructor MyDegrees(Digraph G) {} // indegree of v int indegree(int v) { return 0; } // outdegree of v int outdegree(int v) { return 0; } // sources Iterable<Integer> sources() { return null; } // sinks Iterable<Integer> sinks() { return null; } // is G a map? boolean isMap() { return false; } }
(2) A directed Eulerian cycle is a directed cycle that contains each edge exactly once.
Write a class MyEuler that finds a directed Eulerian cycle or reports that no such cycle exists. Your class should implement the following API:
public class MyEuler { // constructor MyEuler(Digraph G) {} // does G have a directed Eulerian cycle? boolean isEulerian () { return false; } // return a Eulerian cycle (null if the graph is not eulerian) Iterable<Integer> tour () { return null; } }
Note that for a digraph G to have a directed Eulerian cycle it must be the case that each vertex has indegree equal to its outdegree. In addition, all the edges must be connected, but not necessarily all of the nodes. If the graph has no edges then it is Eularian, and the tour is empty -- not null, but an empty Iterable.
As a first step towards solving this problem, rewrite DFS without using recursion, but instead using an explicit stack. (The code is very similar to the code for BFS, but with a stack replacing the queue.)
As a second step, adapt your stack-based dfs to use a local copy of the adjacency lists, rather than calling G each time. That is, add the field adj:
public class MyEuler { private final Queue<Integer>[] adj; private int E; @SuppressWarnings("unchecked") // annoying java generic/array stuff MyEuler(Digraph G) { // create local copy of graph adj = new Queue[G.V()]; for (int v = 0; v < G.V(); v++) { adj[v] = new Queue<Integer>(); for (int w : G.adj(v)) adj[v].enqueue(w); } // get initial number of edges E = G.E (); // TODO ... } }
Modify your stack-based dfs so that it dequeues each edge from adj as it goes.
As a final step, consider the problem of repeatedly finding cycles in G. You must first find a node s that has at least one edge. Start your search with s.
The easiest way to write the code is to repeatedly do the following:
Here is a main program to generate random graphs for testing:
public static void main(String[] args) { //args = new String[] { "data/tinyDG.txt" }; // NO args = new String[] { "data/tinyDGeuler1.txt" }; // YES //args = new String[] { "data/tinyDGeuler2.txt" }; // YES //args = new String[] { "data/tinyDGeuler3.txt" }; // YES //args = new String[] { "data/tinyDGeuler4.txt" }; // YES //args = new String[] { "data/tinyDGeuler5.txt" }; // NO //args = new String[] { "data/tinyDGeuler6.txt" }; // YES //args = new String[] { "10", "20" }; Digraph G; if (args.length == 1) { final In in = new In(args[0]); G = new Digraph(in); } else { final int V = Integer.parseInt(args[0]); final int E = Integer.parseInt(args[1]); // random graph of V vertices and approximately E edges // with indegree[v] = outdegree[v] for all vertices G = new Digraph(V); final int[] indegree = new int[V]; final int[] outdegree = new int[V]; int deficit = 0; for (int i = 0; i < E - deficit/2; i++) { final int v = StdRandom.uniform(V); final int w = StdRandom.uniform(V); if (v == w) { i--; continue; } G.addEdge(v, w); if (outdegree[v] >= indegree[v]) deficit++; else deficit--; outdegree[v]++; if (indegree[w] >= outdegree[w]) deficit++; else deficit--; indegree[w]++; } while (deficit > 0) { final int v = StdRandom.uniform(V); final int w = StdRandom.uniform(V); if (v == w) continue; if (outdegree[v] >= indegree[v]) continue; if (indegree[w] >= outdegree[w]) continue; G.addEdge(v, w); if (outdegree[v] >= indegree[v]) deficit++; else deficit--; outdegree[v]++; if (indegree[w] >= outdegree[w]) deficit++; else deficit--; indegree[w]++; } } StdOut.println(G); final MyEuler euler = new MyEuler(G); if (euler.isEulerian()) { for (final int v : euler.tour()) { StdOut.print(v + " "); } StdOut.println(); } else { StdOut.println("Not eulerian"); } }