diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/NetworkFlow/Graph.cs | 93 | ||||
| -rw-r--r-- | src/Program/Analysis.cs | 89 | ||||
| -rw-r--r-- | src/Program/Program.cs | 131 |
3 files changed, 227 insertions, 86 deletions
diff --git a/src/NetworkFlow/Graph.cs b/src/NetworkFlow/Graph.cs index a66732d..54c2b29 100644 --- a/src/NetworkFlow/Graph.cs +++ b/src/NetworkFlow/Graph.cs @@ -1,22 +1,36 @@ using System; using System.Collections.Generic; +using System.Linq; namespace NetworkFlow { using Nodes = Dictionary<int, Node>; using Path = List<int>; - public class Graph + public class Graph : ICloneable { Dictionary<int, Node> _nodes; + public bool Undirected; public Nodes Nodes { get => _nodes; set => _nodes = value; } - public Graph() + public Graph(bool undirected = false) { + Undirected = undirected; Nodes = new Nodes(); } + public Graph(Graph o) + { + Undirected = o.Undirected; + Nodes = o.Nodes.ToDictionary(entry => entry.Key, + entry => (Node)entry.Value.Clone()); + } + + public Graph ShallowCopy() => (Graph)this.MemberwiseClone(); + public object Clone() => new Graph(this); + // public object Clone() => new Graph(this._nodes, Undirected); + /// <summary> /// Indexer; Retrieves the node with node.Id of <c>id</c> /// </summary> @@ -31,8 +45,14 @@ namespace NetworkFlow /// </summary> public void AddNode(int id) { - if (!this.Nodes.ContainsKey(id)) - this.Nodes.Add(id, new(id)); + this.Nodes.TryAdd(id, new(id)); + } + + public void RemoveNode(int id) + { + if (this[id].Edges.Count > 1) + throw new Exception("Removing this node would leave orphaned batma... edges, I mean edges."); + this.Nodes.Remove(id); } /// <summary> @@ -41,7 +61,20 @@ namespace NetworkFlow public void AddEdge(int u, int v, double capacity) { AddNode(u); - this[u].Edges.Add(v, capacity); + AddNode(v); + + if (!Nodes[u].Edges.TryAdd(v, capacity)) + Nodes[u].Edges[v] += capacity; + + if (Undirected && !Nodes[v].Edges.TryAdd(u, capacity)) + Nodes[v].Edges[u] += capacity; + } + + public void RemoveEdge(int u, int v) + { + Nodes[u].Edges.Remove(v); + if (Undirected && Nodes[v].Edges.ContainsKey(u)) + Nodes[v].Edges.Remove(u); } /// <summary> @@ -81,7 +114,7 @@ namespace NetworkFlow maxFlow += capacity; // output the current progress - Console.WriteLine($"The augmenting path is {String.Join(",", path)} capacity = {capacity}"); + // Console.WriteLine($"The augmenting path is {String.Join(",", path)} capacity = {capacity}"); } // output when completed @@ -129,9 +162,46 @@ namespace NetworkFlow // return an empty path if a path to terminal node was not found return new(); } + + + public double Contraction() + { + + Random random = new Random(); + + // while nodes > 2 + while (Nodes.Count > 2) + { + // pick a random edge + Node node = Nodes.Values.ElementAt(random.Next(0, Nodes.Count)); + + int u = node.Id; + int v = node.Edges.Keys.ElementAt(random.Next(0, node.Edges.Count)); + + // redirect edges of one node (v) to other node (u) + // this includes changing the edges that point to v for each node that v has in its edges + foreach (var edge in Nodes[v].Edges) + if (edge.Key != u) + { + AddEdge(u, edge.Key, edge.Value); + RemoveEdge(v, edge.Key); + } + + // remove the edge from both sides (u and v) + RemoveEdge(u, v); + + // delete node whose edges were redirected (v) + RemoveNode(v); + } + + // return the sum of the remaining edges' weights + return Nodes.ElementAt(0).Value.Edges.ElementAt(0).Value; + } + + } - public struct Node + public struct Node : ICloneable { public int Id { get; set; } public Dictionary<int, double> Edges { get; set; } @@ -141,5 +211,14 @@ namespace NetworkFlow Id = id; Edges = new(); } + + public Node(Node o) + { + Id = o.Id; + Edges = o.Edges.ToDictionary(entry => entry.Key, + entry => entry.Value); + } + + public object Clone() => new Node(this); } }
\ No newline at end of file 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; } + } } |