Code: import edu.princeton.cs.algs4.In; import edu.princeton.cs.algs4.LinkedBag;
ID: 3583005 • Letter: C
Question
Code:
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.LinkedBag;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.SeparateChainingHashST;
import edu.princeton.cs.algs4.StdOut;
public class EuclideanEdgeWeightedGraph {
private int V;
private int E;
private SeparateChainingHashST<Point2D, LinkedBag<EuclideanEdge>> adj;
// Initialize an empty Euclidean edge-weighted graph from an input stream.
public EuclideanEdgeWeightedGraph(In in) {
...
}
// Number of vertices in this Euclidean edge-weighted graph.
public int V() {
...
}
// Number of edges in this Euclidean edge-weighted graph.
public int E() {
...
}
// Add an undirected edge to this Euclidean edge-weighted graph.
public void addEdge(EuclideanEdge e) {
...
}
// Edges incident on vertex v.
public Iterable<EuclideanEdge> adj(Point2D v) {
...
}
// All the edges in this Euclidean edge-weighted graph.
public Iterable<EuclideanEdge> edges() {
LinkedBag<EuclideanEdge> bag = new LinkedBag<EuclideanEdge>();
for (Point2D v : adj.keys()) {
int selfLoops = 0;
for (EuclideanEdge e : adj(v)) {
if (e.other(v).hashCode() > v.hashCode()) {
bag.add(e);
}
else if (e.other(v).equals(v)) {
if (selfLoops % 2 == 0) bag.add(e);
selfLoops++;
}
}
}
return bag;
}
// A string representation of this Euclidean edge-weighted graph.
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " " + E + " ");
for (Point2D v : adj.keys()) {
s.append(v + ": ");
for (EuclideanEdge e : adj(v)) {
s.append(e + " ");
}
s.append(" ");
}
return s.toString();
}
// Test client. [DO NOT EDIT]
public static void main(String[] args) {
In in = new In(args[0]);
EuclideanEdgeWeightedGraph G = new EuclideanEdgeWeightedGraph(in);
for (EuclideanEdge e : G.edges()) {
StdOut.println(e);
}
}
}
I have to replace the "...". Please help. Thank you!
We are using algs4.jar -> http://algs4.cs.princeton.edu/code/
tinyEG.txt -> http://pastebin.com/MHMiLMHE
Problem 4. (Euclidean Edge-weighted Graph) Implement a data type EuclideanEdgeweightedGraph for representing Euclidean e-weighted graphs whose vertices are represented as Point2D objects and edges are represented as Euclidean Edge objects The data type must support the following A method description initialize an empty Euc ean edge-weighted graph from an input stream EuclideanEdgeweightedGraph In in) number of vertices in the graph int V() number of edges in the graph int EC) add an undirected edge to the graph void add Edge (EuclideanEdge e) edges incident on vertex v Iterable adj (Point2D v all the edges in the graph Iterable edges a string representation of the graph String to String java Euclide anEdge Weighted Graph data tinyEG txt 2.99428874799 4.81382481949) (-3. 50590184636 2.70830491327) 7.53951 (1.790 35 96 3543 (-3.50590184636 2.70830491327) 9.13055 72921 07303 3.50590184636 2.70830491327) 3.88256645668 1.2329 13 12479) 8.37393 (-3.505901 84636 2.70830491327) (2.95034889345 4.14320098075) 6.61378 (-3.50590184636 2.70830491327) 3.06299 8289 977 1.37765565012 4.10990 (1.790 35 96 3543 4.7292107303) (2.9503488934 5 4.14320098075) 8.94792 4.143200 98075) 5.45634 3.88256645668 1.23291312479) (2.95034889345 -0.97222 19535182 0.144692907976) (2. 95034889345 4.14320098075) 5.60130 3.24240294366 3.94050921397) (2.95034889345 4.143200 98075) 6. 19607 (-2.99428874 799 4 81382481949) (-3 24240294366 3.94050921397) 8.75785 4.81382481949) 2.99428874799 0.609246278064 2. 3300787821) 3.44346 2.99428874799 4.81382481949) (-0.972219535182 0.144692907976) 5.35497 (-0.9722 1953 5182 0.1446929 07976 1.37765565012) 2.58629 3.06299778289 (1.790 35 96 3543 4.72921 07303) (-3.24240294366 3.94050921397) 10.02461 (1.790 35 96 3543 4.7292107303) 0.609246278064 2 3300787821) 3. 39322 2.99428874799 4.81382481949) (-1.34570880317 2.97279434591) 2.47128 1.34570880317 2.97279434 591 (3.88256645668 1.23291312479) 5.51018 1.34570880317 2.97 279434591) (-0.9722 19535182 0.144692907976) 3. 13978 1.34570880317 2.9722794 34591 3.06299778289 1.377655650 12) 2.34383 (3.882 56 64 56 68 1.23291312479) 3.06299778289 1.37765565012 6.94707 (-0.6092462780 64 2. 3300787821) 3.06299778289 1.377655650 12) 2. 63211Explanation / Answer
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.LinkedBag;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.SeparateChainingHashST;
import edu.princeton.cs.algs4.StdOut;
public class EdgeWeightedGraph
{
private static final String NEWLINE = System.getProperty("line.separator");
private final int V;
private int E;
private Bag<Edge>[] adj;
/**
* Initializes an empty edge-weighted graph with {@code V} vertices and 0 edges.
*
* @param V the number of vertices
* @throws IllegalArgumentException if {@code V < 0}
*/
public EdgeWeightedGraph(int V)
{
if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
this.V = V;
this.E = 0;
adj = (Bag<Edge>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<Edge>();
}
}
/**
* Initializes a random edge-weighted graph with {@code V} vertices and <em>E</em> edges.
*
* @param V the number of vertices
* @param E the number of edges
* @throws IllegalArgumentException if {@code V < 0}
* @throws IllegalArgumentException if {@code E < 0}
*/
public EdgeWeightedGraph(int V, int E) {
this(V);
if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
for (int i = 0; i < E; i++) {
int v = StdRandom.uniform(V);
int w = StdRandom.uniform(V);
double weight = Math.round(100 * StdRandom.uniform()) / 100.0;
Edge e = new Edge(v, w, weight);
addEdge(e);
}
}
public EdgeWeightedGraph(In in) {
this(in.readInt());
int E = in.readInt();
if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
for (int i = 0; i < E; i++) {
int v = in.readInt();
int w = in.readInt();
validateVertex(v);
validateVertex(w);
double weight = in.readDouble();
Edge e = new Edge(v, w, weight);
addEdge(e);
}
}
/**
* Initializes a new edge-weighted graph that is a deep copy of {@code G}.
*
* @param G the edge-weighted graph to copy
*/
public EdgeWeightedGraph(EdgeWeightedGraph G) {
this(G.V());
this.E = G.E();
for (int v = 0; v < G.V(); v++) {
// reverse so that adjacency list is in same order as original
Stack<Edge> reverse = new Stack<Edge>();
for (Edge e : G.adj[v]) {
reverse.push(e);
}
for (Edge e : reverse) {
adj[v].add(e);
}
}
}
/**
* Returns the number of vertices in this edge-weighted graph.
*
* @return the number of vertices in this edge-weighted graph
*/
public int V() {
return V;
}
/**
* Returns the number of edges in this edge-weighted graph.
*
* @return the number of edges in this edge-weighted graph
*/
public int E() {
return E;
}
// throw an IllegalArgumentException unless {@code 0 <= v < V}
private void validateVertex(int v) {
if (v < 0 || v >= V)
throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
}
/**
* Adds the undirected edge {@code e} to this edge-weighted graph.
*
* @param e the edge
* @throws IllegalArgumentException unless both endpoints are between {@code 0} and {@code V-1}
*/
public void addEdge(Edge e) {
int v = e.either();
int w = e.other(v);
validateVertex(v);
validateVertex(w);
adj[v].add(e);
adj[w].add(e);
E++;
}
/**
* Returns the edges incident on vertex {@code v}.
*
* @param v the vertex
* @return the edges incident on vertex {@code v} as an Iterable
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public Iterable<Edge> adj(int v) {
validateVertex(v);
return adj[v];
}
/**
* Returns the degree of vertex {@code v}.
*
* @param v the vertex
* @return the degree of vertex {@code v}
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public int degree(int v) {
validateVertex(v);
return adj[v].size();
}
/**
* Returns all edges in this edge-weighted graph.
* To iterate over the edges in this edge-weighted graph, use foreach notation:
* {@code for (Edge e : G.edges())}.
*
* @return all edges in this edge-weighted graph, as an iterable
*/
public Iterable<Edge> edges() {
Bag<Edge> list = new Bag<Edge>();
for (int v = 0; v < V; v++) {
int selfLoops = 0;
for (Edge e : adj(v)) {
if (e.other(v) > v) {
list.add(e);
}
// only add one copy of each self loop (self loops will be consecutive)
else if (e.other(v) == v) {
if (selfLoops % 2 == 0) list.add(e);
selfLoops++;
}
}
}
return list;
}
/**
* Returns a string representation of the edge-weighted graph.
* This method takes time proportional to <em>E</em> + <em>V</em>.
*
* @return the number of vertices <em>V</em>, followed by the number of edges <em>E</em>,
* followed by the <em>V</em> adjacency lists of edges
*/
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " " + E + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + ": ");
for (Edge e : adj[v]) {
s.append(e + " ");
}
s.append(NEWLINE);
}
return s.toString();
}
/**
* Unit tests the {@ EdgeWeightedGraph} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
In in = new In(args[0]);
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
StdOut.println(G);
}
}