diff options
Diffstat (limited to 'src/Program')
| -rw-r--r-- | src/Program/Analysis.cs | 76 | ||||
| -rw-r--r-- | src/Program/Program.cs | 21 |
2 files changed, 71 insertions, 26 deletions
diff --git a/src/Program/Analysis.cs b/src/Program/Analysis.cs index d0a49cb..d6c6082 100644 --- a/src/Program/Analysis.cs +++ b/src/Program/Analysis.cs @@ -2,20 +2,32 @@ using System; using System.Collections.Generic; using System.Diagnostics; +using System.Linq; +using System.Threading.Tasks; using NetworkFlow; namespace Program { public struct Result { + string Filename; + string ResultType; + int Iterations; public double MinCut; public TimeSpan Runtime; - public Result(double minCut, TimeSpan runtime) + public Result(string filename, String type, int interations, 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})"; + } class Analysis @@ -24,17 +36,22 @@ namespace Program 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; - public Analysis(Graph graph) + public Analysis(Graph graph, string filename) { _graph = graph; + Filename = filename; } public void Analize() { + Console.WriteLine($"\nFilename: {Filename}"); Stopwatch stopwatch = new(); - double result = CalculateExact((Graph)_graph.Clone()); - ExactResult = new(result, stopwatch.Elapsed); + double result = CalculateExact(); + ExactResult = new(Filename, "Exact", 1, result, stopwatch.Elapsed); + + Console.WriteLine(ExactResult); foreach (var iterFunc in IterFuncs) { @@ -44,34 +61,59 @@ namespace Program for (int i = 0; i < 5; i++) { stopwatch.Restart(); - result = CalculateApprox(_graph, iterations); - ApproxResults[iterations].Add(new(result, stopwatch.Elapsed)); + result = CalculateApprox(iterations); + Result approxResult = new(Filename, "Apprx", iterations, result, stopwatch.Elapsed); + ApproxResults[iterations].Add(approxResult); + Console.WriteLine(approxResult); } } } - double CalculateExact(Graph graph) => graph.MaxFlow(0, graph.Nodes.Count - 1); + double CalculateExact() + { + 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; + } - double CalculateApprox(Graph graph, int iterations) + double CalculateApprox(int iterations) { double result = double.MaxValue; - for (int j = 0; j < iterations; j++){ + #region Parallel_Loop + Parallel.For(0, iterations, j => + { var graphClone = (Graph)_graph.Clone(); - result = Math.Min(result, graphClone.Contraction()); - } + double currentResult = graphClone.Contraction(); + if (currentResult != 0) + result = Math.Min(result, currentResult); + }); + #endregion return result; } - public override string ToString() + public List<string> ToCSV() { - 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}"; + 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; } } diff --git a/src/Program/Program.cs b/src/Program/Program.cs index 6aab0a3..c27369a 100644 --- a/src/Program/Program.cs +++ b/src/Program/Program.cs @@ -1,6 +1,5 @@ using System; using System.Collections.Generic; -using System.Diagnostics; using System.IO; using System.Linq; using Graph = NetworkFlow.Graph; @@ -15,29 +14,32 @@ 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"); + if (!graphDir.Exists) { Console.WriteLine($"Failed to open {graphDir}: Graph does not exist."); System.Environment.Exit(1); } - + foreach (var file in graphDir.EnumerateFiles()) { - Graph graph = ReadFile(file.FullName); - Analysis analysis = new(graph); + Graph graph = ReadFile(file); + Analysis analysis = new(graph, file.Name); analysis.Analize(); Analysii.Add(analysis); - Console.WriteLine(analysis.ToString()); + File.AppendAllLines(outfile.FullName, analysis.ToCSV()); } } - public static Graph ReadFile(string file) + public static Graph ReadFile(FileInfo file) { // create default Graph object Graph graph = new Graph(undirected: true); // Read in graph file - foreach (string line in File.ReadLines(file)) + foreach (string line in File.ReadLines(file.FullName)) { // each file line is a Node with optional edges // line format: @@ -52,12 +54,13 @@ namespace Program // AddEdge(int u, int v, double weight) int.TryParse(vals[i], out v); double.TryParse(vals[i + 1], out weight); - graph.AddEdge(u, v, weight); + if (!graph[u].Edges.ContainsKey(v)) + graph.AddEdge(u, v, weight); } } // return object when done return graph; } - + } } |