うまくいかないけどとりあえず残しておく。サンタの家に対するオイラー路(一筆書き)

no_good_euler_tour

#include <iostream>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>

#include <map>
#include <stdexcept>
#include <boost/foreach.hpp>
#include <boost/optional.hpp>

class no_euler_graph : public std::invalid_argument {
public:
    no_euler_graph()
        : std::invalid_argument("no euler graph") {}
};

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


template <class BidirectionalGraph>
inline boost::optional<std::size_t>
    is_euler(const BidirectionalGraph& g,
             typename boost::graph_traits<BidirectionalGraph>::vertex_descriptor s)
{
    typedef boost::graph_traits<BidirectionalGraph> traits;
    typedef typename traits::vertex_descriptor vertex_desc;
    typedef typename traits::degree_size_type degree_size_type;

    std::size_t odd = 0;
    std::size_t m = 0;
    BOOST_FOREACH (const vertex_desc& v, boost::vertices(g)) {
        const degree_size_type size = boost::degree(v, g);
        if (size % 2 == 1) ++odd;
        m += size;
    }
    m /= 2;
    if (!(odd == 0 || (odd == 2 && boost::degree(s, g) % 2 == 0)))
        return boost::none;
    return m;
}

template <class BidirectionalGraph, class Adj, class UnaryFunction>
inline void visit(const BidirectionalGraph& g,
                 Adj& adj,
                 typename boost::graph_traits<BidirectionalGraph>::vertex_descriptor s,
                 UnaryFunction f,
                 std::size_t& path_size)
{
    typedef boost::graph_traits<BidirectionalGraph> traits;
    typedef typename traits::vertex_descriptor vertex_desc;
    typedef typename traits::edge_descriptor edge_desc;

    BOOST_FOREACH (const edge_desc& e, boost::out_edges(s, g)) {
        if (adj[boost::source(e, g)][boost::target(e, g)] > 0) {
            --adj[boost::source(e, g)][boost::target(e, g)];
            --adj[boost::target(e, g)][boost::source(e, g)];
            visit(g, adj, boost::target(e, g), f, path_size);
        }
    }
    f(s);
    ++path_size;
}

template <class BidirectionalGraph, class UnaryFunction>
inline bool euler_path(const BidirectionalGraph& g,
                       typename boost::graph_traits<BidirectionalGraph>::vertex_descriptor s,
                       UnaryFunction f)
{
    boost::optional<std::size_t> m = is_euler(g, s);
    if (!m) {
        boost::throw_exception(no_euler_graph());
        return false;
    }

    typedef boost::graph_traits<BidirectionalGraph> traits;
    typedef typename traits::vertex_descriptor vertex_desc;
    typedef typename traits::edge_descriptor edge_desc;

    const std::size_t n = boost::num_vertices(g);
    std::vector<std::vector<int>> adj(n, std::vector<int>(n));
    BOOST_FOREACH (const edge_desc& e, boost::edges(g)) {
        adj[boost::source(e, g)][boost::target(e, g)] = 1;
    }

    std::size_t path_size = 0;
    visit(g, adj, s, f, path_size);

    return path_size == m.get() + 1;
}

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

    // House of Santa サンタの家 : http://ameblo.jp/masanori432/entry-10058793629.html
    // path variation :  http://www.mathematische-basteleien.de/house.html
    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::vector<vertex_desc> path;

    if (!euler_path(g, B, [&path] (vertex_desc v) { path.push_back(v); })) {
        std::cout << "euler path failed" << std::endl;
//      return 1;
    }

    for (vertex_desc v : path) {
        std::cout << name[v] << std::endl;
    }
}
/*
D
C
E
D
E
B
A
C
B

*/