Est-ce que quelqu'un a vu une implémentation de 2-Sat

Question

Je cherchais depuis longtemps, mais je n'arrive pas à trouver une implémentation de l'algorithme 2-Sat.

Je travaille en C++ avec la bibliothèque boost (qui a un strongly connected component module) et j'ai besoin de quelques conseils pour créer un programme 2-Sat efficace ou trouver une bibliothèque existante pour que je puisse l'utiliser via C++.

Answer 1

Je suppose que vous savez comment modéliser un problème 2-Sat pour le résoudre avec SCC. La façon dont je gère les variables et leur négation n'est pas très élégante, mais permet une implémentation courte: Étant donné n variables numérotées de 0 à n-1, dans les clauses -i signifie la négation de la variable i, et dans le graphique i + n signifie la même chose (je suis clair?)

#include <boost/config.hpp> 
#include <iostream> 
#include <vector> 
#include <boost/graph/strong_components.hpp> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/foreach.hpp> 

typedef std::pair<int, int> clause; 

//Properties of our graph. By default oriented graph 
typedef boost::adjacency_list<> Graph; 


const int nb_vars = 5; 

int var_to_node(int var) 
{ 
    if(var < 0) 
     return (-var + nb_vars); 
    else 
     return var; 
} 

int main(int argc, char ** argv) 
{ 
    std::vector<clause> clauses; 
    clauses.push_back(clause(1,2)); 
    clauses.push_back(clause(2,-4)); 
    clauses.push_back(clause(1,4)); 
    clauses.push_back(clause(1,3)); 
    clauses.push_back(clause(-2,4)); 

    //Creates a graph with twice as many nodes as variables 
    Graph g(nb_vars * 2); 

    //Let's add all the edges 
    BOOST_FOREACH(clause c, clauses) 
    { 
     int v1 = c.first; 
     int v2 = c.second; 
     boost::add_edge(
       var_to_node(-v1), 
       var_to_node(v2), 
       g); 

     boost::add_edge(
       var_to_node(-v2), 
       var_to_node(v1), 
       g); 
    } 

    // Every node will belong to a strongly connected component 
    std::vector<int> component(num_vertices(g)); 
    std::cout << strong_components(g, &component[0]) << std::endl; 

    // Let's check if there is variable having it's negation 
    // in the same SCC 
    bool satisfied = true; 
    for(int i=0; i<nb_vars; i++) 
    { 
     if(component[i] == component[i+nb_vars]) 
      satisfied = false; 
    } 
    if(satisfied) 
     std::cout << "Satisfied!" << std::endl; 
    else 
     std::cout << "Not satisfied!" << std::endl; 
}