有没有人看过2-Sat实现

Question

我一直在寻找一段时间，但我似乎无法找到2-Sat算法的任何实现。

我在C++中使用boost库（其中有strongly connected component module），需要一些指导来创建一个有效的2-Sat程序或找到一个现有的库供我通过C++使用。

Answer 1

我想你知道如何建模一个2-Sat问题来解决SCC问题。 我处理变量和它的否定的方式不是很优雅，但允许一个简短的实现： 给定n个变量编号从0到n-1，在条款中-i表示变量i的否定，并且在图中我+ n表示相同（我清楚吗？）

#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; 
}