blob: f81720096b6669a9e26813d6514581cdc77f6400 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
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);
}
}
}
|
