Question: java question: /* * Graphs.java * * driver program for LinkedGraph.java */ public class Graphs { public static void main (String [] args) { LinkedGraph
java question:
/*
* Graphs.java
*
* driver program for LinkedGraph.java
*/
public class Graphs
{
public static void main (String [] args)
{
LinkedGraph
String [] bostonTowns = {"Somerville", "Natick", "Concord",
"Brookline"};
for (int i = 0; i
{
cities.add("Boston", bostonTowns[i]);
}
String [] northOfBostonTowns = {"Beverly", "Peabody"};
for (int i = 0; i
{
cities.add("Andover", northOfBostonTowns[i]);
}
String [] southOfBostonTowns = {"Norfolk", "Fall River", "Foxboro"};
for (int i = 0; i
{
cities.add("Bridgewater", southOfBostonTowns[i]);
}
System.out.println(" Here are the cities in the graph and some towns "
+ "in their region " + cities);
System.out.println(" Is Boston in the graph? " +
(cities.contains("Boston") ? "yes" : "no"));
System.out.println("Is Worcester in the graph? " +
(cities.contains("Worcester") ? "yes" : "no"));
System.out.println(" Here are the cities near Boston: " +
cities.getNeighbors("Boston"));
System.out.println("Here are the cities near Andover: " +
cities.getNeighbors("Andover"));
String result = cities.containsNeighbor("Boston", "Natick") ? "yes"
: "no";
System.out.println(" Is Natick a neighbor of Boston? " + result);
result = cities.containsNeighbor("Boston", "Foxboro") ? "yes" : "no";
System.out.println("Is Foxboro a neighbor of Boston? " + result);
System.out.println(" Removing Andover from the graph");
System.out.println("neighbors returned: " + cities.remove("Andover"));
System.out.println(cities);
System.out.println(" Removing Boston from the graph");
System.out.println("neighbors returned: " + cities.remove("Boston"));
System.out.println(cities);
System.out.println(" Removing Bridgewater from the graph");
System.out.println("neighbors returned: " +
cities.remove("Bridgewater"));
System.out.println(cities);
System.out.println(" Trying to remove Boston again");
System.out.println("neighbors returned: " + cities.remove("Boston"));
System.out.println(cities);
}
}
/*
* Heap.java
*
* class for creating a maxheap
*/
public class Heap
{
public static final int DEFAULT_CAPACITY = 10;
private T [] collection;
private int size;
public Heap()
{
this(DEFAULT_CAPACITY);
}
@SuppressWarnings("unchecked")
public Heap(int capacity)
{
if (capacity
{
throw new IllegalArgumentException("size must be positive!");
}
collection = (T []) new Comparable [capacity];
size = 0;
}
/*
* converts an array to a heap
*/
public Heap(T [] array)
{
collection = array;
size = array.length;
int parent = (size-2) / 2;
for (int i = parent; i >= 0; i--)
{
siftDown(i);
}
}
public void add (T item)
{
ensureSpace();
collection[size] = item;
size++;
siftUp(size-1);
}
public T remove ()
{
if (size == 0)
{
return null;
}
T removed = collection[0];
collection[0] = collection[size-1];
collection[size-1] = null;
size--;
siftDown(0);
return removed;
}
public T get()
{
if (size == 0)
{
return null;
}
return collection[0];
}
public int size()
{
return size;
}
public String toString()
{
if (size == 0)
{
return "[ ]";
}
String s = "[";
for (int i = 0; i
{
s+= collection[i] + ", ";
}
return s += collection[size-1] + "]";
}
/* helper methods */
private void ensureSpace()
{
if (size == collection.length)
{
@SuppressWarnings("unchecked")
T [] larger = (T []) new Comparable [size * 2];
for (int i = 0; i
{
larger[i] = collection[i];
}
collection = larger;
larger = null;
}
}
private void siftUp(int i)
{
T item;
int child = i;
int parent = ((i - 1)/2);
while (collection[child].compareTo(collection[parent]) > 0 &&
child >= 0)
{
item = collection[child];
collection[child] = collection[parent];
collection[parent] = item;
child = parent;
parent = ((i - 1)/2);
}
}
private void siftDown(int i)
{
int parent = i;
int left = 2 * parent + 1;
int right = 2 * parent + 2;
int larger = 0;
while (left
{
if (right == size) larger = left;
else larger = (collection[left].compareTo(collection[right]) > 0)
? left : right;
if (collection[parent].compareTo(collection[larger]) > 0) break;
T temp = collection[parent];
collection[parent] = collection[larger];
collection[larger] = temp;
parent = larger;
left = 2*parent+1;
right = 2*parent+2;
}
}
}
/*
* LinkedGraph.java
*
* implements a graph using a linked structure
*
*/
public class LinkedGraph
{
private class Node
{
private T vertex;
private LinkedSet
private Node next;
public Node(T item)
{
vertex = item;
neighbors = new LinkedSet
next = null;
}
public String toString()
{
return vertex + ": " + neighbors;
}
}
private Node head;
private int size;
public LinkedGraph()
{
head = null;
size = 0;
}
public boolean add (T vert, T neigh)
{
checkForNull(vert);
checkForNull(neigh);
Node current = head;
for (int i = 0; i
{
if (current.vertex.equals(vert))
{
current.neighbors.add(neigh);
return false;
}
current = current.next;
}
Node newest = new Node(vert);
newest.next = head;
head = newest;
newest.neighbors.add(neigh);
size++;
return true;
}
public LinkedSet getNeighbors(T vert)
{
Node current = head;
for (int i = 0; i
{
if (current.vertex.equals(vert))
{
return current.neighbors;
}
current = current.next;
}
return null;
}
public boolean contains(T vert)
{
Node current = head;
while (current != null)
{
if (current.vertex.equals(vert))
{
return true;
}
current = current.next;
}
return false;
}
public LinkedSet remove (T vert)
{
Node current = head, prev=null;
while (current != null)
{
if (current.vertex.equals(vert))
{
if(current.equals(head)){
head = head.next;
size--;
return current.neighbors;
}
else{
prev.next = current.next;
size--;
return current.neighbors;
}
}
prev = current;
current = current.next;
}
return null;
}
public boolean containsNeighbor(T vert, T neigh)
{
checkForNull(vert);
checkForNull(neigh);
Node current = head;
for (int i = 0; i
{
if (current.vertex.equals(vert))
{
if(current.neighbors.contains(neigh))
return true;
}
current = current.next;
}
return false;
}
public int size()
{
return size;
}
public String toString()
{
if (size == 0) return "[]";
String list = "[";
Node current = head;
for (int i = 0; i
{
list += current + " ";
current = current.next;
}
return list + current + "]";
}
private void checkForNull (T item)
{
if (item == null)
{
throw new IllegalArgumentException("null not a possible value!");
}
}
}
/*
* LinkedSet
*
* linked structure implementation of a set
*
* unordered collection with no duplicates allowed
*/
public class LinkedSet
{
/*
* inner class to represent node
*/
private class Node
{
private T data;
private Node next;
public Node(T item)
{
data = item;
next = null;
}
}
private Node head;
private int size;
/*
* adds item to bag if not already present
*
* returns true if item successfully added, false if not
*/
public boolean add(T item)
{
checkForNull(item);
if (contains(item)) return false;
Node newest = new Node (item);
newest.next = head;
head = newest;
size++;
return true;
}
/*
* removes item from set
*
* returns removed item
*/
public T remove()
{
if (size == 0)
{
return null;
}
T removed = head.data;
head = head.next;
size--;
return removed;
}
/*
* returns item from set
*/
public T get()
{
if (size == 0)
{
return null;
}
return head.data;
}
/*
* returns true if item is in set, false otherwise
*/
public boolean contains(T item)
{
Node current = head;
for (int i = 0; i
{
if (current.data.equals(item))
{
return true;
}
current = current.next;
}
return false;
}
/*
* returns size of set
*/
public int size()
{
return size;
}
/*
* returns string representation of contents of set
*/
public String toString()
{
if (size == 0)
{
return "[ ]";
}
String s = "[";
Node current = head;
while (current.next != null)
{
s += current.data + ", ";
current = current.next;
}
return s + current.data + "]";
}
private void checkForNull (T item)
{
if (item == null)
{
throw new IllegalArgumentException("null not a possible value!");
}
}
}
/* * interface for a set * * unordered collection, no duplicates allowed */
public interface Set
boolean add (T item);
T remove(); T get(); boolean contains (T item); int size(); public String toString(); }
import java.util.Arrays;
public class Sorting
{
/*
* for each element in array, make pass through array, swapping pairs
* of adjacent items if second item bigger than first
*/
public static
{
boolean sorted = false;
for (int i = 0; i
{
if (sorted)
{
break;
}
sorted = true;
for (int j = 0; j
{
if (items[j].compareTo(items[j+1]) > 0)
{
T temp = items[j];
items[j] = items[j+1];
items[j+1] = temp;
sorted = false;
}
}
}
}
/*
* for each position in array, find item that goes there
* and swap with item in that spot
*/
public static
{
for (int i = 0; i
{
int smallest = i;
for (int j = i+1; j
{
if (items[j].compareTo(items[smallest])
{
smallest = j;
}
}
if (smallest > i)
{
T temp = items[i];
items[i] = items[smallest];
items[smallest] = temp;
}
}
}
/*
* for each element in array
* locate position where it goes in sorted subarray to its left
* move elements over to make room
* insert element in its sorted position
*
* 8 7 4 2 9 slide 8 over to insert 7
* 7 8 4 2 9 slide 7 and 8 over to insert 4
* 4 7 8 2 9 slide 4, 7, and 8 over to insert 2
* 2 4 7 8 9
*/
public static
{
}
public static
{
Heap
}
public static void main (String [] args)
{
String [] words = {"banana", "grape", "coconut", "plum",
"apple", "cherries"};
System.out.println(" before sorting " + Arrays.toString(words));
bubbleSort(words);
//selectionSort(words);
//insertionSort(words);
//heapSort(words);
System.out.println(" after sorting " + Arrays.toString(words));
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help