Boost.Graph 一筆書き - Faith and Brave

オイラー閉路というのを求めると、グラフの一筆書きの経路を得ることができます。
Boost.Graphにはオイラー閉路のためのアルゴリズムは用意されていないので、以下のページを参考にBoost.Graphベースで書いてみました。

今回一筆書きするのは、「サンタクロースの家」と呼ばれるグラフです。

サンタクロースの家を一筆書きするコード：

#include <iostream>
#include <deque>
#include <string>
#include <shand/graph/euler_path.hpp>
#include <boost/graph/adjacency_list.hpp>

enum {A, B, C, D, E, N};
const std::string name = "ABCDE";

int main()
{
    typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> Graph;
    typedef boost::graph_traits<Graph>::vertex_descriptor vertex_desc;

    const std::vector<std::pair<int, int> > edges = {
        {A, B},
        {B, C},
        {C, A},
        {B, D},
        {B, E},
        {C, D},
        {D, E},
        {E, C}
    };

    const Graph g(edges.begin(), edges.end(), N);
    std::deque<vertex_desc> path;

    if (!shand::graph::euler_path(g, E, [&path] (vertex_desc v) { path.push_front(v); })) {
        std::cout << "euler path failed" << std::endl;
        return 1;
    }

    BOOST_FOREACH (const vertex_desc& v, path) {
        std::cout << name[v] << std::endl;
    }
}

E
B
A
C
B
D
C
E
D

E, B, A, C, B, D, C, E, Dの順に頂点をたどれば一筆書きになることがわかりました。

これで一筆書きゲームをするときにずるができますね。

euler_path()関数には、第1引数にグラフ構造の変数へのconst参照、第2引数に始点となる頂点、第3引数は発見された順番に頂点が渡される関数オブジェクトを指定します。
「サンタクロースの家」は下段の頂点を始点にしなければ解けないので、DかEを指定する必要があります。
一筆書きが存在しないグラフ／始点が指定された場合には、falseが返ります。

euler_path()関数は、私のGitHubに置いてあります：
shand/graph/euler_path.hpp
サンプルコード(santa_house.cpp)

ちなみに、euler_path()アルゴリズムは、現状では無向版しか用意していません。
有向版は用途が思いついたら実装します。

参照：
【サンタクロースのお家】という一筆書き遊びです
 House of Santa Claus