Homework SourseEuclidean graphs Design and implement an API EuclideanGraph
Euclidean graphs. Design and implement an API EuclideanGraph for graphs
whose vertices are points in the plane that include coordinates. Include a method
show() that uses StdDraw to draw the graph. please give solution in java
Solution
import java.awt.Point;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import edu.princeton.cs.algs4.StdDraw;
public class EuclideanGraph {
private HashMap<String, Integer> st; // string -> index
private String[] keys; // index -> string
private Graph G;
private Point[] points;
private boolean[] marked;
public EuclideanGraph(String filename, String delimiter) throws FileNotFoundException {
st = new HashMap<>();
// First pass builds the index by reading strings to associate
// distinct strings with an index
Scanner in = new Scanner(new File(filename));
while (in.hasNextLine()) {
String point = in.next();
System.out.println(point);
if (!st.containsKey(point))
st.put(point, st.size());
}
System.out.println(\"Done reading \" + filename);
// inverted index to get string keys in an array
keys = new String[st.size()];
for (String name : st.keySet()) {
keys[st.get(name)] = name;
}
// convert string to Point
points = new Point[st.size()];
for (int i = 0; i < st.size(); i++) {
int loc = keys[i].indexOf(\",\");
int x = Integer.parseInt(keys[i].substring(1, loc));
int y = Integer.parseInt(keys[i].substring(loc + 1, keys[i].length() - 1));
points[i] = new Point(x,y);
}
// second pass builds the graph by connecting first vertex on each
// line to all others
G = new Graph(st.size());
in = new Scanner(new File(filename));
while (in.hasNextLine()) {
String x = in.next();
int v = st.get(x);
String y = in.next();
int w = st.get(y);
G.addEdge(v, w);
G.addEdge(w, v);
}
in.close();
}
public void show() {
StdDraw.setScale(-1, 10);
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++) {
if (!marked[v])
bfs(v);
}
}
private void bfs(int s) {
Queue<Integer> Q = new LinkedList<>();
marked[s] = true;
Q.add(s);
while (!Q.isEmpty()) {
int v = Q.poll();
StdDraw.setPenRadius(0.02);
StdDraw.point(points[v].getX(), points[v].getY());
for (int w : G.adj(v)) {
StdDraw.setPenRadius();
StdDraw.line(points[v].getX(), points[v].getY(), points[w].getX(), points[w].getY());
if (!marked[w]) {
marked[w] = true;
Q.add(w);
}
}
}
}
public static void main(String[] args) throws FileNotFoundException {
String filename = args[0];
EuclideanGraph G = new EuclideanGraph(filename, \" \");
G.show();
}
}
Graph.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Graph {
private static final String NEWLINE = System.getProperty(\"line.separator\");
private int V;
private int E;
private List<List<Integer>> adj;
public Graph(int V) {
if (V < 0) throw new IllegalArgumentException(\"Number of vertices must be nonnegative\");
this.V = V;
this.E = 0;
adj = new ArrayList<List<Integer>>(V);
for (int v = 0; v < V; v++) {
List<Integer> list = new LinkedList<Integer>();
adj.add(list);
}
}
public Graph(Scanner in) {
this(in.nextInt());
int E = in.nextInt();
if (E < 0) throw new IllegalArgumentException(\"Number of edges must be nonnegative\");
for (int i = 0; i < E; i++) {
int v = in.nextInt();
int w = in.nextInt();
addEdge(v, w);
}
}
public int V() {
return V;
}
public int E() {
return E;
}
private void validateVertex(int v) {
if (v < 0 || v >= V)
throw new IndexOutOfBoundsException(\"vertex \" + v + \" is not between 0 and \" + (V-1));
}
public void addEdge(int v, int w) {
validateVertex(v);
validateVertex(w);
E++;
adj.get(v).add(w);
adj.get(w).add(v);
}
public Iterable<Integer> adj(int v) {
validateVertex(v);
return adj.get(v);
}
public int degree(int v) {
validateVertex(v);
return adj.get(v).size();
}
/**
* Ex 4.1.3
* deep copy
*/
public Graph(Graph G) {
this(G.V());
this.E = G.E();
for (int v = 0; v < G.V(); v++) {
for (int w : G.adj.get(v))
this.adj.get(v).add(w);
}
}
/**
* Ex 4.1.4
* Add a method hasEdge()
*/
public boolean hasEdge(int v, int w) {
for (int u : adj.get(v))
if (u == w)
return true;
return false;
}
/**
* Ex 4.1.5
* disallow parallel edges and self-loops.
*/
public void validateEdge(int v, int w) throws Exception {
if (v == w)
throw new Exception(\"vertex \" + v + \" has self-loop\");
for (int u : this.adj.get(v))
if (u == w)
throw new Exception(\"vertex \" + v + \" has parallel edge\");
}
/**
* Ex 4.1.7
* Returns a string representation of this graph.
*/
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + \" vertices, \" + E + \" edges \" + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + \": \");
for (int w : adj.get(v)) {
s.append(w + \" \");
}
s.append(NEWLINE);
}
return s.toString();
}
/**
* Ex 4.1.8
* Search API
*/
public class Search {
private int s;
private WeightedQuickUnionUF uf;
/**
* find vertices connected to a source vertex s
* The constructor can build a UF object, do a union() operation
* for each of the graph’s edges.
*/
public Search(Graph G, int s) {
this.s = s;
this.uf = new WeightedQuickUnionUF(G.V());
for (int v = 0; v < G.V(); v++) {
for (int w : G.adj.get(v)) {
if (uf.connected(v, w))
continue;
uf.union(v, w);
}
}
}
/**
* is v connected to s?
* Implement marked(v) by calling connected(s, v)
*/
boolean marked(int v) {
return uf.connected(s, v);
}
int count() {
return uf.count(s);
}
}
public List<Integer> non_articulation_vertex() {
vertexClassification();
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < V; i++) {
if (!articulation[i])
list.add(i);
System.out.println(i + \" \" + disc[i] + \"/\" + low[i]);
}
return list;
}
private boolean[] articulation;
private int time;
private int[] disc;
private int[] low;
public void vertexClassification() {
articulation = new boolean[this.V()];
disc = new int[this.V()];
low = new int[this.V()];
Arrays.fill(disc, -1);
Arrays.fill(low, -1);
time = 0;
for (int v = 0; v < this.V(); v++) {
if (disc[v] == -1)
dfs_ap(v, v);
}
}
private void dfs_ap(int parent, int cur_v) {
int children = 0;
disc[cur_v] = time++;
low[cur_v] = disc[cur_v];
for (int neib : adj.get(cur_v)) {
if (disc[neib] == -1) {
children++;
dfs_ap(cur_v, neib);
// update low number
low[cur_v] = Math.min(low[cur_v], low[neib]);
// non-root of DFS is an articulation point if low[neib] >= disc[cur_v]
if (low[neib] >= disc[cur_v] && parent != cur_v)
articulation[cur_v] = true;
}
// update low number - ignore reverse of edge leading to cur_v
else if (neib != parent)
low[cur_v] = Math.min(low[cur_v], disc[neib]);
}
// root of DFS is an articulation point if it has more than 1 child
if (parent == cur_v && children > 1)
articulation[cur_v] = true;
}
public Graph(Scanner in, String sp) {
this(in.nextInt()); // calls Graph(V)
this.E = in.nextInt();
if (E < 0) throw new IllegalArgumentException(\"Number of edges must be nonnegative\");
in.nextLine();
List<Stack<Integer>> stacks = new ArrayList<>();
for (int i = 0; i < V; i++)
stacks.add(new Stack<Integer>());
while (in.hasNextLine())
{
String[] arr = in.nextLine().split(sp);
int v = Integer.parseInt(arr[0]);
for (int i = 1; i < arr.length; i++) {
int w = Integer.parseInt(arr[i]);
stacks.get(v).push(w);
stacks.get(w).push(v);
}
}
for (int i = 0; i < V; i++) {
Stack<Integer> stack = stacks.get(i);
while (!stack.isEmpty())
adj.get(i).add(stack.pop());
}
}
public static void main(String[] args) throws FileNotFoundException {
Scanner in = new Scanner(new File(args[0]));
Graph G = new Graph(in);
System.out.println(G);
// test for ex 4.1.3
Graph G2 = new Graph(G);
System.out.println(G2);
// test for ex 4.1.4
System.out.println(\"The path \" + (G.hasEdge(2,11) ? \"exists\" : \"does not exist\"));
// test for ex 4.1.8
Search search = G.new Search(G, 0);
System.out.println(search.marked(10));
System.out.println(search.marked(8));
System.out.println(search.count());
// test for ex 4.1.10
in = new Scanner(new File(args[1]));
Graph G3 = new Graph(in);
System.out.println(G3.non_articulation_vertex());
// test for ex 4.1.13
BFS bfs = new BFS(G, 0);
System.out.println(bfs.distTo(3));
System.out.println(bfs.distTo(10));
// test for ex 4.1.15
in = new Scanner(new File(args[2]));
Graph G4 = new Graph(in, \" \");
System.out.println(G4);
// test for ex 4.1.16
in = new Scanner(new File(args[3]));
Graph G5 = new Graph(in);
GraphProperties gp = new GraphProperties(G5);
System.out.println(\"diameter: \" + gp.diameter() + \" radius: \" + gp.radius() + \" center: \" + gp.center());
// test for ex 4.1.17
System.out.println(\"wiener: \" + gp.wiener());
// test for ex 4.1.18
System.out.println(\"girth: \" + gp.girth());
}
}
WeightedQuickUnionUF.java
import java.util.Scanner;
public class WeightedQuickUnionUF {
private int[] parent; // parent[i] = parent of i
private int[] size; // size[i] = number of sites in subtree rooted at i
private int count; // number of components
public WeightedQuickUnionUF(int N) {
count = N;
parent = new int[N];
size = new int[N];
for (int i = 0; i < N; i++) {
parent[i] = i;
size[i] = 1;
}
}
public int count() {
return count;
}
public int count(int p) {
return size[find(p)];
}
public int find(int p) {
validate(p);
while (p != parent[p])
p = parent[p];
return p;
}
private void validate(int p) {
int N = parent.length;
if (p < 0 || p >= N) {
throw new IndexOutOfBoundsException(\"index \" + p + \" is not between 0 and \" + (N-1));
}
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
// make smaller root point to larger one
if (size[rootP] < size[rootQ]) {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
else {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
count--;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N);
while (!in.hasNext()) {
int p = in.nextInt();
int q = in.nextInt();
if (uf.connected(p, q)) continue;
uf.union(p, q);
System.out.println(p + \" \" + q);
}
System.out.println(uf.count() + \" components\");
in.close();
}
}
BFS.java
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
/**
* Ex 4.1.13
* Add a distTo() method
*/
public class BFS {
private int[] distTo; // distTo[v] = number of edges shortest s-v path
private int[] edgeTo; // edgeTo[v] = previous edge on shortest s-v path
private boolean[] marked;
public BFS(Graph G, int s) {
marked = new boolean[G.V()];
distTo = new int[G.V()];
edgeTo = new int[G.V()];
bfs(G, s);
}
private void bfs(Graph G, int s) {
Queue<Integer> q = new LinkedList<Integer>();
for (int v = 0; v < G.V(); v++)
distTo[v] = Integer.MAX_VALUE;
distTo[s] = 0;
marked[s] = true;
q.add(s);
while(!q.isEmpty()) {
int v = q.poll();
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
distTo[w] = distTo[v] + 1;
marked[w] = true;
q.add(w);
}
}
}
}
public int distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
Deque<Integer> path = new ArrayDeque<Integer>();
int x;
for (x = v; distTo[x] != 0; x = edgeTo[x])
path.push(x);
path.push(x);
return path;
}
}
GraphProperties.java
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class GraphProperties {
private Graph G;
private int[] e;
private int diam;
private int rad;
private boolean[] marked;
private int[] dist;
private int[] parent;
/**
* Ex 4.1.16
* The eccentricity of a vertex
*/
GraphProperties(Graph G) {
this.G = G;
e = new int[G.V()];
diam = Integer.MIN_VALUE;
rad = Integer.MAX_VALUE;
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++) {
Arrays.fill(marked, false);
e[v] = BFS(G, v);
diam = Math.max(diam, e[v]);
rad = Math.min(rad, e[v]);
if (v % 10000 == 0)
System.out.print(\"\ processing vertex \" + v);
else if (v % 100 == 0)
System.out.print(\".\");
}
}
private int BFS(Graph G, int s) {
int max = 0;
int[] dist = new int[G.V()];
marked[s] = true;
Queue<Integer> q = new LinkedList<>();
q.add(s);
while (!q.isEmpty()) {
int v = q.poll();
for (int w : G.adj(v)) {
if (!marked[w]) {
dist[w] = dist[v] + 1;
q.add(w);
marked[w] = true;
}
}
}
for (int i = 0; i < dist.length; i++)
max = Math.max(max, dist[i]);
return max;
}
public int diameter() {
return diam;
}
public int radius() {
return rad;
}
public List<Integer> center() {
List<Integer> list = new LinkedList<>();
for (int v = 0; v < G.V(); v++)
if (e[v] == radius())
list.add(v);
return list;
}
/**
* Ex 4.1.17
* The Wiener index of a graph
*/
public int wiener() {
int sum = 0;
for (int s = 0; s < G.V(); s++) { // BFS from each vertex
marked = new boolean[G.V()];
dist = new int[G.V()];
Queue<Integer> q = new LinkedList<>();
q.add(s);
dist[s] = 0;
marked[s] = true;
while (!q.isEmpty()) {
int v = q.poll();
for (int w : G.adj(v)) {
if (!marked[w]) {
dist[w] = dist[v] + 1;
q.add(w);
marked[w] = true;
sum += dist[w];
}
}
}
}
return sum / 2; // we sum the distance twice
}
/**
* 4.1.18
* The girth of a graph
*/
public int girth() {
int girth = Integer.MAX_VALUE;
for (int s = 0; s < G.V(); s++) { // BFS from each vertex
int circle = -1;
marked = new boolean[G.V()];
dist = new int[G.V()];
parent = new int[G.V()];
Queue<Integer> q = new LinkedList<>();
q.add(s);
dist[s] = 0;
parent[s] = s;
marked[s] = true;
while (!q.isEmpty()) {
int v = q.poll();
for (int w : G.adj(v)) {
if (!marked[w]) {
dist[w] = dist[v] + 1;
parent[w] = v;
q.add(w);
marked[w] = true;
} else if (w != parent[v]) {
circle = dist[v] + dist[w] + 1;
break;
}
}
if (circle > 0) break; // found a circle
}
girth = Math.min(girth, circle);
}
return girth;
}
}
euclidean.txt
(0,0) (1,1)
(1,1) (2,2)
(2,2) (2,0)
