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
90
91
92
93
94
95
96
97
98
99
|
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using Graph = NetworkFlow.Graph;
namespace Program
{
class Program
{
static void Main(string[] args)
{
List<Analysis> Analysii = new();
DirectoryInfo graphDir = new DirectoryInfo((args.Length > 0) ? args[0] : "graphs");
DirectoryInfo outDir = new("../../output");
outDir.Create();
if (!graphDir.Exists)
{
Console.WriteLine($"Failed to open {graphDir}: Graph does not exist.");
System.Environment.Exit(1);
}
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 };
foreach (var file in graphDir.EnumerateFiles())
{
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))}");
}
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 Graph ReadFile(FileInfo file)
{
// create default Graph object
Graph graph = new Graph(undirected: true);
// Read in graph file
foreach (string line in File.ReadLines(file.FullName))
{
// each file line is a Node with optional edges
// line format:
// vertex:int optional[ connected-vertex:int edge-weight:double optional[..] ]
List<string> vals = line.Split(' ').ToList();
int u, v;
double weight;
int.TryParse(vals[0], out u);
graph.AddNode(u);
for (int i = 1; i < vals.Count - 1; i += 2)
{
// AddEdge(int u, int v, double weight)
int.TryParse(vals[i], out v);
double.TryParse(vals[i + 1], out weight);
if (!graph[u].Edges.ContainsKey(v))
graph.AddEdge(u, v, weight);
}
}
// return object when done
return graph;
}
}
}
|
