고밀도의 큰 그래프에서 최대 가중치 크리크

Question

~ 17000 개의 가중치 정점 및 ~ 75 % 밀도의 그래프에서 알려진 정점 수를 가진 (대략적 인) 최대 도수를 찾는 데 도움이되는 소프트웨어 또는 알고리즘 설명이 있습니까? ? 나는 Cliquer를 사용하려했지만 너무 느리다. (결과를 얻는 데 며칠이 걸렸다.)

내 문제에 대해서는 약간의 문제가 있습니다. 문제는 sceduling이고, 18 개의 시간 슬롯이 있으며, 각기 다른 수의 대안으로 채워질 수 있습니다. 각 변수는 하나의 슬롯에 대한 하나의 대안을 나타냅니다. 따라서 한 슬롯에 대한 모든 대안은 상호 배타적이며 다른 슬롯에 대한 일부 대안은 호환되지 않습니다. 두 가지 대안이 서로 호환되는 경우 둘 사이에 가장자리가 있습니다. 무게는 대안의 가치를 반복합니다.

Answer 1

Boost Graph Library에는 실제로 문서를 찾을 수는 없지만 실제로는 클릭 검색 알고리즘이 구현 된 것으로 보입니다. 그러나 사용 방법에 대한 아이디어를 얻으려면 the implementation source code of the algorithm과 this example을 살펴볼 수 있습니다.

#include <boost/graph/undirected_graph.hpp> 
#include <boost/graph/bron_kerbosch_all_cliques.hpp> 
#include <set> 
#include <iostream> 

// this is the visitor that will process each clique found by the algorithm 
template <typename VertexWeight> 
struct max_weighted_clique { 
    typedef typename boost::property_traits<VertexWeight>::key_type Vertex; 
    typedef typename boost::property_traits<VertexWeight>::value_type Weight; 

    max_weighted_clique(const VertexWeight& weight_map, std::set<Vertex>& max_clique, Weight& max_weight) 
     : weight_map(weight_map), max_weight(max_weight), max_clique(max_clique) { 
     // max_weight = -inf 
     max_weight = std::numeric_limits<Weight>::lowest(); 
    } 

    // this is called each time a clique is found 
    template <typename Clique, typename Graph> 
    void clique(const Clique& c, const Graph& g) { 
     // check the current clique value 
     std::set<Vertex> current_clique; 
     Weight current_weight = Weight(0); 
     for(auto it = c.begin(); it != c.end(); ++it) { 
      current_clique.insert(*it); 
      current_weight += weight_map[*it]; 
     } 
     // if it is a bigger clique, replace 
     if (current_weight > max_weight) { 
      max_weight = current_weight; 
      max_clique = current_clique; 
     } 
    } 

    const VertexWeight& weight_map; 
    std::set<Vertex> &max_clique; 
    Weight& max_weight; 
}; 


// may replace with long, double... 
typedef int Weight; 

// this struct defines the properties of each vertex 
struct VertexProperty { 
    Weight weight; 
    std::string name; 
}; 

int main(int argc, char *argv[]) { 
    // graph type 
    typedef boost::undirected_graph<VertexProperty> Graph; 
    // vertex descriptor type 
    typedef boost::graph_traits<Graph>::vertex_descriptor Vertex; 

    // create the graph 
    Graph g; 

    // add vertices 
    Vertex v1 = boost::add_vertex(g); 
    g[v1].weight = 5; g[v1].name = "v1"; 
    Vertex v2 = boost::add_vertex(g); 
    g[v2].weight = 2; g[v2].name = "v2"; 
    Vertex v3 = boost::add_vertex(g); 
    g[v3].weight = 6; g[v3].name = "v3"; 
    // add edges 
    boost::add_edge(v1, v2, g); 
    boost::add_edge(v1, v3, g); 
    boost::add_edge(v2, v3, g); 

    // instantiate the visitor 
    auto vertex_weight = boost::get(&VertexProperty::weight, g); 
    std::set<Vertex> max_clique; 
    Weight max_weight; 
    max_weighted_clique<decltype(vertex_weight)> visitor(vertex_weight, max_clique, max_weight); 

    // use the Bron-Kerbosch algorithm to find all cliques 
    boost::bron_kerbosch_all_cliques(g, visitor); 

    // now max_clique holds a set with the max clique vertices and max_weight holds its weight 

    auto vertex_name = boost::get(&VertexProperty::name, g); 
    std::cout << "Max. clique vertices:" << std::endl; 
    for (auto it = max_clique.begin(); it != max_clique.end(); ++it) { 
     std::cout << "\t" << vertex_name[*it] << std::endl; 
    } 
    std::cout << "Max. clique weight = " << max_weight << std::endl; 

    return 0; 
} 

이 코드가 더 잘 수행한다면 모르거나하지 않습니다 당신의 목적을 위해, 당신은 이런 식으로 뭔가를 (이 코드는 컴파일 부스트 1.55.0와 g ++ 4.8.2 플래그 -std=c++11를 사용하여 작동) 할 수 Cliquer보다 나쁘지 만 (큰 그래프에서 많은 수의 파벌을 찾지는 못했지만) 시도해 보시라. (당신의 결론을 나눌 수있다. :)

도 있지만 불행히도 보이지 않는다. (심지어 "숨겨진"것도 아닌) 도발사 검색 알고리즘을 구현할 수 있습니다.

나는 또한 MaxCliquePara이라는 최대 파벌을 찾는 알고리즘의 병렬 구현에 부딪혔다. 필자는 그것을 사용하지 않았기 때문에 사용의 편의성이나 성능에 관해서는 이야기 할 수 없지만, 좋아 보인다. 그러나이 구현에서는 정점 수가 최대 인 클레 크를 검색합니다. 이는 사용자가 원하는 코드를 조정할 수는 있지만 그래도 원하는 것은 아닙니다.

편집 :

그것은 quickbook sources of the library에서 BGL bron_kerbosch_all_cliques()에 대한 몇 가지 문서가 존재하는 것 같다. 문서 생성기이지만 상당히 읽기 쉽습니다. 그래서 그게 있습니다.