diff options
Diffstat (limited to 'src/Program')
-rw-r--r-- | src/Program/Analysis.cs | 89 | ||||
-rw-r--r-- | src/Program/Program.cs | 131 |
2 files changed, 141 insertions, 79 deletions
diff --git a/src/Program/Analysis.cs b/src/Program/Analysis.cs new file mode 100644 index 0000000..f817200 --- /dev/null +++ b/src/Program/Analysis.cs @@ -0,0 +1,89 @@ + +using System; +using System.Collections.Generic; +using System.Diagnostics; +using System.Linq; +using System.Threading.Tasks; +using NetworkFlow; + +namespace Program +{ + public struct Result + { + public double MinCut; + public TimeSpan Runtime; + + public Result(double minCut, TimeSpan runtime) + { + MinCut = minCut; + Runtime = runtime; + } + + public override string ToString() => $"{MinCut} @ {Runtime.TotalMilliseconds}"; + } + + class Analysis + { + Graph _graph; + Result _exact = new(); + Result Exact { get => _exact.Equals(default(Result)) ? (_exact = CalculateExact()) : _exact; } + int Repetitions; + + public Analysis(Graph graph, int repetitions) + { + _graph = graph; + Repetitions = repetitions; + } + + public List<Result> Analize(int iterations) + { + List<Result> results = new(); + results.Add(Exact); + Console.WriteLine($"Exact {Exact}"); + for (int i = 0; i < Repetitions; i++) + { + results.Add(CalculateApprox(iterations)); + Console.WriteLine($"Contract_{i + 1} {results.Last()}"); + } + + return results; + } + + 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); + } + + return new(result, stopwatch.Elapsed); + } + + Result CalculateApprox(int iterations) + { + Stopwatch stopwatch = Stopwatch.StartNew(); + double result = double.MaxValue; + + #region Parallel_Loop + Parallel.For(0, iterations, j => + { + var graphClone = (Graph)_graph.Clone(); + double currentResult = graphClone.Contraction(); + if (currentResult != 0) + result = Math.Min(result, currentResult); + }); + #endregion + + return new(result, stopwatch.Elapsed); + } + } +}
\ No newline at end of file diff --git a/src/Program/Program.cs b/src/Program/Program.cs index 90e80bd..05a91dc 100644 --- a/src/Program/Program.cs +++ b/src/Program/Program.cs @@ -6,102 +6,73 @@ using Graph = NetworkFlow.Graph; namespace Program { + class Program { static void Main(string[] args) { - // attempt to read file from command line args, otherwise asks for a file - FileInfo inputFile = (args.Length > 0) ? new FileInfo(args[0]) : ReadFileName(); - - // attempt to get source and terminal nodes from command line args - string source = (args.Length >= 2) ? args[1] : default(string); - string terminal = (args.Length >= 3) ? args[2] : default(string); - + List<Analysis> Analysii = new(); + DirectoryInfo graphDir = new DirectoryInfo((args.Length > 0) ? args[0] : "graphs"); + DirectoryInfo outDir = new("../../output"); + outDir.Create(); - if (!inputFile.Exists) + if (!graphDir.Exists) { - Console.WriteLine($"Failed to open {inputFile}: File does not exist."); - return; + Console.WriteLine($"Failed to open {graphDir}: Graph does not exist."); + System.Environment.Exit(1); } - // read file into graph - Graph graph = ReadFile(inputFile.FullName); - - // verify command line source and terminal values or gets new values from the user - (int s, int t) = ReadSourceAndTerminal(graph, source, terminal); - - // call maxFlow - double maxFlow = graph.MaxFlow(s, t); - Console.WriteLine($"The max flow is {maxFlow}"); - } + 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 }; - public static (int s, int t) ReadSourceAndTerminal(Graph graph, string source, string terminal) - { - int s, t; - // retries until it succeeds - while (true) + foreach (var file in graphDir.EnumerateFiles()) { - // try to parse supplied values - bool isSetSource = int.TryParse(source, out s); - bool isSetTerminal = int.TryParse(terminal, out t); - - // validates the values are ints and the graph contains the corresponding node - if (!(isSetSource && graph.Nodes.ContainsKey(s))) - { - if (source != default(string)) - Console.WriteLine($"Invalid Source Node: {source}"); - Console.Write($"Enter the Source Node: "); - // asks for a new value - source = Console.ReadLine(); - } - // validates the values are ints and the graph contains the corresponding node - if (!(isSetTerminal && graph.Nodes.ContainsKey(t))) - { - if (terminal != default(string)) - Console.WriteLine($"Invalid Terminal Node: {terminal}"); - Console.Write($"Enter the Terminal Node: "); - // asks for a new value - terminal = Console.ReadLine(); - } - // if everything is correct then we can return - if (isSetSource && isSetTerminal && graph.Nodes.ContainsKey(s) && graph.Nodes.ContainsKey(t)) - break; + Graph graph = ReadFile(file); + 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))}"); } - - return (s, t); + 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 FileInfo ReadFileName() - { - string filePath; - - // continues to ask for a valid filepath until obtained - while (true) - { - Console.Write("Enter a path to a points file: "); - filePath = Console.ReadLine(); - - if (String.IsNullOrEmpty(filePath)) - Console.WriteLine("File path cannot be empty!"); - else if (!System.IO.File.Exists(filePath)) - Console.WriteLine($"{filePath} does not exist."); - else - break; - } - - FileInfo file = new FileInfo(filePath); - - return file; - } - - public static Graph ReadFile(string file) + public static Graph ReadFile(FileInfo file) { // create default Graph object - Graph graph = new Graph(); + 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: @@ -116,11 +87,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; } + } } |