13 files changed, 269 insertions, 26 deletions
diff --git a/.devcontainer/devcontainer.json b/.devcontainer/devcontainer.json
index a5dc476..81c4841 100644
--- a/.devcontainer/devcontainer.json
+++ b/.devcontainer/devcontainer.json
@@ -25,7 +25,8 @@
 		"eamodio.gitlens",
 		"leo-labs.dotnet",
 		"tintoy.msbuild-project-tools",
-		"formulahendry.dotnet-test-explorer"
+		"formulahendry.dotnet-test-explorer",
+		"fernandoescolar.vscode-solution-explorer"
 	],
 	
 	// Use 'forwardPorts' to make a list of ports inside the container available locally.
diff --git a/.vscode/settings.json b/.vscode/settings.json
index 5ef1024..7a73a41 100644
--- a/.vscode/settings.json
+++ b/.vscode/settings.json
@@ -1,9 +1,2 @@
 {
-    "files.exclude": {
-        "**/.gitattributes": true,
-        "**/.gitignore": true,
-        "**/*.csproj": true,
-        "**/bin": true,
-        "**/obj": true
-    }
 }
 \ No newline at end of file
diff --git a/CS340-P6.sln b/CS340-P6.sln
index b330857..9dc4c1c 100644
--- a/CS340-P6.sln
+++ b/CS340-P6.sln
@@ -15,6 +15,10 @@ Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "CS340.Extensions", "src\CS3
 EndProject
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "CS340.PriorityQueue", "src\CS340.PriorityQueue\CS340.PriorityQueue.csproj", "{A8E26365-D1A6-4E9C-9524-D7CFC3E41C76}"
 EndProject
+Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "tests", "tests", "{1C5331E5-D2DC-48A8-8264-3E83B06B4335}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "CS340.PriorityQueue.Tests", "tests\CS340.PriorityQueue.Tests\CS340.PriorityQueue.Tests.csproj", "{CDCD0887-1053-49CE-A01E-D53E9110DD00}"
+EndProject
 Global
 	GlobalSection(SolutionConfigurationPlatforms) = preSolution
 		Debug|Any CPU = Debug|Any CPU
@@ -88,6 +92,18 @@ Global
 		{A8E26365-D1A6-4E9C-9524-D7CFC3E41C76}.Release|x64.Build.0 = Release|Any CPU
 		{A8E26365-D1A6-4E9C-9524-D7CFC3E41C76}.Release|x86.ActiveCfg = Release|Any CPU
 		{A8E26365-D1A6-4E9C-9524-D7CFC3E41C76}.Release|x86.Build.0 = Release|Any CPU
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00}.Debug|x64.ActiveCfg = Debug|Any CPU
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00}.Debug|x64.Build.0 = Debug|Any CPU
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00}.Debug|x86.ActiveCfg = Debug|Any CPU
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00}.Debug|x86.Build.0 = Debug|Any CPU
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00}.Release|Any CPU.Build.0 = Release|Any CPU
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00}.Release|x64.ActiveCfg = Release|Any CPU
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00}.Release|x64.Build.0 = Release|Any CPU
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00}.Release|x86.ActiveCfg = Release|Any CPU
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00}.Release|x86.Build.0 = Release|Any CPU
 	EndGlobalSection
 	GlobalSection(NestedProjects) = preSolution
 		{D2383783-7EAB-4E7F-B9A6-33702BA8E919} = {D035EDB3-98C7-4A59-8C2F-5BD5BB9E83DA}
@@ -95,5 +111,6 @@ Global
 		{2BF6C193-197B-4C49-AE0C-7C8682F1F0CB} = {D035EDB3-98C7-4A59-8C2F-5BD5BB9E83DA}
 		{D94E98AE-9D02-4532-AD8E-DFD118039775} = {D035EDB3-98C7-4A59-8C2F-5BD5BB9E83DA}
 		{A8E26365-D1A6-4E9C-9524-D7CFC3E41C76} = {D035EDB3-98C7-4A59-8C2F-5BD5BB9E83DA}
+		{CDCD0887-1053-49CE-A01E-D53E9110DD00} = {1C5331E5-D2DC-48A8-8264-3E83B06B4335}
 	EndGlobalSection
 EndGlobal
diff --git a/src/CS340.Extensions b/src/CS340.Extensions
-Subproject 73579373cb6596e21037cc2e70a0e4c84556c26
+Subproject 7d01bcd7a01fa877496b7d541648415c2c1830b
diff --git a/src/CS340.Graph b/src/CS340.Graph
-Subproject e538388865e6b078d1afce02c785dc60b5baffa
+Subproject 798aec5e24b847ce9f56ef69793b3c407cbd2a6
diff --git a/src/CS340.PriorityQueue b/src/CS340.PriorityQueue
-Subproject 541ab24f64a3839afb493d8260495eddd4416c3
+Subproject cbb581eefb3ac38f36810865c264d9b52fbd965
diff --git a/src/CS340.TSP/Program.cs b/src/CS340.TSP/Program.cs
index 3dfe855..ef9e211 100644
--- a/src/CS340.TSP/Program.cs
+++ b/src/CS340.TSP/Program.cs
@@ -9,6 +9,7 @@ using Interfaces;
 namespace TSP
 {
     using Graph = Graph<double>;
+    using Tour = Tour<double>;
     class Program
     {
 
@@ -18,11 +19,23 @@ namespace TSP
             foreach (var item in Directory.GetFiles("graphs/"))
             {
                 Graph graph = GraphFile.Read(new FileReader(item));
-                Graph mst = graph.MST(0);
-                GraphFile.Print(mst, new ConsoleWriter());
-                Console.WriteLine(
-                    graph.Vertices.Sum(vertex =>
-                        vertex.Edges.FirstOrDefault(edge => edge.V == vertex.Parent).Weight));
+                // Graph mst = graph.MST(0);
+                // GraphFile.Print(mst, new ConsoleWriter());
+                // Console.WriteLine(
+                //     graph.Vertices.Sum(vertex =>
+                //         vertex.Edges.FirstOrDefault(edge => edge.V == vertex.Parent).Weight));
+
+                Tour bruteForce = TSP.BruteForce(graph, 0);
+                Console.WriteLine(bruteForce);
+                // mst.Vertices.ForEach(vertex =>
+                // {
+                //     Console.Write($"{vertex.Id}");
+                //     vertex.Edges.ForEach(edge => Console.Write($" {edge.V} {edge.Weight.ToString("F1")}"));
+                //     Console.WriteLine();
+                // });
+                // Console.WriteLine(mst.Vertices
+                //        .Sum(vertex => vertex.Edges
+                //        .FirstOrDefault(edge => edge.V == vertex.Parent).Weight));
             }
         }
     }
diff --git a/src/CS340.TSP/TSP.cs b/src/CS340.TSP/TSP.cs
new file mode 100644
index 0000000..a37ab3d
--- /dev/null
+++ b/src/CS340.TSP/TSP.cs
@@ -0,0 +1,72 @@
+using System;
+using System.Diagnostics;
+using System.Linq;
+using Graph;
+
+namespace TSP
+{
+    using City = Vertex<double>;
+    using Tour = Tour<double>;
+
+    public static class TSP
+    {
+        static Tour BestTour = null;
+        static Graph<double> Map;
+
+        public static Tour BruteForce(Graph<double> map, int init)
+        {
+
+            Tour intialTour = new Tour(map.Vertices);
+            GenerateTour(intialTour[init], new Tour(map.Vertices), new Tour());
+
+            return BestTour;
+        }
+
+        static void GenerateTour(City city, Tour tour, Tour visited)
+        {
+            // create local copy of Tour variables
+            Tour currTour = tour.DeepCopy();
+            Tour currVisited = visited.DeepCopy();
+
+            // remove current City from tour
+            bool removed = currTour.Cities.Remove(city);
+
+            //? verify that city was removed
+            Debug.Assert(removed,
+                         $"Failed to remove a city from the tour. \nTour: {tour}\nCity: {city.Id}");
+
+            // add current City to visited
+            if (currVisited.Cities.Count > 0)
+            {
+                city.Parent = currVisited.Cities.Last().Id;
+                city.Key = Map.Vertices[city.Id].Edges
+                                             .Where(edge => edge.V == city.Parent)
+                                             .Last().Weight;
+            }
+
+            currVisited.Cities.Add(city);
+
+            //? verify that city was added
+            Debug.Assert(currVisited.Cities.Contains(city),
+                         $"Failed to add a city to the tour. \nTour: {tour}\nCity: {city.Id}");
+
+            // loop through each city. Each level of recursion has a one less city in currTour.Cities
+            // leaving the base case
+            foreach (City neighbor in currTour.Cities)
+                GenerateTour(neighbor, currTour, currVisited);
+
+
+            if (currTour.Cities.Count == 0)
+            {
+                currVisited.Cities.First().Parent = currVisited.Cities.Last().Id;
+
+                if (BestTour == null || currVisited.Weight < BestTour.Weight)
+                    BestTour = currVisited.DeepCopy();
+                // Debug.Print($"{currTour}");
+            }
+
+
+            return;
+        }
+    }
+}
diff --git a/src/CS340.TSP/Tour.cs b/src/CS340.TSP/Tour.cs
new file mode 100644
index 0000000..456c944
--- /dev/null
+++ b/src/CS340.TSP/Tour.cs
@@ -0,0 +1,43 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using Graph;
+
+namespace TSP
+{
+
+    public class Tour<T> where T : IComparable<T>
+    {
+        public List<Vertex<T>> Cities { get; set; } = new List<Vertex<T>>();
+        public T Weight
+        {
+            get
+            {
+                dynamic _weight = default(T);
+                Cities.Where(city => city.Parent != -1).ToList()
+                        .ForEach(city =>
+                            _weight += city.Edges
+                                .Where(edge => edge.V == city.Parent)
+                                .First().Weight);
+                return _weight;
+            }
+        }
+
+        // indexer: get vertex where vertex.Id == index 
+        public Vertex<T> this[int index] { get => Cities.Find(vertex => vertex.Id == index); }
+
+        public Tour(List<Vertex<T>> cities) => Cities = cities;
+        public Tour() => Cities = new List<Vertex<T>>();
+
+        public Tour<T> DeepCopy()
+        {
+            Tour<T> other = (Tour<T>)this.MemberwiseClone();
+            other.Cities = Cities.ConvertAll(city => city.DeepCopy());
+            return other;
+        }
+        public override string ToString() =>
+            $"tour: {String.Join(" -> ", Cities.Select(city => city.Id))}\n" +
+            $"distance: {Weight}";
+
+    }
+}
diff --git a/src/CS340.TSP/graphs/graph1.txt b/src/CS340.TSP/graphs/graph1.txt
deleted file mode 100644
index f31c4fd..0000000
--- a/src/CS340.TSP/graphs/graph1.txt
+++ /dev/null
@@ -1,13 +0,0 @@
-0 1 78.85429601486528 2 64.62197768561404 3 59.135437767890075 4 71.84705978674423 5 54.08326913195984 6 8.602325267042627 7 50.695167422546305 8 75.69015788066504 9 46.09772228646444 10 79.37883848986453 11 19.209372712298546 12 83.18653737234169 
-1 0 78.85429601486528 2 93.47726996441435 3 21.095023109728988 4 28.635642126552707 5 102.55242561733974 6 72.69112738154499 7 46.861498055439924 8 76.21679604916491 9 50.20956084253277 10 9.219544457292887 11 89.02246907382428 12 55.08175741568164 
-2 0 64.62197768561404 1 93.47726996441435 3 85.23496934944014 4 67.89698078707183 5 21.840329667841555 6 69.6419413859206 7 47.01063709417264 8 28.442925306655784 9 44.77722635447622 10 99.98499887483122 11 83.19254774317228 12 54.62600113499065 
-3 0 59.135437767890075 1 21.095023109728988 2 85.23496934944014 4 33.54101966249684 5 90.21086409075129 6 52.392747589718944 7 39.05124837953327 8 74.10802925459562 9 40.496913462633174 10 20.248456731316587 11 68.11754546370561 12 59.77457653551382 
-4 0 71.84705978674423 1 28.635642126552707 2 67.89698078707183 3 33.54101966249684 5 80.45495634204272 6 68.41052550594829 7 25.298221281347036 8 47.92702786528704 9 30.083217912982647 10 37.21558813185679 11 86.97700845625813 12 27.16615541441225 
-5 0 54.08326913195984 1 102.55242561733974 2 21.840329667841555 3 90.21086409075129 4 80.45495634204272 6 61.032778078668514 7 56.22277118748239 8 49.01020301937138 9 52.40229002629561 10 107.62899237658968 11 70.61161377563892 12 72.78049189171504 
-6 0 8.602325267042627 1 72.69112738154499 2 69.6419413859206 3 52.392747589718944 4 68.41052550594829 5 61.032778078668514 7 49.39635614091387 8 77.80102827083971 9 45.221676218380054 10 72.53275122315436 11 18.788294228055936 12 82.37718130647589 
-7 0 50.695167422546305 1 46.861498055439924 2 47.01063709417264 3 39.05124837953327 4 25.298221281347036 5 56.22277118748239 6 49.39635614091387 8 36.345563690772494 9 5.0 10 53.0 11 68.09552114493287 12 33.015148038438355 
-8 0 75.69015788066504 1 76.21679604916491 2 28.442925306655784 3 74.10802925459562 4 47.92702786528704 5 49.01020301937138 6 77.80102827083971 7 36.345563690772494 9 37.36308338453881 10 84.20213774008353 11 94.847245611035 12 27.80287754891569 
-9 0 46.09772228646444 1 50.20956084253277 2 44.77722635447622 3 40.496913462633174 4 30.083217912982647 5 52.40229002629561 6 45.221676218380054 7 5.0 8 37.36308338453881 10 55.80322571321482 11 63.812224534175265 12 37.21558813185679 
-10 0 79.37883848986453 1 9.219544457292887 2 99.98499887483122 3 20.248456731316587 4 37.21558813185679 5 107.62899237658968 6 72.53275122315436 7 53.0 8 84.20213774008353 9 55.80322571321482 11 87.69264507357501 12 64.00781202322104 
-11 0 19.209372712298546 1 89.02246907382428 2 83.19254774317228 3 68.11754546370561 4 86.97700845625813 5 70.61161377563892 6 18.788294228055936 7 68.09552114493287 8 94.847245611035 9 63.812224534175265 10 87.69264507357501 12 101.01980003939822 
-12 0 83.18653737234169 1 55.08175741568164 2 54.62600113499065 3 59.77457653551382 4 27.16615541441225 5 72.78049189171504 6 82.37718130647589 7 33.015148038438355 8 27.80287754891569 9 37.21558813185679 10 64.00781202322104 11 101.01980003939822 
diff --git a/src/CS340.TSP/graphs/test.txt b/src/CS340.TSP/graphs/test.txt
new file mode 100644
index 0000000..113fb4f
--- /dev/null
+++ b/src/CS340.TSP/graphs/test.txt
@@ -0,0 +1,6 @@
+0 1 78.85429601486528 2 64.62197768561404 3 59.135437767890075 4 71.84705978674423 5 54.08326913195984
+1 0 78.85429601486528 2 93.47726996441435 3 21.095023109728988 4 28.635642126552707 5 102.55242561733974
+2 0 64.62197768561404 1 93.47726996441435 3 85.23496934944014 4 67.89698078707183 5 21.840329667841555
+3 0 59.135437767890075 1 21.095023109728988 2 85.23496934944014 4 33.54101966249684 5 90.21086409075129
+4 0 71.84705978674423 1 28.635642126552707 2 67.89698078707183 3 33.54101966249684 5 80.45495634204272
+5 0 54.08326913195984 1 102.55242561733974 2 21.840329667841555 3 90.21086409075129 4 80.45495634204272
+\ No newline at end of file
diff --git a/tests/CS340.PriorityQueue.Tests/CS340.PriorityQueue.Tests.csproj b/tests/CS340.PriorityQueue.Tests/CS340.PriorityQueue.Tests.csproj
new file mode 100644
index 0000000..9c9f613
--- /dev/null
+++ b/tests/CS340.PriorityQueue.Tests/CS340.PriorityQueue.Tests.csproj
@@ -0,0 +1,27 @@
+<Project Sdk="Microsoft.NET.Sdk">
+
+  <PropertyGroup>
+    <TargetFramework>net5.0</TargetFramework>
+
+    <IsPackable>false</IsPackable>
+  </PropertyGroup>
+
+  <ItemGroup>
+    <PackageReference Include="Microsoft.NET.Test.Sdk" Version="16.7.1" />
+    <PackageReference Include="xunit" Version="2.4.1" />
+    <PackageReference Include="xunit.runner.visualstudio" Version="2.4.3">
+      <IncludeAssets>runtime; build; native; contentfiles; analyzers; buildtransitive</IncludeAssets>
+      <PrivateAssets>all</PrivateAssets>
+    </PackageReference>
+    <PackageReference Include="coverlet.collector" Version="1.3.0">
+      <IncludeAssets>runtime; build; native; contentfiles; analyzers; buildtransitive</IncludeAssets>
+      <PrivateAssets>all</PrivateAssets>
+    </PackageReference>
+  </ItemGroup>
+
+  <ItemGroup>
+    <ProjectReference Include="..\..\src\CS340.PriorityQueue\CS340.PriorityQueue.csproj" />
+    <ProjectReference Include="..\..\src\CS340.Interfaces\CS340.Interfaces.csproj" />
+  </ItemGroup>
+
+</Project>
diff --git a/tests/CS340.PriorityQueue.Tests/PriorityQueueShould.cs b/tests/CS340.PriorityQueue.Tests/PriorityQueueShould.cs
new file mode 100644
index 0000000..beafb41
--- /dev/null
+++ b/tests/CS340.PriorityQueue.Tests/PriorityQueueShould.cs
@@ -0,0 +1,84 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using Xunit;
+
+namespace PriorityQueue.Tests
+{
+    using Node = Node<int>;
+    using Queue = PriorityQueue<Node<int>, int>;
+
+    public class CreatePriorityQueue
+    {
+        [Theory]
+        [InlineData(false, new int[] { 3, 14, 7, 9, 99, 2, 46 }, 4, 99)]
+        [InlineData(true, new int[] { 3, 14, 7, 9, 99, 2, 46 }, 5, 2)]
+        public void Insert_WhenArray_ShouldPQ(bool isMin, int[] input, int expectedId, int expectedkey)
+        {
+            // Arrange
+            int id = 0;
+            Queue priorityQueue = new Queue(input.Length, isMin);
+            Node expected = new Node(expectedId, expectedkey);
+
+            // Act
+            foreach (var key in input)
+                priorityQueue.Insert(new Node(id++, key));
+
+            // Assert
+            Assert.Equal(expected, priorityQueue.Peek());
+        }
+        
+        [Theory]
+        [InlineData(false, new int[] { 3, 14, 7, 9, 99, 2, 46 })]
+        [InlineData(true, new int[] { 3, 14, 7, 9, 99, 2, 46 })]
+        public void Extract_WhenPG_ShouldReturnLargest(bool isMin, int[] input)
+        {
+            // Arrange
+            int id = 0;
+            Node curr, next;
+            List<Node> actual = new List<Node>();
+            Queue queue = new Queue(input.Length, isMin);
+
+            Func<Node, Node, bool> compare = (first, second) =>
+                first.CompareTo(second) * (isMin ? -1 : 1) >= 0;
+
+            // Act
+            foreach (var key in input)
+                queue.Insert(new Node(id++, key));
+
+            // Assert
+            while (!queue.IsEmpty())
+                Assert.True(compare(
+                    curr = queue.Extract(), 
+                    next = queue.Peek()
+                ));
+        }
+
+        [Theory]
+        [InlineData(false, 4, 99)]
+        [InlineData(true, 5, 2)]
+        public void ChangeKey_GivenPQ_ShouldReorderPQ(bool isMin, int expectedId, int expectedkey)
+        {
+            // Arrange
+            int id = 0;
+            int[] array = new int[] { 3, 14, 7, 9, 99, 2, 46 };
+            List<Node> actual = new List<Node>();
+            Queue priorityQueue = new Queue(array.Length, isMin);
+            foreach (var key in array)
+                priorityQueue.Insert(new Node(id++, key));
+
+            // Act
+
+            // Assert
+            Node prev = priorityQueue.Extract();
+            while (!priorityQueue.IsEmpty())
+                actual.Add(priorityQueue.Extract());
+
+            foreach (Node node in actual)
+                Assert.True(prev.Key > (prev = node).Key);
+        }
+
+
+
+    }
+}
+\ No newline at end of file