Select a Chapter: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Back to the Main Page | ||
Chapter Nineteen listings: 14 classes |
public class HamGraph extends ListGraph { /** Create a graph on n vertices with at least 1.5 * n * randomly chosen edges, but the graph cannot be connected * (it must have at least two components). */ public void createUnConnectedGraph (int n) { this.clear(); this.addVertex (new Vertex (n, null)); for (int k = 1; k < 1.5 * this.getNumVertices(); k++) this.addEdgeChosenRandomly(); if (this.isConnected()) this.createUnConnectedGraph (n); } //================================================ /** Add 1 randomly chosen edge at a time until this graph * becomes connected. */ public void makeTheGraphConnected() { while ( ! isConnected()) addEdgeChosenRandomly(); } //================================================ /** Tell whether this graph is connected. STUBBED*/ public boolean isConnected() { return false; } //================================================ /** Add a randomly chosen edge not already in the graph. */ private void addEdgeChosenRandomly() { int one = 1 + (int) (Math.random() * getNumVertices()); int two = 1 + (int) (Math.random() * getNumVertices()); Edge e = new Edge (getVertex (one), getVertex (two)); if (this.contains (e)) addEdgeChosenRandomly(); else { this.add (e); this.add (new Edge (getVertex (two), getVertex (one))); // in the opposite direction, for an undirected graph } } //================================================ }
import java.util.ArrayList; import java.util.Iterator; public abstract class Graph { private ArrayList itsVertices = new ArrayList(); /** Create a graph with zero vertices and zero edges. The * vertices always have ids ranging 1...getNumVertices(). */ public Graph() { super(); // to remind you of the default constructor } //================================================ /** Return the current number of vertices. */ public final int getNumVertices() { return itsVertices.size(); } //================================================ /** Return the Vertex object for the given id. Throw a * RuntimeException if the id is not 1...getNumVertices(). */ public final Vertex getVertex (int id) { return (Vertex) itsVertices.get (id - 1); } //================================================ /** Return an iteration over all Vertex objects. */ public final Iterator vertices() { return itsVertices.iterator(); } //================================================ /** Add the given vertex to the graph if it has no vertex with * the same id number; ignore non-positive ids. Add vertices * as needed for all positive ints below id, with null data. * Throw a RuntimeException if the given vertex is null. */ public void addVertex (Vertex v) { if (v.ID > itsVertices.size()) { for (int k = itsVertices.size() + 1; k < v.ID; k++) itsVertices.add (new Vertex (k, null)); itsVertices.add (v); // added at the end of the list } } //================================================ /** Remove all edges from the Graph. Leave the vertices. */ public abstract void clear(); /** The following methods throw a RuntimeException if the * parameter is null or its vertex ids are not in the range * 1...getNumVertices(), except they may simply ignore 0. * Do not use a Graph iterator to remove anything. */ /** Tell whether this graph contains the given Edge. */ public abstract boolean contains (Edge given); /** Remove the given Edge if it is in there and return true. * But if the Edge is not in there, simply return false. */ public abstract boolean remove (Edge given); /** Add the given Edge if it is not in there and return true. * But if the Edge is in there, simply return false. */ public abstract void add (Edge given); /** Return an iteration over all edges that exit Vertex v. */ public abstract Iterator edgesFrom (Vertex v); /** Return the number of Edges that end at that Vertex. */ public abstract int inDegree (Vertex given); /** Return the number of Edges that start at that Vertex. */ public int outDegree (Vertex given) { Iterator it = edgesFrom (given); int count = 0; while (it.hasNext()) { it.next(); count++; } return count; } //================================================ }
public class Vertex extends GraphPart { public final int ID; public final Object DATA; public Vertex (int id, Object data) { ID = id; DATA = data; } //================================================ } //##################################################### public class GraphPart { private int itsMark = 0; public final int getMark() { return itsMark; } //================================================ public final void setMark (int given) { itsMark = given; } //================================================ } //##################################################### public class Edge extends GraphPart { public final Vertex TAIL; // vertex where it begins public final Vertex HEAD; // vertex where it ends public final double WEIGHT; public Edge (Vertex from, Vertex to) { TAIL = from; HEAD = to; WEIGHT = 1; } //================================================ public boolean equals (Object ob) { return ob instanceof Edge && this.HEAD == ((Edge) ob).HEAD && this.TAIL == ((Edge) ob).TAIL; } //================================================ public Edge (Vertex from, Vertex to, double weight) { TAIL = from; HEAD = to; WEIGHT = weight > 0.0 ? weight : 1.0; } //================================================ }
public class MatrixGraph extends Graph { private Edge[][] edgeAt; private int[] itsIns; /** Specify the maximum number of vertices the graph can have. * This number cannot be changed by later method calls. */ public MatrixGraph (int maxVerts) { super(); edgeAt = new Edge[maxVerts + 1][maxVerts + 1]; // all null itsIns = new int[maxVerts + 1]; } //================================================ public final void addVertex (Vertex v) { if (v.ID >= edgeAt.length) throw new IllegalArgumentException ("not with matrix"); super.addVertex (v); } //================================================ public final void clear() { int maxVerts = edgeAt.length; edgeAt = new Edge[maxVerts + 1][maxVerts + 1]; // all null } //================================================ public final boolean contains (Edge given) { return edgeAt[given.TAIL.ID][given.HEAD.ID] != null; } //================================================ public final boolean remove (Edge given) { Edge e = edgeAt[given.TAIL.ID][given.HEAD.ID]; edgeAt[given.TAIL.ID][given.HEAD.ID] = null; if (e != null) itsIns[given.HEAD.ID]--; return e != null; } //================================================ public final void add (Edge given) { if (edgeAt[given.TAIL.ID][given.HEAD.ID] == null) itsIns[given.HEAD.ID]++; edgeAt[given.TAIL.ID][given.HEAD.ID] = given; } //================================================ public final java.util.Iterator edgesFrom (Vertex v) { ArrayList list = new ArrayList(); for (int k = 1; k <= getNumVertices(); k++) { if (edgeAt[v.ID][k] != null) list.add (edgeAt[v.ID][k]); } return list.iterator(); } } //================================================ public int inDegree (Vertex given) { return itsIns[given.ID]; } //================================================ public int outDegree (Vertex given) // in MatrixGraph { int count = 0; for (int k = 1; k <= getNumVertices(); k++) { if (edgeAt[given.ID][k] != null) count++; } return count; } //=========================================== public boolean hasTwoWayEdge (Vertex given) // in MatrixGraph { for (int k = 1; k <= getNumVertices(); k++) { if (edgeAt[given.ID][k] != null && edgeAt[k][given.ID] != null) return true; } return false; } //=========================================== }
import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; public class ListGraph extends Graph { private ArrayList itsList = new ArrayList(); public ListGraph() { super(); itsList.add (null); // we do not use the value at index 0 } //================================================ public final void addVertex (Vertex v) { super.addVertex (v); if (v.ID >= itsList.size()) { for (int k = itsList.size(); k <= v.ID; k++) itsList.add (new ArrayList()); } } //================================================ /** Remove all edges from the graph, but not the vertices. */ public final void clear() { for (int k = 1; k <= getNumVertices(); k++) itsList.set (k, new ArrayList()); } //================================================ public final boolean contains (Edge given) { return ((Collection) itsList.get (given.TAIL.ID)) .contains (given); } //================================================ public final boolean remove (Edge given) { return ((Collection) itsList.get (given.TAIL.ID)) .remove (given); } //================================================ public final void add (Edge given) { if (given.HEAD.ID < 1 || given.HEAD.ID > getNumVertices()) throw new IllegalArgumentException ("bad vertex"); Collection z = (Collection) itsList.get (given.TAIL.ID); if (z.contains (given)) z.remove (given); z.add (given); } //================================================ public final Iterator edgesFrom (Vertex v) { return ((Collection) itsList.get (v.ID)).iterator(); } //================================================ public int inDegree (Vertex given) { int count = 0; for (int k = 1; k <= getNumVertices(); k++) { if (contains (new Edge (getVertex (k), given))) count++; } return count; } //================================================ public int outDegree (Vertex given) // for ListGraph { return ((Collection) itsList.get (given.ID)).size(); } //================================================ }
public class GraphStuff extends ListGraph // for instance { private void getStarters (QueueADT toCheck) { Iterator verts = vertices(); while (verts.hasNext()) { Vertex v = (Vertex) verts.next(); int numPredecessors = inDegree (v); if (numPredecessors == 0) toCheck.enqueue (v); else v.setMark (numPredecessors); } } //=========================================== private void sort (QueueADT toCheck, QueueADT sorted) { getStarters (toCheck); while ( ! toCheck.isEmpty()) // once per Vertex { Vertex ok = (Vertex) toCheck.dequeue(); sorted.enqueue (ok); Iterator edges = edgesFrom (ok); while (edges.hasNext()) { Vertex v = ((Edge) edges.next()).HEAD; v.setMark (v.getMark() - 1); if (v.getMark() == 0) toCheck.enqueue (v); } } } //=========================================== /** Mark 1 on each vertex reachable from the given Vertex. */ private void markReachables (Vertex given) { given.setMark (1); //1 Iterator it = edgesFrom (given); //2 while (it.hasNext()) //3 { Vertex v = ((Edge) it.next()).HEAD; //4 if (v.getMark() == 0) //5 markReachables (v); //6 } //7 } //================================================ /** Tell whether you can reach each vertex from vertex #1. */ public boolean isConnected() { markReachables (getVertex (1)); //8 Iterator it = vertices(); //9 int count = 0; //10 while (it.hasNext()) //11 { Vertex v = (Vertex) it.next(); //12 if (v.getMark() == 1) //13 { count++; //14 v.setMark (0); //15 } //16 } //17 return count == getNumVertices(); //18 } //================================================ /** Find a path from given through all unmarked vertices and * mark each vertex with its sequence number in that path. */ private boolean solveSalesman (Vertex given, int seqNum) { given.setMark (seqNum); //19 if (seqNum == getNumVertices()) //20 return true; //21 Iterator it = edgesFrom (given); //22 while (it.hasNext()) //23 { Vertex v = ((Edge) it.next()).HEAD; //24 if (v.getMark() == 0) //25 { if (solveSalesman (v, seqNum + 1)) //26 return true; //27 } //28 } //29 given.setMark (0); //30 return false; //31 } //=========================================== private void markDistance (Vertex given, QueueADT queue) { given.setMark (1); queue.enqueue (given); while (! queue.isEmpty()) { Vertex current = (Vertex) queue.dequeue(); Iterator it = this.edgesFrom (current); while (it.hasNext()) { Vertex v = ((Edge) it.next()).HEAD; if (v.getMark() == 0) { v.setMark (current.getMark() + 1); queue.enqueue (v); } } } } //=========================================== public double averageWeight (Vertex given) { Iterator it = edgesFrom (given); double total = ((Edge) it.next()).WEIGHT; int count = 1; while (it.hasNext()) { total += ((Edge) it.next()).WEIGHT; count++; } return total / count; } //================================================ // KRUSKAL'S ALGORITHM /** Return a stack containing the edges on an MST for an * undirected graph. If the graph is not connected, the * edges should form one MST for each connected part. */ public StackADT Kruskals() { StackADT spanner = new NodeStack(); //1 PriQue queue = new TreePriQue (new ByWeight()); //2 putEdgesOnPriorityQueueByWeight (queue); //3 constructMST (spanner, queue, getNumVertices()); //4 return spanner; //5 } //================================================ /** Put all Edges of the Graph on the priority queue with * lighter Edges having higher priority. * Precondition: the queue is not null. */ private void putEdgesOnPriorityQueueByWeight (PriQue queue) { Iterator it = vertices(); //6 while (it.hasNext()) //7 { Iterator edges = edgesFrom ((Vertex) it.next()); //8 while (edges.hasNext()) //9 { Edge e = (Edge) edges.next(); //10 if (e.TAIL.ID < e.HEAD.ID) //11 queue.add (e); //12 } //13 } //14 } //================================================ /** Check each Edge in order from lightest to heaviest. Put * the Edge in spanner whenever its two endpoints do not * have a path between them using Edges already in spanner. * Precondition: spanner and queue are not null. */ private static void constructMST (StackADT spanner, PriQue queue, int numLeft) { UnionFind group = new UnionFind (numLeft + 1); //15 while (! queue.isEmpty() && numLeft > 1) //16 { Edge e = (Edge) queue.removeMin(); //17 if (! group.equates (e.TAIL.ID, e.HEAD.ID)) //18 { spanner.push (e); //19 group.unite (e.TAIL.ID, e.HEAD.ID); //20 numLeft--; //21 } //22 } //23 } //================================================ private static class ByWeight implements java.util.Comparator { public boolean prior (Object one, Object two) { double diff = ((Edge) one).WEIGHT - ((Edge) two).WEIGHT; return diff > 0 ? 1 : diff < 0 ? -1 : 0; //25 } } //================================================ // DIJKSTRA'S ALGORITHM /** Return an array of doubles in which the kth component is * the minimum distance from the given vertex to vertex #k. * A component value of 0.0 means it is not reachable. */ public double[] Dijkstras (Vertex start) { ArrayList fringe = new ArrayList(); //1 double[] dist = new double [getNumVertices() + 1]; //2 updateFringe (start, fringe, dist); //3 dist[start.ID] = -1.0; //4 while (! fringe.isEmpty()) //5 { Vertex best = findClosest (fringe, dist); //6 updateFringe (best, fringe, dist); //7 } //8 return dist; //9 } //================================================ /** Add to the fringe each vertex reachable from vert but * not previously processed. Update the shortest distance * array for any vertex that is reachable from vert. */ private void updateFringe (Vertex vert, ArrayList fringe, double[] dist) { Iterator it = edgesFrom (vert); //10 while (it.hasNext()) //11 { Edge e = (Edge) it.next(); //12 double newDist = dist[vert.ID] + e.WEIGHT; //13 if (dist[e.HEAD.ID] == 0.00) //not on fringe list//14 { dist[e.HEAD.ID] = newDist; //15 fringe.add (e.HEAD); // add to list //16 } //17 else if (newDist < dist[e.HEAD.ID]) //18 dist[e.HEAD.ID] = newDist; //19 } //20 } //================================================ /** Find and return the vertex in the fringe that has the * smallest dist value, after removing it from the fringe. */ private Vertex findClosest (ArrayList fringe, double[] dist) { Vertex best = (Vertex) fringe.get (0); //21 int indexBest = 0; //22 for (int k = 1; k < fringe.size(); k++) //23 { Vertex v = (Vertex) fringe.get (k); //24 if (dist[v.ID] < dist[best.ID]) //25 { best = v; //26 indexBest = k; //27 } //28 } //29 fringe.remove (indexBest); //30 return best; //31 } //================================================ }
public class UnionFind_0 // simple array implementation { private final int itsLength; private int[] itsItem; /** Create a partition of the int values 0...numValues-1, * initially with each int in its own 1-element group. Use * 1 in place of numValues if numValues is not positive. */ public UnionFind_0 (int numValues) { itsLength = numValues > 0 ? numValues : 1; itsItem = new int[itsLength]; for (int k = 0; k < itsLength; k++) itsItem[k] = k; } //================================================ /** Tell whether one and two are in the same group. */ public boolean equates (int one, int two) { return one >= 0 && one < itsLength && two >= 0 && two < itsLength && itsItem[one] == itsItem[two]; } //================================================ /** Assure that one and two are in the same group. * No effect if one or two is not in 0...numValues-1. */ public void unite (int one, int two) { if (one >= 0 && one < itsLength && two >= 0 && two < itsLength && itsItem[one] != itsItem[two]) { for (int k = 0; k < itsLength; k++) { if (itsItem[k] == itsItem[two]) itsItem[k] = itsItem[one]; } } } //=========================================== }
public class UnionFind // Queue of Nodes implementation { private final int itsLength; private Queue[] itsItem; // Queue is a nested class // equates is unchanged. The constructor is an exercise. /** Assure that one and two are in the same group. * No effect if one or two is not in 0...numValues-1. */ public void unite (int one, int two) { if (one >= 0 && one < itsLength && two >= 0 && two < itsLength && itsItem[one] != itsItem[two]) { if (itsItem[one].itsSize >= itsItem[two].itsSize) combineQueues (itsItem[one], itsItem[two]); else // swap the order so the larger is first combineQueues (itsItem[two], itsItem[one]); } } //=========================================== private void combineQueues (Queue first, Queue second) { first.itsRear.itsNext = second.itsFront; first.itsRear = second.itsRear; first.itsSize += second.itsSize; for (Node p = second.itsFront; p != null; p = p.itsNext) itsItem[p.itsData] = first; } //=========================================== /** Tell whether one and two are in the same group. */ public boolean equates (int one, int two) { return one >= 0 && one < itsLength && two >= 0 && two < itsLength && itsItem[one] == itsItem[two]; } //================================================ private static class Queue { public Node itsFront; public Node itsRear; public int itsSize; public Queue (int given) { itsFront = new Node (given, null); itsRear = itsFront; itsSize = 1; } } //=========================================== private static class Node { public int itsData; public Node itsNext; public Node (int data, Node next) { itsData = data; itsNext = next; } } //=========================================== public UnionFind (int numValues) { itsLength = numValues > 0 ? numValues : 1; itsItem = new Queue[itsLength]; for (int k = 0; k < itsLength; k++) itsItem[k] = new Queue (k); } //=========================================== }
public class Fibonacci { public static final int MAX = 10000; private static int[] answer = new int[MAX]; /** Return the nth Fibonacci number, where fib(0) = 1 and * fib(1) = 1 and otherwise fib(n) = fib(n-2) + fib(n-1). * But return 1 if n >= MAX. */ public static int fib (int n) { if (n <= 1 || n >= MAX) return 1; if (answer[n] == 0) // the first request for this value answer[n] = fib (n - 2) + fib (n - 1); return answer[n]; } //================================================ }
public class MergeCount { public static final int MAX = 10000; private static int[] answer = new int[MAX]; /** Return the nth compsMS number, which is the maximum * number of comparisons required to sort n values using * the merge sort logic. But return 0 if n >= MAX. */ public static int compsMS (int n) { if (n <= 1 || n >= MAX) return 0; if (answer[n] == 0) // the first request for this value answer[n] = compsMS (n / 2) + compsMS (n - n / 2) + n - 1; return answer[n]; } //================================================ }
public class TreeCount { public static final int MAX = 10000; private static int[] answer = new int[MAX]; /** Return the nth trees number, which is the number of * different binary trees. But return n if n >= MAX. */ public static int trees (int n) { if (n <= 2 || n >= MAX) return n; if (answer[n] == 0) // the first request for this value { int total = trees (n - 1); for (int k = 2; k <= n / 2; k++) total += trees (k - 1) * trees (n - k); answer[n] = (n % 2 == 0) ? 2 * total : 2 * total + trees (n / 2) * trees (n / 2); } return answer[n]; } //================================================ }
public class LongestCommonSubsequence { public static final int MAX = 1000; private static int[][] answer = new int[MAX][MAX]; private static String one; private static String two; /** Return the length of the longest common subsequence of * the two given Strings. Return 0 if either is null or * has MAX or more characters. */ public static int longest (String first, String second) { if (first == null || second == null || first.length() >= MAX || second.length() >= MAX) return 0; for (int row = 0; row <= first.length(); row++) { for (int col = 0; col <= second.length(); col++) answer[row][col] = row * col == 0 ? 0 : -1; } one = first; two = second; return longest (one.length(), two.length()); } //================================================ private static int longest (int len1, int len2) { if (answer[len1][len2] >= 0) return answer[len1][len2]; if (one.charAt (len1 - 1) == two.charAt (len2 - 1)) answer[len1][len2] = longest (len1 - 1, len2 - 1) + 1; else answer[len1][len2] = Math.max (longest (len1 - 1, len2), longest (len1, len2 - 1)); return answer[len1][len2]; } //================================================ /** Return the length of the LCS of the first len1 characters * of the first String and the first len2 characters of the * second String. Throw an Exception for bad indexes. */ public static int lcs (int len1, int len2) { return answer[len1][len2]; } //================================================ private static int longest_0 (int len1, int len2) { for (int row = 1; row <= len1; row++) for (int col = 1; col <= len2; col++) { if (one.charAt (row - 1) == two.charAt (col - 1)) answer[row][col] = answer[row - 1][col - 1] + 1; else if (answer[row - 1][col] > answer[row][col - 1]) answer[row][col] = answer[row - 1][col]; else answer[row][col] = answer[row][col - 1]; } return answer[len1][len2]; } //================================================ } |
Layout and Design Copyright © Psumonix, LLC. All Rights Reserved. |