そーすにっき

なんかいろいろのせておくばしょ

グラフのライブラリづくり(2/2 Updated)

遅い

概要

  • Dijkstra法, Bellman-Ford法, SPFA, Kruscal法, Unionfindを実装
  • Dijkstra法, Bellman-Ford法, SPFAのverify
  • Bellman-Ford法, SPFAの速度比較

モチベーション

  • いつも空で書いてたけど明らかに時間＆労力の無駄で、バグも埋めるから作ってしまおうという気持ち
  • （Dijkstra法はそもそも書いたことがなかったが解けていない問題埋めに必要だった）

verify

とりあえず

ついでにSPFAとBellman-Ford法の速度比較も
雑に1回だけ実行してtimeで計測
入力はこれを拝借しました
もちろんのことながらいずれもTLEの範囲

Bellman-Ford法

real 0m53.746s
user 0m53.704s
sys 0m0.040s

SPFA

real 0m46.151s
user 0m45.996s
sys 0m0.044s

やはりSPFAに軍配が上がった模様
むしろ上がらなかったらどうしようかと

Todo

  • Unionfind
  • フロー周り（あんまり実装しているものがないのでどうしよう）

コード（需要あるのか）

(2/2 流石に何も書いてないのは雑だなと思い）

  • edge
    • 辺データ（雑）
    • idは便利変数としてとりあえず設置 今後フローとか色々に使えるかなと
  • graph
    • add_edgeとsize()を持っただけのただのvector>
    • 2次元にしている理由は隣接リストの方が気持ちがよいから
    • size()を設置した理由はg.data.size()をg.size()と誤射するパターンが多い為（文字数も減るし）
  • dijkstra
    • バグ埋まってそう（もし見つけたら教えてください）
    • これ書く直前にspfaのqueueをpriority_queueにすればいいだけで実装できることに気づきげんなりした
  • spfa
    • みんな大好きSPFA（嘘）
    • いつもSPSP問題はこれにしていたけども、Dijkstra法じゃないとTLEする制約が厳しい問題が解けなくて困っていた…が、上記の理由によりこれからDijkstra法に逃げそう
  • bellmanford
    • みんな大好きBellman-Ford法（きっとこれは本当）
    • 負辺見つけられるよやったね！でもSPFAより遅いね！という気持ち
template<typename T>
struct edge{
    int f,t;
    T c;
    int id;
    edge(){};
    edge(int f,int t,T c,int id = 0):f(f),t(t),c(c),id(id){};
    bool operator< (const edge &s){
        return c < s.c;
    }
};

template<typename T>
struct graph{
    std::vector<std::vector<edge<T> > > data;
    graph(int v):data(v){};
    void add_edge(edge<T> &e){
        data[e.f].push_back(e);
    }
    void add_edge(int f,int t,T c){
        data[f].emplace_back(f,t,c);
    }
    size_t size(){
        return data.size();
    }
    std::vector<edge<T>> make_edges(){
        std::vector<edge<T>> r;
        for(auto &i:data)std::copy(i.begin(),i.end(),std::back_inserter(r));
        return r;
    }
};

template<typename T>
std::vector<T> dijkstra(graph<T> &g,int s){
    using state = std::pair<T,int>;
    //priority_queue
    std::priority_queue<state,std::vector<state>,std::greater<state>> q;
    q.emplace((T)0,s);
    //data init
    std::vector<T> data(g.size(),std::numeric_limits<T>::max());
    data[s] = (T)0;
    //solve
    while(!q.empty()){
        state cur = q.top();q.pop();
        T c = cur.first; int pos = cur.second;
        if(data[pos] < c)continue;
        for(auto &e : g.data[pos]){
            if(c + e.c < data[e.t]){
                data[e.t] = c + e.c;
                q.emplace(c + e.c, e.t);
            }
        }
    }
    return data;
}

template<typename T>
std::vector<T> spfa(graph<T> &g,int s){
    //queue
    std::queue<int> q;
    q.emplace(s);
    //data init
    std::vector<T> data(g.size(),std::numeric_limits<T>::max()/4);
    std::vector<bool> isq(g.size(),false);
    std::vector<int> count(g.size(),0);
    data[s] = (T)0;isq[s] = true;++count[s];
    //solve
    while(!q.empty()){
        int cur = q.front();q.pop();
        isq[cur] = false;
        for(auto &e:g.data[cur]){
            if(data[e.f] + e.c < data[e.t]){
                data[e.t] = data[e.f] + e.c;
                if(++count[e.t]>=g.size()){
                    fill(data.begin(),data.end(),std::numeric_limits<T>::min());
                    return data;
                }
                if(!isq[e.t]){
                    q.push(e.t);
                    isq[e.t] = true;
                }
            }
        }
    }
    return data;
}

template<typename T>
std::vector<T> bellmanford(graph<T> &g, int s){
    const T INF = std::numeric_limits<T>::max()/4;
    std::vector<T> data(g.size(),INF);
    data[s] = 0;
    for(int i=0;i<g.size()-1;i++){
        for(auto &v:g.data)for(auto &e:v){
            if(data[e.f]==INF)continue;
            data[e.t] = std::min(data[e.f] + e.c,data[e.t]);
        }
    }
    for(auto &v:g.data)for(auto &e:v){
        if(data[e.f]==INF)continue;        
        if(data[e.f] + e.c < data[e.t]){
            fill(data.begin(),data.end(),std::numeric_limits<T>::min());
            break;
        }
    }
    return data;
}