import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
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;
private static String[] colors = {"red", "blue", "green", "purple", "yellow", "brown", "azure",
"gray", "ivory", "lime", "navy", "oliver", "coral", "cyan", "pink"};
private boolean hasCircle = false;
private float thick = 2.0f;
//key is the start point, value is the set of end points
private Map<Integer, Set<Integer>> circles = new HashMap<>();
//position of the pair interchangable
private class Pair implements Comparable<Pair>{
@Override
public String toString() {
return "Pair [a=" + a + ", b=" + b + "]";
}
int a, b;
public Pair(int a, int b) {
this.a = a; this.b = b;
}
@Override
public int compareTo(Pair o) {
return hashCode() - o.hashCode();
}
@Override
public boolean equals(Object o) {
if(!(o instanceof Pair)) return false;
Pair p = (Pair)o;
if((a == p.a && b == p.b) || (a == p.b && b == p.a)) {
return true;
} else {
return false;
}
}
@Override
public int hashCode() {
int hash = 23;
hash = hash * 31 + (a > b ? a : b);
hash = hash * 31 + (a > b ? b : a);
return hash;
}
}
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 boolean dfsHasCircle(Integer start) {
this.start = start;
edgeTo = new Integer[this.size()]; //use map to avoid Index out of bound exception
this.hasCircle = false;
dfsCircle(start, start);
return this.hasCircle;
}
public void dfsCircle(Integer v, Integer from) {
marked.add(v);
for (Integer w : neighbors.get(v)) {
if (!marked.contains(w)) {
edgeTo[w] = v;
dfsCircle(w, v);
} else if (!from.equals(w)) {
this.hasCircle = true;
circles.computeIfAbsent(w, k -> new HashSet<>()).add(v);
}
}
}
private void printCircle(Integer begin, Integer end) {
Stack<Integer> stack = new Stack<>();
boolean rightDirection = false;
for(Integer i = end; !i.equals(start); i = edgeTo[i]) {
stack.push(i);
if(i.equals(begin)) {
rightDirection = true;
break;
}
}
if(begin.equals(start)) {
stack.push(start);
rightDirection = true;
}
if(!rightDirection) {
stack = new Stack<>();
for(Integer i = begin; !i.equals(start); i = edgeTo[i]) {
stack.push(i);
if(i.equals(end)) {
rightDirection = true;
break;
}
}
}
if(end.equals(start)) {
stack.push(start);
rightDirection = true;
}
if(!rightDirection || stack.isEmpty()) {
System.out.println("//traversal didn't discover this two points as start and end of a circle:"
+ begin + " " + end);
return;
}
System.out.println("//======circle #" + count + " ========");
Integer v = stack.pop();
Integer w;
while(!stack.isEmpty()) {
w = stack.pop();
System.out.printf(v + "--" + w + "[label=" + count
+ ", color=" + colors[count%colors.length] + ",penwidth=%.1f];\n", thick);
v = w;
}
System.out.printf(begin + "--" + end + "[label=" + count
+ ", color=" + colors[count%colors.length] + ",penwidth=%.1f];\n", thick);
count++;
thick+=0.5f;
}
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 here
g.dfsHasCircle(15);
Set<Pair> uniqueCircle = new HashSet<>();
g.circles
.keySet()
.stream()
.forEach(
i -> {
Stream.of(g.circles.get(i))
.flatMap(j -> j.stream())
.forEach(k -> uniqueCircle.add(g.new Pair(i, k)));
});
uniqueCircle.stream().forEach(i -> {
g.printCircle(i.a, i.b);
});
System.out.println("//"+uniqueCircle);
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));
System.out.println("is there circle: " + g.hasCircle);
System.out.println("how many circles dected for this traversal: "
+ uniqueCircle.size());
}
}
