Skip to content

Instantly share code, notes, and snippets.

@gtke
Created April 1, 2013 06:00
Show Gist options
  • Select an option

  • Save gtke/5283453 to your computer and use it in GitHub Desktop.

Select an option

Save gtke/5283453 to your computer and use it in GitHub Desktop.
3 simple test cases for Kruskal's algorithm for finding minimum spanning tree in a graph
import static org.junit.Assert.*;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Scanner;
import org.junit.Test;
public class MSTTest {
public ArrayList<Graph> makeGraphList() {
ArrayList<Graph> graphs = new ArrayList<Graph>();
String text = "1 1 2 1#2 1 2 1 3 4 1#3 1 2 1 2 3 5 1 3 2#11 1 2 7 2 3 8 1 4 5 4 2 9 4 5 15 2 5 7 3 5 5 4 6 6 5 6 8 6 7 11 5 7 9";
Scanner input = new Scanner(text);
input.useDelimiter("#");
String currentGraph;
while (input.hasNext()) {
currentGraph = input.next();
graphs.add(new Graph(currentGraph));
}
input.close();
return graphs;
}
@Test
public void testSimpleTwoVertex() {
ArrayList<Graph> graphs = makeGraphList();
Collection<Edge> edgeList = MST.kruskals(graphs.get(0));
assertNotNull(edgeList);
assertEquals(1, edgeList.size());
assertTrue(edgeList.contains(new Edge(new Vertex(1), new Vertex(2), 1)));
}
@Test
public void testSimpleNotConnected() {
ArrayList<Graph> graphs = makeGraphList();
Collection<Edge> edgeList = MST.kruskals(graphs.get(1));
assertNull(edgeList);
}
@Test
public void testSimpleTriangle() {
ArrayList<Graph> graphs = makeGraphList();
Collection<Edge> edgeList = MST.kruskals(graphs.get(2));
assertNotNull(edgeList);
assertEquals(2, edgeList.size());
assertTrue(edgeList.contains(new Edge(new Vertex(1), new Vertex(2), 1)));
assertTrue(edgeList.contains(new Edge(new Vertex(1), new Vertex(3), 2)));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment