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
|
#include <string>
#include "Mongoose_IO.hpp"
#include "Mongoose_EdgeCut.hpp"
#include "Mongoose_Test.hpp"
#include <fstream>
using namespace Mongoose;
int runEdgeSeparatorTest(const std::string &inputFile, const double targetSplit)
{
LogTest("Running Edge Separator Test on " << inputFile);
// Given a symmetric matrix...
EdgeCut_Options *options;
Graph *graph;
options = EdgeCut_Options::create();
if (!options)
{
// Ran out of memory
LogTest("Error creating Options struct in Edge Separator Test");
return EXIT_FAILURE;
}
options->target_split = targetSplit;
// Read graph from file
graph = read_graph(inputFile);
if (!graph)
{
// Ran out of memory
LogTest("Error reading Graph from file in Edge Separator Test");
options->~EdgeCut_Options();
return EXIT_FAILURE;
}
// An edge separator should be computed with default options
EdgeCut *result = edge_cut(graph, options);
options->~EdgeCut_Options();
if (!result)
{
// Error occurred
LogTest("Error computing edge cut in Edge Separator Test");
return EXIT_FAILURE;
}
else
{
// The graph should be partitioned
assert (result->partition != NULL);
int count = 0;
for (int i = 0; i < result->n; i++)
{
bool equals_0 = (result->partition[i] == 0);
bool equals_1 = (result->partition[i] == 1);
assert(equals_0 != equals_1);
count += result->partition[i];
}
double split = (double) count / (double) graph->n;
double target = targetSplit;
if (split > 0.5)
{
split = 1 - split;
}
if (targetSplit > 0.5)
{
target = 1 - target;
}
Logger::printTimingInfo();
LogTest("Cut Properties:");
LogTest(" Cut Cost: " << result->cut_cost);
LogTest(" Imbalance: " << result->imbalance);
}
graph->~Graph();
result->~EdgeCut();
LogTest("Edge Separator Test Completed Successfully");
return EXIT_SUCCESS;
}
|
