疎行列の計算を実装してグラフ理論をかじってみる

経路の道順を求める

　もいっちょいくよー。お次は隣接行列の各成分を「橋の名前」に置き換えます。

　んでもって「文字のまま」で行列の積を計算すべく乗算・加算の定義を差し替えます。

list-7　04_walkpath\04_walkpath.cpp

#include "sparse/matrix.h"
#include "sparse/multiplies.h"
#include "sparse/fill_diagonal.h"

#include <string>

// トークンの切り出し
template<typename T>
bool tokenize(std::basic_string<T>& str, std::basic_string<T>& token, 
              const std::basic_string<T>& delim) {
  using tstring = std::basic_string<T>;
  tstring::size_type bpos = str.find_first_not_of(delim);
  if ( bpos == tstring::npos ) return false;
  tstring::size_type epos = str.find_first_of(delim, bpos);
  if ( epos == tstring::npos ) {
    token = str.substr(bpos);
    str.clear();
  } else {
    token = str.substr(bpos, epos-bpos);
    str.erase(0, epos+1);
  }
  return true;
}

// 乗算 <*>
//    0  <*>  0  = 0
//    0  <*> 'x' = 0
//   "x" <*>  0  = 0
// "a+b" <*> 'c' = "ac+bc"
struct nullable_multiplies {
  std::string* operator()(const std::string* ap, const char* bp,
                                std::string* result) const {
    if ( ap == nullptr ) return nullptr;
    if ( bp == nullptr ) return nullptr;
    result->clear();
    bool atfirst = true;
    std::string delim = "+";
    std::string token;
    std::string str = *ap;
    char ch = *bp;
    if ( str.length() == 0 ) {
      *result = ch;
    } else {
      while ( tokenize(str, token, delim) ) {
        if ( atfirst ) atfirst = false;
        else *result += delim;
        *result += token;
        *result += ch;
      }
    }
    return result;
  }
};

// 加算 <+>
//   0  <+>  0  =   0
//   0  <+> "x" =  "x"
//  "x" <+>  0  =  "x"
//  "x" <+> "y" =  "x+y"
struct nullable_plus {
  std::string* operator()(const std::string* ap, const std::string* bp, 
                                std::string* result) const {
    if ( ap == nullptr && bp == nullptr ) return nullptr;
    if ( ap == nullptr ) *result = *bp;
    else if ( bp == nullptr ) *result = *ap;
    else *result = (*ap) + "+" + (*bp);
    return result;
  }
};

#include <iostream>   // cout, endl

int main() {
  using namespace sparse;

  matrix<std::string> A;
  fill_diagonal(A, 4, std::string());

  matrix<char> B;
  B.insert(0, 0, 'a');
  B.insert(0, 1, 'b');
  B.insert(0, 2, 'c');
  B.insert(1, 2, 'd');
  B.insert(2, 3, 'e');
  B.insert(3, 1, 'f');
  B.finalize();

  nullable_multiplies mulop;
  nullable_plus       addop;

  A = multiplies(A, B, 4, 4, 4, mulop, addop);
  A = multiplies(A, B, 4, 4, 4, mulop, addop);
  A = multiplies(A, B, 4, 4, 4, mulop, addop);

  A.enumerate([](int row, int col, std::string val) {
                std::cout << '[' << row << ',' << col << "] " 
                          << val << std::endl;}); 
  std::cout << std::endl;
}

　この結果は「島iから島jに到達するときに通過する橋のリスト」なんですね。"[0,2] aac+abd" は「島0から3本の橋を渡って島2に行くには、a,a,cまたはa,b,dの順に渡れ」ってことです。

　最後の例：文字式での行列積は状態遷移の検証／テストに使えますね。「ある状態からある状態へn個のイベントで遷移できるか、できるならどのイベントがどんな順序で発生すればいいか」が示されますからね。

　……ゴールデンウィークはこんなコードで遊んでました、TwitterやFacebokあるいはWebページのリンクを基に巨大なグラフを作ってこんな演算を施せば、かなり面白い結果が得られそうです。