2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Back to the Main Page
|
||
|
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. |