src/GRAPHGEN/drag2optimal.cpp
// Given a dag with multiple actions on leaves this function generate all possible dags with only one action per leaf
Given a dag with multiple actions on leaves this function generate all possible dags with only one action per leaf
Given a dag with multiple actions on leaves this function generate all possible dags with only one action per leaf
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) {
    BinaryDrag<conact> nt;
    if (n->isleaf()) {
        std::vector<uint> actions_list = n->data.actions();
        if (actions_list.size() > 1) {
            for (size_t i = 0; i < actions_list.size() - 1; ++i) {
                std::map<const BinaryDrag<conact>::node*, bool> visited_node_cur;
                n->data.action = 0;
                n->data.action.set(actions_list[i] - 1);
                nt = t;
                Dag2OptimalDagRec(nt, nt.GetRoot(), best_tree, best_nodes, best_leaves, visited_node_cur, counter);
            }
            n->data.action = 0;
            n->data.action.set(actions_list[actions_list.size() - 1] - 1);
        }
        return;
    }
    if (!visited_n[n->left]) {
        visited_n[n->left] = true;
        Dag2OptimalDagRec(t, n->left, best_tree, best_nodes, best_leaves, visited_n, counter);
    }
    if (!visited_n[n->right]) {
        visited_n[n->right] = true;
        Dag2OptimalDagRec(t, n->right, best_tree, best_nodes, best_leaves, visited_n, counter);
    }
    if (t.GetRoot() == n) {
        counter++;
        BinaryDrag<conact> dag = t;
        Dag2DagUsingIdenties(dag);
        BinaryDragStatistics ds(dag);
        if (best_nodes > ds.Nodes()) {
            best_nodes = ds.Nodes();
            best_leaves = ds.Leaves();
            best_tree = dag;
        }
        else if (best_nodes == ds.Nodes() && best_leaves > ds.Leaves()) {
            best_leaves = ds.Leaves();
            best_tree = dag;
        }
        if (counter % 1000 == 0) {
            std::cout << counter / 1000 << "\r";
        }
    }
}
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 ) { BinaryDrag < conact > nt ; if ( n -> isleaf ( ) ) { std :: vector < uint > actions_list = n -> data . actions ( ) ; if ( actions_list . size ( ) > 1 ) { for ( size_t i = 0 ; i < actions_list . size ( ) - 1 ; ++ i ) { std :: map < const BinaryDrag < conact > :: node * , bool > visited_node_cur ; n -> data . action = 0 ; n -> data . action . set ( actions_list [ i ] - 1 ) ; nt = t ; Dag2OptimalDagRec ( nt , nt . GetRoot ( ) , best_tree , best_nodes , best_leaves , visited_node_cur , counter ) ; } n -> data . action = 0 ; n -> data . action . set ( actions_list [ actions_list . size ( ) - 1 ] - 1 ) ; } return ; } if ( ! visited_n [ n -> left ] ) { visited_n [ n -> left ] = true ; Dag2OptimalDagRec ( t , n -> left , best_tree , best_nodes , best_leaves , visited_n , counter ) ; } if ( ! visited_n [ n -> right ] ) { visited_n [ n -> right ] = true ; Dag2OptimalDagRec ( t , n -> right , best_tree , best_nodes , best_leaves , visited_n , counter ) ; } if ( t . GetRoot ( ) == n ) { counter ++ ; BinaryDrag < conact > dag = t ; Dag2DagUsingIdenties ( dag ) ; BinaryDragStatistics ds ( dag ) ; if ( best_nodes > ds . Nodes ( ) ) { best_nodes = ds . Nodes ( ) ; best_leaves = ds . Leaves ( ) ; best_tree = dag ; } else if ( best_nodes == ds . Nodes ( ) && best_leaves > ds . Leaves ( ) ) { best_leaves = ds . Leaves ( ) ; best_tree = dag ; } if ( counter % 1000 == 0 ) { std :: cout << counter / 1000 << " \r " ; } } }
Given a dag with multiple actions on leaves this function generate all possible dags with only one action per leaf
Given a dag with multiple actions on leaves this function generate all possible dags with only one action per leaf
// leaf with multiple action // left node not already visited // right node not already visited