Merge branch 'develop'HEADmain

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;
         }
+
     }
 }