diff options
Diffstat (limited to 'src/Program/Analysis.cs')
-rw-r--r-- | src/Program/Analysis.cs | 78 |
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 |