diff options
Diffstat (limited to 'src/Program')
| -rw-r--r-- | src/Program/Analysis.cs | 78 | ||||
| -rw-r--r-- | src/Program/Program.cs | 95 |
2 files changed, 94 insertions, 79 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 diff --git a/src/Program/Program.cs b/src/Program/Program.cs index 90e80bd..6aab0a3 100644 --- a/src/Program/Program.cs +++ b/src/Program/Program.cs @@ -1,104 +1,40 @@ using System; using System.Collections.Generic; +using System.Diagnostics; using System.IO; using System.Linq; 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"); - - 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}"); - } - - 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; - } - - - return (s, t); - } - - 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; + Graph graph = ReadFile(file.FullName); + Analysis analysis = new(graph); + analysis.Analize(); + Analysii.Add(analysis); + Console.WriteLine(analysis.ToString()); } - - FileInfo file = new FileInfo(filePath); - - return file; } public static Graph ReadFile(string 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)) @@ -122,5 +58,6 @@ namespace Program // return object when done return graph; } + } } |