Created
April 1, 2013 06:00
-
-
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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