abc/src/sat/satoko/solver.c
/**
 *  Most books and papers explain conflict analysis and the calculation of the
 *  1UIP (first Unique Implication Point) using an implication graph. This
 *  function, however, do not explicity constructs the graph! It inspects the
 *  trail in reverse and figure out which literals should be added to the
 *  to-be-learnt clause using the reasons of each assignment.
 *
 *  cur_lit: current literal being analyzed.
 *  n_paths: number of unprocessed paths from conlfict node to the current
 *           literal being analyzed (cur_lit).
 *
 *  This functions performs a backward BFS (breadth-first search) for 1UIP node.
 *  The trail works as the BFS queue. The counter of unprocessed but seen
 *  variables (n_paths) allows us to identify when 'cur_lit' is the closest
 *  cause of conflict.
 *
 *  When 'n_paths' reaches zero it means there are no unprocessed reverse paths
 *  back from the conflict node to 'cur_lit' - meaning it is the 1UIP decision
 *  variable.
 *
 */
Most books and papers explain conflict analysis and the calculation of the
1UIP (first Unique Implication Point) using an implication graph. This
function, however, do not explicity constructs the graph. It inspects the
trail in reverse and figure out which literals should be added to the
to-be-learnt clause using the reasons of each assignment.

current literal being analyzed.
n_paths: number of unprocessed paths from conlfict node to the current
literal being analyzed (cur_lit).

This functions performs a backward BFS (breadth-first search) for 1UIP node.
The trail works as the BFS queue. The counter of unprocessed but seen
variables (n_paths) allows us to identify when 'cur_lit' is the closest
cause of conflict.

When 'n_paths' reaches zero it means there are no unprocessed reverse paths
back from the conflict node to 'cur_lit' - meaning it is the 1UIP decision
variable.
Most books and papers explain conflict analysis and the calculation of the 1UIP ( first Unique Implication Point ) using an implication graph . This function however do not explicity constructs the graph . It inspects the trail in reverse and figure out which literals should be added to the to - be - learnt clause using the reasons of each assignment . current literal being analyzed . n_paths : number of unprocessed paths from conlfict node to the current literal being analyzed ( cur_lit ) . This functions performs a backward BFS ( breadth - first search ) for 1UIP node . The trail works as the BFS queue . The counter of unprocessed but seen variables ( n_paths ) allows us to identify when ' cur_lit ' is the closest cause of conflict . When ' n_paths ' reaches zero it means there are no unprocessed reverse paths back from the conflict node to ' cur_lit ' - meaning it is the 1UIP decision variable .
static inline void solver_analyze(solver_t *s, unsigned cref, vec_uint_t *learnt,
                      unsigned *bt_level, unsigned *lbd)
{
    unsigned i;
    unsigned *trail = vec_uint_data(s->trail);
    unsigned idx = vec_uint_size(s->trail) - 1;
    unsigned n_paths = 0;
    unsigned p = UNDEF;
    unsigned var;
    vec_uint_push_back(learnt, UNDEF);
    do {
        struct clause *clause;
        unsigned *lits;
        unsigned j;
        assert(cref != UNDEF);
        clause = clause_fetch(s, cref);
        lits = &(clause->data[0].lit);
        if (p != UNDEF && clause->size == 2 && lit_value(s, lits[0]) == SATOKO_LIT_FALSE) {
            assert(lit_value(s, lits[1]) == SATOKO_LIT_TRUE);
            stk_swap(unsigned, lits[0], lits[1] );
        }
        if (clause->f_learnt)
            clause_act_bump(s, clause);
        if (clause->f_learnt && clause->lbd > 2) {
            unsigned n_levels = clause_clac_lbd(s, lits, clause->size);
            if (n_levels + 1 < clause->lbd) {
                if (clause->lbd <= s->opts.lbd_freeze_clause)
                    clause->f_deletable = 0;
                clause->lbd = n_levels;
            }
        }
        for (j = (p == UNDEF ? 0 : 1); j < clause->size; j++) {
            var = lit2var(lits[j]);
            if (vec_char_at(s->seen, var) || var_dlevel(s, var) == 0)
                continue;
            vec_char_assign(s->seen, var, 1);
            var_act_bump(s, var);
            if (var_dlevel(s, var) == solver_dlevel(s)) {
                n_paths++;
                if (var_reason(s, var) != UNDEF && clause_fetch(s, var_reason(s, var))->f_learnt)
                    vec_uint_push_back(s->last_dlevel, var);
            } else
                vec_uint_push_back(learnt, lits[j]);
        }
        while (!vec_char_at(s->seen, lit2var(trail[idx--])));
        p = trail[idx + 1];
        cref = lit_reason(s, p);
        vec_char_assign(s->seen, lit2var(p), 0);
        n_paths--;
    } while (n_paths > 0);
    vec_uint_data(learnt)[0] = lit_compl(p);
    clause_minimize(s, learnt);
    *bt_level = solver_calc_bt_level(s, learnt);
    *lbd = clause_clac_lbd(s, vec_uint_data(learnt), vec_uint_size(learnt));
    if (vec_uint_size(s->last_dlevel) > 0) {
        vec_uint_foreach(s->last_dlevel, var, i) {
            if (clause_fetch(s, var_reason(s, var))->lbd < *lbd)
                var_act_bump(s, var);
        }
        vec_uint_clear(s->last_dlevel);
    }
    vec_uint_foreach(s->tagged, var, i)
        vec_char_assign(s->seen, var, 0);
    vec_uint_clear(s->tagged);
}
static inline void solver_analyze ( solver_t * s , unsigned cref , vec_uint_t * learnt , unsigned * bt_level , unsigned * lbd ) { unsigned i ; unsigned * trail = vec_uint_data ( s -> trail ) ; unsigned idx = vec_uint_size ( s -> trail ) - 1 ; unsigned n_paths = 0 ; unsigned p = UNDEF ; unsigned var ; vec_uint_push_back ( learnt , UNDEF ) ; do { struct clause * clause ; unsigned * lits ; unsigned j ; assert ( cref != UNDEF ) ; clause = clause_fetch ( s , cref ) ; lits = & ( clause -> data [ 0 ] . lit ) ; if ( p != UNDEF && clause -> size == 2 && lit_value ( s , lits [ 0 ] ) == SATOKO_LIT_FALSE ) { assert ( lit_value ( s , lits [ 1 ] ) == SATOKO_LIT_TRUE ) ; stk_swap ( unsigned , lits [ 0 ] , lits [ 1 ] ) ; } if ( clause -> f_learnt ) clause_act_bump ( s , clause ) ; if ( clause -> f_learnt && clause -> lbd > 2 ) { unsigned n_levels = clause_clac_lbd ( s , lits , clause -> size ) ; if ( n_levels + 1 < clause -> lbd ) { if ( clause -> lbd <= s -> opts . lbd_freeze_clause ) clause -> f_deletable = 0 ; clause -> lbd = n_levels ; } } for ( j = ( p == UNDEF ? 0 : 1 ) ; j < clause -> size ; j ++ ) { var = lit2var ( lits [ j ] ) ; if ( vec_char_at ( s -> seen , var ) || var_dlevel ( s , var ) == 0 ) continue ; vec_char_assign ( s -> seen , var , 1 ) ; var_act_bump ( s , var ) ; if ( var_dlevel ( s , var ) == solver_dlevel ( s ) ) { n_paths ++ ; if ( var_reason ( s , var ) != UNDEF && clause_fetch ( s , var_reason ( s , var ) ) -> f_learnt ) vec_uint_push_back ( s -> last_dlevel , var ) ; } else vec_uint_push_back ( learnt , lits [ j ] ) ; } while ( ! vec_char_at ( s -> seen , lit2var ( trail [ idx -- ] ) ) ) ; p = trail [ idx + 1 ] ; cref = lit_reason ( s , p ) ; vec_char_assign ( s -> seen , lit2var ( p ) , 0 ) ; n_paths -- ; } while ( n_paths > 0 ) ; vec_uint_data ( learnt ) [ 0 ] = lit_compl ( p ) ; clause_minimize ( s , learnt ) ; * bt_level = solver_calc_bt_level ( s , learnt ) ; * lbd = clause_clac_lbd ( s , vec_uint_data ( learnt ) , vec_uint_size ( learnt ) ) ; if ( vec_uint_size ( s -> last_dlevel ) > 0 ) { vec_uint_foreach ( s -> last_dlevel , var , i ) { if ( clause_fetch ( s , var_reason ( s , var ) ) -> lbd < * lbd ) var_act_bump ( s , var ) ; } vec_uint_clear ( s -> last_dlevel ) ; } vec_uint_foreach ( s -> tagged , var , i ) vec_char_assign ( s -> seen , var , 0 ) ; vec_uint_clear ( s -> tagged ) ; }
Most books and papers explain conflict analysis and the calculation of the
  1UIP (first Unique Implication Point) using an implication graph.
Most books and papers explain conflict analysis and the calculation of the 1UIP ( first Unique Implication Point ) using an implication graph .