diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/Program/Analysis.cs | 81 | ||||
| -rw-r--r-- | src/Program/Program.cs | 47 |
2 files changed, 65 insertions, 63 deletions
diff --git a/src/Program/Analysis.cs b/src/Program/Analysis.cs index d6c6082..f817200 100644 --- a/src/Program/Analysis.cs +++ b/src/Program/Analysis.cs @@ -10,83 +10,67 @@ namespace Program { public struct Result { - string Filename; - string ResultType; - int Iterations; public double MinCut; public TimeSpan Runtime; - public Result(string filename, String type, int interations, double minCut, TimeSpan runtime) + public Result(double minCut, TimeSpan runtime) { - Filename = filename; - ResultType = type; - Iterations = interations; MinCut = minCut; Runtime = runtime; } - public string ToCSV() => $"{Filename},{ResultType},{Iterations},{MinCut},{Runtime}"; - public override string ToString() => $"{ResultType} Value: {MinCut}, Runtime: {Runtime} (i: {Iterations})"; - + public override string ToString() => $"{MinCut} @ {Runtime.TotalMilliseconds}"; } 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 string Filename; + Result _exact = new(); + Result Exact { get => _exact.Equals(default(Result)) ? (_exact = CalculateExact()) : _exact; } + int Repetitions; - public Analysis(Graph graph, string filename) + public Analysis(Graph graph, int repetitions) { _graph = graph; - Filename = filename; + Repetitions = repetitions; } - public void Analize() + public List<Result> Analize(int iterations) { - Console.WriteLine($"\nFilename: {Filename}"); - Stopwatch stopwatch = new(); - double result = CalculateExact(); - ExactResult = new(Filename, "Exact", 1, result, stopwatch.Elapsed); - - Console.WriteLine(ExactResult); - - foreach (var iterFunc in IterFuncs) + List<Result> results = new(); + results.Add(Exact); + Console.WriteLine($"Exact {Exact}"); + for (int i = 0; i < Repetitions; i++) { - int iterations = iterFunc(_graph.Nodes.Count); - ApproxResults.Add(iterations, new()); - - for (int i = 0; i < 5; i++) - { - stopwatch.Restart(); - result = CalculateApprox(iterations); - Result approxResult = new(Filename, "Apprx", iterations, result, stopwatch.Elapsed); - ApproxResults[iterations].Add(approxResult); - Console.WriteLine(approxResult); - } + results.Add(CalculateApprox(iterations)); + Console.WriteLine($"Contract_{i + 1} {results.Last()}"); } + + return results; } - double CalculateExact() + Result CalculateExact() { + Stopwatch stopwatch = Stopwatch.StartNew(); double result = double.MaxValue; + // loop t for all nodes foreach (var node in _graph.Nodes.Keys.ToList().Skip(1)) { var graphClone = (Graph)_graph.Clone(); + // take min of current result and new result double currentResult = graphClone.MaxFlow(0, node); if (currentResult != 0) result = Math.Min(result, currentResult); } - Console.WriteLine(); - return result; + + return new(result, stopwatch.Elapsed); } - double CalculateApprox(int iterations) + Result CalculateApprox(int iterations) { + Stopwatch stopwatch = Stopwatch.StartNew(); double result = double.MaxValue; #region Parallel_Loop @@ -99,22 +83,7 @@ namespace Program }); #endregion - return result; - } - - public List<string> ToCSV() - { - List<string> lines = new(); - lines.Add(ExactResult.ToCSV()); - ApproxResults.Values.ToList().ForEach(approx => approx.ForEach(r => lines.Add(r.ToCSV()))); - return lines; - } - - public override string ToString() - { - string outString = ExactResult.ToString(); - ApproxResults.Values.ToList().ForEach(r => outString += String.Join("", r)); - return outString; + return new(result, stopwatch.Elapsed); } } }
\ No newline at end of file diff --git a/src/Program/Program.cs b/src/Program/Program.cs index c27369a..05a91dc 100644 --- a/src/Program/Program.cs +++ b/src/Program/Program.cs @@ -13,9 +13,8 @@ namespace Program { List<Analysis> Analysii = new(); DirectoryInfo graphDir = new DirectoryInfo((args.Length > 0) ? args[0] : "graphs"); - - FileInfo outfile = new("../../output.csv"); - File.WriteAllText(outfile.FullName, $"Filename,ResultType,Iterations,MinCut,Runtime\n"); + DirectoryInfo outDir = new("../../output"); + outDir.Create(); if (!graphDir.Exists) { @@ -23,14 +22,48 @@ namespace Program System.Environment.Exit(1); } + string cuts_header = $"Graph,Exact Cuts,Contract1 Cuts,Contract2 Cuts,Contract3 Cuts,Contract4 Cuts,Contract5 Cuts"; + string times_header = $"Graph,Exact (ms),Contract1 (ms),Contract2 (ms),Contract3 (ms),Contract4 (ms),Contract5 (ms)"; + List<string> constant_cuts = new() { cuts_header }; + List<string> constant_times = new() { times_header }; + List<string> linear_cuts = new() { cuts_header }; + List<string> linear_times = new() { times_header }; + List<string> polynomial_cuts = new() { cuts_header }; + List<string> polynomial_times = new() { times_header }; + foreach (var file in graphDir.EnumerateFiles()) { Graph graph = ReadFile(file); - Analysis analysis = new(graph, file.Name); - analysis.Analize(); - Analysii.Add(analysis); - File.AppendAllLines(outfile.FullName, analysis.ToCSV()); + Analysis analysis = new(graph, 5); + List<Result> results; + int iter; + Console.WriteLine(file.Name); + + iter = 10; + Console.WriteLine($"\nconstant ({iter}):"); + results = analysis.Analize(iter); + constant_cuts.Add($"{file.Name},{String.Join(",", results.Select(r => r.MinCut))}"); + constant_times.Add($"{file.Name},{String.Join(",", results.Select(r => r.Runtime.TotalMilliseconds))}"); + + iter = graph.Nodes.Count; + Console.WriteLine($"\nlinier ({iter}):"); + results = analysis.Analize(iter); + linear_cuts.Add($"{file.Name},{String.Join(",", results.Select(r => r.MinCut))}"); + linear_times.Add($"{file.Name},{String.Join(",", results.Select(r => r.Runtime.TotalMilliseconds))}"); + + iter = (int)(Math.Pow(graph.Nodes.Count, 2) * Math.Log(graph.Nodes.Count, Math.E)); + Console.WriteLine($"\npolynomial ({iter}):"); + results = analysis.Analize(iter); + polynomial_cuts.Add($"{file.Name},{String.Join(",", results.Select(r => r.MinCut))}"); + polynomial_times.Add($"{file.Name},{String.Join(",", results.Select(r => r.Runtime.TotalMilliseconds))}"); } + + File.WriteAllLines($"{outDir.FullName}/constant_cuts.csv", constant_cuts); + File.WriteAllLines($"{outDir.FullName}/constant_times.csv", constant_times); + File.WriteAllLines($"{outDir.FullName}/linear_cuts.csv", linear_cuts); + File.WriteAllLines($"{outDir.FullName}/linear_times.csv", linear_times); + File.WriteAllLines($"{outDir.FullName}/polynomial_cuts.csv", polynomial_cuts); + File.WriteAllLines($"{outDir.FullName}/polynomial_times.csv", polynomial_times); } public static Graph ReadFile(FileInfo file) |