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

Question

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

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

Answer 1

Boost Graph Library实际上似乎有一个集团搜索算法的实现，尽管我还没有找到它的文档。但是，您可以查看算法的实现源代码并在此示例中了解它的使用方式。出于您的目的，您可以执行以下操作（此代码使用 flag 编译并与 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，但不幸的是它似乎没有实现集团搜索算法（甚至不是“隐藏”算法）。

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

编辑：

bron_kerbosch_all_cliques()图书馆的quickbook 资源中似乎存在一些关于 BGL 的文档。虽然它是一个文档生成器，但它的可读性很强。所以就是这样。