Working state but it takes 6 lifetimes to run

Co-authored-by: Neil Kollack <nkollack@gmail.com>

1 files changed, 78 insertions, 0 deletions

diff --git a/src/Program/Analysis.cs b/src/Program/Analysis.cs
new file mode 100644
index 0000000..d0a49cb
--- /dev/null
+++ b/src/Program/Analysis.cs
@@ -0,0 +1,78 @@
+
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using NetworkFlow;
+
+namespace Program
+{
+    public struct Result
+    {
+        public double MinCut;
+        public TimeSpan Runtime;
+
+        public Result(double minCut, TimeSpan runtime)
+        {
+            MinCut = minCut;
+            Runtime = runtime;
+        }
+    }
+
+    class Analysis
+    {
+        Result ExactResult;
+        Dictionary<int, List<Result>> ApproxResults = new();
+        Func<int, int>[] IterFuncs = new Func<int, int>[] { n => 10, n => n, n => (int)(Math.Pow(n, 2) * Math.Log(n, Math.E)) };
+        Graph _graph;
+
+        public Analysis(Graph graph)
+        {
+            _graph = graph;
+        }
+
+        public void Analize()
+        {
+            Stopwatch stopwatch = new();
+            double result = CalculateExact((Graph)_graph.Clone());
+            ExactResult = new(result, stopwatch.Elapsed);
+
+            foreach (var iterFunc in IterFuncs)
+            {
+                int iterations = iterFunc(_graph.Nodes.Count);
+                ApproxResults.Add(iterations, new());
+
+                for (int i = 0; i < 5; i++)
+                {
+                    stopwatch.Restart();
+                    result = CalculateApprox(_graph, iterations);
+                    ApproxResults[iterations].Add(new(result, stopwatch.Elapsed));
+                }
+            }
+        }
+
+        double CalculateExact(Graph graph) => graph.MaxFlow(0, graph.Nodes.Count - 1);
+
+        double CalculateApprox(Graph graph, int iterations)
+        {
+            double result = double.MaxValue;
+
+            for (int j = 0; j < iterations; j++){
+                var graphClone = (Graph)_graph.Clone();
+                result = Math.Min(result, graphClone.Contraction());
+            }
+
+            return result;
+        }
+
+        public override string ToString()
+        {
+            string outString = $"Exact Value: {ExactResult.MinCut}, Exact Runtime: {ExactResult.Runtime}\n";
+
+            foreach (var results in ApproxResults)
+                foreach (var result in results.Value)
+                    outString += $"Approx Value: {result.MinCut}, Approx Runtime: {result.Runtime}";
+
+            return outString;
+        }
+    }
+}
\ No newline at end of file