src/subsume.cpp
// Find clauses connected in the occurrence lists 'occs' which subsume the
// candidate clause 'c' given as first argument.  If this is the case the
// clause is subsumed and the result is positive.   If the clause was
// strengthened the result is negative.  Otherwise the candidate clause
// can not be subsumed nor strengthened and zero is returned.
Find clauses connected in the occurrence lists 'occs' which subsume the
candidate clause 'c' given as first argument.  If this is the case the
clause is subsumed and the result is positive.   If the clause was
strengthened the result is negative.  Otherwise the candidate clause
can not be subsumed nor strengthened and zero is returned.
Find clauses connected in the occurrence lists ' occs ' which subsume the candidate clause ' c ' given as first argument . If this is the case the clause is subsumed and the result is positive . If the clause was strengthened the result is negative . Otherwise the candidate clause can not be subsumed nor strengthened and zero is returned .
inline int
Internal::try_to_subsume_clause (Clause * c, vector<Clause *> & shrunken) {
  stats.subtried++;
  assert (!level);
  LOG (c, "trying to subsume");
  mark (c);	
  Clause * d = 0;
  int flipped = 0;
  const const_literal_iterator ec = c->end ();
  for (const_literal_iterator i = c->begin (); !d && i != ec; i++) {
    int lit = *i;
    if (!flags (lit).added) continue;
    for (int sign = -1; !d && sign <= 1; sign += 2) {
      Bins & bs = bins (sign*lit);
      const const_bins_iterator eb = bs.end ();
      const_bins_iterator b;
      for (b = bs.begin (); !d && b != eb; b++) {
        const int other = *b, tmp = marked (other);
	if (!tmp) continue;
	if (tmp < 0 && sign < 0) continue;
	if (tmp < 0) {
	  if (sign < 0) continue;		 tautological resolvent
	  binary_subsuming.literals[0] = lit;
	  binary_subsuming.literals[1] = other;
	  flipped = other;
	} else {
	  binary_subsuming.literals[0] = sign*lit;
	  binary_subsuming.literals[1] = other;
	  flipped = (sign < 0) ? -lit : INT_MIN;
	}
        assert (binary_subsuming.size == 2);
        assert (!binary_subsuming.redundant);
        d = &binary_subsuming;
      }
      if (d) break;
       In this second loop we check for larger than binary clauses to
       subsume or strengthen the candidate clause.   This is more costly,
       and needs a call to 'subsume_check'.  Otherwise the same contract
       as above for communicating 'subsumption' or 'strengthening' to the
       code after the loop.
      Occs & os = occs (sign * lit);
      const const_occs_iterator eo = os.end ();
      occs_iterator k = os.begin ();
      for (const_occs_iterator j = k; j != eo; j++) {
        Clause * e = *k++ = *j;
        if (d) continue;                         need to copy rest
        if (e->garbage) { k--; continue; }
        flipped = subsume_check (e, c);
        if (!flipped) continue;
        d = e;                                   leave outer loop
        if (flipped == INT_MIN) continue;
        if (sign < 0) assert (flipped == -lit), k--;
        else assert (flipped != lit);
      }
      os.resize (k - os.begin ());
      shrink_occs (os);
    }
  }
  unmark (c);
  if (flipped == INT_MIN) {
    LOG (d, "subsuming");
    subsume_clause (d, c);
    return 1;
  }
  if (flipped) {
    LOG (d, "strengthening");
    strengthen_clause (c, -flipped);
    assert (likely_to_be_kept_clause (c));
    shrunken.push_back (c);
    return -1;
  }
  return 0;
}
inline int Internal :: try_to_subsume_clause ( Clause * c , vector < Clause * > & shrunken ) { stats . subtried ++ ; assert ( ! level ) ; LOG ( c , " " ) ; mark ( c ) ; Clause * d = 0 ; int flipped = 0 ; const const_literal_iterator ec = c -> end ( ) ; for ( const_literal_iterator i = c -> begin ( ) ; ! d && i != ec ; i ++ ) { int lit = * i ; if ( ! flags ( lit ) . added ) continue ; for ( int sign = -1 ; ! d && sign <= 1 ; sign += 2 ) { Bins & bs = bins ( sign * lit ) ; const const_bins_iterator eb = bs . end ( ) ; const_bins_iterator b ; for ( b = bs . begin ( ) ; ! d && b != eb ; b ++ ) { const int other = * b , tmp = marked ( other ) ; if ( ! tmp ) continue ; if ( tmp < 0 && sign < 0 ) continue ; if ( tmp < 0 ) { if ( sign < 0 ) continue ; binary_subsuming . literals [ 0 ] = lit ; binary_subsuming . literals [ 1 ] = other ; flipped = other ; } else { binary_subsuming . literals [ 0 ] = sign * lit ; binary_subsuming . literals [ 1 ] = other ; flipped = ( sign < 0 ) ? - lit : INT_MIN ; } assert ( binary_subsuming . size == 2 ) ; assert ( ! binary_subsuming . redundant ) ; d = & binary_subsuming ; } if ( d ) break ; Occs & os = occs ( sign * lit ) ; const const_occs_iterator eo = os . end ( ) ; occs_iterator k = os . begin ( ) ; for ( const_occs_iterator j = k ; j != eo ; j ++ ) { Clause * e = * k ++ = * j ; if ( d ) continue ; if ( e -> garbage ) { k -- ; continue ; } flipped = subsume_check ( e , c ) ; if ( ! flipped ) continue ; d = e ; if ( flipped == INT_MIN ) continue ; if ( sign < 0 ) assert ( flipped == - lit ) , k -- ; else assert ( flipped != lit ) ; } os . resize ( k - os . begin ( ) ) ; shrink_occs ( os ) ; } } unmark ( c ) ; if ( flipped == INT_MIN ) { LOG ( d , " " ) ; subsume_clause ( d , c ) ; return 1 ; } if ( flipped ) { LOG ( d , " " ) ; strengthen_clause ( c , - flipped ) ; assert ( likely_to_be_kept_clause ( c ) ) ; shrunken . push_back ( c ) ; return -1 ; } return 0 ; }
Find clauses connected in the occurrence lists 'occs' which subsume the
candidate clause 'c' given as first argument.
Find clauses connected in the occurrence lists ' occs ' which subsume the candidate clause ' c ' given as first argument .
// signed! // First we check against all binary clauses.  The other literals of // all binary clauses of 'sign*lit' are stored in one consecutive // array, which is way faster than storing clause pointers and // dereferencing them.  Since this binary clause array is also not // shrunken, we also can bail out earlier if subsumption or // strengthening is determined.  In both cases the (self-)subsuming // clause is stored in 'd', which makes it nonzero and forces // aborting both the outer and inner loop.  If the binary clause can // strengthen the candidate clause 'c' (through self-subsuming // resolution), then 'filled' is set to the literal which can be // removed in 'c', otherwise to 'INT_MIN' which is a non-valid // literal. // // tautological resolvent // In this second loop we check for larger than binary clauses to // subsume or strengthen the candidate clause.   This is more costly, // and needs a call to 'subsume_check'.  Otherwise the same contract // as above for communicating 'subsumption' or 'strengthening' to the // code after the loop. // // need to copy rest // leave outer loop