import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Digraph {
private Map<Integer, Set<Integer>> neighbors = new HashMap<>();
private Set<Integer> marked = new HashSet<>();
private Set<circle> circles = new HashSet<>();
private Map<Integer, Boolean> onStack = new HashMap<>();
private int count;
private Integer[] edgeTo;
private boolean hasCircle;
private static String[] colors = {"red", "blue", "green", "purple", "yellow", "brown", "azure",
"gray", "ivory", "lime", "navy", "oliver", "coral", "cyan", "pink"};
private float thick = 2.0f;
private class circle implements Comparable<circle> {
private Map<Integer, Integer> path;
public Map<Integer, Integer> getPath() {
return path;
}
@Override
public String toString() {
return "circle [path=" + path + "]";
}
public circle(Map<Integer, Integer> path) {
this.path = path;
}
private Integer findMin() {
return path.keySet().stream().min(Integer::compare).get();
}
@Override
public int hashCode() {
Integer min = findMin();
int hash = 23;
for(Integer i = path.get(min); !i.equals(min); i = path.get(i)) {
hash = hash*31 + i;
}
return hash;
}
@Override
public int compareTo(circle o) {
return this.hashCode() - o.hashCode();
}
@Override
public boolean equals(Object o) {
if(!(o instanceof circle)) return false;
return hashCode() - o.hashCode() == 0;
}
}
public Set<Integer> getPoints() {
Set<Integer> points = neighbors.keySet().stream().collect(Collectors.toCollection(HashSet::new));
this.neighbors.values().forEach(i -> points.addAll(i));
return points;
}
public int size() {
return getPoints().size();
}
public long edgeSize() {
return neighbors.values().stream().collect(Collectors.summingLong(Set::size));
}
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 dfsHasCircle(Integer start) {
circles = new HashSet<>();
this.edgeTo = new Integer[this.size()];
this.onStack = new HashMap<>();
this.hasCircle = false;
dfsCircle(start);
}
public void dfsCircle(Integer v) {
marked.add(v);
onStack.put(v, true);
if(neighbors.get(v) == null) return;
for(Integer w : neighbors.get(v)) {
if(!marked.contains(w)) {
edgeTo[w] = v;
dfsCircle(w);
} else if(onStack.get(w)) {
this.hasCircle = true;
Map<Integer, Integer> path = new HashMap<>();
for(Integer i = v; !i.equals(w); i = edgeTo[i]) {
path.put(i, edgeTo[i]);
}
path.put(w, v);
this.circles.add(new circle(path));
}
}
onStack.put(v, false);
}
private void printCircles() {
System.out.println("//" + circles.size() + " circles detected");
this.circles.stream().forEach(i -> {
Map<Integer, Integer> p = i.getPath();
Integer start = p.keySet().stream().findFirst().get();
for(Integer j = p.get(start); !start.equals(j); j = p.get(j)) {
System.out.printf(p.get(j) +"->" + j + "[label=" + count + ", color=" +colors [count%colors.length] + ",penwidth=%.1f];\n", thick);
}
System.out.printf(p.get(start) +"->" + start + "[label=" + count + ", color=" +colors [count%colors.length] + ",penwidth=%.1f];\n", thick);
count++;
thick+=0.5f;
});
}
public static void main(String...args) {
Digraph g = new Digraph();
//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);
//form circles
g.addEdge(7, 5);
g.addEdge(7, 1);
System.out.println("strict digraph {");
g.neighbors.keySet().stream().forEach(i ->
{
Stream.of(g.neighbors.get(i)).flatMap(j -> j.stream())
.forEach(k -> System.out.println(i + "->" + k + ";"));
});
g.dfsHasCircle(3);
g.printCircles();
System.out.println("}");
System.out.println("number of points: " + g.size());
System.out.println("number of edges: " + g.edgeSize());
System.out.println("find circle:" + g.hasCircle);
}
}
