38 if (n2->isleaf() || n1 == n2 || visited_fl[n2])
40 visited_fl[n2] =
true;
42 if (n1 != n2->left &&
EqualTrees(n1, n2->left)) {
46 if (n1 != n2->right &&
EqualTrees(n1, n2->right)) {
56 std::map<BinaryDrag<conact>::node*,
bool> visited_fl;
61 if (!visited_n[n->left])
63 if (!visited_n[n->right])
70 std::map<BinaryDrag<conact>::node*,
bool> visited_n;
75 if (n2->isleaf() || n1 == n2 || visited_fl[n2])
77 visited_fl[n2] =
true;
93 std::map<BinaryDrag<conact>::node*,
bool> visited_fl;
95 if (!n->isleaf() || considering_leaves) {
101 if (!visited_n[n->left])
103 if (!visited_n[n->right])
110 std::map<BinaryDrag<conact>::node*,
bool> visited_n;
119 std::vector<uint> actions_list = n->data.actions();
120 if (actions_list.size() > 1) {
121 for (
size_t i = 0; i < actions_list.size() - 1; ++i) {
122 std::map<const BinaryDrag<conact>::node*,
bool> visited_node_cur;
124 n->data.action.set(actions_list[i] - 1);
129 n->data.action.set(actions_list[actions_list.size() - 1] - 1);
134 if (!visited_n[n->left]) {
136 visited_n[n->left] =
true;
137 Dag2OptimalDagRec(t, n->left, best_tree, best_nodes, best_leaves, visited_n, counter);
140 if (!visited_n[n->right]) {
142 visited_n[n->right] =
true;
143 Dag2OptimalDagRec(t, n->right, best_tree, best_nodes, best_leaves, visited_n, counter);
153 if (best_nodes > ds.
Nodes()) {
154 best_nodes = ds.
Nodes();
155 best_leaves = ds.
Leaves();
158 else if (best_nodes == ds.
Nodes() && best_leaves > ds.
Leaves()) {
159 best_leaves = ds.
Leaves();
163 if (counter % 1000 == 0) {
164 std::cout << counter / 1000 <<
"\r";
173 std::vector<BinaryDrag<conact>> trees;
175 std::map<const BinaryDrag<conact>::node*,
bool> visited_nodes;
177 size_t best_nodes = std::numeric_limits<size_t>::max();
178 size_t best_leaves = std::numeric_limits<size_t>::max();
180 std::cout <<
"** Vector size:" << counter <<
" **\n";
181 std::cout <<
"** Counter:" << counter <<
" **\n";
A BinaryDrag is the GRAPHGEN implementation of a Binary Directed Rooted Acyclic Graph (DRAG in short)
node * GetRoot() const
Returns the last root of the BinaryDrag.
Calculates the statistics of a binary drag with one or multiple roots.
auto Nodes() const
Returns the number of unique nodes inside the DRAG.
auto Leaves() const
Returns the number of unique leaves inside the DRAG.
bool EqualTrees(const BinaryDrag< conact >::node *n1, const BinaryDrag< conact >::node *n2)
Checks whether two (sub)trees 'n1' and 'n2' are equal or nor.
bool equivalent_trees(const BinaryDrag< conact >::node *n1, const BinaryDrag< conact >::node *n2)
void FindAndLinkEquivalencesDagRec(BinaryDrag< conact >::node *n1, BinaryDrag< conact >::node *n2, std::map< BinaryDrag< conact >::node *, bool > &visited_fl)
void FindAndLinkIdentiesDagRec(BinaryDrag< conact >::node *n1, BinaryDrag< conact >::node *n2, std::map< BinaryDrag< conact >::node *, bool > &visited_fl)
void Dag2OptimalDagRec(BinaryDrag< conact > &t, BinaryDrag< conact >::node *n, BinaryDrag< conact > &best_tree, size_t &best_nodes, size_t &best_leaves, std::map< const BinaryDrag< conact >::node *, bool > &visited_n, uint &counter)
void Dag2DagUsingIdenties(BinaryDrag< conact > &t)
void Dag2DagUsingEquivalencesRec(BinaryDrag< conact >::node *n, BinaryDrag< conact > &t, std::map< BinaryDrag< conact >::node *, bool > &visited_n, bool considering_leaves)
void Dag2DagUsingEquivalences(BinaryDrag< conact > &t, bool considering_leaves)
void Dag2OptimalDag(BinaryDrag< conact > &t)
void Dag2DagUsingIdentiesRec(BinaryDrag< conact >::node *n, BinaryDrag< conact > &t, std::map< BinaryDrag< conact >::node *, bool > &visited_n)