メモ帳

メモ帳です.

Qiita に移行します

Qiita

今後は技術的なネタを書く際は Qiita に投稿しようと思います.

qiita.com

読んだ論文の内容をメモしたりする場合は引き続き Hatena Blog を利用すると思います.
Hatena Blog はブログ感覚で不定期に更新できればと思っています.

C++ から MySQL のデータベースに接続する

MySQL

MySQLオープンソースで公開されている RDBMS の1つです.色々なアプリケーションで用いられていますが,C++ のプログラムから MySQL に接続する方法を紹介する記事が少なかったので,実際にソースコードを示しながらまとめたいと思います.
C++ のプログラムからデータベースを操作するには Connector/C++ を用います.
下記のリンクからダウンロード可能です.

MySQL :: Download Connector/C++

実行環境は Mac OS X (10.11) ですが,おそらく Linux でも同様に実行可能だと思います.
C++C++11 を使用しています.

また,MySQL と Connector/C++ のインストールや SQL 構文の詳細については省略します.

Connector/C++

例として基本的な操作を行うプログラムのソースコードを添付します.

以下のテーブルを作成し, SELECT 文でデータを取得したデータを出力しています.

+------+--------+
| cid  | name   |
+------+--------+
|    1 | SIGMOD |
|    2 | VLDB   |
|    3 | ICDE   |
|    4 | KDD    |
+------+--------+

プログラムは次の通りです.

gist.github.com

実行結果は以下の通りになります.

conference table created.
0   cid = 1, name = 'SIGMOD'
1   cid = 2, name = 'VLDB'
2   cid = 3, name = 'ICDE'
3   cid = 4, name = 'KDD'

データベースとの接続は sql::mysql::MySQL_Driver クラスから生成した sql::Connection インスタンスで行います(20, 21 行).

SQL による問い合わせを実行するには sql::Statement を使用します(22 行).

データの追加(INSERT など)のように結果を返さない問い合わせは stmt->execute() で実行します(25~33 行).

一方,データの取得(SELECT など)のように結果を返す問い合わせは stmt->executeQuery() で実行し,結果は sql::ResultSet で受け取ります(35 行).

sql::ResultSet によってデータを取得すると,iterator を通じて各 row に対して操作を行うことができます(38~45 行).

res->getInt(column_num) は,column_num 列目の int 型の要素を取得します(index は 1 から開始).

res->getString(column_name) は,列名が column_name である string 型の要素を取得します.

まとめ

Connector/C++ を用いて MySQL のデータベースに接続しました.
基本的に sql::Statement の execute() か executeQuery() を用いて SQL の問い合わせを行います.

非常に簡易な説明なのでわかりにくいかと思いますが,詳しくは Document を読んでいただけたらと思います.

MySQL :: MySQL Connector/C++ Developer Guide :: 7 Getting Started with Connector/C++: Usage Examples

追記(2016/10/14)

本記事の内容をより詳しくまとめて Qiita に投稿しました.

qiita.com

ぜひこの記事についても参照してみてください.

Boost Graph Library の Compressed Sparse Row を使う

Compressed Sparse Row (CSR)

CSR は疎なグラフの効率的な表現方法である.adjacency_list といった他のフォーマットよりもオーバヘッドが小さいという特徴がある.

BGL にも CSR 方式に基づいたクラスが用意されているが,adjacency_list と使い方が大きく異なる.
adjacency_list は頂点や辺の追加や削除が自由に行えるが,compressed_sparse_row_grpah は一度初期化してしまうと辺の追加や削除ができない.
したがって,動的なグラフには向いていないため,基本的には静的なグラフに用いる.

サンプルコード

compressed_sparse_row_graph クラスを用いたサンプルコードを作成した.

gist.github.com

あらかじめ作成した vector によって初期化している.

adjacency_list のような add_edge() や add_vertex() が実装されていないが,vertex_iterator や edge_iterator によるグラフの走査は同様に実行可能である.

実行結果

A --> B, D, F,
B --> C, D,
C --> D, A,
D --> A,
E --> B, C, D,
F --> E,

まとめ

BGL の compressed_sparse_row_graph クラスを用いてグラフを表現した.
一度初期化してしまうと頂点や辺の追加や削除を行うことができない.
adjacency_list と同様に iterator が用意されているため,頂点や辺の走査が可能である.

Boost Graph Libraryのグラフから疎行列を生成

疎行列

非零要素数がn2(nはグラフのノード数)よりも著しく少ない行列を疎行列という.要するに,ほとんどの要素が0である行列を指す.
グラフの隣接行列はたいてい疎行列となる.

n×n行列はn2個の記憶領域を必要とするが,疎行列は非零要素の値と座標のみを記憶すれば良いため,空間効率的に格納できる.

疎行列を扱うライブラリとして,Eigenを用いた.

Eigen

EigenにはSparseMatrixというクラスが用意されているため,自分で実装する必要がない.

brewでインストールしたが,その他の方法は調査していない.

brew install eigen

使用例

次のグラフの疎行列を生成する.グラフの生成はBGLで行った.

f:id:tomov3:20160623173546p:plain

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <eigen3/Eigen/Sparse>

using namespace std;

typedef boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::bidirectionalS
    > graph;

int main()
{
    graph g;

    add_edge(0, 1, g);
    add_edge(0, 2, g);
    add_edge(1, 4, g);
    add_edge(2, 3, g);
    add_edge(3, 0, g);
    add_edge(4, 3, g);

    int num = num_vertices(g);

    Eigen::SparseMatrix<double> matrix(num, num);

    int from, to;
    for (auto i=vertices(g); i.first!=i.second; i.first++) {
        from = *i.first;
        for (auto j=inv_adjacent_vertices(*i.first, g); j.first!=j.second; j.first++) {
            to = *j.first;
            matrix.insert(from, to) = 1.0;
        }
    }

    cout << matrix << endl;
}

グラフのノードの走査の部分(for文)が少しややこしいが,疎行列の生成は

Eigen::SparseMatrix<double> matrix(num, num);

要素の代入は

matrix.insert(from, to) = 1.0;

といったように,簡単に行うことができる.生成時には0に初期化されている.

実行結果

Nonzero entries:
(1,1) (1,2) (1,4) (_,_) (1,3) (_,_) (1,0) (_,_) (1,3) (_,_)

Outer pointers:
0 2 4 6 8  $
Inner non zeros:
2 1 1 1 1  $

0 0 0 1 0
1 0 0 0 0
1 0 0 0 0
0 0 1 0 1
0 1 0 0 0

このプログラフでは登場していないが,要素の参照はcoeff()で行う.

value = matrix.coeff(row, column);

関数の詳細は

Eigen: SparseMatrix< _Scalar, _Options, _Index > Class Template Reference

に書いてある(詳細は省く).

まとめ

Eigenを用いることで,簡単に疎行列を扱うことができた.
Eigenは疎行列の他にもベクトルなどが定義されているため,線形代数の基本的なライブラリとして扱うことができる.

BGLでプロパティを設定する

boostjp.github.io

を参考にさせていただいた.とても分かりやすかった.

任意のプロパティの設定

BGLのグラフ構造(adjacency_listやadjacency_matrix)は,ノードやエッジのプロパティを自分で設定することができる.プロパティはstruct構造体で設定する.

//ノードのプロパティ
struct City {
    std::string name;
    int population;
    std::vector<int> zipcodes;
};

//エッジのプロパティ
struct Highway {
    std::string name;
    double distance; // km
};

//グラフのプロパティ
struct Country {
    std::string name;
};

上記はノードとエッジをそれぞれ街と道路にみたてた例である.
プロパティによって,任意のグラフを設定することができる.

使用例

上記のページのサンプルをそのまま転載させていただいた.

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

このグラフを可視化すると次のようになる (ノードのname以外のプロパティは省略した).

f:id:tomov3:20160622145955p:plain

このようにプロパティを自分で設定することで,任意のグラフを扱うことができる.
この例では,街とその間の道路を表すグラフを表現することができた.

おまけ

グラフの可視化はGraphvizを用いた.

tomov3.hatenablog.com

出力部分のコードは以下のようになる.

template <class WeightMap,class CapacityMap>
class edge_writer {
public:
  edge_writer(WeightMap w, CapacityMap c) : wm(w),cm(c) {}
  template <class Edge>
  void operator()(std::ostream &out, const Edge& e) const {
    out << "[label=\"" << wm[e] << "\", taillabel=\"" << cm[e] << "\"]";
  }
private:
  WeightMap wm;
  CapacityMap cm;
};

template <class WeightMap, class CapacityMap>
inline edge_writer<WeightMap,CapacityMap> 
make_edge_writer(WeightMap w,CapacityMap c) {
  return edge_writer<WeightMap,CapacityMap>(w,c);
}

std::ofstream file("test.dot");
boost::write_graphviz( file, map, boost::make_label_writer( boost::get(&City::name, map) ),
    make_edge_writer( boost::get(&Highway::distance, map), boost::get(&Highway::name, map) ) );

このコードは

c++ - How to print a graph in graphviz with multiple properties displayed - Stack Overflow

の記事を参考にした(make_edge_writer()の部分).