あめだまふぁくとりー

Boost.Graphとかできますん

第一回 グラフ王 決定戦

BGL C++

dijkstra_shortest_paths での比較

Stanford GraphBase と boost::adjacency_list, boost::vector_as_graph を利用した std::vector によるグラフで boost::dijkstra_shortest_paths の実行時間を 適当に 比較してみました. boost::adjacency_list は節点と枝を保持するデータ構造に選択肢が複数あるので, vecS と listS の4通りの組み合わせで計測しました．

以下が計測結果です. 単位はナノ秒, 試行回数は100,000回です. 最適化オプションはO3です. また，計測に使用したグラフは Stanford GraphBase のページ にある knight3.gb を使用しました．

Average:
  SGB:              5209.81
  v=vecS,e=vecS:    3698.48
  v=vecS,e=listS:   4141.79
  v=listS,e=vecS::  6560.22
  v=listS,e=listS:  6675.47
  vector:           3560.44
Max:
  SGB:              64000
  v=vecS,e=vecS:    76000
  v=vecS,e=listS:   115000
  v=listS,e=vecS::  40000
  v=listS,e=listS:  20000
  vector:           18000
Min:
  SGB:              4000
  v=vecS,e=vecS:    3000
  v=vecS,e=listS:   3000
  v=listS,e=vecS::  6000
  v=listS,e=listS:  6000
  vector:           3000

平均値を見てみると, 節点に vecS を指定した boost::adjacency_list はなかなか良い結果を出しています.

また, std::vector<list<size_t>> で表される vector グラフも同等の良い結果が出ています. 専用のグラフクラスを定義しなくても std::vector で大抵は事足りると考えられます. ちなみに, vector グラフの枝の重みのプロパティマップには std::unorderd_map を使用しました.

C 言語実装である SGB(Stanford GraphBase) はこれらより少し遅い結果になりました.

そして最後に, 節点に listS を指定した boost::adjacency_list が最も遅いという結果に今回はなりました. dijkstra_shortest_paths は開始時に節点を総なめしているので, それをしない dijkstra_shortest_paths_no_color_map を使用すると結果は変わってくるかもしれません.

最大値に関しては測定するごとにかなりばらつきがあるので何とも言えません.

計測用のコード

#include <array>
#include <chrono>
#include <iostream>
#include <unordered_map>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/algorithm/max_element.hpp>
#include <boost/range/algorithm/min_element.hpp>
#include <boost/range/numeric.hpp>
#include <boost/graph/stanford_graph.hpp>
#undef ap
#undef upi
#undef abbr
#undef nickname
#undef conference
#undef HOME
#undef NEUTRAL
#undef AWAY
#undef venue
#undef date
#include <boost/functional/hash/hash.hpp>
#include <boost/graph/vector_as_graph.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/copy.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>

int main()
{
    using namespace boost;
    sgb_graph_ptr sgb_graph = restore_graph(const_cast<char*>("knight3.gb"));

    using result_type = std::array<uint64_t, 100000>;
    {
        dijkstra_shortest_paths(sgb_graph, *vertices(sgb_graph).first
                , weight_map(get(edge_length_t{}, sgb_graph))
                . distance_inf(std::numeric_limits<long>::max()));
    }
    auto sgb_result = result_type{};
    for (auto& result : sgb_result)
    {
        auto const start = std::chrono::system_clock::now();
        dijkstra_shortest_paths(sgb_graph, *vertices(sgb_graph).first
                , weight_map(get(edge_length_t{}, sgb_graph))
                . distance_inf(std::numeric_limits<long>::max()));
        auto const end = std::chrono::system_clock::now();
        result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
    }

    auto vecSvecS_result = result_type{};
    {
        using BoostGraph = adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, long>>;
        auto boost_graph = BoostGraph{};
        copy_graph(sgb_graph, boost_graph
                , vertex_copy([&](auto sgb_v, auto boost_v){
                })
                . edge_copy([&](auto sgb_e, auto boost_e){
                    put(edge_weight, boost_graph, boost_e, get(edge_length_t{}, sgb_graph, sgb_e));
                }));

        {
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
        }
        for (auto& result : vecSvecS_result)
        {
            auto const start = std::chrono::system_clock::now();
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
            auto const end = std::chrono::system_clock::now();
            result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    }

    auto vecSlistS_result = result_type{};
    {
        using BoostGraph = adjacency_list<listS, vecS, directedS, no_property, property<edge_weight_t, long>>;
        auto boost_graph = BoostGraph{};
        copy_graph(sgb_graph, boost_graph
                , vertex_copy([&](auto sgb_v, auto boost_v){
                })
                . edge_copy([&](auto sgb_e, auto boost_e){
                    put(edge_weight, boost_graph, boost_e, get(edge_length_t{}, sgb_graph, sgb_e));
                }));

        {
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
        }
        for (auto& result : vecSlistS_result)
        {
            auto const start = std::chrono::system_clock::now();
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
            auto const end = std::chrono::system_clock::now();
            result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    }

    auto listSvecS_result = result_type{};
    {
        using BoostGraph = adjacency_list<vecS, listS, directedS, property<vertex_index_t, size_t>, property<edge_weight_t, long>>;
        auto boost_graph = BoostGraph{};
        copy_graph(sgb_graph, boost_graph
                , vertex_copy([&](auto sgb_v, auto boost_v){
                    put(vertex_index, boost_graph, boost_v, get(get(vertex_index, sgb_graph), sgb_v));
                })
                . edge_copy([&](auto sgb_e, auto boost_e){
                    put(edge_weight, boost_graph, boost_e, get(edge_length_t{}, sgb_graph, sgb_e));
                }));

        {
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
        }
        for (auto& result : listSvecS_result)
        {
            auto const start = std::chrono::system_clock::now();
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
            auto const end = std::chrono::system_clock::now();
            result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    }

    auto listSlistS_result = result_type{};
    {
        using BoostGraph = adjacency_list<listS, listS, directedS, property<vertex_index_t, size_t>, property<edge_weight_t, long>>;
        auto boost_graph = BoostGraph{};
        copy_graph(sgb_graph, boost_graph
                , vertex_copy([&](auto sgb_v, auto boost_v){
                    put(vertex_index, boost_graph, boost_v, get(get(vertex_index, sgb_graph), sgb_v));
                })
                . edge_copy([&](auto sgb_e, auto boost_e){
                    put(edge_weight, boost_graph, boost_e, get(edge_length_t{}, sgb_graph, sgb_e));
                }));

        {
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
        }
        for (auto& result : listSlistS_result)
        {
            auto const start = std::chrono::system_clock::now();
            dijkstra_shortest_paths(boost_graph, *vertices(boost_graph).first
                    , weight_map(get(edge_weight_t{}, boost_graph))
                    . distance_inf(std::numeric_limits<long>::max()));
            auto const end = std::chrono::system_clock::now();
            result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    }

    auto vector_result = result_type{};
    {
        using VectorGraph = std::vector<std::list<size_t>>;
        auto vector_graph = VectorGraph{};
        using edge_descriptor = graph_traits<VectorGraph>::edge_descriptor;
        auto wmap = std::unordered_map<edge_descriptor, long, boost::hash<edge_descriptor>>{};
        copy_graph(sgb_graph, vector_graph
                , vertex_copy([&](auto, auto){
                })
                . edge_copy([&](auto sgb_e, auto& vector_e){
                    wmap[vector_e] = get(edge_length_t{}, sgb_graph, sgb_e);
                }));
        {
            dijkstra_shortest_paths(vector_graph, *vertices(vector_graph).first
                    , weight_map(make_assoc_property_map(wmap))
                    . distance_inf(std::numeric_limits<long>::max()));
        }
        for (auto& result : vector_result)
        {
            auto const start = std::chrono::system_clock::now();
            dijkstra_shortest_paths(vector_graph, *vertices(vector_graph).first
                    , weight_map(make_assoc_property_map(wmap))
                    . distance_inf(std::numeric_limits<long>::max()));
            auto const end = std::chrono::system_clock::now();
            result = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    }


    std::cout << "Average:" << std::endl;
    std::cout << "  SGB:              " << accumulate(sgb_result, 0.0) / sgb_result.size() << std::endl;
    std::cout << "  v=vecS,e=vecS:    " << accumulate(vecSvecS_result, 0.0) / vecSvecS_result.size() << std::endl;
    std::cout << "  v=vecS,e=listS:   " << accumulate(vecSlistS_result, 0.0) / vecSlistS_result.size() << std::endl;
    std::cout << "  v=listS,e=vecS::  " << accumulate(listSvecS_result, 0.0) / listSvecS_result.size() << std::endl;
    std::cout << "  v=listS,e=listS:  " << accumulate(listSlistS_result, 0.0) / listSlistS_result.size() << std::endl;
    std::cout << "  vector:           " << accumulate(vector_result, 0.0) / vector_result.size() << std::endl;
    std::cout << "Max:" << std::endl;
    std::cout << "  SGB:              " << *max_element(sgb_result) << std::endl;
    std::cout << "  v=vecS,e=vecS:    " << *max_element(vecSvecS_result) << std::endl;
    std::cout << "  v=vecS,e=listS:   " << *max_element(vecSlistS_result) << std::endl;
    std::cout << "  v=listS,e=vecS::  " << *max_element(listSvecS_result) << std::endl;
    std::cout << "  v=listS,e=listS:  " << *max_element(listSlistS_result) << std::endl;
    std::cout << "  vector:           " << *max_element(vector_result) << std::endl;
    std::cout << "Min:" << std::endl;
    std::cout << "  SGB:              " << *min_element(sgb_result) << std::endl;
    std::cout << "  v=vecS,e=vecS:    " << *min_element(vecSvecS_result) << std::endl;
    std::cout << "  v=vecS,e=listS:   " << *min_element(vecSlistS_result) << std::endl;
    std::cout << "  v=listS,e=vecS::  " << *min_element(listSvecS_result) << std::endl;
    std::cout << "  v=listS,e=listS:  " << *min_element(listSlistS_result) << std::endl;
    std::cout << "  vector:           " << *min_element(vector_result) << std::endl;
}