package exercises;
import java.util.*;
/**
* Undirected Weighted Graph
*/
public class UWGraph {
private final String NA = "NA";
private final String NEIGHBOUR = "NEIGHBOUR";
private HashMap vertexMap = new HashMap<>();
private List vertices = new ArrayList<>();
public Vertex addVertex(String key) {
return this.addVertex(key, null);
}
public synchronized Vertex addVertex(String key, HashMap payload) {
if(vertexMap.containsKey(key)) return this.getVertex(key);
Vertex vertex = new Vertex(this.vertices.size() + 1, key, payload);
this.vertices.add(vertex);
this.vertexMap.put(key, vertex.getId());
return vertex;
}
public void addEdge(Edge e, Vertex start, Vertex end) {
if(this.vertexMap.containsKey(start.getKey()) && this.vertexMap.containsKey(end.getKey())) {
this.getVertex(start.getKey()).addAdjacent(end.getId(), e.getWeight());
this.getVertex(end.getKey()).addAdjacent(start.getId(), e.getWeight());
}
}
public int totalVertices() {
return this.vertices.size();
}
public int degree(String vertex) {
if(!this.hasVertex(vertex)) return 0;
return this.getVertex(vertex).degree();
}
public boolean hasVertex(String key) {
return this.vertexMap.containsKey(key);
}
public boolean hasEdge(String start, String end) {
return this.hasVertex(start) && this.hasVertex(end) &&
this.getVertex(start).hasEdgeTo(this.getVertexId(end));
}
public String getEdges(String vertex) {
return this.getVertex(vertex).toString();
}
public void dfs(String key) {
Vertex v = this.getVertex(key);
Stack<int[]> children = new Stack<>();
List visited = new ArrayList<>();
if(v == null) return;
List<int[]> adjacents = v.getAdjacents();
if(adjacents == null || adjacents.size() <= 0) return;
children.addAll(adjacents);
while(!children.isEmpty()) {
int vertex = children.pop()[0] - 1;
if(visited.contains(vertex)) continue;
visited.add(vertex); System.out.println("Visited : " + vertex);
List<int[]> childs = this.vertices.get(vertex).getAdjacents();
if(childs != null && childs.size() > 0) children.addAll(childs);
}
}
public void bfs(String key) {
Vertex v = this.getVertex(key);
Queue<int[]> children = new LinkedList<>();
List visited = new ArrayList<>();
if(v == null) return;
List<int[]> adjacents = v.getAdjacents();
if(adjacents == null || adjacents.size() <= 0) return;
children.addAll(adjacents);
while(!children.isEmpty()) {
int vertex = children.poll()[0] - 1;
if(visited.contains(vertex)) continue;
visited.add(vertex); System.out.println("Visited : " + vertex);
List<int[]> childs = this.vertices.get(vertex).getAdjacents();
if(childs != null && childs.size() > 0) children.addAll(childs);
}
}
private Vertex getVertex(String key) {
return this.vertices.get(this.vertexMap.get(key) - 1);
}
private int getVertexId(String key) {
return this.getVertex(key).getId();
}
}
class Vertex {
private int id;
private String key;
private HashMap payload;
private List<int[]> adjacents;
Vertex(int id, String key, HashMap payload) {
this.id = id;
this.key = key;
this.payload = payload;
this.adjacents = new ArrayList<int[]>();
}
List<int[]> getAdjacents() {
return this.adjacents;
}
String getKey() {
return key;
}
void setKey(String key) {
this.key = key;
}
int getId() {
return id;
}
void setId(int id) {
this.id = id;
}
HashMap getPayload() {
return payload;
}
void setPayload(HashMap payload) {
this.payload = payload;
}
void addAdjacent(int vertex, int weight) {
if(!this.hasEdgeTo(vertex)) this.adjacents.add(new int[] { vertex, weight });
}
int degree() {
if(this.adjacents == null || this.adjacents.size() <= 0) return 0;
return this.adjacents.size();
}
boolean hasEdgeTo(int vertex) {
/**
* Use Bloomfilter to check for FALSE_POSITIVE and proceed to avoid linear search
*/
if(this.adjacents == null || this.adjacents.size() <= 0) return false;
for(int[] adjacent : this.adjacents) {
if(adjacent[0] == vertex) return true;
}
return false;
}
@Override
public String toString() {
if(this.adjacents == null || this.adjacents.size() <= 0) return super.toString();
StringBuilder output = new StringBuilder();
output.append(this.getKey() + ":" + "{");
for(int[] adjacent : this.adjacents) {
output.append(adjacent[0] - 1 + " ");
}
output.append("}");
return output.toString();
}
}
class Edge {
private String key;
private int weight;
Edge(String key, int weight) {
this.key = key;
this.weight = weight;
}
int getWeight() {
return weight;
}
void setWeight(int weight) {
this.weight = weight;
}
String getKey() {
return key;
}
void setKey(String key) {
this.key = key;
}
}
/**
* [ [1, 6, 8],
[0, 4, 6, 9],
[4, 6],
[4, 5, 8],
[1, 2, 3, 5, 9],
[3, 4],
[0, 1, 2],
[8, 9],
[0, 3, 7],
[1, 4, 7]
]
*/
public static void demoGraph() {
UWGraph graph = new UWGraph();
Vertex v0 = graph.addVertex("0"); Vertex v1 = graph.addVertex("1"); Vertex v2 = graph.addVertex("2");
Vertex v3 = graph.addVertex("3"); Vertex v4 = graph.addVertex("4"); Vertex v5 = graph.addVertex("5");
Vertex v6 = graph.addVertex("6"); Vertex v7 = graph.addVertex("7"); Vertex v8 = graph.addVertex("8");
Vertex v9 = graph.addVertex("9");
graph.addEdge(new Edge("01", 1), v0, v1); graph.addEdge(new Edge("06", 6), v0, v6); graph.addEdge(new Edge("08", 8), v0, v8);
graph.addEdge(new Edge("10", 10), v1, v0); graph.addEdge(new Edge("14", 14), v1, v4); graph.addEdge(new Edge("16", 16), v1, v6);
graph.addEdge(new Edge("19", 19), v1, v9);
graph.addEdge(new Edge("24", 24), v2, v4); graph.addEdge(new Edge("26", 26), v2, v6);
graph.addEdge(new Edge("34", 34), v3, v4); graph.addEdge(new Edge("35", 35), v3, v5); graph.addEdge(new Edge("38", 38), v3, v8);
graph.addEdge(new Edge("41", 41), v4, v1); graph.addEdge(new Edge("42", 42), v4, v2); graph.addEdge(new Edge("43", 43), v4, v3);
graph.addEdge(new Edge("45", 45), v4, v5); graph.addEdge(new Edge("49", 49), v4, v9);
graph.addEdge(new Edge("53", 53), v5, v3); graph.addEdge(new Edge("54", 54), v5, v4);
graph.addEdge(new Edge("60", 60), v6, v0); graph.addEdge(new Edge("61", 61), v6, v1); graph.addEdge(new Edge("62", 62), v6, v2);
graph.addEdge(new Edge("78", 78), v7, v8); graph.addEdge(new Edge("79", 79), v7, v9);
graph.addEdge(new Edge("80", 80), v8, v0); graph.addEdge(new Edge("83", 83), v8, v3); graph.addEdge(new Edge("87", 87), v8, v7);
graph.addEdge(new Edge("91", 91), v9, v1); graph.addEdge(new Edge("94", 94), v9, v4); graph.addEdge(new Edge("97", 97), v9, v7);
System.out.println("Vertex 0, Degree :" + graph.degree(v0.getKey()) + ", Edges : " + graph.getEdges(v0.getKey()));
System.out.println("Vertex 1, Degree :" + graph.degree(v1.getKey()) + ", Edges : " + graph.getEdges(v1.getKey()));
System.out.println("Vertex 2, Degree :" + graph.degree(v2.getKey()) + ", Edges : " + graph.getEdges(v2.getKey()));
System.out.println("Vertex 3, Degree :" + graph.degree(v3.getKey()) + ", Edges : " + graph.getEdges(v3.getKey()));
System.out.println("Vertex 4, Degree :" + graph.degree(v4.getKey()) + ", Edges : " + graph.getEdges(v4.getKey()));
System.out.println("Vertex 5, Degree :" + graph.degree(v5.getKey()) + ", Edges : " + graph.getEdges(v5.getKey()));
System.out.println("Vertex 6, Degree :" + graph.degree(v6.getKey()) + ", Edges : " + graph.getEdges(v6.getKey()));
System.out.println("Vertex 7, Degree :" + graph.degree(v7.getKey()) + ", Edges : " + graph.getEdges(v7.getKey()));
System.out.println("Vertex 8, Degree :" + graph.degree(v8.getKey()) + ", Edges : " + graph.getEdges(v8.getKey()));
System.out.println("Vertex 9, Degree :" + graph.degree(v9.getKey()) + ", Edges : " + graph.getEdges(v9.getKey()));
//graph.dfs("0");
graph.bfs("0");
}
