graph - 高密度大图中的最大加权团

Question

是否有任何软件或算法描述可以在具有约 17000 个加权顶点和约 75% 密度的图中找到已知顶点数的最大集团(大约)？我尝试使用 Cliquer，但它太慢了(我花了几天时间才得到结果)。

关于我的问题，以防万一 - 这是一个时间安排问题，我有 18 个时间段，每个时间段都可以由不同数量的备选方案填充。每个变量代表一个插槽的一个备选方案。因此，一个槽的所有备选方案都是互斥的，而不同槽的一些备选方案是不兼容的。如果两个替代方案兼容，则它们之间存在优势。权重代表备选方案的值(value)。

Answer 1

Boost Graph Library实际上似乎有一个集团搜索算法的实现，虽然我还没有找到它的文档。不过，你可以看看 the implementation source code of the algorithm在 this example了解它是如何使用的。为了你的目的，你可以做这样的事情(这段代码编译并使用 Boost 1.55.0 和 g++ 4.8.2 使用标志 -std=c++11):

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

我不知道这段代码的性能会比 Cliquer 更好还是更差(我没有在大图中进行过太多 clique 搜索)，但你不妨试一试(并分享你的结论:))

还有一个Parallel Boost Graph Library , 但不幸的是它似乎没有实现 clique 搜索算法(甚至不是“隐藏”算法)。

另外，我刚刚遇到了一个算法的并行实现，用于查找名为 MaxCliquePara 的最大派系。 .我没有使用过它，所以我不能谈论易用性或性能，但它看起来不错。但是，请注意此实现搜索具有最大顶点数量的派系，这并不是您要查找的内容 - 尽管您可以根据需要调整代码。

编辑:

quickbook sources of the library 中似乎存在一些关于 BGL bron_kerbosch_all_cliques() 的文档.虽然它是一个文档生成器，但它的可读性很好。就是这样。