Skip to content

Instantly share code, notes, and snippets.

@johncarl81

johncarl81/gist:1920172

Created February 27, 2012 00:47
Show Gist options
  • Save johncarl81/1920172 to your computer and use it in GitHub Desktop.
Save johncarl81/1920172 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.txt
package org.cs500.homework3
import org.junit.Before;
import org.junit.Test;
import java.util.*;
import static junit.framework.Assert.assertFalse;
import static junit.framework.Assert.assertTrue;
/**
* @author John Ericksen
*/
public class Tester {
private GraphFactory graphFactory;
@Before
public void setup(){
graphFactory = new GraphFactory();
}
@Test
public void test(){
testGraph("0 1 1 1 \n" +
"1 0 1 1 \n" +
"1 1 0 1 \n" +
"1 1 1 0", 4, 3);
testGraph("0 0 0 1 1 1 \n" +
"0 0 0 1 1 1 \n" +
"0 0 0 1 1 1 \n" +
"1 1 1 0 0 0 \n" +
"1 1 1 0 0 0 \n" +
"1 1 1 0 0 0 ", 6, 3);
testGraph("0 1 0 0 0 0 1 1 \n" +
"1 0 1 0 0 0 0 1 \n" +
"0 1 0 1 0 0 0 1 \n" +
"0 0 1 0 1 0 0 1 \n" +
"0 0 0 1 0 1 0 1 \n" +
"0 0 0 0 1 0 1 1 \n" +
"1 0 0 0 0 1 0 1 \n" +
"1 1 1 1 1 1 1 0 ", 8, 5);
testGraph("0 1 0 0 1 0 1 0 0 0 \n" +
"1 0 1 0 0 0 0 1 0 0 \n" +
"0 1 0 1 0 0 0 0 1 0 \n" +
"0 0 1 0 1 0 0 0 0 1 \n" +
"1 0 0 1 0 1 0 0 0 0 \n" +
"0 0 0 0 1 0 0 1 1 0 \n" +
"1 0 0 0 0 0 0 0 1 1 \n" +
"0 1 0 0 0 1 0 0 0 1 \n" +
"0 0 1 0 0 1 1 0 0 0 \n" +
"0 0 0 1 0 0 1 1 0 0 ", 10, 6);
testGraph(
"0 1 1 0 0 1 1 1 0 0 0 0 \n" +
"1 0 1 1 1 1 0 0 0 0 0 0 \n" +
"1 1 0 1 0 0 0 1 1 0 0 0 \n" +
"0 1 1 0 1 0 0 0 1 1 0 0 \n" +
"0 1 0 1 0 1 0 0 0 1 1 0 \n" +
"1 1 0 0 1 0 1 0 0 0 1 0 \n" +
"1 0 0 0 0 1 0 1 0 0 1 1 \n" +
"1 0 1 0 0 0 1 0 1 0 0 1 \n" +
"0 0 1 1 0 0 0 1 0 1 0 1 \n" +
"0 0 0 1 1 0 0 0 1 0 1 1 \n" +
"0 0 0 0 1 1 1 0 0 1 0 1 \n" +
"0 0 0 0 0 0 1 1 1 1 1 0", 12, 9);
testGraph( "0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 \n" +
"0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 \n" +
"0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 \n" +
"1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 \n" +
"0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 \n" +
"0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 \n" +
"0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 \n" +
"0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 \n" +
"0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 \n" +
"1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 \n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 ",
16, 7);
testGraph("0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 \n" +
"1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 \n" +
"0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 \n" +
"1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 \n" +
"0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 \n" +
"0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 \n" +
"0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 \n" +
"0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 \n" +
"1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 \n" +
"0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 \n" +
"0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 \n" +
"0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 \n" +
"0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 \n" +
"0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0", 20, 12);
testGraph("0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 \n" +
"1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n" +
"0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 \n" +
"0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 \n" +
"0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n" +
"0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 \n" +
"0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 \n" +
"0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 \n" +
"1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 \n" +
"0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 \n" +
"0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 \n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 \n" +
"0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 \n" +
"0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 \n" +
"1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0", 30, 15);
}
private void testGraph(String matrix, int size, int k) {
System.out.println("Trying matrix size: " + size);
Graph g = graphFactory.createGraph(matrix, size);
long start = System.currentTimeMillis();
assertTrue(vertexCover(g, k));
System.out.println("Cover " + k + " success taking: " + (System.currentTimeMillis() - start) + "ms");
start = System.currentTimeMillis();
assertFalse(vertexCover(g, k - 1));
System.out.println("NonCover " + (k - 1) + " success taking: " + (System.currentTimeMillis() - start) + "ms");
}
private class Graph{
Map<Integer, Set<Integer>> graphMap = new HashMap<Integer, Set<Integer>>();
public Graph() {
}
public Graph remove(Integer node) {
Graph g = duplicate();
g.innerRemove(node);
return g;
}
public Graph remove(Set<Integer> children) {
Graph g = duplicate();
for (Integer child : children) {
g.innerRemove(child);
}
return g;
}
private void innerRemove(Integer node){
graphMap.remove(node);
for(Set<Integer> children : graphMap.values()){
Iterator<Integer> childIter = children.iterator();
while(childIter.hasNext()){
Integer child = childIter.next();
if(child.equals(node)){
childIter.remove();
}
}
}
}
private Graph duplicate() {
Graph g = new Graph();
for (Map.Entry<Integer, Set<Integer>> nodeSetEntry : graphMap.entrySet()) {
for (Integer valueNode : nodeSetEntry.getValue()) {
g.add(nodeSetEntry.getKey(), valueNode);
}
}
return g;
}
public void add(Integer one, Integer two){
if(!graphMap.containsKey(one)){
graphMap.put(one, new HashSet<Integer>());
}
graphMap.get(one).add(two);
}
public Collection<Integer> getNodes(){
return graphMap.keySet();
}
public Set<Integer> getChildren(Integer node) {
return graphMap.get(node);
}
public int size(){
return graphMap.size();
}
public boolean isEmpty() {
return graphMap.isEmpty();
}
}
public boolean vertexCover(Graph g, int k){
if(k < 0){
return false;
}
else if(g.isEmpty()){
return true;
}
//grab arbitrary node
Integer node = g.getNodes().iterator().next();
//case where the given vertex is in the cover
if(vertexCover(g.remove(node), k - 1)){
return true;
}
//case where the given vertex is out of the cover, and
//therefore the children must be in the cover
if(vertexCover(g.remove(node).remove(g.getChildren(node)), k - g.getChildren(node).size())){
return true;
}
return false;
}
private class GraphFactory {
public Graph createGraph(String input, int size){
Graph g = new Graph();
String[] rows = input.split("\\n");
if(rows.length != size){
throw new RuntimeException("size not correct");
}
for(int i = 0; i < size; i++){
String[] columns = rows[i].split("\\s+");
if(columns.length != size){
throw new RuntimeException("size not correct");
}
for(int j = 0; j < size; j++){
if(columns[j].equals("1")){
g.add(j,i);
}
}
}
return g;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment