Skip to content

Instantly share code, notes, and snippets.

@steghio

steghio/AAA_Graph_Utils.txt

Last active August 8, 2021 08:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save steghio/adcdc51e4babf732451ec018f084fc05 to your computer and use it in GitHub Desktop.
Save steghio/adcdc51e4babf732451ec018f084fc05 to your computer and use it in GitHub Desktop.
Download ZIP
Graph utilities
Raw
BellmanFordJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import com.blogspot.groglogs.structures.InOutEdge;
import com.blogspot.groglogs.structures.Vertex;
import org.junit.Test;
import java.util.LinkedList;
import java.util.List;
import static org.junit.Assert.assertEquals;
public class BellmanFordJTests {
List<Vertex> vertices, path;
List<InOutEdge> edges;
Vertex start, end;
boolean hasNegCycle;
@Test
public void badInput() {
try {
GraphUtils.buildBellmanFordTable(vertices, edges, start);
}catch(IllegalArgumentException e){
System.out.println("null input got IllegalArgumentException: " + e.getMessage());
}
start = null;
end = new Vertex("A");
vertices = new LinkedList<>();
vertices.add(end);
edges = new LinkedList<>();
try {
GraphUtils.buildBellmanFordTable(vertices, edges, start);
}catch(IllegalArgumentException e){
System.out.println("null start got IllegalArgumentException: " + e.getMessage());
}
start = new Vertex("A");
end = new Vertex("A");
vertices = null;
edges = new LinkedList<>();
try {
GraphUtils.buildBellmanFordTable(vertices, edges, start);
}catch(IllegalArgumentException e){
System.out.println("null vertices got IllegalArgumentException: " + e.getMessage());
}
start = new Vertex("A");
end = new Vertex("A");
vertices = new LinkedList<>();
edges = null;
try {
GraphUtils.buildBellmanFordTable(vertices, edges, start);
}catch(IllegalArgumentException e){
System.out.println("null edges got IllegalArgumentException: " + e.getMessage());
}
start = new Vertex("A");
end = new Vertex("B");
vertices = new LinkedList<>();
vertices.add(end);
edges = new LinkedList<>();
try {
GraphUtils.buildBellmanFordTable(vertices, edges, start);
}catch(IllegalArgumentException e){
System.out.println("start not in vertices got IllegalArgumentException: " + e.getMessage());
}
}
@Test
public void simpleGraph() {
start = new Vertex("A");
end = new Vertex("B");
vertices = new LinkedList<>();
vertices.add(start);
vertices.add(end);
edges = new LinkedList<>();
InOutEdge e = new InOutEdge("AB", 0, start, end);
edges.add(e);
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
assertEquals("Simple graph 1 edge path length is 2", 2, path.size());
start = new Vertex("A");
Vertex mid = new Vertex("B");
end = new Vertex("C");
vertices = new LinkedList<>();
vertices.add(start);
vertices.add(end);
vertices.add(mid);
edges = new LinkedList<>();
e = new InOutEdge("AB", 0, start, mid);
edges.add(e);
e = new InOutEdge("BC", 0, mid, end);
edges.add(e);
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
assertEquals("Simple graph 2 edges path length is 3", 3, path.size());
start = new Vertex("A");
mid = new Vertex("B");
end = new Vertex("C");
Vertex last = new Vertex("D");
vertices = new LinkedList<>();
vertices.add(start);
vertices.add(end);
vertices.add(mid);
vertices.add(last);
edges = new LinkedList<>();
e = new InOutEdge("AB", 0, start, mid);
edges.add(e);
e = new InOutEdge("BC", 0, mid, end);
edges.add(e);
e = new InOutEdge("CD", 0, end, last);
edges.add(e);
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
assertEquals("Simple graph 3 edges path 2 length is 3", 3, path.size());
hasNegCycle = GraphUtils.hasNegCycleBF(vertices, edges);
assertEquals("Simple graph has no cycle", false, hasNegCycle);
}
@Test
public void simpleNegGraph() {
start = new Vertex("A");
end = new Vertex("B");
vertices = new LinkedList<>();
vertices.add(start);
vertices.add(end);
edges = new LinkedList<>();
InOutEdge e = new InOutEdge("AB", -1, start, end);
edges.add(e);
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
assertEquals("Simple negative graph 1 edge path length is 2", 2, path.size());
start = new Vertex("A");
Vertex mid = new Vertex("B");
end = new Vertex("C");
vertices = new LinkedList<>();
vertices.add(start);
vertices.add(end);
vertices.add(mid);
edges = new LinkedList<>();
e = new InOutEdge("AB", -1, start, mid);
edges.add(e);
e = new InOutEdge("BC", -1, mid, end);
edges.add(e);
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
assertEquals("Simple negative graph 2 edges path length is 3", 3, path.size());
start = new Vertex("A");
mid = new Vertex("B");
end = new Vertex("C");
Vertex last = new Vertex("D");
vertices = new LinkedList<>();
vertices.add(start);
vertices.add(end);
vertices.add(mid);
vertices.add(last);
edges = new LinkedList<>();
e = new InOutEdge("AB", -1, start, mid);
edges.add(e);
e = new InOutEdge("BC", -1, mid, end);
edges.add(e);
e = new InOutEdge("CD", -1, end, last);
edges.add(e);
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
assertEquals("Simple negative graph 3 edges path 2 length is 3", 3, path.size());
hasNegCycle = GraphUtils.hasNegCycleBF(vertices, edges);
assertEquals("Simple negative graph has no cycle", false, hasNegCycle);
}
@Test
public void simpleMixGraph() {
start = new Vertex("A");
end = new Vertex("B");
vertices = new LinkedList<>();
vertices.add(start);
vertices.add(end);
edges = new LinkedList<>();
InOutEdge e = new InOutEdge("AB", 1, start, end);
edges.add(e);
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
assertEquals("Simple mixed graph 1 edge path length is 2", 2, path.size());
start = new Vertex("A");
Vertex mid = new Vertex("B");
end = new Vertex("C");
vertices = new LinkedList<>();
vertices.add(start);
vertices.add(end);
vertices.add(mid);
edges = new LinkedList<>();
e = new InOutEdge("AB", 1, start, mid);
edges.add(e);
e = new InOutEdge("BC", -1, mid, end);
edges.add(e);
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
assertEquals("Simple mixed graph 2 edges path length is 3", 3, path.size());
start = new Vertex("A");
mid = new Vertex("B");
end = new Vertex("C");
Vertex last = new Vertex("D");
vertices = new LinkedList<>();
vertices.add(start);
vertices.add(end);
vertices.add(mid);
vertices.add(last);
edges = new LinkedList<>();
e = new InOutEdge("AB", -1, start, mid);
edges.add(e);
e = new InOutEdge("BC", 1, mid, end);
edges.add(e);
e = new InOutEdge("CD", -1, end, last);
edges.add(e);
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
assertEquals("Simple mixed graph 3 edges path 2 length is 3", 3, path.size());
hasNegCycle = GraphUtils.hasNegCycleBF(vertices, edges);
assertEquals("Simple mixed graph has no cycle", false, hasNegCycle);
}
@Test
public void simpleNoPathGraph() {
start = new Vertex("A");
Vertex mid = new Vertex("B");
end = new Vertex("C");
vertices = new LinkedList<>();
vertices.add(start);
vertices.add(end);
vertices.add(mid);
edges = new LinkedList<>();
InOutEdge e = new InOutEdge("AB", 0, start, mid);
edges.add(e);
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
assertEquals("Simple no path graph has no path", 0, path.size());
hasNegCycle = GraphUtils.hasNegCycleBF(vertices, edges);
assertEquals("Simple no path graph has no cycle", false, hasNegCycle);
}
@Test
public void simpleNegCycleGraph() {
start = new Vertex("A");
Vertex mid = new Vertex("B");
end = new Vertex("C");
vertices = new LinkedList<>();
vertices.add(start);
vertices.add(end);
vertices.add(mid);
edges = new LinkedList<>();
InOutEdge e = new InOutEdge("AB", -1, start, mid);
edges.add(e);
e = new InOutEdge("BC", -1, mid, end);
edges.add(e);
e = new InOutEdge("CA", -1, end, start);
edges.add(e);
GraphUtils.buildBellmanFordTable(vertices, edges, start);
hasNegCycle = GraphUtils.hasNegCycleBF(vertices, edges);
assertEquals("Simple negative cycle graph has cycle", true, hasNegCycle);
}
@Test
public void complexNoNegNoCyleGraph() {
Vertex a, b, c, d, e, f, g, h;
vertices = new LinkedList<>();
a = new Vertex("A");
start = a;
vertices.add(a);
b = new Vertex("B");
vertices.add(b);
c = new Vertex("C");
vertices.add(c);
d = new Vertex("D");
vertices.add(d);
e = new Vertex("E");
vertices.add(e);
f = new Vertex("F");
vertices.add(f);
g = new Vertex("G");
vertices.add(g);
h = new Vertex("H");
vertices.add(h);
edges = new LinkedList<>();
InOutEdge ed = new InOutEdge("AB", 9, a, b);
edges.add(ed);
ed = new InOutEdge("AC", 5, a, c);
edges.add(ed);
ed = new InOutEdge("AD", 8, a, d);
edges.add(ed);
ed = new InOutEdge("BD", 5, b, d);
edges.add(ed);
ed = new InOutEdge("CD", 4, c, d);
edges.add(ed);
ed = new InOutEdge("BE", 4, b, e);
edges.add(ed);
ed = new InOutEdge("DE", 6, d, e);
edges.add(ed);
ed = new InOutEdge("CF", 12, c, f);
edges.add(ed);
ed = new InOutEdge("DF", 7, d, f);
edges.add(ed);
ed = new InOutEdge("EF", 1, e, f);
edges.add(ed);
ed = new InOutEdge("CG", 15, c, g);
edges.add(ed);
ed = new InOutEdge("FG", 3, f, g);
edges.add(ed);
ed = new InOutEdge("BH", 20, b, h);
edges.add(ed);
ed = new InOutEdge("EH", 13, e, h);
edges.add(ed);
ed = new InOutEdge("FH", 11, f, h);
edges.add(ed);
ed = new InOutEdge("GH", 9, g, h);
edges.add(ed);
end = h;
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
hasNegCycle = GraphUtils.hasNegCycleBF(vertices, edges);
assertEquals("Complex no negative no cycle graph has path A-H 5", 5, path.size());
System.out.println("Complex no negative no cycle graph path A-H");
for(Vertex v : path) System.out.println(v.getLabel());
assertEquals("Complex no negative no cycle graph has cycle", false, hasNegCycle);
end = e;
path = GraphUtils.getShortestPath(vertices, edges, start, end);
assertEquals("Complex no negative no cycle graph has path A-E 3", 3, path.size());
System.out.println("Complex no negative no cycle graph path A-E");
for(Vertex v : path) System.out.println(v.getLabel());
end = c;
path = GraphUtils.getShortestPath(vertices, edges, start, end);
assertEquals("Complex no negative no cycle graph has path A-C 2", 2, path.size());
System.out.println("Complex no negative no cycle graph path A-C");
for(Vertex v : path) System.out.println(v.getLabel());
}
@Test
public void complexNegCyleGraph() {
Vertex a, b, c, d;
vertices = new LinkedList<>();
a = new Vertex("A");
vertices.add(a);
b = new Vertex("B");
vertices.add(b);
c = new Vertex("C");
vertices.add(c);
d = new Vertex("D");
vertices.add(d);
edges = new LinkedList<>();
InOutEdge ed = new InOutEdge("AD", 1, a, d);
edges.add(ed);
ed = new InOutEdge("DC", 1, d, c);
edges.add(ed);
ed = new InOutEdge("CB", 2, c, b);
edges.add(ed);
ed = new InOutEdge("BA", -5, b, a);
edges.add(ed);
start = d;
end = a;
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
hasNegCycle = GraphUtils.hasNegCycleBF(vertices, edges);
assertEquals("Complex negative cycle graph has no path D-A", null, path);
assertEquals("Complex negative cycle graph has cycle", true, hasNegCycle);
edges = new LinkedList<>();
ed = new InOutEdge("AB", 1, a, b);
edges.add(ed);
ed = new InOutEdge("BC", 1, b, c);
edges.add(ed);
ed = new InOutEdge("CB", -2, c, b);
edges.add(ed);
ed = new InOutEdge("CD", 1000, c, d);
edges.add(ed);
ed = new InOutEdge("AD", -1000, a, d);
edges.add(ed);
start = a;
end = d;
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
hasNegCycle = GraphUtils.hasNegCycleBF(vertices, edges);
assertEquals("Complex negative cycle graph has no path A-D", null, path);
assertEquals("Complex negative cycle graph has cycle", true, hasNegCycle);
Vertex e = new Vertex("E");
vertices.add(e);
edges = new LinkedList<>();
ed = new InOutEdge("AB", 99, a, b);
edges.add(ed);
ed = new InOutEdge("AE", -99, a, e);
edges.add(ed);
ed = new InOutEdge("BC", 15, b, c);
edges.add(ed);
ed = new InOutEdge("CB", -42, c, b);
edges.add(ed);
ed = new InOutEdge("CD", 10, c, d);
edges.add(ed);
start = a;
end = d;
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
hasNegCycle = GraphUtils.hasNegCycleBF(vertices, edges);
assertEquals("Complex negative cycle graph has no path A-D", null, path);
assertEquals("Complex negative cycle graph has cycle", true, hasNegCycle);
}
@Test
public void complexNegNoCyleGraph() {
Vertex a, b, c, d, e, f;
vertices = new LinkedList<>();
a = new Vertex("A");
vertices.add(a);
b = new Vertex("B");
vertices.add(b);
c = new Vertex("C");
vertices.add(c);
d = new Vertex("D");
vertices.add(d);
e = new Vertex("E");
vertices.add(e);
f = new Vertex("F");
vertices.add(f);
edges = new LinkedList<>();
InOutEdge ed = new InOutEdge("AB", 1, a, b);
edges.add(ed);
ed = new InOutEdge("BC", 1, b, c);
edges.add(ed);
ed = new InOutEdge("CD", 1, c, d);
edges.add(ed);
ed = new InOutEdge("DE", -1, d, e);
edges.add(ed);
ed = new InOutEdge("EF", -1, e, f);
edges.add(ed);
ed = new InOutEdge("FC", -1, f, c);
edges.add(ed);
start = a;
end = b;
GraphUtils.buildBellmanFordTable(vertices, edges, start);
path = GraphUtils.getShortestPath(vertices, edges, start, end);
hasNegCycle = GraphUtils.hasNegCycleBF(vertices, edges);
assertEquals("Complex negative no cycle graph has path A-B 2", 2, path.size());
assertEquals("Complex negative no cycle graph has cycle", true, hasNegCycle);
}
}
Raw
EquationsPossibleJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import org.junit.Test;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
public class EquationsPossibleJTests {
String[] equations;
@Test
public void nullEmpty() {
equations = null;
assertTrue("null", GraphUtils.equationsPossible(equations));
equations = new String[]{};
assertTrue("empty", GraphUtils.equationsPossible(equations));
}
@Test
public void oneEquation() {
equations = new String[]{"a==b"};
assertTrue("a==b", GraphUtils.equationsPossible(equations));
equations = new String[]{"a!=b"};
assertTrue("a!=b", GraphUtils.equationsPossible(equations));
}
@Test
public void twoEquation() {
equations = new String[]{"a==b", "b==c"};
assertTrue("a==b,b==c", GraphUtils.equationsPossible(equations));
equations = new String[]{"a!=b", "b!=c"};
assertTrue("a!=b,b!=c", GraphUtils.equationsPossible(equations));
equations = new String[]{"a==b", "b!=a"};
assertFalse("a==b,b!=a", GraphUtils.equationsPossible(equations));
}
@Test
public void threeEquation() {
equations = new String[]{"a==b", "b==c", "c==a"};
assertTrue("a==b,b==c,c==a", GraphUtils.equationsPossible(equations));
equations = new String[]{"a!=b", "b!=c", "c==a"};
assertTrue("a!=b,b!=c,c==a", GraphUtils.equationsPossible(equations));
equations = new String[]{"a==b", "b==c", "c!=a"};
assertFalse("a==b,b==c,c!=a", GraphUtils.equationsPossible(equations));
}
}
Raw
EulerianPathJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import org.junit.Test;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import static org.junit.Assert.assertEquals;
public class EulerianPathJTests {
List<List<String>> tickets;
List<String> out, expected;
String start;
private static void addEdge(List<List<String>> edges, String source, String dest){
List<String> edge = new ArrayList<>();
edge.add(source);
edge.add(dest);
edges.add(edge);
}
private static void checkEdges(List<String> out, List<String> expected){
int i = 0;
for(String s : out){
assertEquals("edge is correct", expected.get(i), s);
i++;
}
}
@Test
public void nullEmpty() {
tickets = null;
start = "asd";
out = GraphUtils.eulerianPath(tickets, start);
expected = new LinkedList<>();
assertEquals("null", expected.size(), out.size());
tickets = new ArrayList<>();
start = "asd";
out = GraphUtils.eulerianPath(tickets, start);
expected = new LinkedList<>();
assertEquals("empty", expected.size(), out.size());
tickets = new ArrayList<>();
tickets.add(new ArrayList<>());
start = null;
out = GraphUtils.eulerianPath(tickets, start);
expected = new LinkedList<>();
assertEquals("null start", expected.size(), out.size());
tickets = new ArrayList<>();
tickets.add(new ArrayList<>());
start = "";
out = GraphUtils.eulerianPath(tickets, start);
expected = new LinkedList<>();
assertEquals("empty start", expected.size(), out.size());
}
@Test
public void oneEdge() {
tickets = new ArrayList<>();
addEdge(tickets, "asd", "lol");
start = "asd";
out = GraphUtils.eulerianPath(tickets, start);
expected = new LinkedList<>();
expected.add("asd");
expected.add("lol");
assertEquals("one edge", expected.size(), out.size());
checkEdges(out, expected);
tickets = new ArrayList<>();
addEdge(tickets, "lol", "asd");
start = "asd";
out = GraphUtils.eulerianPath(tickets, start);
expected = new LinkedList<>();
assertEquals("one edge no path", expected.size(), out.size());
}
@Test
public void edgeVisitedSorted() {
tickets = new ArrayList<>();
addEdge(tickets, "a", "b");
addEdge(tickets, "a", "c");
addEdge(tickets, "b", "c");
addEdge(tickets, "c", "a");
start = "a";
out = GraphUtils.eulerianPath(tickets, start);
expected = new LinkedList<>();
expected.add("a");
expected.add("b");
expected.add("c");
expected.add("a");
expected.add("c");
assertEquals("a,b - a,c - b,c - c,a", expected.size(), out.size());
checkEdges(out, expected);
tickets = new ArrayList<>();
addEdge(tickets, "jfk", "kul");
addEdge(tickets, "jfk", "nrt");
addEdge(tickets, "nrt", "jfk");
start = "jfk";
out = GraphUtils.eulerianPath(tickets, start);
expected = new LinkedList<>();
expected.add("jfk");
expected.add("nrt");
expected.add("jfk");
expected.add("kul");
assertEquals("jfk,kul - jfk,nrt - nrt,jfk", expected.size(), out.size());
checkEdges(out, expected);
}
@Test
public void sample() {
tickets = new ArrayList<>();
addEdge(tickets, "sfo", "hko");
addEdge(tickets, "yyz", "sfo");
addEdge(tickets, "yul", "yyz");
addEdge(tickets, "hko", "ord");
start = "yul";
out = GraphUtils.eulerianPath(tickets, start);
expected = new LinkedList<>();
expected.add("yul");
expected.add("yyz");
expected.add("sfo");
expected.add("hko");
expected.add("ord");
assertEquals("sfo,hko - yyz,sfo - yul,yyz - hko,ord", expected.size(), out.size());
checkEdges(out, expected);
tickets = new ArrayList<>();
addEdge(tickets, "sfo", "com");
addEdge(tickets, "com", "yyz");
start = "com";
out = GraphUtils.eulerianPath(tickets, start);
expected = new LinkedList<>();
assertEquals("sfo,com - com,yyz", expected.size(), out.size());
}
}
Raw
FindAllPathsFromSourceToDestInDAGJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
public class FindAllPathsFromSourceToDestInDAGJTests {
int[][] graph;
List<List<Integer>> expected, out;
@Test
public void nullEmpty() {
graph = null;
assertTrue("null", GraphUtils.findAllPathsFromSourceToDestInDAG(graph).isEmpty());
graph = new int[][]{};
assertTrue("empty", GraphUtils.findAllPathsFromSourceToDestInDAG(graph).isEmpty());
}
@Test
public void oneNode() {
graph = new int[][]{{}};
out = GraphUtils.findAllPathsFromSourceToDestInDAG(graph);
expected = new ArrayList<>();
List<Integer> res = new ArrayList<>();
res.add(0);
expected.add(res);
assertEquals("one node", expected.size(), out.size());
for(int i = 0; i < expected.size(); i++){
assertEquals("node is correct", expected.get(i), out.get(i));
}
}
@Test
public void twoNode() {
graph = new int[][]{
{1},
{}
};
out = GraphUtils.findAllPathsFromSourceToDestInDAG(graph);
expected = new ArrayList<>();
List<Integer> res = new ArrayList<>();
res.add(0);
res.add(1);
expected.add(res);
assertEquals("one node", expected.size(), out.size());
for(int i = 0; i < expected.size(); i++){
assertEquals("node is correct", expected.get(i), out.get(i));
}
}
@Test
public void threeNode() {
graph = new int[][]{
{1,2},
{2},
{}
};
out = GraphUtils.findAllPathsFromSourceToDestInDAG(graph);
expected = new ArrayList<>();
List<Integer> res = new ArrayList<>();
res.add(0);
res.add(1);
res.add(2);
expected.add(res);
List<Integer> res1 = new ArrayList<>();
res1.add(0);
res1.add(2);
expected.add(res1);
assertEquals("three node", expected.size(), out.size());
for(int i = 0; i < expected.size(); i++){
assertEquals("node is correct", expected.get(i), out.get(i));
}
}
@Test
public void moreNode() {
graph = new int[][]{
{1,2},//0
{3},//1
{3},//2
{}//3
};
out = GraphUtils.findAllPathsFromSourceToDestInDAG(graph);
expected = new ArrayList<>();
List<Integer> res = new ArrayList<>();
res.add(0);
res.add(1);
res.add(3);
expected.add(res);
List<Integer> res1 = new ArrayList<>();
res1.add(0);
res1.add(2);
res1.add(3);
expected.add(res1);
assertEquals("three node", expected.size(), out.size());
for(int i = 0; i < expected.size(); i++){
assertEquals("node is correct", expected.get(i), out.get(i));
}
}
}
Raw
GraphUtils.java
package com.blogspot.groglogs.graphutils;
import com.blogspot.groglogs.structures.InOutEdge;
import com.blogspot.groglogs.structures.OutEdge;
import com.blogspot.groglogs.structures.Vertex;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
public class GraphUtils {
private static HashMap<Vertex, Integer> distances;
private static HashMap<Vertex, Vertex> path;
private static final int infinity = Integer.MAX_VALUE;
private static final int neg_infinity = Integer.MIN_VALUE;
//global timer for Tarjan algorithm
private static int timerTarjan = 0;
//global counter for path-based SCC algorithm
private static int counterPathBasedSCC = 0;
private static final int PATH_BASED_SCC_PREORDER_NUMBER_ALREADY_IN_SCC = -1;
//checks if an edge can be relaxed
private static boolean canRelax(InOutEdge e){
int startDist = distances.get(e.getStartVertex());
int endDist = distances.get(e.getEndVertex());
if(startDist == neg_infinity) return true;
if( startDist != infinity && startDist + e.getWeight() < endDist){
distances.put(e.getEndVertex(), neg_infinity);
}
return false;
}
//adjusts the computed table if an edge can be relaxed
private static void checkNegRelax(InOutEdge e){
int startDist = distances.get(e.getStartVertex());
int endDist = distances.get(e.getEndVertex());
if(startDist == neg_infinity) distances.put(e.getEndVertex(), neg_infinity);
if( startDist != infinity && startDist + e.getWeight() < endDist){
distances.put(e.getEndVertex(), neg_infinity);
}
}
/*
relaxes an edge, it will update the cost to reach the end vertex
if a better path is found passing through a different edge
*/
private static void relax(InOutEdge e){
int startDist = distances.get(e.getStartVertex());
int endDist = distances.get(e.getEndVertex());
if( startDist != infinity && startDist + e.getWeight() < endDist){
distances.put(e.getEndVertex(), startDist + e.getWeight());
path.put(e.getEndVertex(), e.getStartVertex());
}
}
/*
builds the data structure we need to perform our calculations later on.
From a starting vertex, calculates the paths to each other vertex and their cost
*/
public static void buildBellmanFordTable(List<Vertex> vertices, List<InOutEdge> edges, Vertex start){
if(vertices == null || edges == null || start == null || !vertices.contains(start)){
throw new IllegalArgumentException("vertices, edges and start cannot be null and start must be in vertices!");
}
distances = new HashMap<>();
path = new HashMap<>();
//initialize the table. Start distance to itself is 0 and all other are set to infinity
for(Vertex v : vertices) distances.put(v, infinity);
distances.put(start, 0);
for(int i = 0; i < vertices.size() - 1; i++){
for(InOutEdge e: edges){
relax(e);
}
}
}
//if after additional V iterations we can still perform a relaxation, there must be a negative cycle
public static boolean hasNegCycleBF(List<Vertex> vertices, List<InOutEdge> edges){
for(int i = 0; i < vertices.size(); i++) {
for (InOutEdge e : edges) {
if (canRelax(e)) return true;
}
}
return false;
}
//run an additional V iterations to update the table with information about negative cycles
private static void checkNegCycleBF(List<Vertex> vertices, List<InOutEdge> edges){
for(int i = 0; i < vertices.size(); i++) {
for (InOutEdge e : edges) {
checkNegRelax(e);
}
}
}
//return null if a negative cycle is present on the path, empty if no path can be found, the path in reverse order otherwise
public static List<Vertex> getShortestPath(List<Vertex> vertices, List<InOutEdge> edges, Vertex start, Vertex end){
//updates the table to mark negative cycles. If there are, but are not on the path from start to end, we're good :)
checkNegCycleBF(vertices, edges);
if(path.containsKey(end) && distances.get(end) != infinity){
List<Vertex> out = new LinkedList<>();
Vertex curr = end;
out.add(curr);
while(curr != start){
//does our path contain a negative cycle?
if(distances.get(curr) == neg_infinity) return null;
curr = path.get(curr);
out.add(curr);
}
return out;
}
//no path exists
return new LinkedList<>();
}
//return the topological sorting (dependency resolution), if any, of the given graph (list of edges)
public static List<Vertex> getTopologicalSorting(List<InOutEdge> edges){
if(edges == null) throw new IllegalArgumentException("Edges list cannot be null!");
List<Vertex> sorted = new LinkedList<>();
Queue<Vertex> free = new LinkedList<>(); //all nodes with no dependency
Map<Vertex, List<Vertex>> dependencies = new HashMap<>(); //list of nodes I depend on
Map<Vertex, List<Vertex>> require = new HashMap<>(); //list of nodes that depend on me
for(InOutEdge e : edges){
//who do I depend on
List<Vertex> dep = dependencies.get(e.getStartVertex());
if(dep == null) dep = new LinkedList<>();
dep.add(e.getEndVertex());
dependencies.put(e.getStartVertex(), dep);
//if at the end the list for this vertex is null or empty, it means it has no dependencies and can be processed immediately
//this is needed to track nodes that have no dependency
dep = dependencies.get(e.getEndVertex());
if(dep == null) dep = new LinkedList<>();
dependencies.put(e.getEndVertex(), dep);
//who depends on me
dep = require.get(e.getEndVertex());
if(dep == null) dep = new LinkedList<>();
dep.add(e.getStartVertex());
require.put(e.getEndVertex(), dep);
//this is needed to track nodes on which nobody depends on
dep = require.get(e.getEndVertex());
if(dep == null) dep = new LinkedList<>();
require.put(e.getEndVertex(), dep);
}
//find all nodes that have no dependencies
for(Map.Entry<Vertex, List<Vertex>> entry : dependencies.entrySet()){
if(entry.getValue().isEmpty()) free.add(entry.getKey());
}
//process each free node
while(!free.isEmpty()){
Vertex curr = free.remove();
//I can be safely processed since I have no more dependencies
sorted.add(curr);
//REMEMBER to remove me from the list of dependencies!
dependencies.remove(curr);
//remove me from the list of each node waiting for me, if any
List<Vertex> deps = require.get(curr);
//ALWAYS check, maybe no one depends on me!
if(deps == null || deps.isEmpty()) continue;
for(Vertex v : deps){
List<Vertex> dep = dependencies.get(v);
dep.remove(curr);
//if after removing me, this vertex has no more dependencies, it is now free as well
//otherwise, simply update its dependency list
if(dep.size() == 0){
free.add(v);
dependencies.remove(v);
}
else dependencies.put(v, dep);
}
}
//we should have no more dependencies waiting at this point, if so, this is not a DAG
if(!dependencies.isEmpty()) throw new RuntimeException("Graph has at least one cycle!");
return sorted;
}
//return the topological sorting (dependency resolution), if any, of the given graph (list of edges)
//uses a stack instead of a queue
public static List<Vertex> getTopologicalSortingStack(List<InOutEdge> edges){
List<Vertex> sorted = new LinkedList<>();
if(edges == null) {
return sorted;
}
Stack<Vertex> free = new Stack<>(); //all nodes with no dependency
Map<Vertex, Set<Vertex>> dependencies = new HashMap<>(); //list of nodes I depend on
Map<Vertex, Set<Vertex>> require = new HashMap<>(); //list of nodes that depend on me
for(InOutEdge e : edges){
//who do I depend on
Set<Vertex> dep = dependencies.getOrDefault(e.getStartVertex(), new HashSet<>());
dep.add(e.getEndVertex());
dependencies.put(e.getStartVertex(), dep);
//if at the end the list for this vertex is null or empty, it means it has no dependencies and can be processed immediately
//this is needed to track nodes that have no dependency
dep = dependencies.getOrDefault(e.getEndVertex(), new HashSet<>());
dependencies.put(e.getEndVertex(), dep);
//who depends on me
dep = require.getOrDefault(e.getEndVertex(), new HashSet<>());
dep.add(e.getStartVertex());
require.put(e.getEndVertex(), dep);
//this is needed to track nodes on which nobody depends on
dep = require.getOrDefault(e.getEndVertex(), new HashSet<>());
require.put(e.getEndVertex(), dep);
}
//find all nodes that have no dependencies
for(Map.Entry<Vertex, Set<Vertex>> entry : dependencies.entrySet()){
if(entry.getValue().isEmpty()) free.push(entry.getKey());
}
//process each free node
while(!free.isEmpty()){
Vertex curr = free.pop();
//I can be safely processed since I have no more dependencies
sorted.add(curr);
//REMEMBER to remove me from the list of dependencies!
dependencies.remove(curr);
//remove me from the list of each node waiting for me, if any
Set<Vertex> deps = require.getOrDefault(curr, new HashSet<>());
for(Vertex v : deps){
Set<Vertex> dep = dependencies.get(v);
dep.remove(curr);
//if after removing me, this vertex has no more dependencies, it is now free as well
//otherwise, simply update its dependency list
if(dep.isEmpty()){
free.add(v);
dependencies.remove(v);
}
else dependencies.put(v, dep);
}
}
//we should have no more dependencies waiting at this point, if so, this is not a DAG
if(!dependencies.isEmpty()) {
return new LinkedList<>();
}
return sorted;
}
/*
Implementation of Kosaraju's algorithm to find strongly connected components in a directed graph
A single node is always a SCC
We collect the biggest SCCs and return them as Sets in a List
An empty graph has no SCCs
*/
public static List<Set<Vertex>> findStronglyConnectedComponentsKosaraju(List<Vertex> graph, List<InOutEdge> edges){
List<Set<Vertex>> sccs = new ArrayList<>();
if(graph == null || graph.size() == 0) return sccs;
Stack<Vertex> vertices = new Stack<>();
Set<Vertex> visited = new HashSet<>();
//first DFS, we visit the whole graph and add nodes to the stack ONLY after we are done processing them
//if the graph is not all connected, we need to ensure we don't skip separate subgraphs
for(Vertex v : graph) {
//but for those components that are all connected, we would be scanning the same data again, so skip those cases
if(!visited.contains(v)) {
dfsKosarajuBuildStack(v, visited, vertices);
}
}
//reverse all edges in the graph, creating the inverted graph
reverseEdges(graph, edges);
//second DFS, this time we can build the list of strongly connected components
//we pop nodes from the stack ignoring already visited ones
//and do a normal DFS, tracking all nodes visited so far
//when we can no longer travel, all nodes tracked until that point are one SCC
//we continue until stack is empty
//reinitialize visited set
visited = new HashSet<>();
//each SCC will be tracked in a new set
Set<Vertex> scc;
while(!vertices.empty()){
Vertex v = vertices.pop();
//if we haven't seen this node yet, start a new SCC
if(!visited.contains(v)){
scc = new HashSet<>();
//same DFS as before but instead of adding to stack, we add to set
dfsKosarajuFindSCC(v, visited, scc);
//when that DFS is over, all nodes we managed to reach are one SCC
sccs.add(scc);
}
}
return sccs;
}
//helper for findStronglyConnectedComponentsKosaraju
//performs a DFS visit of the graph. We skip already visited nodes and only add to the stack
//before we would return from the call on that node
private static void dfsKosarajuBuildStack(Vertex v, Set<Vertex> visited, Stack<Vertex> vertices){
visited.add(v);
for(OutEdge e : v.getOutEdges()){
if(!visited.contains(e.getEndVertex())) {
dfsKosarajuBuildStack(e.getEndVertex(), visited, vertices);
}
}
vertices.push(v);
}
//helper for findStronglyConnectedComponentsKosaraju
//reverses all edges in the graph
//this heavily depends on how is the graph represented, for example we use adjacency lists for easier traversing
//but to reverse it's best to have a separate list of edges
//so we use both together in our case
private static void reverseEdges(List<Vertex> graph, List<InOutEdge> edges){
//could be our graph is just a collection of single nodes
if(edges == null || edges.size() == 0) return;
//we track here temporarily the map vertex -> list of destinations
//we use this to rebuild later the adjacency lists of our nodes
Map<Vertex, Set<Vertex>> invertedEdges = new HashMap<>();
//invert all edges in the graph
for(InOutEdge e : edges){
Vertex tmp = e.getStartVertex();
e.setStartVertex(e.getEndVertex());
e.setEndVertex(tmp);
//track the new start->end connection in the map
Set<Vertex> outEdges = invertedEdges.get(e.getStartVertex());
if(outEdges == null){
outEdges = new HashSet<>();
}
outEdges.add(e.getEndVertex());
invertedEdges.put(e.getStartVertex(), outEdges);
}
//update every vertex in the graph with the new list of destinations
//thus inverting the whole graph
for(Vertex v : graph){
List<OutEdge> outEdges = new ArrayList<>();
//we can build the list of destinations from our temporary map
for(Vertex end : invertedEdges.get(v)){
outEdges.add(new OutEdge(end));
}
v.setOutEdges(outEdges);
}
}
//helper for findStronglyConnectedComponentsKosaraju
//performs a DFS visit of the graph. We skip already visited nodes and only add to the set
//before we would return from the call on that node
private static void dfsKosarajuFindSCC(Vertex v, Set<Vertex> visited, Set<Vertex> scc){
visited.add(v);
for(OutEdge e : v.getOutEdges()){
if(!visited.contains(e.getEndVertex())) {
dfsKosarajuFindSCC(e.getEndVertex(), visited, scc);
}
}
scc.add(v);
}
/*
Implementation of Tarjan's algorithm to find strongly connected components in a directed graph
A single node is always a SCC
We collect the biggest SCCs and return them as Sets in a List
An empty graph has no SCCs
*/
public static List<Set<Vertex>> findStronglyConnectedComponentsTarjan(List<Vertex> graph) {
List<Set<Vertex>> sccs = new ArrayList<>();
if(graph == null || graph.size() == 0) return sccs;
//this lists all visited nodes along with their discovery time
Map<Vertex, Integer> discoveryTimes = new HashMap<>();
//if the graph is not all connected, we need to ensure we don't skip separate subgraphs
for(Vertex v : graph) {
//but for those components that are all connected, we would be scanning the same data again, so skip those cases
if(!discoveryTimes.containsKey(v)) {
//this information is local to the subgraph in case our graph is not fully connected
Map<Vertex, Integer> lowestDiscoveryTimes = new HashMap<>();
Set<Vertex> inStack = new HashSet<>();
Stack<Vertex> stack = new Stack<>();
dfsTarjan(v, discoveryTimes, lowestDiscoveryTimes, stack, inStack, sccs);
}
}
return sccs;
}
//helper for findStronglyConnectedComponentsTarjan
//performs the DFS visit and identifies the SCCs
private static void dfsTarjan(Vertex v, Map<Vertex, Integer> discoveryTimes, Map<Vertex, Integer> lowestDiscoveryTimes, Stack<Vertex> stack, Set<Vertex> inStack, List<Set<Vertex>> sccs){
//we just discovered this node, set its discovery time and lowest discovery time equal to the timer
discoveryTimes.put(v, timerTarjan);
//it cannot happen that we just discovered a node for which we already have a lowest discovery time
//therefore if the node was not in discoveryTimes map, it also won't be in lowestDiscoveryTimes map
lowestDiscoveryTimes.put(v, timerTarjan);
//add this node to the stack
stack.push(v);
inStack.add(v);
//follow our edges
for(OutEdge e : v.getOutEdges()){
//if the destination was already discovered, we might be following a back link
Integer destinationDiscoveryTime = discoveryTimes.get(e.getEndVertex());
if(destinationDiscoveryTime != null) {
//if the destination is still in our stack, then this is a back link
//otherwise it would be a cross link, which we ignore
if (inStack.contains(e.getEndVertex())) {
//if we are following a back link, we might need to update our lowest discovery value
//we pick the minimum between our lowest discovery time and the discovery time of the destination
lowestDiscoveryTimes.put(v, Math.min(lowestDiscoveryTimes.get(v), discoveryTimes.get(e.getEndVertex())));
}
}
//otherwise we visit the new node following the forward link
else {
//increase global timer before visiting each new node
timerTarjan++;
dfsTarjan(e.getEndVertex(), discoveryTimes, lowestDiscoveryTimes, stack, inStack, sccs);
//before backtracking from that destination, we need to check whether we need to update our lowest discovery time
//since one of the following nodes might have reached the head of the SCC we might be in
//we pick the minimum between our lowest discovery time and the lowest discovery time of the destination
lowestDiscoveryTimes.put(v, Math.min(lowestDiscoveryTimes.get(v), lowestDiscoveryTimes.get(e.getEndVertex())));
}
}
//if we arrive here, it means we are backtracking since the DFS could not progress further
//and we have explored all our edges
//we then check whether we are the head of a SCC
//if our discovery time is equal to the lowest discovery time for the component we are part of, then we are the head
if(discoveryTimes.get(v) == lowestDiscoveryTimes.get(v)){
//all nodes that are part of the component of which we are the head of, will have the same discovery time as us
//we pop nodes from the stack and add them to the SCC until we find the head
Set<Vertex> scc = new HashSet<>();
//keep popping until we either find the head or have an empty stack
while(!stack.empty()){
Vertex tmp = stack.pop();
//remember to also remove it from the list of nodes currently in the stack
inStack.remove(tmp);
//add each node to the current SCC
scc.add(tmp);
//if we found the head, stop
if(tmp.equals(v)){
break;
}
}
//add the found SCC to the result list
sccs.add(scc);
}
}
/*
Implementation of path-based algorithm to find strongly connected components in a directed graph
A single node is always a SCC
We collect the biggest SCCs and return them as Sets in a List
An empty graph has no SCCs
*/
public static List<Set<Vertex>> findStronglyConnectedComponentsPathBased(List<Vertex> graph) {
List<Set<Vertex>> sccs = new ArrayList<>();
if (graph == null || graph.size() == 0) return sccs;
//this lists all visited nodes along with their preorder number
Map<Vertex, Integer> preorderNumbers = new HashMap<>();
//if the graph is not all connected, we need to ensure we don't skip separate subgraphs
for(Vertex v : graph) {
//but for those components that are all connected, we would be scanning the same data again, so skip those cases
if(!preorderNumbers.containsKey(v)) {
//this information is local to the subgraph in case our graph is not fully connected
Stack<Vertex> seen = new Stack<>();
Stack<Vertex> potentialSCCs = new Stack<>();
dfsPathBased(v, preorderNumbers, seen, potentialSCCs, sccs);
}
}
return sccs;
}
//helper for findStronglyConnectedComponentsPathBased
private static void dfsPathBased(Vertex v, Map<Vertex, Integer> preorderNumbers, Stack<Vertex> seen, Stack<Vertex> potentialSCCs, List<Set<Vertex>> sccs){
//whenever we encounter a new node, we set its preorder number and update the counter
preorderNumbers.put(v, counterPathBasedSCC);
counterPathBasedSCC++;
//we also add the node to both stacks
seen.push(v);
potentialSCCs.push(v);
for(OutEdge e : v.getOutEdges()){
Integer preorderNumberDestination = preorderNumbers.get(e.getEndVertex());
//if our destination hasn't been visited yet, visit its subgraph
if(preorderNumberDestination == null){
dfsPathBased(e.getEndVertex(), preorderNumbers, seen, potentialSCCs, sccs);
}
//otherwise, if our destination is NOT yet part of a SCC
//we remove nodes from the potentialSCCs stack until we find a node that has a preorder number less than or equal to the preorder number of our destination
//meaning we followed a back link and discovered a SCC so now need to get its head by looking for the very first node we visited before reaching the back link
//that node, will have been visited before us and must have a lower preorder number than all other nodes in the same SCC
//we use PATH_BASED_SCC_PREORDER_NUMBER_ALREADY_IN_SCC (-1) as preorder number to indicate we added a node to a SCC
else if(preorderNumberDestination != PATH_BASED_SCC_PREORDER_NUMBER_ALREADY_IN_SCC){
while(!potentialSCCs.empty()){
Vertex top = potentialSCCs.peek();
if(preorderNumbers.get(top) > preorderNumbers.get(e.getEndVertex())){
potentialSCCs.pop();
}
//very important, stop when our pop condition doesn't hold true anymore!
else{
break;
}
}
}
}
//before backtracking, we verify whether we are the head of a discovered SCC
//in that case, we would be at the top of the potentialSCCs stack
if(!potentialSCCs.empty() && potentialSCCs.peek().equals(v)){
Set<Vertex> scc = new HashSet<>();
//we keep popping nodes from the seen stack in the order they were visited until we find ourselves
//all nodes popped are part of the same SCC
while(!seen.empty()){
Vertex component = seen.pop();
//we update the preorder number to track the information that this node is now part of a SCC
preorderNumbers.put(component, PATH_BASED_SCC_PREORDER_NUMBER_ALREADY_IN_SCC);
scc.add(component);
if(component.equals(v)){
break;
}
}
//remember to remove this node from the potentialSCCs as we collected the SCC he was the head of
potentialSCCs.pop();
sccs.add(scc);
}
}
/*
Given a graph and a start vertex, determine what is the minimum amount of new edges to add so that every other
node is reachable from the start in any number of hops.
The graph is simplified by finding all SCCs, then squashing them. An in edge into any component of an SCC
make the whole SCC reachable.
After squashing, all nodes in the graph that do not have an incoming edge except for the start and its SCC
are the minimum required to satisfy our condition.
*/
public static Set<Vertex> findMinimumNewEdgesForFullyConnectedGraphFromStart(List<Vertex> graph, Vertex start) {
Set<Vertex> newDestinations = new HashSet<>();
if (graph == null || graph.size() == 0 || start == null) return newDestinations;
//we should also handle the case where the start vertex is not in the graph
//we find all SCCs, if any
List<Set<Vertex>> sccs = findStronglyConnectedComponentsTarjan(graph);
//process the scc list a bit so it's faster to find which nodes are in which SCC later
//key = node, value = SCC he is in
Map<Vertex, Set<Vertex>> nodeSCCs = new HashMap<>();
for(Set<Vertex> s : sccs){
for(Vertex v : s){
nodeSCCs.put(v, s);
}
}
//now we check for each node what is its in degree
//SCCs will count as a single element
//the start and its SCC, if any, are always reachable from the start, so we immediately track them
//we scan the graph one more time and count the incoming edges for each node. For nodes in a SCC
//the incoming edge is ignored if coming from another node in same SCC
//At the end, we want all the nodes that have at least one incoming edge tracked here
Set<Vertex> hasInEdge = new HashSet<>();
//start vertex and its SCC, if any, always have an in edge since they are always reachable from start node
//this is important since a different start node might yield different results!
hasInEdge.add(start);
hasInEdge.addAll(nodeSCCs.get(start));
for(Vertex v : graph){
for(OutEdge e : v.getOutEdges()){
//we do not care about in degree for start vertex
if(!e.getEndVertex().equals(start)){
//find, if any, the SCC of this node
Set<Vertex> scc = nodeSCCs.get(v);
//consider this edge unless both start and destination are in same SCC
if(scc == null || !(scc.contains(v) && scc.contains(e.getEndVertex()))){
hasInEdge.add(e.getEndVertex());
//in case this node was in a SCC, also track all other nodes in SCC as having same edge
hasInEdge.addAll(nodeSCCs.get(e.getEndVertex()));
}
}
}
}
//now we look for those nodes that did NOT have an incoming edge at all
//if an SCC did not have any incoming edge, we pick only one node from it
//since adding a connection to any node in the SCC will allow reaching all others in same SCC
Set<Vertex> evaluated = new HashSet<>();
for(Vertex v : graph){
//ignore start vertex and do not count same SCC multiple times
if(!v.equals(start) && !hasInEdge.contains(v) && !evaluated.contains(v)){
newDestinations.add(v);
//mark node as evaluated and if this node was part of an SCC, consider the whole SCC as evaluated too so we only add one connection
evaluated.add(v);
evaluated.addAll(nodeSCCs.get(v));
}
}
return newDestinations;
}
/**
* Given a certain amount of change and a set of available coins, find the minimum number of coins necessary
* to return that exact change.
* @param change the change to compose.
* @param coins the available coins.
* @return the minimum number of coins necessary to compose that change or -1 if not possible.
*/
public static int minimumCoinsForChange(int change, int... coins){
if(change <= 0 || coins == null || coins.length == 0){
return -1;
}
//key = amount, value = number of coins to compose that amount
Map<Integer, Integer> minCoinsForAmounts = new HashMap<>();
minCoinsForAmounts.put(change, 0);
/*
Consider our amounts as a graph starting with initial amount at the root. Each edge is the resulting VALID amount
generated using one of the available coins. First branch to reach amount 0 used the minimum number of coins.
We MUST track the (amount, numberOfCoins) information separately to easily skip repeated branches we already calculated
since if we saw them already, it means we have a way to reach that amount using fewer coins overall.
Using BFS we are guaranteed that as soon as we hit the target we have the best answer.
R:c
/ | \
A:c-c1 B:c-c2 C:c-c3
/ | \
A-c1 A-c2 A-c3 ..... .....
....
*/
Queue<Integer> amounts = new ArrayDeque<>();
amounts.add(change);
while(!amounts.isEmpty()){
int currAmount = amounts.poll();
for(int coin : coins){
int newAmount = currAmount - coin;
//if we reached the target, return numberOfCoins + 1 since we used one last coin to reach it
if(newAmount == 0){
return minCoinsForAmounts.get(currAmount) + 1;
}
//only valid amounts should be considered
if(newAmount > 0){
Integer minCoinsForAmount = minCoinsForAmounts.get(newAmount);
//if we somehow already could generate this amount before, it means we have a way of making it with fewer coins
//so we should abandon the current path as it won't lead to the minimal solution
//otherwise we track the new amount considering we used another coin to get there
if(minCoinsForAmount == null){
minCoinsForAmounts.put(newAmount, minCoinsForAmounts.get(currAmount) + 1);
amounts.add(newAmount);
}
}
}
//optional, but it's not necessary to keep data for this amount since we won't ever get back here again
minCoinsForAmounts.remove(currAmount);
}
return -1;
}
/**
* Given a target number an a set of step increments, calculate in how many ways can we reach the target starting from 0
* using the available step increments.
* @param target the target number to reach starting from 0.
* @param steps the available step increments to move forward.
* @return the number of ways the target can be reached using the available steps.
*/
public static int howManyWaysforTarget(int target, int... steps){
if(target < 0 || steps == null || steps.length == 0){
return -1;
}
//no need to run calculation, if target equals start position, there is only one way to reach it
if(target == 0){
return 1;
}
//key = target, value = number of ways to reach it
Map<Integer, Integer> waysForTargets = new HashMap<>();
waysForTargets.put(0, 1);
/*
Similar to minimumCoinsForChange we can use that approach but inverted to find this solution. Start from 0
and branch up, the faster routes will reach targets before slower ones, whenever a route reaches an existing target
it is guaranteed by the BFS approach that all other faster options that the current route have already been explored
*/
Queue<Integer> targets = new LinkedList<>();
targets.add(0);
while(!targets.isEmpty()){
int currTarget = targets.poll();
for(int step : steps){
int newTarget = currTarget + step;
//we jump too far
if(newTarget > target){
continue;
}
Integer waysForTarget = waysForTargets.get(newTarget);
//if we see this new target for the first time, the number of ways to reach it is exactly the same as
//the number of ways to reach us since there's only one path to here
if(waysForTarget == null){
waysForTargets.put(newTarget, waysForTargets.get(currTarget));
//if new target is the goal, no need to queue it since we won't gain anything from exploring it
if(newTarget < target) {
targets.add(newTarget);
}
}
//otherwise we've already seen this target from quicker routes, the number of ways to reach it is the sum
//of the ways to reach it from the other routes, plus the number of ways to reach us
//and there is no need to continue from us since that target will be in the queue already somewhere later than us
else {
waysForTargets.put(newTarget, waysForTarget + waysForTargets.get(currTarget));
}
}
//optional, but it's not necessary to keep data for this target since we won't ever get back here again
waysForTargets.remove(currTarget);
}
//last check in case we could not find a route to the target with the given steps
Integer waysForTarget = waysForTargets.get(target);
if(waysForTarget == null){
return -1;
}
return waysForTarget;
}
/**
* Given an array of numbers and a target, find how many subsequences in the array sum up to the target.
* Numbers are all positive and no duplicates are present, array is not sorted.
* @param target the target to reach.
* @param numbers the available numbers.
* @return the number of subsequences that sum up to given target, -1 if none exist.
*/
public static int howManySubsequencesSumUpToTarget(int target, int... numbers){
if(target <= 0 || numbers == null || numbers.length == 0){
return -1;
}
/*
Similar to howManyWaysforTarget but we can't reuse already chosen values, therefore walk the array and process all elements
in the queue at that level, then move on to the next element and repeat the process.
Everytime we reach the target, we track it.
*/
Queue<Integer> targets = new LinkedList<>();
targets.add(0);
int currNumber = -1;
int totWays = 0;
//keep going until we have made a choice for all numbers in the queue
while(!targets.isEmpty()){
int currTarget = targets.poll();
//0 was the starting "pick none" choice, whenever we encounter it, we need to advance to the next number in our input
//then enqueue it again immediately as it will denote when we are finished considering the current element
//and can advance to the next
if(currTarget == 0) {
currNumber++;
}
//we have exhausted all elements in input, must stop the search
if(currNumber >= numbers.length){
break;
}
//choose to NOT add this number to this target, simply enqueue the previous one
//no point in adding if we are at the end of array, either we found the result or not
if(currNumber + 1 < numbers.length) {
targets.add(currTarget);
}
//choose to add this number to this target
int step = numbers[currNumber];
int newTarget = currTarget + step;
//we jump too far, cannot choose this number together with us
if(newTarget > target){
continue;
}
//if new target is the goal, no need to queue it since we won't gain anything from exploring it
//so simply count the way and move on, otherwise, enqueue it
if(newTarget < target) {
if(currNumber + 1 < numbers.length) {
targets.add(newTarget);
}
}
else{
totWays++;
}
}
//maybe it was impossible to reach the target
if(totWays == 0){
return -1;
}
return totWays;
}
//helper for eulerianPath
private static void findEulerianPath(LinkedList<String> out, Map<String, PriorityQueue<String>> edges, String source){
//get possible destinations from this source
PriorityQueue<String> destinations = edges.getOrDefault(source, new PriorityQueue<>());
//for each destination, explore it
while(!destinations.isEmpty()){
//next destination in alphabetical order
//mark edge as visited (remove from the queue) so we won't visit it again
String next = destinations.poll();
//if we have no more edges, remove the whole entry from the map
//we will need this later to check if we explored all edges
if(destinations.isEmpty()) {
edges.remove(source);
}
else{
edges.put(source, destinations);
}
//explore this edge
findEulerianPath(out, edges, next);
}
//when we have explored all edges of this vertex, append vertex to HEAD of path
out.addFirst(source);
}
/**
* Given a list of flights and a start airport, find the earliest lexicographically sorted path that covers all
* tickets, if it exists.
* @param tickets the flights in the form source,destination.
* @param start the starting airport.
* @return the earliest lexicographically sorted path that covers all tickets.
*/
public static List<String> eulerianPath(List<List<String>> tickets, String start){
LinkedList<String> out = new LinkedList<>();
if(tickets == null || tickets.isEmpty() || start == null || start.isEmpty()){
return out;
}
//key = source, value = alphabetically sorted destinations
Map<String, PriorityQueue<String>> edges = new HashMap<>();
/*
//optional - all vertices in the graph
Set<String> vertices = new HashSet<>();
//optional - find a start and end path candidates
Map<String, Integer> inDegrees = new HashMap<>();
Map<String, Integer> outDegrees = new HashMap<>();
*/
//populate map from tickets, priority queue will sort destinations for us
for(List<String> edge : tickets){
String source = edge.get(0);
String dest = edge.get(1);
PriorityQueue<String> destinations = edges.getOrDefault(source, new PriorityQueue<>());
destinations.add(dest);
edges.put(source, destinations);
/*
//optional - track in and out degree for this vertex
int inDegree = inDegrees.getOrDefault(dest, 0);
inDegrees.put(dest, inDegree + 1);
int outDegree = outDegrees.getOrDefault(source, 0);
outDegrees.put(source, outDegree + 1);
//optional - track vertices
vertices.add(source);
vertices.add(dest);
*/
}
/*
//optional - check if a path can be formed
//count out degree - in degree = 1, if more vertices satisfy this condition, there is not path
int countOutIn = 0;
//count out in degree - out degree = 1, if more vertices satisfy this condition, there is not path
int countInOut = 0;
for(String vertex : vertices){
if(outDegrees.getOrDefault(vertex, 0) - inDegrees.getOrDefault(vertex, 0) == 1){
countOutIn++;
}
if(countOutIn > 1){
return out;
}
if(inDegrees.getOrDefault(vertex, 0) - outDegrees.getOrDefault(vertex, 0) == 1){
countInOut++;
}
if(countInOut > 1){
return out;
}
}
*/
//find the path
findEulerianPath(out, edges, start);
//if we have some edges left, we did NOT find a path that traversed all of them
if(!edges.isEmpty()){
return new ArrayList<>();
}
return out;
}
//helper for findAllPathsFromSourceToDestInDAG
private static void buildPathsFromSourceToDestInDAG(List<List<Integer>> out, Stack<Integer> s, int[][] graph){
//top element is last on current path, we continue from there
int top = s.peek();
//if we have reached destination, add all nodes in stack to solution
if(top == graph.length - 1){
//foreach on stack gives elements starting at bottom, so no need to addFirst
List<Integer> res = new ArrayList<>(s.size());
for(Integer i : s){
res.add(i);
}
out.add(res);
}
//otherwise, pick an edge and explore from there
else{
for(int j = 0; j < graph[top].length; j++){
//add this destination to stack
s.push(graph[top][j]);
//explore from there
buildPathsFromSourceToDestInDAG(out, s, graph);
//remove that destination from stack and continue
s.pop();
}
}
}
/**
* Given a DAG, find all paths from a given source and destination.
* @param graph the adjacency list represented with an array of arrays. Start is element 0, end is element size - 1.
* @return the list of app paths from source to dest in the given DAG.
*/
public static List<List<Integer>> findAllPathsFromSourceToDestInDAG(int[][] graph) {
List<List<Integer>> out = new ArrayList<>();
if(graph == null || graph.length == 0){
return out;
}
/*
Add source to a stack, then use recursion to find all paths from source to dest.
Each time we pick one edge, add the destination to the stack and call recursion on that destination.
When destination is reached, we scan the scan and track all elements as a solution.
When we get back from a recursive call, we remove ourselves from the stack.
*/
Stack<Integer> s = new Stack<>();
s.push(0);
buildPathsFromSourceToDestInDAG(out, s, graph);
return out;
}
//helper for twoColor
//runs DFS to attempt 2 coloring all vertices connected to a given source
private static boolean twoColorGraph(int v, Map<Integer, Set<Integer>> adj, Map<Integer, Integer> vColor){
//check if this node has a color
int currColor = vColor.getOrDefault(v, -1);
//if not, assign a default value to it
if(currColor == -1){
currColor = 1;
vColor.put(v, 1);
}
//color its neighbors of the opposite color
for(int next : adj.getOrDefault(v, new HashSet<>())){
//get neighbor color
int nextColor = vColor.getOrDefault(next, -1);
//if it has no color, color it the opposite color of current vertex
if(nextColor == -1){
//1 - color will invert between 0 and 1 values: 1 - 0 = 1, 1 - 1 = 0
vColor.put(next, 1 - vColor.get(v));
//then continue coloring from that vertex, if it can't be done, stop and return failure
if(!twoColorGraph(next, adj, vColor)){
return false;
}
}
//if neighbor has a color and it's same as us, stop and return failure, otherwise continue with next neighbor
else{
if(nextColor == currColor){
return false;
}
}
}
return true;
}
/**
* Given a graph expressed with adjacency list, return a 2 coloring (bipartition) of it, if possible.
* @param graph the input graph.
* @return if possible, a bipartition (2 coloring) of the given graph.
*/
public static Map<Integer, Integer> twoColor(int[][] graph){
if(graph == null || graph.length == 0 || graph[0].length == 0){
return new HashMap<>();
}
//convert input to adjacency list
Map<Integer, Set<Integer>> adj = new HashMap<>();
for(int[] edge : graph){
//edge is bidirectional first <-> second
int f = edge[0];
int s = edge[1];
Set<Integer> fe = adj.getOrDefault(f, new HashSet<>());
Set<Integer> se = adj.getOrDefault(s, new HashSet<>());
fe.add(s);
se.add(f);
adj.put(f, fe);
adj.put(s, se);
}
//will contain the vertices colors if graph can be colored
//could also be an array where idx = vertex and value = color
//but then it is assumed all vertices are in increasing order value
Map<Integer, Integer> vColor = new HashMap<>();
for(int v : adj.keySet()){
//skip already colored vertices
if(vColor.get(v) != null){
continue;
}
//otherwise attempt coloring via DFS, if it can't be done, stop and return
if(!twoColorGraph(v, adj, vColor)){
return new HashMap<>();
}
}
return vColor;
}
/**
* Given a series of equality and inequality equations, verify whether they can be satisfied.
* Equations are in the form:
* a==b
* a!=b
* Where a,b are the two variables
* Example:
* a==b, b==c, c==a -> ok
* a==b, b==c, c!=a -> ko
* @param equations the input equations.
* @return true if all equations can be satisfied.
*/
public static boolean equationsPossible(String[] equations){
if(equations == null || equations.length == 0){
return true;
}
//track here for each variable, all equal variables (same color)
Map<Character, Set<Character>> sameColor = new HashMap<>();
//track here for each variable its color
Map<Character, Integer> charColor = new HashMap<>();
//parse all equations to build an adjacency list from equality equations
for (String eq: equations) {
//all variables here must have same color later
if (eq.charAt(1) == '=') {
char f = eq.charAt(0);
char s = eq.charAt(eq.length() - 1);
Set<Character> fSet = sameColor.getOrDefault(f, new HashSet<>());
Set<Character> sSet = sameColor.getOrDefault(s, new HashSet<>());
fSet.add(s);
sSet.add(f);
sameColor.put(f, fSet);
sameColor.put(s, sSet);
}
}
//start coloring each variable
int nextColor = -1;
//pick any variable and color all its neighbors with the same color
for (char c : sameColor.keySet()) {
//if this variable has no color, assign the next available color to it
if (charColor.getOrDefault(c, -1) == -1) {
nextColor++;
//the color all its neigbhors with same color using DFS
Stack<Character> stack = new Stack();
stack.push(c);
while (!stack.isEmpty()) {
char next = stack.pop();
for (char same : sameColor.getOrDefault(next, new HashSet<>())) {
if (charColor.getOrDefault(same, -1) == -1) {
charColor.put(same, nextColor);
stack.push(same);
}
}
}
}
}
//now process inequality equations, based on colors previously assigned, if two variables are in a situation
//where a==b and a!=b, we cannot satisfy that
for (String eq: equations) {
if (eq.charAt(1) == '!') {
char f = eq.charAt(0);
char s = eq.charAt(eq.length() - 1);
//invalid situations: a!=a OR a==b && a!=b
if (f == s || charColor.getOrDefault(f, -1) == charColor.getOrDefault(s, -2)){
return false;
}
}
}
return true;
}
}
Raw
HowManySubsequencesSumUpToTargetJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class HowManySubsequencesSumUpToTargetJTests {
int target;
int[] numbers;
@Test
public void invalidInput() {
target = -1;
numbers = new int[]{1, 5, 10, 25};
assertEquals("target -1", -1, GraphUtils.howManySubsequencesSumUpToTarget(target, numbers));
target = 1;
numbers = new int[]{};
assertEquals("no numbers", -1, GraphUtils.howManySubsequencesSumUpToTarget(target, numbers));
target = 1;
numbers = null;
assertEquals("null numbers", -1, GraphUtils.howManySubsequencesSumUpToTarget(target, numbers));
}
@Test
public void impossibleTarget() {
target = 1;
numbers = new int[]{2};
assertEquals("impossible target", -1, GraphUtils.howManySubsequencesSumUpToTarget(target, numbers));
}
@Test
public void onlyOneNumber() {
target = 1;
numbers = new int[]{1};
assertEquals("only one number equal to target", 1, GraphUtils.howManySubsequencesSumUpToTarget(target, numbers));
target = 5;
numbers = new int[]{1};
assertEquals("only one number not equal to target", -1, GraphUtils.howManySubsequencesSumUpToTarget(target, numbers));
}
@Test
public void twoNumbers() {
target = 2;
numbers = new int[]{1, 5};
assertEquals("two numbers cannot add to target", -1, GraphUtils.howManySubsequencesSumUpToTarget(target, numbers));
target = 6;
numbers = new int[]{1, 5};
assertEquals("two numbers can add to target", 1, GraphUtils.howManySubsequencesSumUpToTarget(target, numbers));
}
@Test
public void sampleTargets() {
target = 16;
numbers = new int[]{10,2,6,4};
assertEquals("10,2,6,4 target 16", 2, GraphUtils.howManySubsequencesSumUpToTarget(target, numbers));
}
}
Raw
HowManyWaysForTargetJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class HowManyWaysForTargetJTests {
int target;
int[] steps;
@Test
public void invalidInput() {
target = -1;
steps = new int[]{1, 5, 10, 25};
assertEquals("target -1 expected -1", -1, GraphUtils.howManyWaysforTarget(target, steps));
target = 1;
steps = new int[]{};
assertEquals("no steps expected -1", -1, GraphUtils.howManyWaysforTarget(target, steps));
target = 1;
steps = null;
assertEquals("null steps expected -1", -1, GraphUtils.howManyWaysforTarget(target, steps));
}
@Test
public void impossibleTarget() {
target = 1;
steps = new int[]{2};
assertEquals("impossible target, expected -1", -1, GraphUtils.howManyWaysforTarget(target, steps));
}
@Test
public void onlyOneStep() {
target = 1;
steps = new int[]{1};
assertEquals("only one step equal to target, expected 1", 1, GraphUtils.howManyWaysforTarget(target, steps));
target = 5;
steps = new int[]{1};
assertEquals("only one step equal to multiple of target, expected 1", 1, GraphUtils.howManyWaysforTarget(target, steps));
}
@Test
public void twoSteps() {
target = 2;
steps = new int[]{1, 5};
assertEquals("only one step less than amount, expected 1", 1, GraphUtils.howManyWaysforTarget(target, steps));
target = 5;
steps = new int[]{1, 5};
assertEquals("two steps, one equal to target, expected 2", 2, GraphUtils.howManyWaysforTarget(target, steps));
}
@Test
public void sampleTargets() {
target = 0;
steps = new int[]{1, 2, 4, 5};
assertEquals("target 0, expected 1", 1, GraphUtils.howManyWaysforTarget(target, steps));
target = 3;
steps = new int[]{1, 3, 5};
assertEquals("target 3, steps 1,3,5 expected 2", 2, GraphUtils.howManyWaysforTarget(target, steps));
target = 2;
steps = new int[]{1, 3, 5};
assertEquals("target 2, steps 1,3,5 expected 1", 1, GraphUtils.howManyWaysforTarget(target, steps));
target = 4;
steps = new int[]{1, 2};
assertEquals("target 4, steps 1,2 expected 5", 5, GraphUtils.howManyWaysforTarget(target, steps));
}
}
Raw
InOutEdge.java
package com.blogspot.groglogs.structures;
import java.util.Objects;
public class InOutEdge {
private String label;
private int weight;
private Vertex startVertex, endVertex;
public InOutEdge(String label, int weight, Vertex startVertex, Vertex endVertex){
this.label = label;
this.weight = weight;
this.startVertex = startVertex;
this.endVertex = endVertex;
}
public InOutEdge(String label, int weight){
this.label = label;
this.weight = weight;
}
public InOutEdge(String label){
this.label = label;
this.weight = 0;
}
public InOutEdge(Vertex startVertex, Vertex endVertex){
this.label = startVertex.getLabel() + "-" + endVertex.getLabel();
this.startVertex = startVertex;
this.endVertex = endVertex;
}
public void setEndVertex(Vertex v){
this.endVertex = v;
}
public void setStartVertex(Vertex v){
this.startVertex = v;
}
public void setWeight(int weight){
this.weight = weight;
}
public String getLabel(){
return this.label;
}
public int getWeight() {
return this.weight;
}
public Vertex getEndVertex() {
return this.endVertex;
}
public Vertex getStartVertex() {
return this.startVertex;
}
@Override
public boolean equals(Object o) {
if (o == this) return true;
if (!(o instanceof InOutEdge)) {
return false;
}
InOutEdge e = (InOutEdge) o;
return label == e.label;
}
@Override
public int hashCode() {
return Objects.hash(label);
}
}
Raw
KosarajuJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import com.blogspot.groglogs.structures.InOutEdge;
import com.blogspot.groglogs.structures.Vertex;
import org.junit.Test;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
public class KosarajuJTests {
List<Vertex> vertices;
List<InOutEdge> edges;
List<Set<Vertex>> out;
@Test
public void emptyGraph() {
vertices = null;
edges = null;
out = null;
assertEquals("empty graph expected empty output", 0, GraphUtils.findStronglyConnectedComponentsKosaraju(vertices, edges).size());
}
@Test
public void singleElementGraph() {
vertices = new ArrayList<>(1);
Vertex v = new Vertex("single");
vertices.add(v);
edges = new ArrayList<>(0);
out = GraphUtils.findStronglyConnectedComponentsKosaraju(vertices, edges);
assertEquals("single element graph expected single scc", 1, out.size());
assertEquals("single element graph expected single vertex scc", 1, out.get(0).size());
assertTrue("single element graph expected single vertex output", out.get(0).contains(v));
}
@Test
public void multipleElementsAllDisconnectedGraph() {
vertices = new ArrayList<>(3);
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
edges = new ArrayList<>(0);
out = GraphUtils.findStronglyConnectedComponentsKosaraju(vertices, edges);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("multiple elements all disconnected graph expected 3 scc", 3, out.size());
for(Set<Vertex> s : out) {
assertEquals("multiple elements all disconnected graph expected single vertex scc", 1, s.size());
allVerticesInScc.addAll(s);
}
assertTrue("multiple elements all disconnected expected all vertex output", allVerticesInScc.containsAll(vertices));
}
@Test
public void twoIslandsGraph() {
vertices = new ArrayList<>(4);
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
v1.addEdge(v2);
v2.addEdge(v1);
v3.addEdge(v4);
v4.addEdge(v3);
edges = new ArrayList<>(4);
InOutEdge e1 = new InOutEdge(v1, v2);
edges.add(e1);
InOutEdge e2 = new InOutEdge(v2, v1);
edges.add(e2);
InOutEdge e3 = new InOutEdge(v3, v4);
edges.add(e3);
InOutEdge e4 = new InOutEdge(v4, v3);
edges.add(e4);
out = GraphUtils.findStronglyConnectedComponentsKosaraju(vertices, edges);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("two islands graph expected 2 scc", 2, out.size());
for(Set<Vertex> s : out) {
assertEquals("two islands graph graph expected 2 vertex scc", 2, s.size());
allVerticesInScc.addAll(s);
}
assertTrue("two islands expected all vertex output", allVerticesInScc.containsAll(vertices));
}
@Test
public void allConnectedGraph() {
vertices = new ArrayList<>(4);
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
v1.addEdge(v2);
v2.addEdge(v3);
v3.addEdge(v4);
v4.addEdge(v1);
edges = new ArrayList<>(4);
InOutEdge e1 = new InOutEdge(v1, v2);
edges.add(e1);
InOutEdge e2 = new InOutEdge(v2, v3);
edges.add(e2);
InOutEdge e3 = new InOutEdge(v3, v4);
edges.add(e3);
InOutEdge e4 = new InOutEdge(v4, v1);
edges.add(e4);
out = GraphUtils.findStronglyConnectedComponentsKosaraju(vertices, edges);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("all connected graph expected 1 scc", 1, out.size());
for(Set<Vertex> s : out) {
assertEquals("all connected graph expected all vertices in scc", vertices.size(), s.size());
allVerticesInScc.addAll(s);
}
assertTrue("all connected graph expected all vertices in output", allVerticesInScc.containsAll(vertices));
}
@Test
public void sampleGraph() {
/*
2 6 -> 7
^ \ ^ /|
/ \ | / |
/ \ | / |
/ v | v v
1 <- 3 -> 4 -> 5 -> 8
*/
vertices = new ArrayList<>();
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
Vertex v5 = new Vertex("5");
vertices.add(v5);
Vertex v6 = new Vertex("6");
vertices.add(v6);
Vertex v7 = new Vertex("7");
vertices.add(v7);
Vertex v8 = new Vertex("8");
vertices.add(v8);
v1.addEdge(v2);
v2.addEdge(v3);
v3.addEdge(v1);
v3.addEdge(v4);
v4.addEdge(v5);
v5.addEdge(v6);
v5.addEdge(v8);
v6.addEdge(v7);
v7.addEdge(v5);
v7.addEdge(v8);
edges = new ArrayList<>();
InOutEdge e1 = new InOutEdge(v1, v2);
edges.add(e1);
InOutEdge e2 = new InOutEdge(v2, v3);
edges.add(e2);
InOutEdge e3 = new InOutEdge(v3, v1);
edges.add(e3);
InOutEdge e4 = new InOutEdge(v3, v4);
edges.add(e4);
InOutEdge e5 = new InOutEdge(v4, v5);
edges.add(e5);
InOutEdge e6 = new InOutEdge(v5, v6);
edges.add(e6);
InOutEdge e7 = new InOutEdge(v5, v8);
edges.add(e7);
InOutEdge e8 = new InOutEdge(v6, v7);
edges.add(e8);
InOutEdge e9 = new InOutEdge(v7, v5);
edges.add(e9);
InOutEdge e10 = new InOutEdge(v7, v8);
edges.add(e10);
out = GraphUtils.findStronglyConnectedComponentsKosaraju(vertices, edges);
Set<Vertex> scc1 = new HashSet<>();
scc1.add(v1);
scc1.add(v2);
scc1.add(v3);
Set<Vertex> scc2 = new HashSet<>();
scc2.add(v4);
Set<Vertex> scc3 = new HashSet<>();
scc3.add(v5);
scc3.add(v6);
scc3.add(v7);
Set<Vertex> scc4 = new HashSet<>();
scc4.add(v8);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("sample graph expected 4 scc", 4, out.size());
for(Set<Vertex> s : out) {
allVerticesInScc.addAll(s);
if(s.size() == 1){
assertTrue("sample graph expected scc are correct", s.containsAll(scc2) || s.containsAll(scc4));
} else {
assertTrue("sample graph expected scc are correct", s.containsAll(scc1) || s.containsAll(scc3));
}
System.out.println("SCC is:");
for(Vertex v : s){
System.out.print(v.getLabel() + ", ");
}
System.out.println("----");
}
assertTrue("sample graph expected all vertices in output", allVerticesInScc.containsAll(vertices));
}
@Test
public void otherSampleGraph() {
/*
1 <- 5
| ^
v |
2 -> 4 -> 7
| | ^
| | //
v v v
3 <- 6
*/
vertices = new ArrayList<>();
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
Vertex v5 = new Vertex("5");
vertices.add(v5);
Vertex v6 = new Vertex("6");
vertices.add(v6);
Vertex v7 = new Vertex("7");
vertices.add(v7);
v1.addEdge(v2);
v2.addEdge(v3);
v2.addEdge(v4);
v4.addEdge(v5);
v4.addEdge(v6);
v4.addEdge(v7);
v5.addEdge(v1);
v6.addEdge(v3);
v6.addEdge(v7);
v7.addEdge(v6);
edges = new ArrayList<>();
InOutEdge e1 = new InOutEdge(v1, v2);
edges.add(e1);
InOutEdge e2 = new InOutEdge(v2, v3);
edges.add(e2);
InOutEdge e3 = new InOutEdge(v2, v4);
edges.add(e3);
InOutEdge e4 = new InOutEdge(v4, v5);
edges.add(e4);
InOutEdge e5 = new InOutEdge(v4, v6);
edges.add(e5);
InOutEdge e6 = new InOutEdge(v4, v7);
edges.add(e6);
InOutEdge e7 = new InOutEdge(v5, v1);
edges.add(e7);
InOutEdge e8 = new InOutEdge(v6, v3);
edges.add(e8);
InOutEdge e9 = new InOutEdge(v6, v7);
edges.add(e9);
InOutEdge e10 = new InOutEdge(v7, v6);
edges.add(e10);
out = GraphUtils.findStronglyConnectedComponentsKosaraju(vertices, edges);
Set<Vertex> scc1 = new HashSet<>();
scc1.add(v3);
Set<Vertex> scc2 = new HashSet<>();
scc2.add(v6);
scc2.add(v7);
Set<Vertex> scc3 = new HashSet<>();
scc3.add(v1);
scc3.add(v2);
scc3.add(v4);
scc3.add(v5);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("other sample graph expected 3 scc", 3, out.size());
for(Set<Vertex> s : out) {
allVerticesInScc.addAll(s);
if(s.size() == 1){
assertTrue("other sample graph expected scc are correct", s.containsAll(scc1));
} else if(s.size() == 2) {
assertTrue("other sample graph expected scc are correct", s.containsAll(scc2));
} else {
assertTrue("other sample graph expected scc are correct", s.containsAll(scc3));
}
System.out.println("SCC is:");
for(Vertex v : s){
System.out.print(v.getLabel() + ", ");
}
System.out.println("----");
}
assertTrue("other sample graph expected all vertices in output", allVerticesInScc.containsAll(vertices));
}
}
Raw
MinimumCoinsForChangeJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class MinimumCoinsForChangeJTests {
int change;
int[] coins;
@Test
public void invalidInput() {
change = 0;
coins = new int[]{1, 5, 10, 25};
assertEquals("change 0 expected -1", -1, GraphUtils.minimumCoinsForChange(change, coins));
change = 1;
coins = new int[]{};
assertEquals("no coins expected -1", -1, GraphUtils.minimumCoinsForChange(change, coins));
change = 1;
coins = null;
assertEquals("null coins expected -1", -1, GraphUtils.minimumCoinsForChange(change, coins));
}
@Test
public void impossibleAmount() {
change = 1;
coins = new int[]{2};
assertEquals("impossible amount, expected -1", -1, GraphUtils.minimumCoinsForChange(change, coins));
}
@Test
public void onlyOneCoin() {
change = 1;
coins = new int[]{1};
assertEquals("only one coin equal to amount, expected 1", 1, GraphUtils.minimumCoinsForChange(change, coins));
change = 5;
coins = new int[]{1};
assertEquals("only one coin equal to multiple of amount, expected 5", 5, GraphUtils.minimumCoinsForChange(change, coins));
}
@Test
public void twoCoins() {
change = 2;
coins = new int[]{1, 5};
assertEquals("only one coin less than amount, expected 2", 2, GraphUtils.minimumCoinsForChange(change, coins));
change = 5;
coins = new int[]{1, 5};
assertEquals("two coins, one equal to amount, expected 1", 1, GraphUtils.minimumCoinsForChange(change, coins));
}
@Test
public void sampleAmounts() {
change = 32;
coins = new int[]{1, 5, 10, 25};
assertEquals("amount 32, coins 1,5,10,25 expected 4", 4, GraphUtils.minimumCoinsForChange(change, coins));
change = 6;
coins = new int[]{1, 3, 4};
assertEquals("amount 6, coins 1,3,4 expected 2", 2, GraphUtils.minimumCoinsForChange(change, coins));
}
}
Raw
MinimumEdgesForFullyConnectedGraphJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import com.blogspot.groglogs.structures.Vertex;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
public class MinimumEdgesForFullyConnectedGraphJTests {
List<Vertex> vertices;
Vertex start;
Set<Vertex> out;
@Test
public void emptyNullGraph() {
vertices = null;
out = null;
start = null;
assertEquals("null everything expected empty output", 0, GraphUtils.findMinimumNewEdgesForFullyConnectedGraphFromStart(vertices, start).size());
vertices = null;
out = null;
start = new Vertex("1");
assertEquals("null graph expected empty output", 0, GraphUtils.findMinimumNewEdgesForFullyConnectedGraphFromStart(vertices, start).size());
vertices = new ArrayList<>(1);
vertices.add(new Vertex("1"));
out = null;
start = null;
assertEquals("null start expected empty output", 0, GraphUtils.findMinimumNewEdgesForFullyConnectedGraphFromStart(vertices, start).size());
vertices = new ArrayList<>();
out = null;
start = null;
assertEquals("empty graph expected empty output", 0, GraphUtils.findMinimumNewEdgesForFullyConnectedGraphFromStart(vertices, start).size());
}
@Test
public void singleElementGraph() {
vertices = new ArrayList<>(1);
Vertex v = new Vertex("single");
vertices.add(v);
start = v;
out = GraphUtils.findMinimumNewEdgesForFullyConnectedGraphFromStart(vertices, start);
assertEquals("single element graph expected no new connections", 0, out.size());
}
@Test
public void multipleElementsAllDisconnectedGraph() {
vertices = new ArrayList<>(3);
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
start = v1;
out = GraphUtils.findMinimumNewEdgesForFullyConnectedGraphFromStart(vertices, start);
assertEquals("multiple elements all disconnected graph expected V - 1 connections", vertices.size() - 1, out.size());
assertTrue("multiple elements all disconnected expected no start in output", !out.contains(start));
}
@Test
public void allConnectedGraph() {
vertices = new ArrayList<>(4);
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
v1.addEdge(v2);
v2.addEdge(v3);
v3.addEdge(v4);
v4.addEdge(v1);
start = v1;
out = GraphUtils.findMinimumNewEdgesForFullyConnectedGraphFromStart(vertices, start);
assertEquals("all connected graph expected 0 connections", 0, out.size());
}
@Test
public void twoIslandsGraph() {
vertices = new ArrayList<>(4);
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
v1.addEdge(v2);
v2.addEdge(v1);
v3.addEdge(v4);
v4.addEdge(v3);
start = v1;
out = GraphUtils.findMinimumNewEdgesForFullyConnectedGraphFromStart(vertices, start);
assertEquals("two islands graph expected 1 connection", 1, out.size());
assertTrue("two islands expected either vertex from other subgraph", out.contains(v3) || out.contains(v4));
}
@Test
public void sampleGraph() {
/*
DSM -> ORD -> BGI -> LGA <-
^ |
| |
SFO -> SAN -> EYW -> LHR |
^ | |
\--------------------| |
|
JFK ---------------------/
^ ^
| \
ICN <- HND <- EWR
TLV -> DEL -> DOH
|
v
SIN <-> CDG -> BUD
Contains the following SCCs:
SCC1 = EYW, LHR, SFO, SAN
SCC2 = SIN, CDG
Simplified graph:
SCC1 -> DSM -> ORD -> BGI -> LGA
^
EWR -> HND -> JFK ------------|
| ^
v /
ICN
TLV -> DEL -> SCC2 -> BUD
|
v
DOH
Start node is LGA, we expect 3 connections: EWR, TLV, any node in SCC1
*/
vertices = new ArrayList<>();
Vertex dsm = new Vertex("dsm");
vertices.add(dsm);
Vertex ord = new Vertex("ord");
vertices.add(ord);
Vertex bgi = new Vertex("bgi");
vertices.add(bgi);
Vertex lga = new Vertex("lga");
vertices.add(lga);
Vertex sin = new Vertex("sin");
vertices.add(sin);
Vertex cdg = new Vertex("cdg");
vertices.add(cdg);
Vertex bud = new Vertex("bud");
vertices.add(bud);
Vertex del = new Vertex("del");
vertices.add(del);
Vertex doh = new Vertex("doh");
vertices.add(doh);
Vertex tlv = new Vertex("tlv");
vertices.add(tlv);
Vertex ewr = new Vertex("ewr");
vertices.add(ewr);
Vertex hnd = new Vertex("hnd");
vertices.add(hnd);
Vertex icn = new Vertex("icn");
vertices.add(icn);
Vertex jfk = new Vertex("jfk");
vertices.add(jfk);
Vertex eyw = new Vertex("eyw");
vertices.add(eyw);
Vertex lhr = new Vertex("lhr");
vertices.add(lhr);
Vertex sfo = new Vertex("sfo");
vertices.add(sfo);
Vertex san = new Vertex("san");
vertices.add(san);
dsm.addEdge(ord);
ord.addEdge(bgi);
bgi.addEdge(lga);
sin.addEdge(cdg);
cdg.addEdge(sin);
cdg.addEdge(bud);
del.addEdge(cdg);
del.addEdge(doh);
tlv.addEdge(del);
ewr.addEdge(hnd);
hnd.addEdge(icn);
hnd.addEdge(jfk);
icn.addEdge(jfk);
jfk.addEdge(lga);
eyw.addEdge(lhr);
lhr.addEdge(sfo);
sfo.addEdge(san);
sfo.addEdge(dsm);
san.addEdge(eyw);
start = lga;
out = GraphUtils.findMinimumNewEdgesForFullyConnectedGraphFromStart(vertices, start);
assertEquals("sample graph expected 3 connection", 3, out.size());
assertTrue("sample graph expected EWR connection", out.contains(ewr));
assertTrue("sample graph expected TLV connection", out.contains(tlv));
assertTrue("sample graph expected connection to SCC1", out.contains(eyw) || out.contains(lhr) || out.contains(sfo) || out.contains(san));
}
}
Raw
OutEdge.java
package com.blogspot.groglogs.structures;
import java.util.Objects;
public class OutEdge {
private String label;
private int weight;
private Vertex endVertex;
public OutEdge(String label, int weight, Vertex endVertex){
this.label = label;
this.weight = weight;
this.endVertex = endVertex;
}
public OutEdge(String label, int weight){
this.label = label;
this.weight = weight;
}
public OutEdge(String label, Vertex endVertex){
this.label = label;
this.weight = 0;
this.endVertex = endVertex;
}
public OutEdge(String label){
this.label = label;
this.weight = 0;
}
public OutEdge(Vertex endVertex){
this.label = endVertex.getLabel();
this.endVertex = endVertex;
this.weight = 0;
}
public void setEndVertex(Vertex v){
this.endVertex = v;
}
public void setWeight(int weight){
this.weight = weight;
}
public String getLabel(){
return this.label;
}
public int getWeight() {
return this.weight;
}
public Vertex getEndVertex() {
return this.endVertex;
}
@Override
public boolean equals(Object o) {
if (o == this) return true;
if (!(o instanceof OutEdge)) {
return false;
}
OutEdge e = (OutEdge) o;
return label == e.label;
}
@Override
public int hashCode() {
return Objects.hash(label);
}
}
Raw
PathBasedSCCJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import com.blogspot.groglogs.structures.Vertex;
import org.junit.Test;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
public class PathBasedSCCJTests {
List<Vertex> vertices;
List<Set<Vertex>> out;
@Test
public void emptyGraph() {
vertices = null;
out = null;
assertEquals("empty graph expected empty output", 0, GraphUtils.findStronglyConnectedComponentsPathBased(vertices).size());
}
@Test
public void singleElementGraph() {
vertices = new ArrayList<>(1);
Vertex v = new Vertex("single");
vertices.add(v);
out = GraphUtils.findStronglyConnectedComponentsPathBased(vertices);
assertEquals("single element graph expected single scc", 1, out.size());
assertEquals("single element graph expected single vertex scc", 1, out.get(0).size());
assertTrue("single element graph expected single vertex output", out.get(0).contains(v));
}
@Test
public void multipleElementsAllDisconnectedGraph() {
vertices = new ArrayList<>(3);
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
out = GraphUtils.findStronglyConnectedComponentsPathBased(vertices);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("multiple elements all disconnected graph expected 3 scc", 3, out.size());
for(Set<Vertex> s : out) {
assertEquals("multiple elements all disconnected graph expected single vertex scc", 1, s.size());
allVerticesInScc.addAll(s);
}
assertTrue("multiple elements all disconnected expected all vertex output", allVerticesInScc.containsAll(vertices));
}
@Test
public void twoIslandsGraph() {
vertices = new ArrayList<>(4);
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
v1.addEdge(v2);
v2.addEdge(v1);
v3.addEdge(v4);
v4.addEdge(v3);
out = GraphUtils.findStronglyConnectedComponentsPathBased(vertices);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("two islands graph expected 2 scc", 2, out.size());
for(Set<Vertex> s : out) {
assertEquals("two islands graph graph expected 2 vertex scc", 2, s.size());
allVerticesInScc.addAll(s);
}
assertTrue("two islands expected all vertex output", allVerticesInScc.containsAll(vertices));
}
@Test
public void allConnectedGraph() {
vertices = new ArrayList<>(4);
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
v1.addEdge(v2);
v2.addEdge(v3);
v3.addEdge(v4);
v4.addEdge(v1);
out = GraphUtils.findStronglyConnectedComponentsPathBased(vertices);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("all connected graph expected 1 scc", 1, out.size());
for(Set<Vertex> s : out) {
assertEquals("all connected graph expected all vertices in scc", vertices.size(), s.size());
allVerticesInScc.addAll(s);
}
assertTrue("all connected graph expected all vertices in output", allVerticesInScc.containsAll(vertices));
}
@Test
public void sampleGraph() {
/*
2 6 -> 7
^ \ ^ /|
/ \ | / |
/ \ | / |
/ v | v v
1 <- 3 -> 4 -> 5 -> 8
*/
vertices = new ArrayList<>();
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
Vertex v5 = new Vertex("5");
vertices.add(v5);
Vertex v6 = new Vertex("6");
vertices.add(v6);
Vertex v7 = new Vertex("7");
vertices.add(v7);
Vertex v8 = new Vertex("8");
vertices.add(v8);
v1.addEdge(v2);
v2.addEdge(v3);
v3.addEdge(v1);
v3.addEdge(v4);
v4.addEdge(v5);
v5.addEdge(v6);
v5.addEdge(v8);
v6.addEdge(v7);
v7.addEdge(v5);
v7.addEdge(v8);
out = GraphUtils.findStronglyConnectedComponentsPathBased(vertices);
Set<Vertex> scc1 = new HashSet<>();
scc1.add(v1);
scc1.add(v2);
scc1.add(v3);
Set<Vertex> scc2 = new HashSet<>();
scc2.add(v4);
Set<Vertex> scc3 = new HashSet<>();
scc3.add(v5);
scc3.add(v6);
scc3.add(v7);
Set<Vertex> scc4 = new HashSet<>();
scc4.add(v8);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("sample graph expected 4 scc", 4, out.size());
for(Set<Vertex> s : out) {
allVerticesInScc.addAll(s);
if(s.size() == 1){
assertTrue("sample graph expected scc are correct", s.containsAll(scc2) || s.containsAll(scc4));
} else {
assertTrue("sample graph expected scc are correct", s.containsAll(scc1) || s.containsAll(scc3));
}
System.out.println("SCC is:");
for(Vertex v : s){
System.out.print(v.getLabel() + ", ");
}
System.out.println("----");
}
assertTrue("sample graph expected all vertices in output", allVerticesInScc.containsAll(vertices));
}
@Test
public void otherSampleGraph() {
/*
1 <- 5
| ^
v |
2 -> 4 -> 7
| | ^
| | //
v v v
3 <- 6
*/
vertices = new ArrayList<>();
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
Vertex v5 = new Vertex("5");
vertices.add(v5);
Vertex v6 = new Vertex("6");
vertices.add(v6);
Vertex v7 = new Vertex("7");
vertices.add(v7);
v1.addEdge(v2);
v2.addEdge(v3);
v2.addEdge(v4);
v4.addEdge(v5);
v4.addEdge(v6);
v4.addEdge(v7);
v5.addEdge(v1);
v6.addEdge(v3);
v6.addEdge(v7);
v7.addEdge(v6);
out = GraphUtils.findStronglyConnectedComponentsPathBased(vertices);
Set<Vertex> scc1 = new HashSet<>();
scc1.add(v3);
Set<Vertex> scc2 = new HashSet<>();
scc2.add(v6);
scc2.add(v7);
Set<Vertex> scc3 = new HashSet<>();
scc3.add(v1);
scc3.add(v2);
scc3.add(v4);
scc3.add(v5);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("other sample graph expected 3 scc", 3, out.size());
for(Set<Vertex> s : out) {
allVerticesInScc.addAll(s);
if(s.size() == 1){
assertTrue("other sample graph expected scc are correct", s.containsAll(scc1));
} else if(s.size() == 2) {
assertTrue("other sample graph expected scc are correct", s.containsAll(scc2));
} else {
assertTrue("other sample graph expected scc are correct", s.containsAll(scc3));
}
System.out.println("SCC is:");
for(Vertex v : s){
System.out.print(v.getLabel() + ", ");
}
System.out.println("\n----");
}
assertTrue("other sample graph expected all vertices in output", allVerticesInScc.containsAll(vertices));
}
}
Raw
TarjanJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import com.blogspot.groglogs.structures.Vertex;
import org.junit.Test;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
public class TarjanJTests {
List<Vertex> vertices;
List<Set<Vertex>> out;
@Test
public void emptyGraph() {
vertices = null;
out = null;
assertEquals("empty graph expected empty output", 0, GraphUtils.findStronglyConnectedComponentsTarjan(vertices).size());
}
@Test
public void singleElementGraph() {
vertices = new ArrayList<>(1);
Vertex v = new Vertex("single");
vertices.add(v);
out = GraphUtils.findStronglyConnectedComponentsTarjan(vertices);
assertEquals("single element graph expected single scc", 1, out.size());
assertEquals("single element graph expected single vertex scc", 1, out.get(0).size());
assertTrue("single element graph expected single vertex output", out.get(0).contains(v));
}
@Test
public void multipleElementsAllDisconnectedGraph() {
vertices = new ArrayList<>(3);
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
out = GraphUtils.findStronglyConnectedComponentsTarjan(vertices);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("multiple elements all disconnected graph expected 3 scc", 3, out.size());
for(Set<Vertex> s : out) {
assertEquals("multiple elements all disconnected graph expected single vertex scc", 1, s.size());
allVerticesInScc.addAll(s);
}
assertTrue("multiple elements all disconnected expected all vertex output", allVerticesInScc.containsAll(vertices));
}
@Test
public void twoIslandsGraph() {
vertices = new ArrayList<>(4);
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
v1.addEdge(v2);
v2.addEdge(v1);
v3.addEdge(v4);
v4.addEdge(v3);
out = GraphUtils.findStronglyConnectedComponentsTarjan(vertices);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("two islands graph expected 2 scc", 2, out.size());
for(Set<Vertex> s : out) {
assertEquals("two islands graph graph expected 2 vertex scc", 2, s.size());
allVerticesInScc.addAll(s);
}
assertTrue("two islands expected all vertex output", allVerticesInScc.containsAll(vertices));
}
@Test
public void allConnectedGraph() {
vertices = new ArrayList<>(4);
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
v1.addEdge(v2);
v2.addEdge(v3);
v3.addEdge(v4);
v4.addEdge(v1);
out = GraphUtils.findStronglyConnectedComponentsTarjan(vertices);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("all connected graph expected 1 scc", 1, out.size());
for(Set<Vertex> s : out) {
assertEquals("all connected graph expected all vertices in scc", vertices.size(), s.size());
allVerticesInScc.addAll(s);
}
assertTrue("all connected graph expected all vertices in output", allVerticesInScc.containsAll(vertices));
}
@Test
public void sampleGraph() {
/*
2 6 -> 7
^ \ ^ /|
/ \ | / |
/ \ | / |
/ v | v v
1 <- 3 -> 4 -> 5 -> 8
*/
vertices = new ArrayList<>();
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
Vertex v5 = new Vertex("5");
vertices.add(v5);
Vertex v6 = new Vertex("6");
vertices.add(v6);
Vertex v7 = new Vertex("7");
vertices.add(v7);
Vertex v8 = new Vertex("8");
vertices.add(v8);
v1.addEdge(v2);
v2.addEdge(v3);
v3.addEdge(v1);
v3.addEdge(v4);
v4.addEdge(v5);
v5.addEdge(v6);
v5.addEdge(v8);
v6.addEdge(v7);
v7.addEdge(v5);
v7.addEdge(v8);
out = GraphUtils.findStronglyConnectedComponentsTarjan(vertices);
Set<Vertex> scc1 = new HashSet<>();
scc1.add(v1);
scc1.add(v2);
scc1.add(v3);
Set<Vertex> scc2 = new HashSet<>();
scc2.add(v4);
Set<Vertex> scc3 = new HashSet<>();
scc3.add(v5);
scc3.add(v6);
scc3.add(v7);
Set<Vertex> scc4 = new HashSet<>();
scc4.add(v8);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("sample graph expected 4 scc", 4, out.size());
for(Set<Vertex> s : out) {
allVerticesInScc.addAll(s);
if(s.size() == 1){
assertTrue("sample graph expected scc are correct", s.containsAll(scc2) || s.containsAll(scc4));
} else {
assertTrue("sample graph expected scc are correct", s.containsAll(scc1) || s.containsAll(scc3));
}
System.out.println("SCC is:");
for(Vertex v : s){
System.out.print(v.getLabel() + ", ");
}
System.out.println("----");
}
assertTrue("sample graph expected all vertices in output", allVerticesInScc.containsAll(vertices));
}
@Test
public void otherSampleGraph() {
/*
1 <- 5
| ^
v |
2 -> 4 -> 7
| | ^
| | //
v v v
3 <- 6
*/
vertices = new ArrayList<>();
Vertex v1 = new Vertex("1");
vertices.add(v1);
Vertex v2 = new Vertex("2");
vertices.add(v2);
Vertex v3 = new Vertex("3");
vertices.add(v3);
Vertex v4 = new Vertex("4");
vertices.add(v4);
Vertex v5 = new Vertex("5");
vertices.add(v5);
Vertex v6 = new Vertex("6");
vertices.add(v6);
Vertex v7 = new Vertex("7");
vertices.add(v7);
v1.addEdge(v2);
v2.addEdge(v3);
v2.addEdge(v4);
v4.addEdge(v5);
v4.addEdge(v6);
v4.addEdge(v7);
v5.addEdge(v1);
v6.addEdge(v3);
v6.addEdge(v7);
v7.addEdge(v6);
out = GraphUtils.findStronglyConnectedComponentsTarjan(vertices);
Set<Vertex> scc1 = new HashSet<>();
scc1.add(v3);
Set<Vertex> scc2 = new HashSet<>();
scc2.add(v6);
scc2.add(v7);
Set<Vertex> scc3 = new HashSet<>();
scc3.add(v1);
scc3.add(v2);
scc3.add(v4);
scc3.add(v5);
Set<Vertex> allVerticesInScc = new HashSet<>();
assertEquals("other sample graph expected 3 scc", 3, out.size());
for(Set<Vertex> s : out) {
allVerticesInScc.addAll(s);
if(s.size() == 1){
assertTrue("other sample graph expected scc are correct", s.containsAll(scc1));
} else if(s.size() == 2) {
assertTrue("other sample graph expected scc are correct", s.containsAll(scc2));
} else {
assertTrue("other sample graph expected scc are correct", s.containsAll(scc3));
}
System.out.println("SCC is:");
for(Vertex v : s){
System.out.print(v.getLabel() + ", ");
}
System.out.println("\n----");
}
assertTrue("other sample graph expected all vertices in output", allVerticesInScc.containsAll(vertices));
}
}
Raw
TopologicalSortingJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import com.blogspot.groglogs.structures.InOutEdge;
import com.blogspot.groglogs.structures.Vertex;
import org.junit.Test;
import java.util.LinkedList;
import java.util.List;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
public class TopologicalSortingJTests {
List<InOutEdge> edges;
List<Vertex> sorted, expected;
@Test
public void nullEmpty() {
edges = null;
try {
sorted = GraphUtils.getTopologicalSorting(edges);
}catch(IllegalArgumentException e){
System.out.println("null input got IllegalArgumentException: " + e.getMessage());
}
edges = new LinkedList<>();
sorted = new LinkedList<>();
assertEquals("empty input expected empty", sorted.size(), GraphUtils.getTopologicalSorting(edges).size());
}
@Test
public void withCycle() {
edges = new LinkedList<>();
InOutEdge e = new InOutEdge(new Vertex("A"), new Vertex("B"));
edges.add(e);
e = new InOutEdge(new Vertex("B"), new Vertex("A"));
edges.add(e);
try{
sorted = GraphUtils.getTopologicalSorting(edges);
} catch(RuntimeException ex){
System.out.println("Graph with cycle got RuntimeException: " + ex.getMessage());
}
edges = new LinkedList<>();
e = new InOutEdge(new Vertex("A"), new Vertex("B"));
edges.add(e);
e = new InOutEdge(new Vertex("B"), new Vertex("C"));
edges.add(e);
e = new InOutEdge(new Vertex("C"), new Vertex("A"));
edges.add(e);
try{
sorted = GraphUtils.getTopologicalSorting(edges);
} catch(RuntimeException ex){
System.out.println("Graph with cycle got RuntimeException: " + ex.getMessage());
}
}
@Test
public void noCycle() {
edges = new LinkedList<>();
InOutEdge e = new InOutEdge(new Vertex("A"), new Vertex("B"));
edges.add(e);
e = new InOutEdge(new Vertex("B"), new Vertex("C"));
edges.add(e);
sorted = GraphUtils.getTopologicalSorting(edges);
System.out.println("AB, BC edges expected C,B,A");
for(Vertex v : sorted) System.out.println(v.getLabel());
edges = new LinkedList<>();
e = new InOutEdge(new Vertex("A"), new Vertex("B"));
edges.add(e);
e = new InOutEdge(new Vertex("B"), new Vertex("C"));
edges.add(e);
e = new InOutEdge(new Vertex("D"), new Vertex("E"));
edges.add(e);
sorted = GraphUtils.getTopologicalSorting(edges);
System.out.println("AB, BC, DE edges expected C,B,A,E,D or similar");
for(Vertex v : sorted) System.out.println(v.getLabel());
edges = new LinkedList<>();
e = new InOutEdge(new Vertex("A"), new Vertex("B"));
edges.add(e);
e = new InOutEdge(new Vertex("B"), new Vertex("C"));
edges.add(e);
e = new InOutEdge(new Vertex("D"), new Vertex("E"));
edges.add(e);
e = new InOutEdge(new Vertex("E"), new Vertex("F"));
edges.add(e);
e = new InOutEdge(new Vertex("E"), new Vertex("G"));
edges.add(e);
sorted = GraphUtils.getTopologicalSorting(edges);
System.out.println("AB, BC, DE, EF, EG edges expected C,B,A,F,G,E,D or similar");
for(Vertex v : sorted) System.out.println(v.getLabel());
}
@Test
public void nullEmptyStack() {
edges = null;
assertTrue("null", GraphUtils.getTopologicalSortingStack(edges).isEmpty());
edges = new LinkedList<>();
assertTrue("empty", GraphUtils.getTopologicalSortingStack(edges).isEmpty());
}
@Test
public void withCycleStack() {
edges = new LinkedList<>();
InOutEdge e = new InOutEdge(new Vertex("A"), new Vertex("B"));
edges.add(e);
e = new InOutEdge(new Vertex("B"), new Vertex("A"));
edges.add(e);
assertTrue("cycle a-b-a", GraphUtils.getTopologicalSortingStack(edges).isEmpty());
edges = new LinkedList<>();
e = new InOutEdge(new Vertex("A"), new Vertex("B"));
edges.add(e);
e = new InOutEdge(new Vertex("B"), new Vertex("C"));
edges.add(e);
e = new InOutEdge(new Vertex("C"), new Vertex("A"));
edges.add(e);
assertTrue("cycle a-b-c-a", GraphUtils.getTopologicalSortingStack(edges).isEmpty());
}
@Test
public void noCycleStack() {
edges = new LinkedList<>();
InOutEdge e = new InOutEdge(new Vertex("A"), new Vertex("B"));
edges.add(e);
e = new InOutEdge(new Vertex("B"), new Vertex("C"));
edges.add(e);
sorted = GraphUtils.getTopologicalSortingStack(edges);
System.out.println("stack AB, BC edges expected C,B,A");
for(Vertex v : sorted) System.out.println(v.getLabel());
edges = new LinkedList<>();
e = new InOutEdge(new Vertex("A"), new Vertex("B"));
edges.add(e);
e = new InOutEdge(new Vertex("B"), new Vertex("C"));
edges.add(e);
e = new InOutEdge(new Vertex("D"), new Vertex("E"));
edges.add(e);
sorted = GraphUtils.getTopologicalSortingStack(edges);
System.out.println("stack AB, BC, DE edges expected C,B,A,E,D or similar");
for(Vertex v : sorted) System.out.println(v.getLabel());
edges = new LinkedList<>();
e = new InOutEdge(new Vertex("A"), new Vertex("B"));
edges.add(e);
e = new InOutEdge(new Vertex("B"), new Vertex("C"));
edges.add(e);
e = new InOutEdge(new Vertex("D"), new Vertex("E"));
edges.add(e);
e = new InOutEdge(new Vertex("E"), new Vertex("F"));
edges.add(e);
e = new InOutEdge(new Vertex("E"), new Vertex("G"));
edges.add(e);
sorted = GraphUtils.getTopologicalSortingStack(edges);
System.out.println("stack AB, BC, DE, EF, EG edges expected C,B,A,F,G,E,D or similar");
for(Vertex v : sorted) System.out.println(v.getLabel());
}
}
Raw
TwoColorBipartitionJTests.java
package com.blogspot.groglogs.test.graphutils;
import com.blogspot.groglogs.graphutils.GraphUtils;
import org.junit.Test;
import java.util.HashMap;
import java.util.Map;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
public class TwoColorBipartitionJTests {
int[][] graph;
Map<Integer, Integer> expected, out;
private void checkResult(Map<Integer, Integer> expected, Map<Integer, Integer> out){
assertEquals("size", expected.size(), out.size());
for(Map.Entry<Integer, Integer> e : expected.entrySet()){
assertTrue("key is correct", out.containsKey(e.getKey()));
assertEquals("value is correct", e.getValue(), out.get(e.getKey()));
}
}
@Test
public void nullEmpty() {
graph = null;
assertTrue("null", GraphUtils.twoColor(graph).isEmpty());
graph = new int[][]{};
assertTrue("empty", GraphUtils.twoColor(graph).isEmpty());
graph = new int[][]{{}};
assertTrue("no edges", GraphUtils.twoColor(graph).isEmpty());
}
@Test
public void twoNode() {
graph = new int[][]{{1,2}};
out = GraphUtils.twoColor(graph);
expected = new HashMap<>();
expected.put(1, 1);
expected.put(2, 0);
assertEquals("two node", expected.size(), out.size());
checkResult(expected, out);
}
@Test
public void threeNode() {
graph = new int[][]{
{1,2},
{2,3},
{3,1}
};
out = GraphUtils.twoColor(graph);
expected = new HashMap<>();
assertEquals("three node no coloring", expected.size(), out.size());
checkResult(expected, out);
graph = new int[][]{
{1,2},
{2,3}
};
out = GraphUtils.twoColor(graph);
expected = new HashMap<>();
expected.put(1, 1);
expected.put(2, 0);
expected.put(3, 1);
assertEquals("three node coloring", expected.size(), out.size());
checkResult(expected, out);
}
}
Raw
Vertex.java
package com.blogspot.groglogs.structures;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
public class Vertex {
private String label;
private List<OutEdge> outEdges;
public Vertex(String label, List<OutEdge> outEdges){
this.label = label;
this.outEdges = outEdges;
}
public Vertex(String label){
this.label = label;
this.outEdges = new LinkedList<>();
}
public void addEdge(Vertex endVertex){
OutEdge e = new OutEdge(this.label + "-" + endVertex.getLabel(), endVertex);
this.outEdges.add(e);
}
public void addEdge(OutEdge e){
this.outEdges.add(e);
}
public void setOutEdges(List<OutEdge> outEdges){
this.outEdges = outEdges;
}
public String getLabel() {
return this.label;
}
public List<OutEdge> getOutEdges(){
return this.outEdges;
}
@Override
public boolean equals(Object o) {
if (o == this) return true;
if (!(o instanceof Vertex)) {
return false;
}
Vertex v = (Vertex) o;
return label == v.label;
}
@Override
public int hashCode() {
return Objects.hash(label);
}
}
@steghio
Copy link
Author

steghio commented Jan 28, 2018 •
edited

Full description at:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment