package graphs;
import java.util.ArrayList;
import java.util.HashMap;
public class Graph {
private class vertex{
HashMap<String, Integer> nbrs = new HashMap<>();
}
HashMap<String, vertex> vtces;
public Graph() {
vtces=new HashMap<>();
}
public int numVertex() {
return this.vtces.size();
}
public boolean containsVertex(String vname) {
return this.vtces.containsKey(vname);
}
public void addVertex(String vname) {
vertex vtx = new vertex();
vtces.put(vname, vtx);
}
public void removeVertex(String vname) {
vertex vtx = vtces.get(vname);
ArrayList<String> keys = new ArrayList<>(vtx.nbrs.keySet());
for(String key: keys) {
vertex nbrvtx = vtces.get(key);
nbrvtx.nbrs.remove(vname);
}
vtces.remove(vname);
}
public int numEdges() {
int count=0;
ArrayList<String> keys = new ArrayList<>(vtces.keySet());
for(String key:keys) {
vertex vtx = vtces.get(key);
count = count + vtx.nbrs.size();
}
return count/2;
}
public boolean containsEdge(String vname1 , String vname2) {
vertex vtx1 = vtces.get(vname1);
vertex vtx2 = vtces.get(vname2);
if(vtx1==null || vtx2==null || !vtx1.nbrs.containsKey(vname2)) {
return false;
}
return true;
}
public void addEdge(String vname1,String vname2,int cost) {
vertex vtx1 = vtces.get(vname1); //2K
vertex vtx2 = vtces.get(vname2); //4K
if(vtx1==null || vtx2==null || vtx1.nbrs.containsKey(vname2)) {
return ;
}
vtx1.nbrs.put(vname2, cost); //2K nbrs Put C with a given Cost
vtx2.nbrs.put(vname1, cost); //4K nbrs Put A with a given Cost
}
public void removeEdge(String vname1,String vname2) {
vertex vtx1 = vtces.get(vname1); //2K
vertex vtx2 = vtces.get(vname2); //4K
if(vtx1==null || vtx2==null || !vtx1.nbrs.containsKey(vname2)) {
return ;
}
vtx1.nbrs.remove(vname2); //2K nbrs remove C
vtx2.nbrs.remove(vname1); //4K nbrs remove A
}
public void display() {
System.out.println("-------------------------------------------------------------------------------------------------------------------");
ArrayList<String> keys = new ArrayList<>(vtces.keySet());
for(String key: keys) {
vertex vtx=vtces.get(key);
System.out.println(key+" : "+vtx.nbrs);
}
System.out.println("-------------------------------------------------------------------------------------------------------------------");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Graph graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");
graph.addVertex("G");
graph.addEdge("A", "B", 2);
graph.addEdge("A", "D", 3);
graph.addEdge("B", "C", 1);
graph.addEdge("C", "D", 8);
graph.addEdge("D", "E", 10);
graph.addEdge("E", "F", 45);
graph.addEdge("E", "G", 7);
graph.addEdge("F", "G", 18);
graph.display();
System.out.println(graph.numVertex());
System.out.println(graph.numEdges());
System.out.println(graph.containsEdge("A"," D"));
System.out.println(graph.containsEdge("E"," F"));
graph.removeEdge("A", "B");
graph.display();
graph.removeVertex("F");
graph.display();
graph.addVertex("F");
graph.display();
graph.addEdge("F", "A", 10);
graph.display();
}
}