34 cout <<
"Usage: " << name <<
" <options>" << endl
35 <<
" -m <int> tree size (edges) (default: 1000)" << endl
36 <<
" -n <int> number of trees to test (default: 100)" << endl
37 <<
" -l <int> number of different labels to assign to the nodes (default: 2)" << endl
38 <<
" -s <int> seed (default: 12345678)" << endl
39 <<
" -r use RePair-inspired combiner" << endl
40 <<
" -g <file> set output file for edge compression ratios (default: no output)" << endl
41 <<
" -o <file> set output file for debug information (default: no output)" << endl
42 <<
" -w <path> set output folder for generated trees as XML files (default: don't write)" << endl
43 <<
" -t <int> number of threads to use (default: #cores)" << endl
44 <<
" -v verbose" << endl
45 <<
" -vv extra verbose" << endl;
51 const int numLabels,
const bool useRepair,
const bool verbose,
const bool extraVerbose,
55 if (verbose) cout << endl <<
"Round " << iteration <<
", seed is " <<seed << endl;
68 if (verbose) cout <<
"Generated " << tree.
summary() <<
" in " << timer.
get() <<
"ms" << endl;
76 const string filename(treePath +
"/" + std::to_string(iteration) +
"_" + std::to_string(seed) +
".xml");
94 cout <<
"minRatio = " << debugInfo.
minEdgeRatio <<
" for seed " << seed << endl;
99 cout <<
"Top DAG construction took " << timer.
get() <<
"ms" << endl;
109 const double percentage = (edges * 100.0) / treeEdges;
110 const double ratio = ((int)(1000 / percentage)) / 10.0;
113 cout <<
"Top dag has " << dag.
nodes.size() - 1 <<
" nodes, " << edges <<
" edges (" << percentage
114 <<
"% of original tree, " << ratio <<
":1)" << endl;
125 int main(
int argc,
char **argv) {
128 if (argParser.
isSet(
"h") || argParser.
isSet(
"-help")) {
133 const int size = argParser.
get<
int>(
"m", 1000);
134 const int numIterations = argParser.
get<
int>(
"n", 100);
135 const uint numLabels = argParser.
get<uint>(
"l", 2);
136 const uint seed = argParser.
get<uint>(
"s", 12345678);
137 const bool verbose = argParser.
isSet(
"v") || argParser.
isSet(
"vv");
138 const bool extraVerbose = argParser.
isSet(
"vv");
139 const bool useRepair = argParser.
isSet(
"r");
140 const string ratioFilename = argParser.
get<
string>(
"g",
"");
141 const string debugFilename = argParser.
get<
string>(
"o",
"");
142 const string treePath = argParser.
get<
string>(
"w",
"");
144 if (treePath !=
"") {
148 int numWorkers(std::thread::hardware_concurrency());
149 numWorkers = argParser.
get<
int>(
"t", numWorkers);
151 Statistics statistics(ratioFilename, debugFilename);
154 cout <<
"Running experiments with " << numIterations <<
" trees of size " << size <<
" with " << numLabels
155 <<
" different labels" << flush;
158 vector<uint> seeds(numIterations);
159 if (numIterations > 1) {
160 std::seed_seq seedSeq({(uint)size, (uint)numIterations, numLabels, seed});
161 seedSeq.generate(seeds.begin(), seeds.end());
168 auto worker = [&](
int start,
int end) {
170 for (
int i = start; i < end; ++i) {
171 runIteration(i, engine, seeds[i], size, numLabels, useRepair, verbose, extraVerbose, statistics, bar, treePath);
175 const int treesPerThread = numIterations / numWorkers;
176 const int leftovers = numIterations % numWorkers;
178 vector<std::thread> workers;
180 cout <<
" using " << numWorkers <<
" threads" << endl;
182 int min(0), max(treesPerThread);
183 for (
int i = 0; i < numWorkers; ++i) {
187 workers.push_back(std::thread(worker, min, max));
189 max += treesPerThread;
192 for (std::thread &worker : workers) {
198 statistics.compute();
199 statistics.dump(std::cerr);
Transform a tree into its top tree.
vector< DagNode< DataType > > nodes
Ordered tree data structure.
void undraw()
remove all traces of the bar from the output stream
double mergeDuration
the time it took to transform the tree into its top tree (in milliseconds)
double dagDuration
the time it took to compute the top tree's minimal DAG (in milliseconds)
double generationDuration
the time it took to generate the tree (in milliseconds)
uint_fast64_t numDagEdges
number of edges in the minimal DAG
void runIteration(const int iteration, RandomGeneratorType &generator, const uint seed, const int size, const int numLabels, const bool useRepair, const bool verbose, const bool extraVerbose, Statistics &statistics, ProgressBar &bar, const string &treePath)
int main(int argc, char **argv)
bool isSet(const string &arg) const
check whether an argument was set
double avgDepth
average depth of the tree's nodes
uint_fast64_t height
height of the tree
double statDuration
the time spent on statistical stuff
Parse command-line arguments.
uint_fast64_t numDagNodes
number of nodes in the minimal DAG
void construct(DebugInfo *debugInfo=NULL)
void addDebugInfo(const DebugInfo &info)
add a debug info object
Holds debug information about a tree compression run.
T get(const string &key, const T defaultValue=T())
Generates ordered unlabelled trees uniformly at random.
Transform a tree into its top tree.
double minEdgeRatio
the minimum ratio of edges before and after an iteration (there are theoretical bounds on this) ...
double ioDuration
the time spent on I/O
string summary() const
A one-line summary of the tree.
bool makePathRecursive(std::string path, int permissions=0755)
XML tree writer (empty template for overloading)
int countEdges() const
Count the number of edges in the DAG.
A binary DAG that is specialised to be a top tree's minimal DAG.
void generateTree(TreeType &tree, const int numEdges, const bool verbose=false)
void construct(DebugInfo *debugInfo=NULL, const double minRatio=1.2)
std::mt19937 RandomGeneratorType
the type of random generator used