Desperately need addEdge function for my graph, everytime I wish to add a vertex
ID: 3831250 • Letter: D
Question
Desperately need addEdge function for my graph, everytime I wish to add a vertex that already exists it overwrite. For instance I might need to add a new vertex to one that already exists and im struggling with the codes for this
class Vertex implements Comparable<Vertex> {
private Integer id;
private Integer distance;
private Integer x;
private Integer y;
public Vertex(Integer id, Integer distance) {
super();
this.id = id;
this.distance = distance;
}
public Integer getId() {
return id;
}
public Integer getDistance() {
return distance;
}
public void setId(Integer id) {
this.id = id;
}
public void setDistance(Integer distance) {
this.distance = distance;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((distance == null) ? 0 : distance.hashCode());
result = prime * result + ((id == null) ? 0 : id.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Vertex other = (Vertex) obj;
if (distance == null) {
if (other.distance != null)
return false;
} else if (!distance.equals(other.distance))
return false;
if (id == null) {
if (other.id != null)
return false;
} else if (!id.equals(other.id))
return false;
return true;
}
@Override
public String toString() {
return "Vertex [id=" + id + ", distance=" + distance + "]";
}
@Override
public int compareTo(Vertex o) {
if (this.distance < o.distance)
return -1;
else if (this.distance > o.distance)
return 1;
else
return this.getId().compareTo(o.getId());
}
}
class Graph{
private final Map<Integer, List<Vertex>> vertices;
public Graph() {
this.vertices = new HashMap<Integer, List<Vertex>>();
}
public void addVertex(int character, List<Vertex> vertex) {
this.vertices.put(character, vertex);
}
public void createVertex(int character){
this.vertices.put(character, null);
}
public Set<Integer> getSet(){
return vertices.keySet();
}
public List<Vertex> getKeyValues(Object key){
return vertices.get(key);
}
public Collection<List<Vertex>> getValues(){
return vertices.values();
}
//custom
public boolean containsVertex(int vertex) {
return vertices.containsKey(vertex);
}
public void removeVertex(int vertex){
if (!this.vertices.containsKey(vertex)) {
throw new IllegalArgumentException("Vertex doesn't exist.");
}
this.vertices.remove(vertex);
for(Integer i: this.getAllVertices() ){
this.vertices.get(i).remove(vertex);
}
}
public Set<Integer> getAllVertices() {
return this.vertices.keySet();
}
/*
public boolean addEdge(List<Vertex> vertex1, int vertex2) {
return addEdge(vertex1, vertex2, 0);
}
public boolean addEdge(List<Vertex> vertex1, int vertex2, int weight) {
if (!containsVertex(vertex1) || !containsVertex(vertex2)) {
throw new RuntimeException("Vertex does not exist");
}
// add the edge
List<Vertex> node1 = getNode(vertex1);
List<Vertex> node2 = getNode(vertex2);
return node1.addEdge(node2, weight);
}
private List<Vertex> getNode(int value) {
return vertices.get(value);
}
*/
public List<Integer> getShortestPath(int start, int finish) {
final Map<Integer, Integer> distances = new HashMap<Integer, Integer>();
final Map<Integer, Vertex> previous = new HashMap<Integer, Vertex>();
PriorityQueue<Vertex> nodes = new PriorityQueue<Vertex>();
for(Integer vertex : vertices.keySet()) {
if (vertex == start) {
distances.put(vertex, 0);
nodes.add(new Vertex(vertex, 0));
} else {
distances.put(vertex, Integer.MAX_VALUE);
nodes.add(new Vertex(vertex, Integer.MAX_VALUE));
}
previous.put(vertex, null);
}
while (!nodes.isEmpty()) {
Vertex smallest = nodes.poll();
if (smallest.getId() == finish) {
final ArrayList<Integer> path = new ArrayList<Integer>();
while (previous.get(smallest.getId()) != null) {
path.add(smallest.getId());
smallest = previous.get(smallest.getId());
}
return path;
}
if (distances.get(smallest.getId()) == Integer.MAX_VALUE) {
break;
}
for (Vertex neighbor : vertices.get(smallest.getId())) {
Integer alt = distances.get(smallest.getId()) + neighbor.getDistance();
if (alt < distances.get(neighbor.getId())) {
distances.put(neighbor.getId(), alt);
previous.put(neighbor.getId(), smallest);
forloop:
for(Vertex n : nodes) {
if (n.getId() == neighbor.getId()) {
nodes.remove(n);
n.setDistance(alt);
nodes.add(n);
break forloop;
}
}
}
}
}
ArrayList<Integer> list = new ArrayList<Integer>(distances.keySet());
return list;
}
public ArrayList<Integer> reverse(ArrayList<Integer> list) {
for(int i = 0, j = list.size() - 1; i < j; i++) {
list.add(i, list.remove(j));
}
return list;
}
}
Explanation / Answer
The code you have given is dijkstras algorithm and the code you expected is given below and please execute the code it will give you the correct results as you expected.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
public class Dijkstras {
public static void main(String[] args) {
Graph g = new Graph();
g.addVertex('A', Arrays.asList(new Vertex('B', 7), new Vertex('C', 8)));
g.addVertex('B', Arrays.asList(new Vertex('A', 7), new Vertex('F', 2)));
g.addVertex('C', Arrays.asList(new Vertex('A', 8), new Vertex('F', 6), new Vertex('G', 4)));
g.addVertex('D', Arrays.asList(new Vertex('F', 8)));
g.addVertex('E', Arrays.asList(new Vertex('H', 1)));
g.addVertex('F', Arrays.asList(new Vertex('B', 2), new Vertex('C', 6), new Vertex('D', 8), new Vertex('G', 9), new Vertex('H', 3)));
g.addVertex('G', Arrays.asList(new Vertex('C', 4), new Vertex('F', 9)));
g.addVertex('H', Arrays.asList(new Vertex('E', 1), new Vertex('F', 3)));
System.out.println(g.getShortestPath('A', 'H'));
}
}
class Vertex implements Comparable<Vertex> {
private Character id;
private Integer distance;
public Vertex(Character id, Integer distance) {
super();
this.id = id;
this.distance = distance;
}
public Character getId() {
return id;
}
public Integer getDistance() {
return distance;
}
public void setId(Character id) {
this.id = id;
}
public void setDistance(Integer distance) {
this.distance = distance;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((distance == null) ? 0 : distance.hashCode());
result = prime * result + ((id == null) ? 0 : id.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Vertex other = (Vertex) obj;
if (distance == null) {
if (other.distance != null)
return false;
} else if (!distance.equals(other.distance))
return false;
if (id == null) {
if (other.id != null)
return false;
} else if (!id.equals(other.id))
return false;
return true;
}
@Override
public String toString() {
return "Vertex [id=" + id + ", distance=" + distance + "]";
}
@Override
public int compareTo(Vertex o) {
if (this.distance < o.distance)
return -1;
else if (this.distance > o.distance)
return 1;
else
return this.getId().compareTo(o.getId());
}
}
class Graph {
private final Map<Character, List<Vertex>> vertices;
public Graph() {
this.vertices = new HashMap<Character, List<Vertex>>();
}
public void addVertex(Character character, List<Vertex> vertex) {
this.vertices.put(character, vertex);
}
public List<Character> getShortestPath(Character start, Character finish) {
final Map<Character, Integer> distances = new HashMap<Character, Integer>();
final Map<Character, Vertex> previous = new HashMap<Character, Vertex>();
PriorityQueue<Vertex> nodes = new PriorityQueue<Vertex>();
for(Character vertex : vertices.keySet()) {
if (vertex == start) {
distances.put(vertex, 0);
nodes.add(new Vertex(vertex, 0));
} else {
distances.put(vertex, Integer.MAX_VALUE);
nodes.add(new Vertex(vertex, Integer.MAX_VALUE));
}
previous.put(vertex, null);
}
while (!nodes.isEmpty()) {
Vertex smallest = nodes.poll();
if (smallest.getId() == finish) {
final List<Character> path = new ArrayList<Character>();
while (previous.get(smallest.getId()) != null) {
path.add(smallest.getId());
smallest = previous.get(smallest.getId());
}
return path;
}
if (distances.get(smallest.getId()) == Integer.MAX_VALUE) {
break;
}
for (Vertex neighbor : vertices.get(smallest.getId())) {
Integer alt = distances.get(smallest.getId()) + neighbor.getDistance();
if (alt < distances.get(neighbor.getId())) {
distances.put(neighbor.getId(), alt);
previous.put(neighbor.getId(), smallest);
forloop:
for(Vertex n : nodes) {
if (n.getId() == neighbor.getId()) {
nodes.remove(n);
n.setDistance(alt);
nodes.add(n);
break forloop;
}
}
}
}
}
return new ArrayList<Character>(distances.keySet());
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.