implement function isConnected()

1 files changed, 35 insertions, 0 deletions

diff --git a/dk/abcdefghijklmnopqrstuvxyzæøå/bachelorizer/model/Combi.java b/dk/abcdefghijklmnopqrstuvxyzæøå/bachelorizer/model/Combi.java
index 6feea62..85227a7 100644
--- a/dk/abcdefghijklmnopqrstuvxyzæøå/bachelorizer/model/Combi.java
+++ b/dk/abcdefghijklmnopqrstuvxyzæøå/bachelorizer/model/Combi.java
@@ -3,10 +3,14 @@
 
 package dk.abcdefghijklmnopqrstuvxyzæøå.bachelorizer.model;
 
+import java.util.Collection;
+import java.util.Set;
+
 import com.example.portfolio3.AdjListGraph;
 import com.example.portfolio3.Graph;
 import com.example.portfolio3.GraphAlgorithms;
 import com.example.portfolio3.MatrixGraph;
+import com.example.portfolio3.Vertex;
 
 /// Combi - static sample dataset of course combinations
 ///
@@ -43,6 +47,10 @@ public final class Combi {
 		// TODO: avoid reading and parsing file twice
 		Graph g = new MatrixGraph(_vertice_count);
 		GraphAlgorithms.readGraph(g, path);
+
+		// ensure the graph is connected
+		isConnected(g);
+
 		GraphAlgorithms.printGraph(g);
 
 		// release temporary variables for garbage collection
@@ -63,4 +71,31 @@ public final class Combi {
 
 		Combi combi = new Combi(path);
 	}
+
+	/// check that graph is connected
+	///
+	/// If check fails, throw an unchecked exception,
+	/// since it occurs at runtime and is unrecoverable.
+	///
+	/// @param g  Graph to inspect
+	/// @throws IllegalArgumentException
+	/// https://docs.oracle.com/javase/tutorial/essential/exceptions/runtime.html
+	public void isConnected(Graph g) {
+
+		// collect all vertices in the graph
+		Collection<Vertex> c = g.vertices();
+
+		// pick a random vertice in the graph
+		Vertex v = g.vertices().iterator().next();
+
+		// resolve visitable vertices
+		Set<Vertex> visited = GraphAlgorithms.visitDepthFirst(
+			g, v);
+
+		// throw exception if not all vertices were visited
+		if (visited.size() != c.size()) {
+			throw new IllegalArgumentException(
+				"graph is not connected");
+		}
+	}
 }