グラフ

#include <utility>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS> Graph;
typedef std::pair<int, int> Edge;

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

int main()
{
    const std::vector<Edge> edges = {
        {A, B}, {A, C}, {A, D},
        {B, E}, {C, E}, {D, E}
    };

    const Graph g(edges.begin(), edges.end(), N);

    boost::print_graph(g, name.c_str());
}

#include <utility>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS> Graph;
typedef std::pair<int, int> Edge;

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

int main()
{
    Graph g;

    // 頂点を追加
    std::map<int, Graph::vertex_descriptor> desc;
    for (int i = 0; i < N; ++i) {
        desc[i] = add_vertex(g);
    }

    // 辺を追加
    add_edge(desc[A], desc[B], g);
    add_edge(desc[A], desc[C], g);
    add_edge(desc[A], desc[D], g);
    add_edge(desc[B], desc[E], g);
    add_edge(desc[C], desc[E], g);
    add_edge(desc[D], desc[E], g);

    boost::print_graph(g, name.c_str());
}

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

struct City {
    std::string name;
    int population;
    std::vector<int> zipcodes;
};

struct Highway {
    std::string name;
    double distance; // km
};

struct Country {
    std::string name;
};

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    City,    // 頂点のBundleプロパティ
    Highway, // 辺のBundleプロパティ
    Country  // グラフのBundleプロパティ
> Map;

int main()
{
    Map map;

    // グラフのBundleプロパティを設定
    map[boost::graph_bundle].name = "Japan";

    // 街(頂点)を2つ追加
    Map::vertex_descriptor v1 = add_vertex(map);
    Map::vertex_descriptor v2 = add_vertex(map);

    // 頂点のBundleプロパティを設定
    map[v1].name = "Tokyo";
    map[v1].population = 13221169;
    map[v1].zipcodes.push_back(1500013);

    map[v2].name = "Nagoya";
    map[v2].population = 2267048;
    map[v2].zipcodes.push_back(4600006);

    // 辺を追加
    bool inserted = false;
    Map::edge_descriptor e;
    boost::tie(e, inserted) = add_edge(v1, v2, map);

    // 辺のBundleプロパティを設定
    map[e].name = "Tomei Expessway";
    map[e].distance = 325.5;

    // Highwayクラスのdistanceメンバを辺の重みとして計算
    std::vector<double> distance(boost::num_vertices(map));
    boost::dijkstra_shortest_paths(map, v1,
            boost::weight_map(boost::get(&Highway::distance, map)).
            distance_map(&distance[0]));

    std::cout << "Tokyo-Nagoya : " << distance[v2] << "km" << std::endl;
}

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

struct City {
    std::string name;
    int population;
    std::vector<int> zipcodes;
};

struct Highway {
    std::string name;
    double distance; // km
};

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    City,    // 頂点のBundleプロパティ
    Highway // 辺のBundleプロパティ
> Map;

int main()
{
    Map map;

    // 街(頂点)を2つ追加
    Map::vertex_descriptor v1 = add_vertex(map);
    Map::vertex_descriptor v2 = add_vertex(map);

    // 頂点のBundleプロパティを設定
    map[v1].name = "Tokyo";
    map[v1].population = 13221169;
    map[v1].zipcodes.push_back(1500013);

    map[v2].name = "Nagoya";
    map[v2].population = 2267048;
    map[v2].zipcodes.push_back(4600006);

    // 辺を追加
    bool inserted = false;
    Map::edge_descriptor e;
    boost::tie(e, inserted) = add_edge(v1, v2, map);

    // 辺のBundleプロパティを設定
    map[e].name = "Tomei Expessway";
    map[e].distance = 325.5;

    // 頂点を列挙
    // vertices()関数は、グラフオブジェクトを引数にとり、
    // 頂点リストのイテレータ範囲としてstd::pair<Iterator, Iterator>型を返す。
    std::cout << "vertices :" << std::endl;
    auto vertex_range = vertices(map);
    for (auto first = vertex_range.first, last = vertex_range.second; first != last; ++first) {
        Map::vertex_descriptor v = *first;
        std::cout << "  " << map[v].name << std::endl;
    }

    // 辺を列挙
    // edges()関数は、グラフオブジェクトを引数にとり、
    // 辺リストのイテレータ範囲としてstd::pair<Iterator, Iterator>型を返す。
    std::cout << "edges :" << std::endl;
    auto edge_range = edges(map);
    for (auto first = edge_range.first, last = edge_range.second; first != last; ++first) {
        Map::edge_descriptor e = *first;
        std::cout << "  " << map[e].name << std::endl;
    }
}

#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/assign/list_of.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
    boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;
typedef std::pair<int, int>                             Edge;
typedef boost::graph_traits<Graph>::vertex_descriptor   Vertex;

enum { S, A, B, C, D, E, F, Z, N };
const std::string Names = "SABCDEFZ";

// グラフを作る
Graph make_graph()
{
    const std::vector<Edge> edges = boost::assign::list_of<Edge>
        (S, A)
        (A, B)
        (B, C)
        (B, D)
        (C, E)
        (C, F)
        (D, F)
        (E, D)
        (F, E)
        (E, Z)
        (F, Z)
    ;

    const std::vector<int> weights = boost::assign::list_of
        (3)
        (1)
        (2)
        (3)
        (7)
        (12)
        (2)
        (11)
        (3)
        (2)
        (2)
    ;

    return Graph(edges.begin(), edges.end(), weights.begin(), N);
}

int main()
{
    const Graph g = make_graph();
    const Vertex from = S; // 開始地点
    const Vertex to = Z; // 目的地

    // 最短経路を計算
    std::vector<Vertex> parents(boost::num_vertices(g));
    boost::dijkstra_shortest_paths(g, from,
                boost::predecessor_map(&parents[0]));

    // 経路なし
    if (parents[to] == to) {
        std::cout << "no path" << std::endl;
        return 1;
    }

    // 最短経路の頂点リストを作成
    std::deque<Vertex> route;
    for (Vertex v = to; v != from; v = parents[v]) {
        route.push_front(v);
    }
    route.push_front(from);

    // 最短経路を出力
    for (const Vertex v : route) {
        std::cout << Names[v] << std::endl;
    }
}

#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/assign/list_of.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
    boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;
typedef std::pair<int, int>                             Edge;
typedef boost::graph_traits<Graph>::vertex_descriptor   Vertex;

enum { S, A, B, C, D, E, F, Z, N };
const std::string Names = "SABCDEFZ";

// グラフを作る
Graph make_graph()
{
    const std::vector<Edge> edges = boost::assign::list_of<Edge>
        (S, A)
        (A, B)
        (B, C)
        (B, D)
        (C, E)
        (C, F)
        (D, F)
        (E, D)
        (F, E)
        (E, Z)
        (F, Z)
    ;

    const std::vector<int> weights = boost::assign::list_of
        (3)
        (1)
        (2)
        (3)
        (7)
        (12)
        (2)
        (11)
        (3)
        (2)
        (2)
    ;

    return Graph(edges.begin(), edges.end(), weights.begin(), N);
}

int main()
{
    const Graph g = make_graph();
    const Vertex from = S; // 開始地点
    const Vertex to = Z; // 目的地

    std::vector<Vertex> parents(boost::num_vertices(g));
    std::vector<std::size_t> distance(boost::num_vertices(g));

    // 最短経路を計算
    boost::dijkstra_shortest_paths(g, from,
                boost::predecessor_map(&parents[0]).distance_map(&distance[0]));

    // 経路なし
    if (parents[to] == to) {
        std::cout << "no path" << std::endl;
        return 1;
    }

    // 最短経路の頂点リストを作成
    std::deque<Vertex> route;
    for (Vertex v = to; v != from; v = parents[v]) {
        route.push_front(v);
    }
    route.push_front(from);

    // 経路の長さを計算
    const std::size_t n = distance[to];
    std::cout << "route length:" << n << std::endl;

    // 最短経路を出力
    for (const Vertex v : route) {
        std::cout << Names[v] << std::endl;
    }
}

#include <iostream>
#include <cassert>

#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/assign/list_of.hpp>

#include <boost/detail/lightweight_test.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> Graph;
typedef std::pair<int, int> Edge;

enum { A, B, C, D, E, N };
const int vertex_count = N;

int main()
{
    const std::vector<Edge> edges = boost::assign::list_of<Edge>
        (A, B)(B, E)
        (A, C)(C, E)
    ; // Dはどこにも繋がっていない

    const Graph g(edges.begin(), edges.end(), vertex_count);

    // 全部白のカラーマップを作って渡す
    std::vector<boost::default_color_type> color(vertex_count, boost::white_color);

    // AからEに到達可能か調べる
    if (boost::is_reachable(A, E, g, color.data())) {
        std::cout << "AからEに到達可能" << std::endl;
    }
    else {
        assert(false);
    }

    // AからDに到達可能か調べる
    if (!boost::is_reachable(A, D, g, color.data())) {
        std::cout << "AからDに到達不可能" << std::endl;
    }
    else {
        assert(false);
    }
}

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

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
    boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;
typedef std::pair<int, int>                             Edge;
typedef boost::graph_traits<Graph>::vertex_descriptor   Vertex;

enum { S, A, B, C, D, E, F, G, Z, N };
const std::string Names = "SABCDEFGZ";

// グラフを作る
Graph make_graph()
{
    const std::vector<Edge> edges = {
        {S, A},
        {A, B},
        {B, C},
        {B, D},
        {C, E},
        {D, G},
        {E, D},
        {G, E},
        {E, F},
        {F, Z},
        {G, Z},
    };

    // 辺の重みは1
    const std::vector<int> weights(edges.size(), 1);

    return Graph(edges.begin(), edges.end(), weights.begin(), N);
}

int main()
{
    const Graph g = make_graph();
    const Vertex from = S; // 開始地点
    const Vertex to = Z; // 目的地

    // 最短経路を計算
    std::vector<Vertex> parents(boost::num_vertices(g));
    boost::dijkstra_shortest_paths(g, from,
                boost::predecessor_map(&parents[0]));

    // 経路なし
    if (parents[to] == to) {
        std::cout << "no path" << std::endl;
        return 1;
    }

    // 最短経路の頂点リストを作成
    std::deque<Vertex> route;
    for (Vertex v = to; v != from; v = parents[v]) {
        route.push_front(v);
    }
    route.push_front(from);

    // 最短経路を出力
    for (const Vertex v : route) {
        std::cout << Names[v] << std::endl;
    }
}

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

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> Graph;
const int vertex_count = 12;

Graph make_graph1()
{
    const std::vector<std::pair<int, int>> edges = {
        { 0,  1}, { 1, 2},
        { 0,  2},
        { 3,  4}, { 4, 5},
        { 5,  6}, { 6, 3},
        { 7,  8}, { 8, 9},
        { 9, 10},
        {10, 11}, {11, 7}
    };
    return Graph(edges.begin(), edges.end(), vertex_count);
}

Graph make_graph2()
{
    const std::vector<std::pair<int, int>> edges = {
        { 9, 10}, {10, 11},
        {11,  9},
        { 0,  1}, { 1,  3},
        { 3,  2}, { 2,  0},
        { 4,  5}, { 5,  7},
        { 7,  8},
        { 8,  6}, { 6,  4}
    };
    return Graph(edges.begin(), edges.end(), vertex_count);
}

int main()
{
    const Graph g1 = make_graph1();
    const Graph g2 = make_graph2();

    const bool result = boost::isomorphism(g1, g2);
    std::cout << "isomorphic? " << std::boolalpha << result << std::endl;
}

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
    boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;
typedef std::pair<int, int> Edge;
typedef boost::graph_traits<Graph>::edge_descriptor EdgeDesc;

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

Graph make_graph()
{
    const std::vector<Edge> edges = {
        {A, C},
        {B, D},
        {B, E},
        {C, B},
        {C, D},
        {D, E},
        {E, A}
    };

    const std::vector<int> weights = {
        1,
        1,
        2,
        7,
        3,
        1,
        1
    };
    return Graph(edges.begin(), edges.end(), weights.begin(), N);
}

int main()
{
    const Graph g = make_graph();

    std::vector<EdgeDesc> spanning_tree;
    boost::kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));

    for (const EdgeDesc& e : spanning_tree) {
        std::cout << "(" << Name[boost::source(e, g)] << ","
                         << Name[boost::target(e, g)] << ")" << std::endl;
    }
}

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
    boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;
typedef std::pair<int, int> Edge;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDesc;

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

Graph make_graph()
{
    const std::vector<Edge> edges = {
        {A, C},
        {B, D},
        {B, E},
        {C, B},
        {C, D},
        {D, E},
        {E, A},
    }

    const std::vector<int> weights = {
        1,
        1,
        2,
        7,
        3,
        1,
        1,
    };
    return Graph(edges.begin(), edges.end(), weights.begin(), N);
}

int main()
{
    Graph g = make_graph();

    std::vector<VertexDesc> parents(N);
    boost::prim_minimum_spanning_tree(g, &parents[0]);

    for (std::size_t i = 0; i < N; ++i) {
        if (parents[i] != i) {
            std::cout << "parent[" << Name[i] << "] = " << Name[parents[i]] << std::endl;
        }
        else {
            std::cout << "parent[" << Name[i] << "] = no parent" << std::endl;
        }
    }
}

#include <iostream>
#include <vector>
#include <iterator>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/adaptor/reversed.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS> Graph;
typedef std::pair<int, int> Edge;

Graph make_graph()
{
    const std::vector<Edge> edges = {
        {0, 1}, {2, 4},
        {2, 5},
        {0, 3}, {1, 4},
        {4, 3}
    };
    return Graph(edges.begin(), edges.end(), 6);
}

int main()
{
    const Graph g = make_graph();

    std::vector<int> result;
    boost::topological_sort(g, std::back_inserter(result));

    boost::for_each(result | boost::adaptors::reversed, [](int vertex) {
        std::cout << vertex << std::endl;
    });
}

#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;
    }
}

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

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS> Graph;
typedef std::pair<int, int> Edge;

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

int main()
{
    const std::vector<Edge> edges = {
        {A, B}, {A, C}, {A, D},
        {B, E}, {C, E}, {D, E}
    };

    const Graph g(edges.begin(), edges.end(), N);

    // graphvizの形式(*.dot)で出力
    std::ofstream file("test.dot");
    boost::write_graphviz(file, g, boost::make_label_writer(name.c_str()));
}

#include <fstream>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/graph_utility.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS> Graph;

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

int main()
{
    std::ifstream file("test.dot");

    Graph g;
    boost::dynamic_properties dp(boost::ignore_other_properties);
    boost::read_graphviz(file, g, dp);

    boost::print_graph(g, name.c_str());
}