マトロイドクラスのインターフェースの説明
(combinatorial_opt/matroids/matroid_example.hpp)

• View this file on GitHub
• Last update: 2021-09-05 18:41:59+09:00
• Include: #include "combinatorial_opt/matroids/matroid_example.hpp"

本リポジトリで一般的なマトロイドに対して適用されるアルゴリズムは，以下のようなメソッドを持つマトロイドクラスを前提に動作する．

• int size() const 台集合の要素数を返す関数．
• template <class State = std::vector<bool>> void set(const State &I); 現在の部分集合を独立集合 $I$ で更新する．
• std::vector<Element> circuit(Element e) const; （$I$ が独立で）$I + e$ が従属集合である場合，サーキットを返す． $I + e$ も独立の場合，空ベクトルを返す．マトロイド交差アルゴリズムなど，体感的にはサーキットクエリの重さが時間計算量にダイレクトに影響するため，set() による前処理と circuit() による取得の両者の効率化が重要である．

Code

#pragma once
#include <vector>

struct MatroidExample {
    using Element = int;

    int size() const; // # of elements of set we consider

    // If I is NOT independent or e \in I, undefined.
    // If I is independent and I + {e} is not, return elements of the circuit.
    // If I + {e} is also independent, return empty vector.
    template <class State = std::vector<bool>> void set(State I);
    std::vector<Element> circuit(Element e) const;
};

#line 2 "combinatorial_opt/matroids/matroid_example.hpp"
#include <vector>

struct MatroidExample {
    using Element = int;

    int size() const; // # of elements of set we consider

    // If I is NOT independent or e \in I, undefined.
    // If I is independent and I + {e} is not, return elements of the circuit.
    // If I + {e} is also independent, return empty vector.
    template <class State = std::vector<bool>> void set(State I);
    std::vector<Element> circuit(Element e) const;
};

Back to top page