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.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 Map<Integer, Boolean> isRed = new HashMap<>();
private Map<Integer, Integer> path = new HashMap<>();
private boolean isBipartite = true;
private Map<Integer, Integer> fromSource = new HashMap<>();
private Set<Integer> changedColor = new HashSet<>();
private Integer currentSource = 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 colorGraph() {
for(Integer s : neighbors.keySet()) {
currentSource = s;
if(!marked.contains(s)) {
isRed.put(s, true);
bfs(s);
}
}
}
private void bfs(Integer s) {
Queue<Integer> queue = new LinkedList<>();
marked.add(s);
isRed.put(s, true);
fromSource.put(s, s);
queue.add(s);
while(!queue.isEmpty()) {
Integer v = queue.poll();
if(neighbors.get(v) == null) {
continue;
}
for(Integer w : neighbors.get(v)) {
if(!marked.contains(w)) {
fromSource.put(w, currentSource);
path.put(w, v);
marked.add(w);
isRed.put(w, !isRed.get(v));
queue.add(w);
} else {
if(isRed.get(w) == isRed.get(v)) {
if(fromSource.get(w).equals(fromSource.get(v))) {
if(!w.equals(v)) {
this.isBipartite = false;
}
} else {
path.put(w, v);
Integer u = v;
for(u = v; path.get(u) != null; u=path.get(u)) {
if(changedColor.contains(u)) {
this.isBipartite = false;
} else {
changedColor.add(u);
isRed.put(u, !isRed.get(u));
}
}
isRed.put(u, !isRed.get(u));
}
}
}
}
}
}
private void dfs(Integer v) {
fromSource.put(v, currentSource);
marked.add(v);
if(neighbors.get(v)==null) {
System.out.println(v + " has no neighbor points");
return;
}
for(Integer w : neighbors.get(v)) {
if(!marked.contains(w)) {
path.put(w, v);
isRed.put(w, !isRed.get(v));
dfs(w);
} else if(isRed.get(v)==isRed.get(w)) {
if(fromSource.get(w).equals(fromSource.get(v))) {
if(!w.equals(v)) {
isBipartite = false;
}
} else {
path.put(w, v);
Integer u = v;
for(u = v; path.get(u) != null; u = path.get(u)) {
if(changedColor.contains(u)) { //can not satisfy 2 different colored neighbor points
isBipartite = false;
} else {
isRed.put(u, !isRed.get(u));
changedColor.add(u);
}
}
isRed.put(u, !isRed.get(u));
}
}
}
}
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);
g.addEdge(i, i + 3); //replace above line
}
for(int i = 15; i < 17; i++) {
g.addEdge(i, i+1);
}
g.addEdge(19, 19);
g.colorGraph();
System.out.println("strict digraph {");
g.isRed.entrySet().forEach(i -> {
System.out.println(i.getKey() + "[color=" + (i.getValue() ? "red" : "blue") + "];");
});
g.neighbors.keySet().stream().forEach(i ->
{
Stream.of(g.neighbors.get(i)).flatMap(j -> j.stream())
.forEach(k -> {
System.out.println(i + "->" + k + ";");
});
});
System.out.println("}");
System.out.println("number of points: " + g.size());
System.out.println("number of edges: " + g.edgeSize());
System.out.println("is bipartite:" + g.isBipartite);
}
}
