Skip to content

GitLab

An error occurred while fetching the assigned milestone of the selected merge_request.
Merged
Created by Archie Shahidullah@archie:expressionless:Developer

Review Tests for Project 8

2 unresolved threads
Compare
and
9 files
+ 113
- 44
src/edu/c‎altech/cs2‎
datastr‎uctures‎
BeaverMaps‎Graph.java‎ +3 -12
Graph‎.java‎ +1 -1
inter‎faces‎
IDiction‎ary.java‎ +2 -0
IGrap‎h.java‎ +12 -12
proj‎ect08‎
BeaverM‎aps.java‎ +1 -0
MapsAutoCom‎pleter.java‎ +2 -0
tests/edu/calte‎ch/cs2/project08‎
Beavermap‎Tests.java‎ +49 -11
Dijkstra‎Test.java‎ +11 -8
GraphTe‎sts.java‎ +32 -0
src/edu/caltech/cs2/datastructures/BeaverMapsGraph.java
+ 3
- 12
Show all unchanged lines Show 20 lines
import com.google.gson.JsonElement;
import com.google.gson.JsonParser;
import edu.caltech.cs2.interfaces.IDeque;
import edu.caltech.cs2.interfaces.IDictionary;
import edu.caltech.cs2.interfaces.ISet;
import edu.caltech.cs2.interfaces.*;
Please register or sign in to reply
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
public class BeaverMapsGraph extends Graph<Long, Double> {
private static JsonParser JSON_PARSER = new JsonParser();
private IDictionary<Long, Location> ids;
private ISet<Location> buildings;
Show 20 lines Show all unchanged lines Show 20 lines
* @return the JSON data from filename
*/
private static JsonElement fromFile(String filename) {
try {
return JSON_PARSER.parse(
new FileReader(
new File(filename)
)
);
try (FileReader reader = new FileReader(filename)) {
return JsonParser.parseReader(reader);
} catch (IOException e) {
return null;
}
Show 20 lines Show all unchanged lines
src/edu/caltech/cs2/datastructures/Graph.java
+ 1
- 1
Show all unchanged lines Show 20 lines
import edu.caltech.cs2.interfaces.*;
public class Graph<V, E> extends IGraph<V, E> {
public class Graph<V, E> implements IGraph<V, E> {
@Override
public boolean addVertex(V vertex) {
Show 20 lines Show all unchanged lines
src/edu/caltech/cs2/interfaces/IDictionary.java
+ 2
- 0
package edu.caltech.cs2.interfaces;
import edu.caltech.cs2.datastructures.LinkedDeque;
public interface IDictionary<K, V> extends Iterable<K> {
public static class Entry<K, V> {
Show 20 lines Show all unchanged lines
src/edu/caltech/cs2/interfaces/IGraph.java
+ 12
- 12
package edu.caltech.cs2.interfaces;
public abstract class IGraph<V, E> {
public interface IGraph<V, E> {
/**
* Add a vertex to the graph.
* @param vertex The vertex to add
* @return true if vertex was not present already.
*/
public abstract boolean addVertex(V vertex);
public boolean addVertex(V vertex);
/**
* Adds edge e to the graph.
*
* @param e The edge to add.
* @throws IllegalArgumentException
* If e is not a valid edge (eg. refers to vertices not in the graph).
* @return true If e was not already present; false if it was (in which case the graph is still updated).
* If src and dest are not valid vertices (eg. refers to vertices not in the graph).
* @return true If src and dest were not already present; false if it was (in which case the graph is still updated).
*/
public abstract boolean addEdge(V src, V dest, E e);
public boolean addEdge(V src, V dest, E e);
/**
* Adds edge e to the graph in both directionns.
*
* @param e The edge to add.
* @throws IllegalArgumentException
* If e is not a valid edge (eg. refers to vertices not in the graph).
* @return true If e was not already present in either direction; false if it was (in which case the graph is still updated).
* If src and dest are not valid vertices (eg. refers to vertices not in the graph).
* @return true If src and dest were not already present in either direction; false if it was (in which case the graph is still updated).
*/
public abstract boolean addUndirectedEdge(V src, V dest, E e);
public boolean addUndirectedEdge(V src, V dest, E e);
/**
* Remove an edge from src to dest from the graph.
Show 20 lines Show all unchanged lines Show 20 lines
* @throws IllegalArgumentException if src or dest is not in the graph.
* @return true if an edge from src to dest edge was present.
*/
public abstract boolean removeEdge(V src, V dest);
public boolean removeEdge(V src, V dest);
/**
* Returns the set of vertices in the graph.
* @return The set of all vertices in the graph.
*/
public abstract ISet<V> vertices();
public ISet<V> vertices();
/**
* Tests if vertices i and j are adjacent, returning the edge between
Show 20 lines Show all unchanged lines Show 20 lines
* @return The edge from i to j if it exists in the graph;
* null otherwise.
*/
public abstract E adjacent(V i, V j);
public E adjacent(V i, V j);
/**
* Return the neighbours of a given vertex when this graph is treated as
Show 20 lines Show all unchanged lines Show 20 lines
* @throws IllegalArgumentException if vertex is not in the graph.
* @return The set of neighbors of vertex.
*/
public abstract ISet<V> neighbors(V vertex);
public ISet<V> neighbors(V vertex);
}
\ No newline at end of file
src/edu/caltech/cs2/project08/BeaverMaps.java
+ 1
- 0
Show all unchanged lines Show 20 lines
import com.sun.net.httpserver.HttpHandler;
import com.sun.net.httpserver.HttpServer;
import edu.caltech.cs2.datastructures.BeaverMapsGraph;
import edu.caltech.cs2.datastructures.LinkedDeque;
import edu.caltech.cs2.datastructures.Location;
import edu.caltech.cs2.interfaces.IDeque;
import edu.caltech.cs2.interfaces.ISet;
Show 20 lines Show all unchanged lines
src/edu/caltech/cs2/project08/MapsAutoCompleter.java
+ 2
- 0
package edu.caltech.cs2.project08;
import edu.caltech.cs2.datastructures.LinkedDeque;
import edu.caltech.cs2.datastructures.Location;
import edu.caltech.cs2.datastructures.TrieMap;
import edu.caltech.cs2.interfaces.IDeque;
import edu.caltech.cs2.interfaces.ISet;
import edu.caltech.cs2.interfaces.ITrieMap;
Show 20 lines Show all unchanged lines
tests/edu/caltech/cs2/project08/BeavermapTests.java
+ 49
- 11
Show all unchanged lines Show 20 lines
import edu.caltech.cs2.helpers.Inspection;
import edu.caltech.cs2.helpers.Reflection;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
Show 20 lines Show all unchanged lines Show 20 lines
import org.hamcrest.MatcherAssert;
import org.hamcrest.collection.IsIterableContainingInAnyOrder;
import org.hamcrest.collection.IsIterableContainingInOrder;
import org.hamcrest.core.IsCollectionContaining;
import org.hamcrest.core.IsIterableContaining;
import org.junit.jupiter.api.*;
import org.junit.jupiter.api.MethodOrderer;
import org.junit.jupiter.api.TestMethodOrder;
Show 20 lines Show all unchanged lines Show 20 lines
@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
public class BeavermapTests {
private static String BEAVERMAP_GRAPH_SOURCE = "src/edu/caltech/cs2/datastructures/BeaverMapsGraph.java";
private static JsonParser JSON_PARSER = new JsonParser();
private static JsonElement fromFile(String filename) {
try {
return JSON_PARSER.parse(
new FileReader(
new File(filename)
)
);
} catch (IOException e) {
try (FileReader reader = new FileReader(filename)) {
return JsonParser.parseReader(reader);
}
catch (IOException e) {
return null;
}
}
Show 20 lines Show all unchanged lines Show 20 lines
}
}
@Tag("C")
@DisplayName("Test addVertex() updates BeaverMapsGraph properly")
@Test
public void testAddVertexBeaverMapsGraph() {
BeaverMapsGraph bmg = new BeaverMapsGraph(
"data/caltech/caltech.buildings.json",
"data/caltech/caltech.waypoints.json",
"data/caltech/caltech.roads.json");
JsonElement bs = fromFile("data/pasadena/pasadena.buildings.json");
for (JsonElement b : bs.getAsJsonArray()) {
Location loc = new Location(b.getAsJsonObject());
bmg.addVertex(loc);
assertNotNull(bmg.getLocationByID(loc.id), "Location id " + loc.id + " not found by id");
}
}
@Tag("C")
@DisplayName("BeaverMapsGraph implements required public methods")
@Test
Show 20 lines Show all unchanged lines Show 20 lines
.map(x -> x.getName())
.collect(Collectors.toList()));
MatcherAssert.assertThat(new ArrayList<>(actual),
IsCollectionContaining.hasItems((expected.toArray())));
IsIterableContaining.hasItems((expected.toArray())));
}
Show 20 lines Show all unchanged lines Show 20 lines
}
}
@Tag("A")
@DisplayName("Test buildings are ignored in dijkstra path")
@Test
public void testDijkstraIgnoreBuildings() {
BeaverMapsGraph bmg = new BeaverMapsGraph(
"data/caltech/caltech.buildings.json",
"data/caltech/caltech.waypoints.json",
"data/caltech/caltech.roads.json");
JsonElement s = fromFile("data/caltech/caltech.paths_trace.json");
for (JsonElement b : s.getAsJsonArray()) {
JsonObject curr = b.getAsJsonObject();
Location start = bmg.getLocationByID(curr.get("start").getAsLong());
Location target = bmg.getLocationByID(curr.get("target").getAsLong());
IDeque<Location> actualPath = bmg.dijkstra(start, target);
if (actualPath == null) {
continue;
}
for (Location loc : actualPath){
if (loc.id == start.id || loc.id == target.id) {
continue;
}
ISet<Location> buildings = Reflection.getFieldValue(BeaverMapsGraph.class, "buildings", bmg);
assertFalse(buildings.contains(loc), "Location " + loc.id + " in path is a building");
}
}
}
@Tag("A")
@DisplayName("Test Dijkstra")
Show 20 lines Show all unchanged lines
tests/edu/caltech/cs2/project08/DijkstraTest.java
+ 11
- 8
Show all unchanged lines Show 20 lines
Scanner s = new Scanner(new File("data/dijkstra/" + traceFile));
if (res == null) {
assertEquals(s.nextLine(), "null", "Path exists but was not found");
String line = s.nextLine();
if (line.equals("null")) {
assertNull(res, "Path does not exist but was found");
}
else {
assertNotNull(res, "Path exists but was not found");
for (Location l : res) {
if (prev != null) {
pathLen += bmg.adjacent(prev.id, l.id);
Show 20 lines Show all unchanged lines Show 20 lines
prev = l;
}
double expectedLen = s.nextDouble();
double expectedLen = Double.parseDouble(line);
assertEquals(expectedLen, pathLen, "Path lengths are not equivalent");
}
Show 20 lines Show all unchanged lines Show 20 lines
@Order(3)
@DisplayName("Tests Dijkstra on random graph and paths")
@Test
public void dijkstraStressTest() throws FileNotFoundException{
public void dijkstraStressTest() throws FileNotFoundException {
final int num_tests = 1000;
IGraph<Integer, Integer> refg = new Graph<Integer, Integer>();
Show 20 lines Show all unchanged lines Show 20 lines
BeaverMapsGraph bmg = GraphMaker.transformToLocations(refg);
IDeque<Location> res = bmg.dijkstra(new Location(startvertex), new Location(endvertex));
if (res == null) {
assertEquals(s.nextLine(), "null", "Path exists but was not found");
String line = s.nextLine();
if (line.equals("null")) {
assertNull(res, "Path does not exist but was found");
}
else {
assertNotNull(res, "Path exists but was not found");
double pathLen = 0;
Location prev = null;
for (Location l : res) {
Show 20 lines Show all unchanged lines Show 20 lines
prev = l;
}
double expectedLen = s.nextDouble();
s.nextLine();
double expectedLen = Double.parseDouble(line);
assertEquals(expectedLen, pathLen, "Path lengths are not equivalent");
}
}
Show 20 lines Show all unchanged lines
tests/edu/caltech/cs2/project08/GraphTests.java
+ 32
- 0
Show all unchanged lines Show 20 lines
});
}
@Test
public void undirectedEdgeTest() {
assertTimeout(Duration.ofMillis(SIMPLE_OP_TIMEOUT_MS), () -> {
IGraph<String, Integer> g = new Graph<>();
assertTrue(g.addVertex("1"), "Should be able to add a vertex");
assertEquals(1, g.vertices().size(), "Should have correct number of vertices");
assertTrue(g.addVertex("2"), "Should be able to add a vertex");
assertEquals(2, g.vertices().size(), "Should have correct number of vertices");
assertTrue(g.addVertex("3"), "Should be able to add a vertex");
assertEquals(3, g.vertices().size(), "Should have correct number of vertices");
assertTrue(g.addUndirectedEdge("1", "2", 1), "Should be able to add new edge");
assertFalse(g.addEdge("1", "2", 1), "Should not be able to add new edge");
assertFalse(g.addEdge("1", "2", 2), "Should not be able to add new edge");
assertFalse(g.addEdge("2", "1", 1), "Should not be able to add new edge");
assertFalse(g.addEdge("2", "1", 2), "Should not be able to add new edge");
assertTrue(g.addUndirectedEdge("1", "3", 1), "Should be able to add new edge");
assertFalse(g.addEdge("1", "3", 1), "Should not be able to add new edge");
assertFalse(g.addEdge("1", "3", 2), "Should not be able to add new edge");
assertFalse(g.addEdge("3", "1", 1), "Should not be able to add new edge");
assertFalse(g.addEdge("3", "1", 2), "Should not be able to add new edge");
assertTrue(g.addUndirectedEdge("2", "3", 1), "Should be able to add new edge");
assertFalse(g.addEdge("2", "3", 1), "Should not be able to add new edge");
assertFalse(g.addEdge("2", "3", 2), "Should not be able to add new edge");
assertFalse(g.addEdge("3", "2", 1), "Should not be able to add new edge");
assertFalse(g.addEdge("3", "2", 2), "Should not be able to add new edge");
});
}
@Test
public void stringEdgeTest() {
assertTimeout(Duration.ofMillis(SIMPLE_OP_TIMEOUT_MS), () -> {
Show 20 lines Show all unchanged lines