aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/NetworkFlow/Graph.cs109
-rw-r--r--src/Program/Analysis.cs78
-rw-r--r--src/Program/Program.cs95
3 files changed, 197 insertions, 85 deletions
diff --git a/src/NetworkFlow/Graph.cs b/src/NetworkFlow/Graph.cs
index a66732d..3b0d879 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 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>
@@ -50,6 +83,24 @@ namespace NetworkFlow
public void ChangeEdge(int u, int v, double capacity)
=> this[u].Edges[v] -= capacity;
+
+ public Graph ToUndirected()
+ {
+ Graph graph = new Graph(undirected: true);
+
+ foreach (var node in Nodes.Values)
+ foreach (var edge in node.Edges)
+ {
+ graph.AddNode(node.Id);
+
+ // if child node does not have an edge pointing back to parent
+ if (!this[edge.Key].Edges.ContainsKey(node.Id))
+ graph.AddEdge(edge.Key, node.Id, edge.Value);
+ }
+
+ return graph;
+ }
+
/// <summary>
/// Finds the maximum flow possible from the <c>source</c>
/// node to the <c>terminal</c> node.
@@ -129,9 +180,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 +229,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..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;
}
+
}
}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-09-22 02:39:31 +0000