Find a plane graph that is self-dual (you can do this by trial-and-error or by l
ID: 3679179 • Letter: F
Question
Find a plane graph that is self-dual (you can do this by trial-and-error or by looking online; e.g., at Mathworld or Wikipedia, but let us know what method you use). A graph GG is self-dual if it is isomorphic to its dual. Give the bijection between the vertices of the two graphs that demonstrates that they are isomorphic.
Below is the rotation system of a plane graph. Draw all possible embeddings in the plane (i.e., each face should be an outer face in exactly one of the embeddings).
Below is the rotation system for a graph embedded on a surface. What surface is it embedded on? Draw a nice diagram of the graph as embedded on this surface.
Find an example of a biconnected bipartite non-Hamiltonian graph. Noting that any Hamiltonian bipartite graph must be balanced in the sense that the cardinalities of the partite sets must be equal, it is not hard to find an example graph that is unbalanced. Can you find one that is balanced? Explain why your graph has the required properties.
From the book 4.4.15.
Programming Problem:
Background:
This assignment is based on a problem from a programming contest. It has been modified somewhat, partially so that we can use JUnit testing. You are encouraged to try to solve it as you would encounter it in an actual contest. That is, try to solve it in an hour or two, without using the internet, but using only paper materials.
the Problem:
Two intrepid astronauts, Fred and Wilma, have volunteered to undertake travel from Earth to beyond the galaxy in order to verify whether certain planets are inhabitable or not. Fortunately, some wormholes have been discovered which effectively reduces the travel distance between some planets to zero. For all other planets distance is simply the Euclidean distance between them. Given the location of Earth, planets, and wormholes, your task is to determine the shortest travel distance between any pairs of planets. Input to our main:
The first line of input is a single integer, TT (1T101T10), the number of test cases.
Each test case consists of planets, wormholes, and a set of distance queries.
The planets list for a test case starts with a single integer, pp (1<p<601<p<60), the number of planets. Following this are p lines, where each line contains a planet name along with the planet's integer coordinates, i.e. name x y z (0<x,y,z<21060<x,y,z<2106). The names of the planets will consist only of ASCII letters and numbers, and will always start with an ASCII letter. Planet names are case-sensitive (Earth and earth are distinct planets). The length of a planet name will never be greater than 50 characters. All coordinates are given in parsecs.
The wormholes list for a test case starts with a single integer, ww (0<w<400<w<40), the number of wormholes, followed by the list of ww wormholes. Each wormhole consists of two planet names separated by a space. The first planet name marks the entrance of wormhole, and the second planet name marks the exit from the wormhole. The planets that mark wormholes will be chosen from the list of planets given in the preceding section. Note: you can't enter a wormhole at its exit.
The queries list for a test case starts with a single integer, qq (1<q<201<q<20), the number of queries. Each query consists of two planet names separated by a space. Both planets will have been listed in the planet list.
Output for the main:
For each test case, output a line. "Case ii:", the number of the iith test case. Then, for each query in that test case, output a line that states "The distancee from planet1, to planet2 is dd parsecs using ww wormholes.", where the planets are the names from the query, dd is the shortest possible travel distance between the two planets, and ww is the leastnumber of wormholes used in any shortest route (because of ties, there could be several shortest routes, which could use different numbers of wormholes). Round dd to the nearest integer. Sample Input for main:
Sample Output
Program Structure:
You should write a class Worm whose outline is shown below. (In a programming contest, you would have to write everything from scratch.)
In case it is not clear from the main above (which you should read carefully), the constructor takes as input some text in the following format.
Explanation / Answer
Worm.java
import java.lang.Exception;
import java.util.*;
public class Worm {
// planets and their position in space
HashMap<String, Point> Coordinates;
ShortestPath sp;
public Worm( In in ) {
Coordinates = new HashMap<String, Point>();
int num_planets = in.readInt();
for (int i = 0; i < num_planets; i++) {
String planet = in.readString();
double x = in.readDouble();
double y = in.readDouble();
double z = in.readDouble();
Coordinates.put(planet, new Point(x, y, z));
}
Graph graph = new Graph(Coordinates);
Wormholes wormholes = new Wormholes();
int num_wormholes = in.readInt();
for (int i = 0; i < num_wormholes; i++) {
String from = in.readString();
String to = in.readString();
wormholes.add(new Wormhole(from, to));
}
sp = new ShortestPath(graph, wormholes);
}
public double dist( String origP, String destP ) {
return sp.distanceBetween(origP, destP);
}
public int worms( String origP, String destP ) {
return sp.wormholesBetween(origP, destP);
}
public String query( String origP, String destP ) {
return "The distance from " + origP + " and " + destP + " is " + sp.distanceBetween(origP, destP) + " parsecs using " + worms(origP, destP) + " wormholes.";
}
public static void main(String[] args) {
// You can test your program with something like this.
System.out.println(args[0]);
In in = new In( args[0] );
int T = in.readInt(); // number of cases
for (int t=1; t<=T; t++) {
System.out.println("Case " + t + ":") ;
Worm w = new Worm( in );
int Q = in.readInt() ; // number of items in list
for (int i=0; i<Q; i++) {
String p1s = in.readString() ;
String p2s = in.readString() ;
System.out.println( w.query( p1s, p2s ) ) ;
}
}
}
}
Wormhole.java
import java.util.*;
import java.lang.Exception;
public class Wormhole {
public final String from;
public final String to;
public Wormhole(String from, String to)
{ this.from = from; this.to = to; }
public boolean equals(Object o) {
if (o instanceof Wormhole) {
if (((Wormhole)o).from == this.from && ((Wormhole)o).to == this.to) {
return true;
}
}
return false;
}
}
Wormholes.java
import java.util.*;
import java.lang.Exception;
public class Wormholes implements Iterable<Wormhole> {
ArrayList<Wormhole> wormholes = new ArrayList<Wormhole>();
public Wormholes() { }
public void add(Wormhole w) { wormholes.add(w); }
public boolean exists(EdgeTo e) {
return exists(new Wormhole(e.from, e.to));
}
public Iterator<Wormhole> iterator() {
return wormholes.iterator();
}
public boolean exists(Wormhole w) {
for (Wormhole o : wormholes) {
if ((w.from == o.from) && (w.to == o.to)) {return true;}
}
return false;
}
}
ShortestPath.java
import java.lang.Exception;
import java.util.*;
import java.lang.Math;
/* CONTRACT:
must compute the distance between two planets least number of wormholes in any shortest path bt two planets
output the distance from p1 to p2 is x parsecs using y wormholes
*/
public class ShortestPath extends IndecesBuilder {
Graph graph;
Wormholes wormholes;
double[][] distTo;
int[][] wormTo;
HashMap<String, Integer> indeces;
public int V() { return graph.V(); }
public ShortestPath(Graph graph, Wormholes holes) {
this.graph = graph;
this.wormholes = holes;
indeces = this.Indeces(graph);
wormTo = new int[graph.V()][graph.V()];
distTo = new double[graph.V()][graph.V()];
for (int j = 0; j < V(); ++j) {
for (int i = 0; i < V(); ++i) {
distTo[i][j] = Double.POSITIVE_INFINITY;
wormTo[i][j] = 0;
}
}
for (String p : graph.planets()) {
for (EdgeTo e : graph.adjacencyList(p)) {
distTo[indeces.get(e.from).intValue()][indeces.get(e.to).intValue()] = e.distance;
}
}
for (Wormhole w : holes) {
distTo[indeces.get(w.from).intValue()][indeces.get(w.to).intValue()] = 0;
wormTo[indeces.get(w.from).intValue()][indeces.get(w.to).intValue()] = 1;
}
for (int k = 0; k < V(); ++k) {
for (int j = 0; j < V(); ++j) {
for (int i = 0; i < V(); ++i) {
if (distTo[j][i] > distTo[j][k] + distTo[k][i]) {
wormTo[j][i] = wormTo[j][k] + wormTo[k][i];
}
distTo[j][i] = Math.min(distTo[j][i], distTo[j][k] + distTo[k][i]);
}
}
}
}
public int wormholesBetween(String p1, String p2) {
return wormTo[indeces.get(p1).intValue()][indeces.get(p2).intValue()];
}
public double distanceBetween(String p1, String p2) {
return distTo[indeces.get(p1).intValue()][indeces.get(p2).intValue()];
}
public boolean query(String p1, String p2)
{ return false; }
}
EdgeTo.java
import java.util.*;
import java.lang.Exception;
public class EdgeTo implements Comparable<EdgeTo> {
public final String from;
public final String to;
public final double distance;
public EdgeTo(String from, String to, double distance) {
this.from = from;
this.to = to;
this.distance = distance;
}
public boolean equals(Object o) {
if (o instanceof EdgeTo) {
if (((EdgeTo)o).to == this.to && ((EdgeTo)o).from == this.from) {
return true;
}
}
return false;
}
public int compareTo(EdgeTo e) {
if (e.distance > this.distance) return 1;
if (e.distance < this.distance) return -1;
return 0;
}
}
Graph.java
import java.util.*;
import java.lang.Exception;
public class Graph {
HashMap<String, ArrayList<EdgeTo>> graph;
public int V() { return graph.keySet().size(); }
public Graph(HashMap<String, Point> coords) {
// build graph
// for every planet in coordinates
// calculate the euclidean distance between all other planets
// and add that distance to the graph
graph = new HashMap<String, ArrayList<EdgeTo>>();
for (Map.Entry<String, Point> planet : coords.entrySet()) {
ArrayList<EdgeTo> adj_list = new ArrayList<EdgeTo>();
Point p1 = planet.getValue();
for (Map.Entry<String, Point> edge : coords.entrySet()) {
Point p2 = edge.getValue();
double distance = p1.distanceTo(p2);
adj_list.add(new EdgeTo(planet.getKey(), edge.getKey(), distance));
}
graph.put(planet.getKey(), adj_list);
}
}
public ArrayList<EdgeTo> adjacencyList(String vertex) {
return graph.get(vertex);
}
public Set<String> planets() {
return graph.keySet();
}
public void addEdge(String v1, String v2, double distance) {
graph.get(v1).add(new EdgeTo(v1, v2, distance));
graph.get(v2).add(new EdgeTo(v2, v1, distance));
}
}
Point.java
import java.util.*;
import java.lang.Exception;
public class Point {
public double x; double y; double z;
public Point(double x, double y, double z)
{ this.x = x; this.y = y; this.z = z; }
public double distanceTo(Point p) {
return euclideanDistance(this, p);
}
public static double euclideanDistance( Point p1, Point p2 ) {
return Math.sqrt(
Math.pow(p1.x - p2.x, 2) +
Math.pow(p1.y - p2.y, 2) +
Math.pow(p1.z - p2.z, 2)
);
}
}
IndecesBuilder.java
import java.lang.Exception;
import java.util.*;
import java.lang.Math;
public abstract class IndecesBuilder {
public HashMap<String, Integer> Indeces(Graph g) {
HashMap<String, Integer> indeces = new HashMap<String, Integer>();
int c = 0;
for (String p : g.planets()) {
indeces.put(p, new Integer(c++));
}
return indeces;
}
public ArrayList<String> Planets(Graph g) {
ArrayList<String> p = new ArrayList<String>(g.V());
HashMap<String, Integer> indeces = Indeces(g);
for (Map.Entry e : indeces.entrySet()) {
p.add(((Integer)e.getValue()).intValue(), (String)e.getKey());
}
return p;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.