3

~17000 の加重頂点と ~75% の密度を持つグラフで既知の頂点数を持つ最大クリークを (およそ) 見つけることができるソフトウェアまたはアルゴリズムの説明はありますか? Cliquer を使用しようとしましたが、遅すぎます (結果を得るのに数日かかりました)。

念のため、私の問題について少し-それはスケジューリングの問題です.18のタイムスロットがあり、それぞれが異なる数の選択肢で満たされる可能性があります. 各変数は、1 つのスロットの 1 つの選択肢を表します。したがって、1 つのスロットのすべての代替は相互に排他的であり、異なるスロットの一部の代替は互換性がありません。2 つの代替案に互換性がある場合、それらの間に優位性があります。重みは、代替の値を表します。

4

1 に答える 1

4

Boost Graph Libraryには、実際にはクリーク検索アルゴリズムが実装されているようですが、そのドキュメントは見つかりませんでした。ただし、アルゴリズムの実装ソース コードとこの例を見て、その使用方法を理解することができます。あなたの目的のために、次のようなことを行うことができます (このコードは、フラグを使用して 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 よりもパフォーマンスが良いか悪いかはわかりません (大きなグラフでクリーク検索を行ったことはあまりありません) が、試してみてください (そして結論を​​共有してください :) )。

Parallel Boost Graph Libraryもありますが、残念ながら、クリーク検索アルゴリズムを実装していないようです (「隠された」アルゴリズムでさえありません)。

また、 MaxCliqueParaと呼ばれる最大クリークを見つけるアルゴリズムの並列実装にぶつかりました。使用していないので使い勝手や性能はなんとも言えませんが、良さそうです。ただし、この実装では最大数の頂点を持つクリークが検索されることに注意してください。これは、まさに探しているものではありません。ただし、必要に応じてコードを微調整することはできます。

編集：

ライブラリのクイックブック ソースにbron_kerbosch_all_cliques()、BGL に関するドキュメントがいくつかあるようです。これはドキュメント ジェネレーターですが、かなり読みやすいです。それで、それがあります。

于 2014-04-26T12:17:59.940 に答える