Please i need help fixing my graph class according to the interface i will provi
ID: 3829794 • Letter: P
Question
Please i need help fixing my graph class according to the interface i will provide i will aslo provide the graphtest class, road class and town class for implementation but the Only class i need fixed is the graph class though you can make changes per your programing style if you feel those are needed thanks.i have some if not most of the test working so when you do run the tests you will see what needs to be fixed my code is somewhat right as i don't get total failures but i'm having issue to logically implement what is asked of me.
GRAPH CLASS
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import com.sun.javafx.geom.Edge;
public class Graph implements GraphInterface//Town (Vertex) , Road(edge)
{
private List vertices ;//Store vertices
private Map> adjacencyList; // [vertices] -> [edge]
private List edges;//store edges
//private List > list;//adjacency list
//creates an empty graph
public Graph() {
this.vertices =new ArrayList();
this. edges= new ArrayList();
adjacencyList = new HashMap>();
}
//creates a graph from vertices and edges stored in a list
public Graph(List vertices, Listedges)
{
for(int i=0;i {
addVertex(vertices.get(i));
}
}
//creates adjacency list for each vertex
public void createAdjacencyList( Listedges, int numOfVertices){
for(Road edge:edges)
{
addEdge(edge.getEndPoint1(),edge.getEndPoint2(), numOfVertices, null);
}
}
/**
* Tests the given vertices for null and for membership in the graph.
* @param v1 First vertex to examine.
* @param v2 Second vertex to examine.
* @throws IllegalArgumentException If any vertex is not part of this graph.
* @throws NullPointerException If any vertex is null.
*/
protected void checkVertices(Town v1, Town v2) {
if (!this.containsVertex(v1)) {
throw new IllegalArgumentException();
}
if (!this.containsVertex(v2)) {
throw new IllegalArgumentException();
}
}
@Override
public Road getEdge(Town sourceVertex, Town destinationVertex) {
checkVertices(sourceVertex, destinationVertex);//method 1 for check
if(destinationVertex==null||sourceVertex==null)//check method 2
{
return null;
}
adjacencyList.get(sourceVertex).addAll( edges);
//List edge = List.get(sourceVertex.);
// List edge = adjacencyList.get(sourceVertex);
for (Road e : edges) {
if (e.getEndPoint1().equals(sourceVertex) && e.getEndPoint2().equals(destinationVertex)) {
return e;
}
/* if (e.equals(destinationVertex)) {
return (Road) edge;
}*/
}
// return (Road) edge;
return null;
}
@Override
public Road addEdge(Town sourceVertex, Town destinationVertex, int weight, String description) {
Road e = new Road(sourceVertex, destinationVertex, description);
edges.add((Road) e);
return (Road) e;
/*checkVertices(sourceVertex, destinationVertex);//check 1
if(!containsVertex(sourceVertex)||!containsVertex(destinationVertex))
{
throw new IllegalArgumentException();
}
if(destinationVertex==null||sourceVertex==null)//check method 2
{
throw new NullPointerException();
}
if(containsEdge(sourceVertex, destinationVertex))
{
Road edge = new Road (sourceVertex, destinationVertex, weight, description);
adjacencyList.get(sourceVertex).add(edge);
return edge;
}
//if(edges.get(weight) != null)
else return null;*/
}
@Override
public boolean addVertex(Town v) {
/*if(vertices.size()==0){
vertices.add(v);
}
else {
for (int i = 0; i < vertices.size(); i++) {
if (vertices.get(i).compareTo(v)>0) {
vertices.addAll(i, vertices);
return true;
}
}
vertices.addAll(vertices);
}
return true;*/
adjacencyList.put(v, edges);
if(v==null)
{
throw new NullPointerException();
}
//if specified vertex is not already present add new one
if(!vertices.contains(vertices.equals(v)))
{
vertices.add(v);
edges.addAll(new ArrayList());
return true;
}
else return false;
}
@Override
public boolean containsEdge(Town sourceVertex, Town destinationVertex) {
//List edge = adjacencyList.get(sourceVertex);
for (Road e : edges) {
if (e.getEndPoint1().equals(sourceVertex) && e.getEndPoint2().equals(destinationVertex)) {
return true;
}
}
return false;
/*if(getEdge(sourceVertex, destinationVertex)!=null){
return true;
}
else return false;*/
//return getEdge(sourceVertex, destinationVertex)!=null;
}
@Override
public boolean containsVertex(Town v) {
/*if(v==null)
{
return false;
}
if(vertices.contains(vertices.equals(v))){
return true;
}
else return false;*/
adjacencyList.get(v);
return vertices.contains(v);
}
@Override
public Set edgeSet() {
return null;
// TODO Auto-generated method stub
//return (Set) adjacencyList.get(vertices);
//return new TreeSet();
}
@Override
public Set edgesOf(Town vertex) {
TreeSeth = new TreeSet();
//List edge = adjacencyList.get(vertex);
for (Road e : edges) {
Town f1 = e.getEndPoint1();
Town f2 = e.getEndPoint2();
if (f1.equals(vertex) || f2.equals(vertex)) {
h.add((Road) e);
}
}
return h;
}
@Override
public Road removeEdge(Town sourceVertex, Town destinationVertex, int weight, String description) {
//List edge = adjacencyList.get(sourceVertex);
for (Road e : edges) {
if (((Road) e).getEndPoint1().equals(sourceVertex) && ((Road) e).getEndPoint2().equals(destinationVertex)) {
edges.remove(e);
return (Road) e;
}
}
return null;
}
@Override
public boolean removeVertex(Town v) {
if(v==null)
{
return false;
}
vertices.remove(v);
return false;
}
@Override
public Set vertexSet() {
// TODO Auto-generated method stub
return new TreeSet();
}
@Override
public ArrayList shortestPath(Town sourceVertex, Town destinationVertex) {
// TODO Auto-generated method stub
return null;
}
@Override
public void dijkstraShortestPath(Town sourceVertex) {
// TODO Auto-generated method stub
}
/*public List getVertices() {
return vertices;
}
public void setVertices(List vertices) {
this.vertices = vertices;
}
public List getEdges() {
return edges;
}
public void setEdges(List edges) {
this.edges = edges;
}
public List > getList() {
return list;
}
public void setList(List > list) {
this.list = list;
}
*/
}
Graph INTERFACE
import java.util.*;
/**
* The root interface in the graph hierarchy. A mathematical graph-theory graph
* object G(V,E) contains a set V of vertices and a set
* E of edges. Each edge e=(v1,v2) in E connects vertex v1 to vertex v2.
*
* Through generics, a graph can be typed to specific classes for vertices
* V and edges E. Such a graph can contain
* vertices of type V and all sub-types and Edges of type
* E and all sub-types.
*/
public interface GraphInterface
{
//~ Methods ----------------------------------------------------------------
/**
* Returns an edge connecting source vertex to target vertex if such
* vertices and such edge exist in this graph. Otherwise returns
* null. If any of the specified vertices is null
* returns null
*
* In undirected graphs, the returned edge may have its source and target
* vertices in the opposite order.
*
* @param sourceVertex source vertex of the edge.
* @param destinationVertex target vertex of the edge.
*
* @return an edge connecting source vertex to target vertex.
*/
public E getEdge(V sourceVertex, V destinationVertex);
/**
* Creates a new edge in this graph, going from the source vertex to the
* target vertex, and returns the created edge.
*
* The source and target vertices must already be contained in this
* graph. If they are not found in graph IllegalArgumentException is
* thrown.
*
*
* @param sourceVertex source vertex of the edge.
* @param destinationVertex target vertex of the edge.
* @param weight weight of the edge
* @param description description for edge
*
* @return The newly created edge if added to the graph, otherwise null.
*
* @throws IllegalArgumentException if source or target vertices are not
* found in the graph.
* @throws NullPointerException if any of the specified vertices is null.
*/
public E addEdge(V sourceVertex, V destinationVertex, int weight, String description);
/**
* Adds the specified vertex to this graph if not already present. More
* formally, adds the specified vertex, v, to this graph if
* this graph contains no vertex u such that
* u.equals(v). If this graph already contains such vertex, the call
* leaves this graph unchanged and returns false. In combination
* with the restriction on constructors, this ensures that graphs never
* contain duplicate vertices.
*
* @param v vertex to be added to this graph.
*
* @return true if this graph did not already contain the specified
* vertex.
*
* @throws NullPointerException if the specified vertex is null.
*/
public boolean addVertex(V v);
/**
* Returns true if and only if this graph contains an edge going
* from the source vertex to the target vertex. In undirected graphs the
* same result is obtained when source and target are inverted. If any of
* the specified vertices does not exist in the graph, or if is
* null, returns false.
*
* @param sourceVertex source vertex of the edge.
* @param destinationVertex target vertex of the edge.
*
* @return true if this graph contains the specified edge.
*/
public boolean containsEdge(V sourceVertex, V destinationVertex);
/**
* Returns true if this graph contains the specified vertex. More
* formally, returns true if and only if this graph contains a
* vertex u such that u.equals(v). If the
* specified vertex is null returns false.
*
* @param v vertex whose presence in this graph is to be tested.
*
* @return true if this graph contains the specified vertex.
*/
public boolean containsVertex(V v);
/**
* Returns a set of the edges contained in this graph. The set is backed by
* the graph, so changes to the graph are reflected in the set. If the graph
* is modified while an iteration over the set is in progress, the results
* of the iteration are undefined.
*
*
* @return a set of the edges contained in this graph.
*/
public Set edgeSet();
/**
* Returns a set of all edges touching the specified vertex (also
* referred to as adjacent vertices). If no edges are
* touching the specified vertex returns an empty set.
*
* @param vertex the vertex for which a set of touching edges is to be
* returned.
*
* @return a set of all edges touching the specified vertex.
*
* @throws IllegalArgumentException if vertex is not found in the graph.
* @throws NullPointerException if vertex is null.
*/
public Set edgesOf(V vertex);
/**
* Removes an edge going from source vertex to target vertex, if such
* vertices and such edge exist in this graph.
*
* If weight >- 1 it must be checked
* If description != null, it must be checked
*
* Returns the edge if removed
* or null otherwise.
*
* @param sourceVertex source vertex of the edge.
* @param destinationVertex target vertex of the edge.
* @param weight weight of the edge
* @param description description of the edge
*
* @return The removed edge, or null if no edge removed.
*/
public E removeEdge(V sourceVertex, V destinationVertex, int weight, String description);
/**
* Removes the specified vertex from this graph including all its touching
* edges if present. More formally, if the graph contains a vertex
* u such that u.equals(v), the call removes all edges
* that touch u and then removes u itself. If no
* such u is found, the call leaves the graph unchanged.
* Returns true if the graph contained the specified vertex. (The
* graph will not contain the specified vertex once the call returns).
*
* If the specified vertex is null returns false.
*
* @param v vertex to be removed from this graph, if present.
*
* @return true if the graph contained the specified vertex;
* false otherwise.
*/
public boolean removeVertex(V v);
/**
* Returns a set of the vertices contained in this graph. The set is backed
* by the graph, so changes to the graph are reflected in the set. If the
* graph is modified while an iteration over the set is in progress, the
* results of the iteration are undefined.
*
*
* @return a set view of the vertices contained in this graph.
*/
public Set vertexSet();
/**
* Find the shortest path from the sourceVertex to the destinationVertex
* call the dijkstraShortestPath with the sourceVertex
* @param sourceVertex starting vertex
* @param destinationVertex ending vertex
* @return An arraylist of Strings that describe the path from sourceVertex
* to destinationVertex
*/
public ArrayList shortestPath(V sourceVertex, V destinationVertex);
/**
* Dijkstra's Shortest Path Method. Internal structures are built which
* hold the ability to retrieve the path, shortest distance from the
* sourceVertex to all the other vertices in the graph, etc.
* @param sourceVertex the vertex to find shortest path from
*
*/
public void dijkstraShortestPath(V sourceVertex);
}
// End Graph.java
Graph TEST
import static org.junit.Assert.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.Set;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
public class GraphTest {
private GraphInterface graph;
private Town[] town;
@Before
public void setUp() throws Exception {
graph = new Graph();
town = new Town[12];
for (int i = 1; i < 12; i++) {
town[i] = new Town("Town_" + i);
graph.addVertex(town[i]);
}
graph.addEdge(town[1], town[2], 2, "Road_1");
graph.addEdge(town[1], town[3], 4, "Road_2");
graph.addEdge(town[1], town[5], 6, "Road_3");
graph.addEdge(town[3], town[7], 1, "Road_4");
graph.addEdge(town[3], town[8], 2, "Road_5");
graph.addEdge(town[4], town[8], 3, "Road_6");
graph.addEdge(town[6], town[9], 3, "Road_7");
graph.addEdge(town[9], town[10], 4, "Road_8");
graph.addEdge(town[8], town[10], 2, "Road_9");
graph.addEdge(town[5], town[10], 5, "Road_10");
graph.addEdge(town[10], town[11], 3, "Road_11");
graph.addEdge(town[2], town[11], 6, "Road_12");
}
@After
public void tearDown() throws Exception {
graph = null;
}
@Test
public void testGetEdge() {
assertEquals(new Road(town[2], town[11],6, "Road_12"), graph.getEdge(town[2], town[11]));
assertEquals(new Road(town[3], town[7],1, "Road_4"), graph.getEdge(town[3], town[7]));
}
@Test
public void testAddEdge() {
assertEquals(false, graph.containsEdge(town[3], town[5]));
graph.addEdge(town[3], town[5], 1, "Road_13");
assertEquals(true, graph.containsEdge(town[3], town[5]));
}
@Test
public void testAddVertex() {
Town newTown = new Town("Town_12");
assertEquals(false, graph.containsVertex(newTown));
graph.addVertex(newTown);
assertEquals(true, graph.containsVertex(newTown));
}
@Test
public void testContainsEdge() {
assertEquals(true, graph.containsEdge(town[2], town[11]));
assertEquals(false, graph.containsEdge(town[3], town[5]));
}
@Test
public void testContainsVertex() {
assertEquals(true, graph.containsVertex(new Town("Town_2")));
assertEquals(false, graph.containsVertex(new Town("Town_12")));
}
@Test
public void testEdgeSet() {
Set roads = graph.edgeSet();
ArrayList roadArrayList = new ArrayList();
for(Road road : roads)
roadArrayList.add(road.getName());
Collections.sort(roadArrayList);
assertEquals("Road_1", roadArrayList.get(0));
assertEquals("Road_10", roadArrayList.get(1));
assertEquals("Road_11", roadArrayList.get(2));
assertEquals("Road_12", roadArrayList.get(3));
assertEquals("Road_2", roadArrayList.get(4));
assertEquals("Road_8", roadArrayList.get(10));
}
@Test
public void testEdgesOf() {
Set roads = graph.edgesOf(town[1]);
ArrayList roadArrayList = new ArrayList();
for(Road road : roads)
roadArrayList.add(road.getName());
Collections.sort(roadArrayList);
assertEquals("Road_1", roadArrayList.get(0));
assertEquals("Road_2", roadArrayList.get(1));
assertEquals("Road_3", roadArrayList.get(2));
}
@Test
public void testEdgesOfSTUDENT() {
fail("Test not implemented yet");
}
@Test
public void testRemoveEdge() {
assertEquals(true, graph.containsEdge(town[2], town[11]));
graph.removeEdge(town[2], town[11], 6, "Road_12");
assertEquals(false, graph.containsEdge(town[2], town[11]));
}
@Test
public void testRemoveEdgeSTUDENT() {
fail("Test not implemented yet");
}
@Test
public void testRemoveVertex() {
assertEquals(true, graph.containsVertex(town[2]));
graph.removeVertex(town[2]);
assertEquals(false, graph.containsVertex(town[2]));
}
@Test
public void testVertexSet() {
Set roads = graph.vertexSet();
assertEquals(true,roads.contains(town[1]));
assertEquals(true, roads.contains(town[10]));
assertEquals(true, roads.contains(town[11]));
assertEquals(true, roads.contains(town[2]));
assertEquals(true, roads.contains(town[3]));
}
@Test
public void testTown_1ToTown_11() {
String beginTown = "Town_1", endTown = "Town_11";
Town beginIndex=null, endIndex=null;
Set towns = graph.vertexSet();
Iterator iterator = towns.iterator();
while(iterator.hasNext())
{
Town town = iterator.next();
if(town.getName().equals(beginTown))
beginIndex = town;
if(town.getName().equals(endTown))
endIndex = town;
}
if(beginIndex != null && endIndex != null)
{
ArrayList path = graph.shortestPath(beginIndex,endIndex);
assertNotNull(path);
assertTrue(path.size() > 0);
assertEquals("Town_1 via Road_1 to Town_2 2 mi",path.get(0).trim());
assertEquals("Town_2 via Road_12 to Town_11 6 mi",path.get(1).trim());
}
else
fail("Town names are not valid");
}
@Test
public void testTown1ToTown_10() {
String beginTown = "Town_1", endTown = "Town_10";
Town beginIndex=null, endIndex=null;
Set towns = graph.vertexSet();
Iterator iterator = towns.iterator();
while(iterator.hasNext())
{
Town town = iterator.next();
if(town.getName().equals(beginTown))
beginIndex = town;
if(town.getName().equals(endTown))
endIndex = town;
}
if(beginIndex != null && endIndex != null)
{
ArrayList path = graph.shortestPath(beginIndex,endIndex);
assertNotNull(path);
assertTrue(path.size() > 0);
assertEquals("Town_1 via Road_2 to Town_3 4 mi",path.get(0).trim());
assertEquals("Town_3 via Road_5 to Town_8 2 mi",path.get(1).trim());
assertEquals("Town_8 via Road_9 to Town_10 2 mi",path.get(2).trim());
}
else
fail("Town names are not valid");
}
@Test
public void testTown_4ToTown_11() {
String beginTown = "Town_4", endTown = "Town_11";
Town beginIndex=null, endIndex=null;
Set towns = graph.vertexSet();
Iterator iterator = towns.iterator();
while(iterator.hasNext())
{
Town town = iterator.next();
if(town.getName().equals(beginTown))
beginIndex = town;
if(town.getName().equals(endTown))
endIndex = town;
}
if(beginIndex != null && endIndex != null)
{
ArrayList path = graph.shortestPath(beginIndex,endIndex);
assertNotNull(path);
assertTrue(path.size() > 0);
assertEquals("Town_4 via Road_6 to Town_8 3 mi",path.get(0).trim());
assertEquals("Town_8 via Road_9 to Town_10 2 mi",path.get(1).trim());
assertEquals("Town_10 via Road_11 to Town_11 3 mi",path.get(2).trim());
}
else
fail("Town names are not valid");
}
@Test
public void testTown_5ToTown_2STUDENT() {
fail("Test not implemented yet");
}
}
ROAD CLASS
import java.util.ArrayList;
public class Road implements Comparable{
private Town endPoint1, endPoint2;
private int weight;//distance between vertices
private String roadName;
/**
* Constructor
* @param source- One town on the road
* @param destination - Another town on the road
* @param degrees - Weight of the edge, i.e., distance from one town to the other
* @param name - Name of the road
*/
public Road(Town source, Town destination, int i, String name) {
super();
this.endPoint1 = source;
this.endPoint2 = destination;
this.roadName=name;
this.weight = i;
}
/**
* Constructor with weight preset at 1
* @param source
* @param destination
* @param name
*/
public Road(Town source, Town destination, String name) {
this.endPoint1=source;
this.endPoint2=destination;
this.weight= 1;
this.roadName=name;
}
public Road(String town1, String town2, int weight, String roadName2) {
this.weight = weight;
}
/**
* @return-the road name
*/
public String getName() {
return roadName;
}
//returns 0 if the road names are the same, a positive or negative number if the road names are not the same
@Override
public int compareTo(Road o) {
if(roadName.compareTo(roadName)>1)
return 1;
//return endPoint1.compareTo(endPoint2);
return 0;
}
/**
* @return- the first town on the road
*/
public Town getEndPoint1() {
return endPoint1;
}
public void setEndPoint1(Town endPoint1) {
this.endPoint1 = endPoint1;
}
/**
* @return- the second town on the road
*/
public Town getEndPoint2() {
return endPoint2;
}
public void setEndPoint2(Town endPoint2) {
this.endPoint2 = endPoint2;
}
public void setName(String name) {
this.roadName = name;
}
/**
* @return-the distance of the road
*/
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return "Edge [source=" + endPoint1 + ", destination=" + endPoint2
+ ", distance=" + weight + "]";
}
@Override
public boolean equals(Object r) {
/*Returns true if each of the ends of the road r is the same as the ends of this road.
Remember that a road that goes from point A to point B is the same as a road that goes
from point B to point A.
* */
//if(r.toString().equals(endPoint1)
if(this.endPoint1.equals(this.endPoint2))
{
//r.getClass();
return true;
}
/*if(this.weight==(o.weight))
{
return 1;
}*/
return super.equals(r);
}
}
TOWN CLASS
import java.util.ArrayList;
/**
* class holds the name of the town and a list of adjacent towns
*
*/
public class Town implements Comparable {
//private ArrayList towns;
private String name;
private Town templateTown;
private int wt;
//constructor
/**
* @param name
*/
public Town(String name) {
this.name=name;
String[] details = name.split(" of ");
String[] names = details[0].split(" ");
}
public Town(Town templateTown) {
this.setTemplateTown(templateTown);
}
@Override
public int hashCode() {
// TODO Auto-generated method stub
return super.hashCode();
}
@Override
public boolean equals(Object obj) {
// TODO Auto-generated method stub
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Town friend = (Town) obj;
if (name != null ? !name.equals(friend.name) : friend.name != null) return false;
// if (lname != null ? !lname.equals(friend.lname) : friend.lname != null) return false;
// return !(hometown != null ? !hometown.equals(friend.hometown) : friend.hometown != null);
return super.equals(obj);
}
/**
* @param name
*/
public void setName(String name) {
this.name = name;
}
/**
* @return
*/
public String getName() {
// TODO Auto-generated method stub
return name;
}
/* (non-Javadoc)
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
@Override
public int compareTo(Town o) {
// TODO Auto-generated method stub
/*if(this.name.equals(o.getName()))
{
return 0;
}
/*if(this.weight==(o.weight))
{
return 1;
}*/
/*else return -1;*/
return name.compareTo(o.getName());
}
public String toString()
{
return name;
}
public Town getTemplateTown() {
return templateTown;
}
public void setTemplateTown(Town templateTown) {
this.templateTown = templateTown;
}
public int getWt() {
return wt;
}
/**
* @param i
*/
public void setWt(int i) {
this.wt=i;
}
/*public ArrayList getTowns() {
return towns;
}
public void setTowns(ArrayList towns) {
this.towns = towns;
}
*/
}
Explanation / Answer
You missed declaring generic class type <E,V> in interface that is first mistake and also declaring interface type declaring in graph class. Remaining are small issues which I made bold for understand.. please check
Graph.java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class Graph implements GraphInterface<Road,Town>//Town (Vertex) , Road(edge)
{
private List<Town> vertices;//Store vertices
private Map adjacencyList ; // [vertices] -> [edge]
private List<Road> edges;//store edges
//private List > list;//adjacency list
//creates an empty graph
public Graph() {
this.vertices = new ArrayList();
this.edges = new ArrayList<Road>();
adjacencyList = new HashMap<> ();
}
//creates a graph from vertices and edges stored in a list
public Graph(List<Town> vertices, List edges) {
for (int i = 0; i <vertices.size();i++) {
addVertex(vertices.get(i));
}
}
//creates adjacency list for each vertex
public void createAdjacencyList(List<Road> edges, int numOfVertices) {
for (int i = 0; i <edges.size();i++) {
addEdge(edges.get(i).getEndPoint1(), edges.get(i).getEndPoint2(), numOfVertices, null);
}
}
/**
* Tests the given vertices for null and for membership in the graph.
*
* @param v1 First vertex to examine.
* @param v2 Second vertex to examine.
* @throws IllegalArgumentException If any vertex is not part of this graph.
* @throws NullPointerException If any vertex is null.
*/
protected void checkVertices(Town v1, Town v2) {
if (!this.containsVertex(v1)) {
throw new IllegalArgumentException();
}
if (!this.containsVertex(v2)) {
throw new IllegalArgumentException();
}
}
@Override
public Road getEdge(Town sourceVertex, Town destinationVertex) {
checkVertices(sourceVertex, destinationVertex);//method 1 for check
if (destinationVertex == null || sourceVertex == null)//check method 2
{
return null;
}
edges.add((Road) adjacencyList.get(sourceVertex));
//List edge = List.get(sourceVertex.);
// List edge = adjacencyList.get(sourceVertex);
for (Road e : edges) {
if (e.getEndPoint1().equals(sourceVertex) && e.getEndPoint2().equals(destinationVertex)) {
return e;
}
/* if (e.equals(destinationVertex)) {
return (Road) edge;
}*/
}
// return (Road) edge;
return null;
}
@Override
public Road addEdge(Town sourceVertex, Town destinationVertex, int weight, String description) {
Road e = new Road(sourceVertex, destinationVertex, description);
edges.add((Road) e);
return (Road) e;
/*checkVertices(sourceVertex, destinationVertex);//check 1
if(!containsVertex(sourceVertex)||!containsVertex(destinationVertex))
{
throw new IllegalArgumentException();
}
if(destinationVertex==null||sourceVertex==null)//check method 2
{
throw new NullPointerException();
}
if(containsEdge(sourceVertex, destinationVertex))
{
Road edge = new Road (sourceVertex, destinationVertex, weight, description);
adjacencyList.get(sourceVertex).add(edge);
return edge;
}
//if(edges.get(weight) != null)
else return null;*/
}
@Override
public boolean addVertex(Town v) {
/*if(vertices.size()==0){
vertices.add(v);
}
else {
for (int i = 0; i < vertices.size(); i++) {
if (vertices.get(i).compareTo(v)>0) {
vertices.addAll(i, vertices);
return true;
}
}
vertices.addAll(vertices);
}
return true;*/
adjacencyList.put(v, edges);
if (v == null) {
throw new NullPointerException();
}
//if specified vertex is not already present add new one
if (!vertices.contains(vertices.equals(v))) {
vertices.add(v);
edges.addAll(new ArrayList());
return true;
} else {
return false;
}
}
@Override
public boolean containsEdge(Town sourceVertex, Town destinationVertex) {
//List edge = adjacencyList.get(sourceVertex);
for (Road e : edges) {
if (e.getEndPoint1().equals(sourceVertex) && e.getEndPoint2().equals(destinationVertex)) {
return true;
}
}
return false;
/*if(getEdge(sourceVertex, destinationVertex)!=null){
return true;
}
else return false;*/
//return getEdge(sourceVertex, destinationVertex)!=null;
}
@Override
public boolean containsVertex(Town v) {
/*if(v==null)
{
return false;
}
if(vertices.contains(vertices.equals(v))){
return true;
}
else return false;*/
adjacencyList.get(v);
return vertices.contains(v);
}
@Override
public Set edgeSet() {
return null;
// TODO Auto-generated method stub
//return (Set) adjacencyList.get(vertices);
//return new TreeSet();
}
@Override
public Set edgesOf(Town vertex) {
TreeSet h = new TreeSet();
//List edge = adjacencyList.get(vertex);
for (Road e : edges) {
Town f1 = e.getEndPoint1();
Town f2 = e.getEndPoint2();
if (f1.equals(vertex) || f2.equals(vertex)) {
h.add((Road) e);
}
}
return h;
}
@Override
public Road removeEdge(Town sourceVertex, Town destinationVertex, int weight, String description) {
//List edge = adjacencyList.get(sourceVertex);
for (Road e : edges) {
if (((Road) e).getEndPoint1().equals(sourceVertex) && ((Road) e).getEndPoint2().equals(destinationVertex)) {
edges.remove(e);
return (Road) e;
}
}
return null;
}
@Override
public boolean removeVertex(Town v) {
if (v == null) {
return false;
}
vertices.remove(v);
return false;
}
@Override
public Set vertexSet() {
// TODO Auto-generated method stub
return new TreeSet();
}
@Override
public ArrayList shortestPath(Town sourceVertex, Town destinationVertex) {
// TODO Auto-generated method stub
return null;
}
@Override
public void dijkstraShortestPath(Town sourceVertex) {
// TODO Auto-generated method stub
}
/*public List getVertices() {
return vertices;
}
public void setVertices(List vertices) {
this.vertices = vertices;
}
public List getEdges() {
return edges;
}
public void setEdges(List edges) {
this.edges = edges;
}
public List > getList() {
return list;
}
public void setList(List > list) {
this.list = list;
}
*/
}
---------------------------------------------------------------------------------------------------------------------------------------------------
Interface
import java.util.*;
/**
* The root interface in the graph hierarchy. A mathematical graph-theory graph
* object G(V,E) contains a set V of vertices and a set E of edges. Each edge
* e=(v1,v2) in E connects vertex v1 to vertex v2.
*
* Through generics, a graph can be typed to specific classes for vertices V and
* edges E. Such a graph can contain vertices of type V and all sub-types and
* Edges of type E and all sub-types.
*/
public interface GraphInterface<E,V> {
//~ Methods ----------------------------------------------------------------
/**
* Returns an edge connecting source vertex to target vertex if such
* vertices and such edge exist in this graph. Otherwise returns null. If
* any of the specified vertices is null returns null
*
* In undirected graphs, the returned edge may have its source and target
* vertices in the opposite order.
*
* @param sourceVertex source vertex of the edge.
* @param destinationVertex target vertex of the edge.
*
* @return an edge connecting source vertex to target vertex.
*/
public E getEdge(V sourceVertex, V destinationVertex);
/**
* Creates a new edge in this graph, going from the source vertex to the
* target vertex, and returns the created edge.
*
* The source and target vertices must already be contained in this graph.
* If they are not found in graph IllegalArgumentException is thrown.
*
*
* @param sourceVertex source vertex of the edge.
* @param destinationVertex target vertex of the edge.
* @param weight weight of the edge
* @param description description for edge
*
* @return The newly created edge if added to the graph, otherwise null.
*
* @throws IllegalArgumentException if source or target vertices are not
* found in the graph.
* @throws NullPointerException if any of the specified vertices is null.
*/
public E addEdge(V sourceVertex, V destinationVertex, int weight, String description);
/**
* Adds the specified vertex to this graph if not already present. More
* formally, adds the specified vertex, v, to this graph if this graph
* contains no vertex u such that u.equals(v). If this graph already
* contains such vertex, the call leaves this graph unchanged and returns
* false. In combination with the restriction on constructors, this ensures
* that graphs never contain duplicate vertices.
*
* @param v vertex to be added to this graph.
*
* @return true if this graph did not already contain the specified vertex.
*
* @throws NullPointerException if the specified vertex is null.
*/
public boolean addVertex(V v);
/**
* Returns true if and only if this graph contains an edge going from the
* source vertex to the target vertex. In undirected graphs the same result
* is obtained when source and target are inverted. If any of the specified
* vertices does not exist in the graph, or if is null, returns false.
*
* @param sourceVertex source vertex of the edge.
* @param destinationVertex target vertex of the edge.
*
* @return true if this graph contains the specified edge.
*/
public boolean containsEdge(V sourceVertex, V destinationVertex);
/**
* Returns true if this graph contains the specified vertex. More formally,
* returns true if and only if this graph contains a vertex u such that
* u.equals(v). If the specified vertex is null returns false.
*
* @param v vertex whose presence in this graph is to be tested.
*
* @return true if this graph contains the specified vertex.
*/
public boolean containsVertex(V v);
/**
* Returns a set of the edges contained in this graph. The set is backed by
* the graph, so changes to the graph are reflected in the set. If the graph
* is modified while an iteration over the set is in progress, the results
* of the iteration are undefined.
*
*
* @return a set of the edges contained in this graph.
*/
public Set edgeSet();
/**
* Returns a set of all edges touching the specified vertex (also referred
* to as adjacent vertices). If no edges are touching the specified vertex
* returns an empty set.
*
* @param vertex the vertex for which a set of touching edges is to be
* returned.
*
* @return a set of all edges touching the specified vertex.
*
* @throws IllegalArgumentException if vertex is not found in the graph.
* @throws NullPointerException if vertex is null.
*/
public Set edgesOf(V vertex);
/**
* Removes an edge going from source vertex to target vertex, if such
* vertices and such edge exist in this graph.
*
* If weight >- 1 it must be checked If description != null, it must be
* checked
*
* Returns the edge if removed or null otherwise.
*
* @param sourceVertex source vertex of the edge.
* @param destinationVertex target vertex of the edge.
* @param weight weight of the edge
* @param description description of the edge
*
* @return The removed edge, or null if no edge removed.
*/
public E removeEdge(V sourceVertex, V destinationVertex, int weight, String description);
/**
* Removes the specified vertex from this graph including all its touching
* edges if present. More formally, if the graph contains a vertex u such
* that u.equals(v), the call removes all edges that touch u and then
* removes u itself. If no such u is found, the call leaves the graph
* unchanged. Returns true if the graph contained the specified vertex. (The
* graph will not contain the specified vertex once the call returns).
*
* If the specified vertex is null returns false.
*
* @param v vertex to be removed from this graph, if present.
*
* @return true if the graph contained the specified vertex; false
* otherwise.
*/
public boolean removeVertex(V v);
/**
* Returns a set of the vertices contained in this graph. The set is backed
* by the graph, so changes to the graph are reflected in the set. If the
* graph is modified while an iteration over the set is in progress, the
* results of the iteration are undefined.
*
*
* @return a set view of the vertices contained in this graph.
*/
public Set vertexSet();
/**
* Find the shortest path from the sourceVertex to the destinationVertex
* call the dijkstraShortestPath with the sourceVertex
*
* @param sourceVertex starting vertex
* @param destinationVertex ending vertex
* @return An arraylist of Strings that describe the path from sourceVertex
* to destinationVertex
*/
public ArrayList shortestPath(V sourceVertex, V destinationVertex);
/**
* Dijkstra's Shortest Path Method. Internal structures are built which hold
* the ability to retrieve the path, shortest distance from the sourceVertex
* to all the other vertices in the graph, etc.
*
* @param sourceVertex the vertex to find shortest path from
*
*/
public void dijkstraShortestPath(V sourceVertex);
}