import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Graph {
private Set<Integer> marked = new HashSet<>();
private Map<Integer, Set<Integer>> neighbors = new HashMap<>();
private Integer[] edgeTo;
private Integer start;
private int count = 0;
public Set<Integer> getPoints() {
return neighbors.keySet();
}
public int size() {
return getPoints().size();
}
public long edgeSize() {
return neighbors.values().stream().collect(Collectors.summingLong(Set::size))/2;
}
public void addEdge(int a, int b) {
neighbors.computeIfAbsent(a, k -> new HashSet<Integer>()).add(b);
neighbors.computeIfAbsent(b, k -> new HashSet<Integer>()).add(a);
}
public void dfsPathSearch(Integer start) {
this.start = start;
edgeTo = new Integer[this.size()];
dfs(start);
}
private void dfs(Integer v) {
marked.add(v);
for(Integer w : neighbors.get(v)) {
if(!marked.contains(w)) {
edgeTo[w] = v;
dfs(w);
}
}
}
public void bfsPath(Integer s) {
this.start = s;
edgeTo = new Integer[this.size()];
Queue<Integer> queue = new LinkedList<>();
marked.add(s);
queue.add(s);
while(!queue.isEmpty()) {
Integer v = queue.poll();
for(Integer w : neighbors.get(v)) {
if(!marked.contains(w)) {
marked.add(w);
edgeTo[w] = v;
queue.add(w);
}
}
}
}
private void printPath(Integer end) {
if(!marked.contains(end)) {
System.out.println("//point not reachable " + end);
}
Stack<Integer> stack = new Stack<>();
for(Integer i = end; !i.equals(start); i = edgeTo[i]) {
stack.push(i);
}
stack.push(start);
Integer i = stack.pop();
Integer j = null;
while(!stack.isEmpty()) {
j = stack.pop();
System.out.println(i +"--" + j + "[label=" + (count++) + ", color=red,penwidth=3.0];");
i = j;
}
}
public static void main(String...args) {
Graph g = new Graph();
//change the number of points and edges here.
for(int i = 0; i < 7; i++) {
g.addEdge(i, i + 1);
g.addEdge(i, i + 2);
}
for(int i = 15; i < 17; i++) {
g.addEdge(i, i+1);
}
g.addEdge(19, 19);
System.out.println("strict graph {");
g.neighbors.keySet().stream().forEach(i ->
{
Stream.of(g.neighbors.get(i)).flatMap(j -> j.stream())
.forEach(k -> System.out.println(i + "--" + k + ";"));
});
//change the start point and goal point here
//g.dfsPathSearch(3);
g.bfsPath(3);
g.printPath(6);
System.out.println("}");
System.out.println("number of points: " + g.size());
System.out.println("number of edges: " + g.edgeSize());
System.out.println("can we reach point 6 from 3? " + g.marked.contains(6));
System.out.println("can we reach point 16 from 3? " + g.marked.contains(16));
System.out.println("can we reach point 19 from 3? " + g.marked.contains(19));
}
}
