/**
* Rishi Verma
* rktios@gmail.com
* 21-March-2015
* Common graph implementations in Java
*/
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
class GraphNode {
private HashMap
<Integer, LinkedList
<Integer
>> adjList
= null; private HashMap
<Integer, Boolean
> visited
= null; public Stack<Integer> topologicalSortStack = new Stack<Integer>();
enum BIPARTITECOLOR {
NOTVISITED, RED, BLUE
}
private HashMap
<Integer, BIPARTITECOLOR
> bipartiteColor
= null;
public void initializeBipartiteColor() {
bipartiteColor
= new HashMap
<Integer, BIPARTITECOLOR
>();
for (int node : adjList.keySet()) {
bipartiteColor.put(node, BIPARTITECOLOR.NOTVISITED);
}
}
public GraphNode(int node[]) {
System.
out.
println("GraphNode.GraphNode()");
adjList
= new HashMap
<Integer, LinkedList
<Integer
>>();
for (int i : node) {
adjList.put(i, new LinkedList<Integer>());
}
}
void checkBipartite(int source) {
initializeBipartiteColor();
Queue<Integer> q = new LinkedList<Integer>();
q.add(source);
bipartiteColor.put(source, BIPARTITECOLOR.RED);
System.
out.
println(doCheckBipartite
(q
));
}
boolean doCheckBipartite(Queue<Integer> q) {
if (false == q.isEmpty()) {
int currentNode = q.remove();
BIPARTITECOLOR color = bipartiteColor.get(currentNode);
LinkedList<Integer> neighbours = findNeighbour(currentNode);
for (Integer neighbour
: neighbours
) { if (bipartiteColor.get(neighbour) == BIPARTITECOLOR.NOTVISITED) {
q.add(neighbour);
if (color == BIPARTITECOLOR.RED) {
bipartiteColor.put(neighbour, BIPARTITECOLOR.BLUE);
} else {
bipartiteColor.put(neighbour, BIPARTITECOLOR.RED);
}
} else {
if (color == bipartiteColor.get(neighbour)) {
return false;
}
}
}
return doCheckBipartite(q);
}
return true;
}
public void addEdge(int source, int destination) {
adjList.get(source).add(destination);
}
public LinkedList<Integer> findNeighbour(int node) {
// System.out.println("GraphNode.findNeighbour() source: " + node);
LinkedList<Integer> neighbours = adjList.get(node);
// System.out.println(i);
}
return neighbours;
}
public void initializeVisitedMap() {
System.
out.
println("GraphNode.dfs()"); // Creating Visited hashmap
visited
= new HashMap
<Integer, Boolean
>(); Set<Integer> key = adjList.keySet();
for (int i : key) {
visited.put(i, false);
}
// doDfs(source);
}
public void dfs(int source) {
if (true == visited.get(source)) {
return;
}
visited.put(source, true);
System.
err.
println("GraphNode.doDfs() " + source
);
LinkedList<Integer> neighbours = findNeighbour(source);
for (int neighbour : neighbours) {
dfs(neighbour);
}
}
public void bfs(int source) {
Queue<Integer> bfsq = new LinkedList<Integer>();
bfsq.add(source);
visited.put(source, true);
doBfs(bfsq);
}
private void doBfs(Queue<Integer> q) {
if (q.isEmpty() == false) {
System.
err.
println("GraphNode.bfs() " + currentNode
);
LinkedList<Integer> neighbours = findNeighbour(currentNode);
if (false == visited.get(i)) {
visited.put(i, true);
q.add(i);
}
}
doBfs(q);
}
}
private void topologicalSortOnEachNode(int source) {
if (true == visited.get(source)) {
return;
}
visited.put(source, true);
LinkedList<Integer> neighbours = adjList.get(source);
topologicalSortOnEachNode(i);
}
topologicalSortStack.push(source);
}
public void topologicalSort() {
Set<Integer> nodes = adjList.keySet();
System.
out.
println("GraphNode.topologicalSort() " + node
); topologicalSortOnEachNode(node);
}
}
public void printTopologicalSortStack() {
System.
out.
println("GraphNode.printTopologicalSortStack()");
/*
* for (Integer i : topologicalSortStack) { System.out.println(i); }
*/
while (topologicalSortStack.isEmpty() == false) {
System.
out.
println(topologicalSortStack.
pop()); }
}
/**
*
*
* @param source
* @param parent
*/
public boolean isCyclic(int source, int parent) {
if (true == visited.get(source)) {
return true;
}
visited.put(source, true);
LinkedList<Integer> neighbours = findNeighbour(source);
for (int neighbour : neighbours) {
if (parent != neighbour && true == visited.get(neighbour)) {
System.
out.
println("isCyclic() TRUE Source" + source
+ " Parent " + parent + "Neighbour" + neighbour);
return true;
}
return isCyclic(neighbour, source);
}
return false;
}
}
class Graph {
public static void main
(String[] args
) { System.
out.
println("Graph.main()"); // GraphNode graphNode = createGraphExampleForDfs();
GraphNode graphNode = createGraphExampleForCycle();
// GraphNode graphNode = createGraphExampleForTopologicalSort();
// GraphNode graphNode = createGraphExampleForBiPartite();
// graphNode.findNeighbour(1);
graphNode.initializeVisitedMap();
// graphNode.topologicalSort();
// graphNode.printTopologicalSortStack();
// graphNode.dfs(2);
System.
out.
println("IS cyclic " + graphNode.
isCyclic(3,
3)); // graphNode.bfs(4);
// graphNode.checkBipartite(4);
}
private static GraphNode createGraphExampleForBiPartite() {
int node[] = { 0, 1, 2, 3, 4 };
GraphNode graphNode = new GraphNode(node);
graphNode.addEdge(0, 1);
graphNode.addEdge(0, 4);
graphNode.addEdge(1, 0);
graphNode.addEdge(1, 2);
graphNode.addEdge(2, 1);
graphNode.addEdge(2, 3);
graphNode.addEdge(3, 2);
graphNode.addEdge(3, 4);
graphNode.addEdge(4, 0);
graphNode.addEdge(4, 3);
return graphNode;
}
private static GraphNode createGraphExampleForTopologicalSort() {
int nodeList[] = { 0, 1, 2, 3, 4, 5 };
// Ref graph
// http://c...content-available-to-author-only...g.com/images/topologicalsort.png
GraphNode graphNode = new GraphNode(nodeList);
graphNode.addEdge(2, 3);
graphNode.addEdge(3, 1);
graphNode.addEdge(4, 0);
graphNode.addEdge(4, 1);
graphNode.addEdge(5, 0);
graphNode.addEdge(5, 2);
return graphNode;
}
private static GraphNode createGraphExampleForDfs() {
int nodeList[] = { 0, 1, 2, 3, 4 };
// Ref graph
/*
* http://d...content-available-to-author-only...t.net/wp-content/uploads/
* graph_representation12.png
*/
GraphNode graphNode = new GraphNode(nodeList);
graphNode.addEdge(0, 1);
graphNode.addEdge(0, 4);
graphNode.addEdge(1, 0);
graphNode.addEdge(1, 2);
graphNode.addEdge(1, 3);
graphNode.addEdge(1, 4);
graphNode.addEdge(2, 1);
graphNode.addEdge(2, 3);
graphNode.addEdge(3, 1);
graphNode.addEdge(3, 2);
graphNode.addEdge(3, 4);
graphNode.addEdge(4, 0);
graphNode.addEdge(4, 1);
graphNode.addEdge(4, 3);
return graphNode;
}
// For testing cycleGraph
private static GraphNode createGraphExampleForCycle() {
int nodeList[] = { 0, 1, 2, 3, 4, 5 };
// Ref graph
/*
* http://d...content-available-to-author-only...t.net/wp-content/uploads/cycleGraph-300
* x156.png
*/GraphNode graphNode = new GraphNode(nodeList);
graphNode.addEdge(0, 1);
graphNode.addEdge(0, 3);
graphNode.addEdge(0, 5);
graphNode.addEdge(1, 0);
graphNode.addEdge(1, 2);
graphNode.addEdge(2, 1);
graphNode.addEdge(2, 5);
graphNode.addEdge(3, 0);
graphNode.addEdge(3, 4);
graphNode.addEdge(4, 3);
graphNode.addEdge(5, 0);
graphNode.addEdge(5, 2);
return graphNode;
}
}
CgovKioKICogUmlzaGkgVmVybWEKICogcmt0aW9zQGdtYWlsLmNvbQogKiAyMS1NYXJjaC0yMDE1CiAqIENvbW1vbiBncmFwaCBpbXBsZW1lbnRhdGlvbnMgaW4gSmF2YQogKi8KaW1wb3J0IGphdmEudXRpbC5IYXNoTWFwOwppbXBvcnQgamF2YS51dGlsLkxpbmtlZExpc3Q7CmltcG9ydCBqYXZhLnV0aWwuUXVldWU7CmltcG9ydCBqYXZhLnV0aWwuU2V0OwppbXBvcnQgamF2YS51dGlsLlN0YWNrOwoKY2xhc3MgR3JhcGhOb2RlIHsKCXByaXZhdGUgSGFzaE1hcDxJbnRlZ2VyLCBMaW5rZWRMaXN0PEludGVnZXI+PiBhZGpMaXN0ID0gbnVsbDsKCXByaXZhdGUgSGFzaE1hcDxJbnRlZ2VyLCBCb29sZWFuPiB2aXNpdGVkID0gbnVsbDsKCXB1YmxpYyBTdGFjazxJbnRlZ2VyPiB0b3BvbG9naWNhbFNvcnRTdGFjayA9IG5ldyBTdGFjazxJbnRlZ2VyPigpOwoKCWVudW0gQklQQVJUSVRFQ09MT1IgewoJCU5PVFZJU0lURUQsIFJFRCwgQkxVRQoJfQoKCXByaXZhdGUgSGFzaE1hcDxJbnRlZ2VyLCBCSVBBUlRJVEVDT0xPUj4gYmlwYXJ0aXRlQ29sb3IgPSBudWxsOwoKCXB1YmxpYyB2b2lkIGluaXRpYWxpemVCaXBhcnRpdGVDb2xvcigpIHsKCgkJYmlwYXJ0aXRlQ29sb3IgPSBuZXcgSGFzaE1hcDxJbnRlZ2VyLCBCSVBBUlRJVEVDT0xPUj4oKTsKCgkJZm9yIChpbnQgbm9kZSA6IGFkakxpc3Qua2V5U2V0KCkpIHsKCQkJYmlwYXJ0aXRlQ29sb3IucHV0KG5vZGUsIEJJUEFSVElURUNPTE9SLk5PVFZJU0lURUQpOwoJCX0KCX0KCglwdWJsaWMgR3JhcGhOb2RlKGludCBub2RlW10pIHsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIkdyYXBoTm9kZS5HcmFwaE5vZGUoKSIpOwoKCQlhZGpMaXN0ID0gbmV3IEhhc2hNYXA8SW50ZWdlciwgTGlua2VkTGlzdDxJbnRlZ2VyPj4oKTsKCgkJZm9yIChpbnQgaSA6IG5vZGUpIHsKCQkJYWRqTGlzdC5wdXQoaSwgbmV3IExpbmtlZExpc3Q8SW50ZWdlcj4oKSk7CgkJfQoKCX0KCgl2b2lkIGNoZWNrQmlwYXJ0aXRlKGludCBzb3VyY2UpIHsKCQlpbml0aWFsaXplQmlwYXJ0aXRlQ29sb3IoKTsKCQlRdWV1ZTxJbnRlZ2VyPiBxID0gbmV3IExpbmtlZExpc3Q8SW50ZWdlcj4oKTsKCQlxLmFkZChzb3VyY2UpOwoJCWJpcGFydGl0ZUNvbG9yLnB1dChzb3VyY2UsIEJJUEFSVElURUNPTE9SLlJFRCk7CgkJU3lzdGVtLm91dC5wcmludGxuKGRvQ2hlY2tCaXBhcnRpdGUocSkpOwoKCX0KCglib29sZWFuIGRvQ2hlY2tCaXBhcnRpdGUoUXVldWU8SW50ZWdlcj4gcSkgewoKCQlpZiAoZmFsc2UgPT0gcS5pc0VtcHR5KCkpIHsKCgkJCWludCBjdXJyZW50Tm9kZSA9IHEucmVtb3ZlKCk7CgkJCUJJUEFSVElURUNPTE9SIGNvbG9yID0gYmlwYXJ0aXRlQ29sb3IuZ2V0KGN1cnJlbnROb2RlKTsKCQkJTGlua2VkTGlzdDxJbnRlZ2VyPiBuZWlnaGJvdXJzID0gZmluZE5laWdoYm91cihjdXJyZW50Tm9kZSk7CgoJCQlmb3IgKEludGVnZXIgbmVpZ2hib3VyIDogbmVpZ2hib3VycykgewoJCQkJaWYgKGJpcGFydGl0ZUNvbG9yLmdldChuZWlnaGJvdXIpID09IEJJUEFSVElURUNPTE9SLk5PVFZJU0lURUQpIHsKCQkJCQlxLmFkZChuZWlnaGJvdXIpOwoJCQkJCWlmIChjb2xvciA9PSBCSVBBUlRJVEVDT0xPUi5SRUQpIHsKCQkJCQkJYmlwYXJ0aXRlQ29sb3IucHV0KG5laWdoYm91ciwgQklQQVJUSVRFQ09MT1IuQkxVRSk7CgkJCQkJfSBlbHNlIHsKCQkJCQkJYmlwYXJ0aXRlQ29sb3IucHV0KG5laWdoYm91ciwgQklQQVJUSVRFQ09MT1IuUkVEKTsKCQkJCQl9CgkJCQl9IGVsc2UgewoJCQkJCWlmIChjb2xvciA9PSBiaXBhcnRpdGVDb2xvci5nZXQobmVpZ2hib3VyKSkgewoJCQkJCQlyZXR1cm4gZmFsc2U7CgkJCQkJfQoJCQkJfQoJCQl9CgkJCXJldHVybiBkb0NoZWNrQmlwYXJ0aXRlKHEpOwoKCQl9CgkJcmV0dXJuIHRydWU7Cgl9CgoJcHVibGljIHZvaWQgYWRkRWRnZShpbnQgc291cmNlLCBpbnQgZGVzdGluYXRpb24pIHsKCgkJYWRqTGlzdC5nZXQoc291cmNlKS5hZGQoZGVzdGluYXRpb24pOwoKCX0KCglwdWJsaWMgTGlua2VkTGlzdDxJbnRlZ2VyPiBmaW5kTmVpZ2hib3VyKGludCBub2RlKSB7CgkJLy8gU3lzdGVtLm91dC5wcmludGxuKCJHcmFwaE5vZGUuZmluZE5laWdoYm91cigpIHNvdXJjZTogIiArIG5vZGUpOwoKCQlMaW5rZWRMaXN0PEludGVnZXI+IG5laWdoYm91cnMgPSBhZGpMaXN0LmdldChub2RlKTsKCgkJZm9yIChJbnRlZ2VyIGkgOiBuZWlnaGJvdXJzKSB7CgkJCS8vIFN5c3RlbS5vdXQucHJpbnRsbihpKTsKCQl9CgoJCXJldHVybiBuZWlnaGJvdXJzOwoJfQoKCXB1YmxpYyB2b2lkIGluaXRpYWxpemVWaXNpdGVkTWFwKCkgewoJCVN5c3RlbS5vdXQucHJpbnRsbigiR3JhcGhOb2RlLmRmcygpIik7CgkJLy8gQ3JlYXRpbmcgVmlzaXRlZCBoYXNobWFwCgkJdmlzaXRlZCA9IG5ldyBIYXNoTWFwPEludGVnZXIsIEJvb2xlYW4+KCk7CgkJU2V0PEludGVnZXI+IGtleSA9IGFkakxpc3Qua2V5U2V0KCk7CgkJZm9yIChpbnQgaSA6IGtleSkgewoJCQl2aXNpdGVkLnB1dChpLCBmYWxzZSk7CgkJfQoKCQkvLyBkb0Rmcyhzb3VyY2UpOwoKCX0KCglwdWJsaWMgdm9pZCBkZnMoaW50IHNvdXJjZSkgewoKCQlpZiAodHJ1ZSA9PSB2aXNpdGVkLmdldChzb3VyY2UpKSB7CgkJCXJldHVybjsKCQl9CgkJdmlzaXRlZC5wdXQoc291cmNlLCB0cnVlKTsKCQlTeXN0ZW0uZXJyLnByaW50bG4oIkdyYXBoTm9kZS5kb0RmcygpICIgKyBzb3VyY2UpOwoKCQlMaW5rZWRMaXN0PEludGVnZXI+IG5laWdoYm91cnMgPSBmaW5kTmVpZ2hib3VyKHNvdXJjZSk7CgkJZm9yIChpbnQgbmVpZ2hib3VyIDogbmVpZ2hib3VycykgewoJCQlkZnMobmVpZ2hib3VyKTsKCgkJfQoJfQoKCXB1YmxpYyB2b2lkIGJmcyhpbnQgc291cmNlKSB7CgoJCVF1ZXVlPEludGVnZXI+IGJmc3EgPSBuZXcgTGlua2VkTGlzdDxJbnRlZ2VyPigpOwoJCWJmc3EuYWRkKHNvdXJjZSk7CgkJdmlzaXRlZC5wdXQoc291cmNlLCB0cnVlKTsKCQlkb0JmcyhiZnNxKTsKCX0KCglwcml2YXRlIHZvaWQgZG9CZnMoUXVldWU8SW50ZWdlcj4gcSkgewoJCWlmIChxLmlzRW1wdHkoKSA9PSBmYWxzZSkgewoJCQlJbnRlZ2VyIGN1cnJlbnROb2RlID0gcS5yZW1vdmUoKTsKCgkJCVN5c3RlbS5lcnIucHJpbnRsbigiR3JhcGhOb2RlLmJmcygpICIgKyBjdXJyZW50Tm9kZSk7CgoJCQlMaW5rZWRMaXN0PEludGVnZXI+IG5laWdoYm91cnMgPSBmaW5kTmVpZ2hib3VyKGN1cnJlbnROb2RlKTsKCQkJZm9yIChJbnRlZ2VyIGkgOiBuZWlnaGJvdXJzKSB7CgkJCQlpZiAoZmFsc2UgPT0gdmlzaXRlZC5nZXQoaSkpIHsKCQkJCQl2aXNpdGVkLnB1dChpLCB0cnVlKTsKCQkJCQlxLmFkZChpKTsKCQkJCX0KCgkJCX0KCQkJZG9CZnMocSk7CgkJfQoJfQoKCXByaXZhdGUgdm9pZCB0b3BvbG9naWNhbFNvcnRPbkVhY2hOb2RlKGludCBzb3VyY2UpIHsKCQlpZiAodHJ1ZSA9PSB2aXNpdGVkLmdldChzb3VyY2UpKSB7CgkJCXJldHVybjsKCQl9CgkJdmlzaXRlZC5wdXQoc291cmNlLCB0cnVlKTsKCQlMaW5rZWRMaXN0PEludGVnZXI+IG5laWdoYm91cnMgPSBhZGpMaXN0LmdldChzb3VyY2UpOwoJCWZvciAoSW50ZWdlciBpIDogbmVpZ2hib3VycykgewoJCQl0b3BvbG9naWNhbFNvcnRPbkVhY2hOb2RlKGkpOwoJCX0KCQl0b3BvbG9naWNhbFNvcnRTdGFjay5wdXNoKHNvdXJjZSk7CgoJfQoKCXB1YmxpYyB2b2lkIHRvcG9sb2dpY2FsU29ydCgpIHsKCgkJU2V0PEludGVnZXI+IG5vZGVzID0gYWRqTGlzdC5rZXlTZXQoKTsKCQlmb3IgKEludGVnZXIgbm9kZSA6IG5vZGVzKSB7CgkJCVN5c3RlbS5vdXQucHJpbnRsbigiR3JhcGhOb2RlLnRvcG9sb2dpY2FsU29ydCgpICIgKyBub2RlKTsKCQkJdG9wb2xvZ2ljYWxTb3J0T25FYWNoTm9kZShub2RlKTsKCQl9CgoJfQoKCXB1YmxpYyB2b2lkIHByaW50VG9wb2xvZ2ljYWxTb3J0U3RhY2soKSB7CgkJU3lzdGVtLm91dC5wcmludGxuKCJHcmFwaE5vZGUucHJpbnRUb3BvbG9naWNhbFNvcnRTdGFjaygpIik7CgoJCS8qCgkJICogZm9yIChJbnRlZ2VyIGkgOiB0b3BvbG9naWNhbFNvcnRTdGFjaykgeyBTeXN0ZW0ub3V0LnByaW50bG4oaSk7IH0KCQkgKi8KCgkJd2hpbGUgKHRvcG9sb2dpY2FsU29ydFN0YWNrLmlzRW1wdHkoKSA9PSBmYWxzZSkgewoJCQlTeXN0ZW0ub3V0LnByaW50bG4odG9wb2xvZ2ljYWxTb3J0U3RhY2sucG9wKCkpOwoJCX0KCX0KCgkvKioKCSAqCgkgKiAKCSAqIEBwYXJhbSBzb3VyY2UKCSAqIEBwYXJhbSBwYXJlbnQKCSAqLwoJcHVibGljIGJvb2xlYW4gaXNDeWNsaWMoaW50IHNvdXJjZSwgaW50IHBhcmVudCkgewoKCQlpZiAodHJ1ZSA9PSB2aXNpdGVkLmdldChzb3VyY2UpKSB7CgkJCXJldHVybiB0cnVlOwoJCX0KCQl2aXNpdGVkLnB1dChzb3VyY2UsIHRydWUpOwoKCQlMaW5rZWRMaXN0PEludGVnZXI+IG5laWdoYm91cnMgPSBmaW5kTmVpZ2hib3VyKHNvdXJjZSk7CgkJZm9yIChpbnQgbmVpZ2hib3VyIDogbmVpZ2hib3VycykgewoJCQlpZiAocGFyZW50ICE9IG5laWdoYm91ciAmJiB0cnVlID09IHZpc2l0ZWQuZ2V0KG5laWdoYm91cikpIHsKCQkJCVN5c3RlbS5vdXQucHJpbnRsbigiaXNDeWNsaWMoKSBUUlVFIFNvdXJjZSIgKyBzb3VyY2UKCQkJCQkJKyAiIFBhcmVudCAiICsgcGFyZW50ICsgIk5laWdoYm91ciIgKyBuZWlnaGJvdXIpOwoJCQkJcmV0dXJuIHRydWU7CgkJCX0KCgkJCXJldHVybiBpc0N5Y2xpYyhuZWlnaGJvdXIsIHNvdXJjZSk7CgoJCX0KCQlyZXR1cm4gZmFsc2U7Cgl9Cgp9CgpjbGFzcyBHcmFwaCB7CgoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewoJCVN5c3RlbS5vdXQucHJpbnRsbigiR3JhcGgubWFpbigpIik7CgkJLy8gR3JhcGhOb2RlIGdyYXBoTm9kZSA9IGNyZWF0ZUdyYXBoRXhhbXBsZUZvckRmcygpOwoKCQlHcmFwaE5vZGUgZ3JhcGhOb2RlID0gY3JlYXRlR3JhcGhFeGFtcGxlRm9yQ3ljbGUoKTsKCQkvLyBHcmFwaE5vZGUgZ3JhcGhOb2RlID0gY3JlYXRlR3JhcGhFeGFtcGxlRm9yVG9wb2xvZ2ljYWxTb3J0KCk7CgkJLy8gR3JhcGhOb2RlIGdyYXBoTm9kZSA9IGNyZWF0ZUdyYXBoRXhhbXBsZUZvckJpUGFydGl0ZSgpOwoJCS8vIGdyYXBoTm9kZS5maW5kTmVpZ2hib3VyKDEpOwoJCWdyYXBoTm9kZS5pbml0aWFsaXplVmlzaXRlZE1hcCgpOwoJCS8vIGdyYXBoTm9kZS50b3BvbG9naWNhbFNvcnQoKTsKCQkvLyBncmFwaE5vZGUucHJpbnRUb3BvbG9naWNhbFNvcnRTdGFjaygpOwoJCS8vIGdyYXBoTm9kZS5kZnMoMik7CgkJU3lzdGVtLm91dC5wcmludGxuKCJJUyBjeWNsaWMgIiArIGdyYXBoTm9kZS5pc0N5Y2xpYygzLCAzKSk7CgkJLy8gZ3JhcGhOb2RlLmJmcyg0KTsKCQkvLyBncmFwaE5vZGUuY2hlY2tCaXBhcnRpdGUoNCk7Cgl9CgoJcHJpdmF0ZSBzdGF0aWMgR3JhcGhOb2RlIGNyZWF0ZUdyYXBoRXhhbXBsZUZvckJpUGFydGl0ZSgpIHsKCgkJaW50IG5vZGVbXSA9IHsgMCwgMSwgMiwgMywgNCB9OwoJCUdyYXBoTm9kZSBncmFwaE5vZGUgPSBuZXcgR3JhcGhOb2RlKG5vZGUpOwoKCQlncmFwaE5vZGUuYWRkRWRnZSgwLCAxKTsKCQlncmFwaE5vZGUuYWRkRWRnZSgwLCA0KTsKCgkJZ3JhcGhOb2RlLmFkZEVkZ2UoMSwgMCk7CgkJZ3JhcGhOb2RlLmFkZEVkZ2UoMSwgMik7CgoJCWdyYXBoTm9kZS5hZGRFZGdlKDIsIDEpOwoJCWdyYXBoTm9kZS5hZGRFZGdlKDIsIDMpOwoKCQlncmFwaE5vZGUuYWRkRWRnZSgzLCAyKTsKCQlncmFwaE5vZGUuYWRkRWRnZSgzLCA0KTsKCgkJZ3JhcGhOb2RlLmFkZEVkZ2UoNCwgMCk7CgkJZ3JhcGhOb2RlLmFkZEVkZ2UoNCwgMyk7CgoJCXJldHVybiBncmFwaE5vZGU7Cgl9CgoJcHJpdmF0ZSBzdGF0aWMgR3JhcGhOb2RlIGNyZWF0ZUdyYXBoRXhhbXBsZUZvclRvcG9sb2dpY2FsU29ydCgpIHsKCQlpbnQgbm9kZUxpc3RbXSA9IHsgMCwgMSwgMiwgMywgNCwgNSB9OwoJCS8vIFJlZiBncmFwaAoJCS8vIGh0dHA6Ly9jLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5nLmNvbS9pbWFnZXMvdG9wb2xvZ2ljYWxzb3J0LnBuZwoJCUdyYXBoTm9kZSBncmFwaE5vZGUgPSBuZXcgR3JhcGhOb2RlKG5vZGVMaXN0KTsKCgkJZ3JhcGhOb2RlLmFkZEVkZ2UoMiwgMyk7CgoJCWdyYXBoTm9kZS5hZGRFZGdlKDMsIDEpOwoKCQlncmFwaE5vZGUuYWRkRWRnZSg0LCAwKTsKCQlncmFwaE5vZGUuYWRkRWRnZSg0LCAxKTsKCgkJZ3JhcGhOb2RlLmFkZEVkZ2UoNSwgMCk7CgkJZ3JhcGhOb2RlLmFkZEVkZ2UoNSwgMik7CgoJCXJldHVybiBncmFwaE5vZGU7Cgl9CgoJcHJpdmF0ZSBzdGF0aWMgR3JhcGhOb2RlIGNyZWF0ZUdyYXBoRXhhbXBsZUZvckRmcygpIHsKCQlpbnQgbm9kZUxpc3RbXSA9IHsgMCwgMSwgMiwgMywgNCB9OwoJCS8vIFJlZiBncmFwaAoJCS8qCgkJICogaHR0cDovL2QuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLnQubmV0L3dwLWNvbnRlbnQvdXBsb2Fkcy8KCQkgKiBncmFwaF9yZXByZXNlbnRhdGlvbjEyLnBuZwoJCSAqLwoJCUdyYXBoTm9kZSBncmFwaE5vZGUgPSBuZXcgR3JhcGhOb2RlKG5vZGVMaXN0KTsKCQlncmFwaE5vZGUuYWRkRWRnZSgwLCAxKTsKCQlncmFwaE5vZGUuYWRkRWRnZSgwLCA0KTsKCgkJZ3JhcGhOb2RlLmFkZEVkZ2UoMSwgMCk7CgkJZ3JhcGhOb2RlLmFkZEVkZ2UoMSwgMik7CgkJZ3JhcGhOb2RlLmFkZEVkZ2UoMSwgMyk7CgkJZ3JhcGhOb2RlLmFkZEVkZ2UoMSwgNCk7CgoJCWdyYXBoTm9kZS5hZGRFZGdlKDIsIDEpOwoJCWdyYXBoTm9kZS5hZGRFZGdlKDIsIDMpOwoKCQlncmFwaE5vZGUuYWRkRWRnZSgzLCAxKTsKCQlncmFwaE5vZGUuYWRkRWRnZSgzLCAyKTsKCQlncmFwaE5vZGUuYWRkRWRnZSgzLCA0KTsKCgkJZ3JhcGhOb2RlLmFkZEVkZ2UoNCwgMCk7CgkJZ3JhcGhOb2RlLmFkZEVkZ2UoNCwgMSk7CgkJZ3JhcGhOb2RlLmFkZEVkZ2UoNCwgMyk7CgoJCXJldHVybiBncmFwaE5vZGU7Cgl9CgoJLy8gRm9yIHRlc3RpbmcgY3ljbGVHcmFwaAoJcHJpdmF0ZSBzdGF0aWMgR3JhcGhOb2RlIGNyZWF0ZUdyYXBoRXhhbXBsZUZvckN5Y2xlKCkgewoJCWludCBub2RlTGlzdFtdID0geyAwLCAxLCAyLCAzLCA0LCA1IH07CgkJLy8gUmVmIGdyYXBoCgkJLyoKCQkgKiBodHRwOi8vZC4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4udC5uZXQvd3AtY29udGVudC91cGxvYWRzL2N5Y2xlR3JhcGgtMzAwCgkJICogeDE1Ni5wbmcKCQkgKi9HcmFwaE5vZGUgZ3JhcGhOb2RlID0gbmV3IEdyYXBoTm9kZShub2RlTGlzdCk7CgkJZ3JhcGhOb2RlLmFkZEVkZ2UoMCwgMSk7CgkJZ3JhcGhOb2RlLmFkZEVkZ2UoMCwgMyk7CgkJZ3JhcGhOb2RlLmFkZEVkZ2UoMCwgNSk7CgoJCWdyYXBoTm9kZS5hZGRFZGdlKDEsIDApOwoJCWdyYXBoTm9kZS5hZGRFZGdlKDEsIDIpOwoKCQlncmFwaE5vZGUuYWRkRWRnZSgyLCAxKTsKCQlncmFwaE5vZGUuYWRkRWRnZSgyLCA1KTsKCgkJZ3JhcGhOb2RlLmFkZEVkZ2UoMywgMCk7CgkJZ3JhcGhOb2RlLmFkZEVkZ2UoMywgNCk7CgoJCWdyYXBoTm9kZS5hZGRFZGdlKDQsIDMpOwoKCQlncmFwaE5vZGUuYWRkRWRnZSg1LCAwKTsKCQlncmFwaE5vZGUuYWRkRWRnZSg1LCAyKTsKCgkJcmV0dXJuIGdyYXBoTm9kZTsKCX0KfQo=