有向グラフ至上主義

個人的なアウトプットの統合管理を目的としたブログです。

毎日3時間チャレンジを1か月やってみた

毎日3時間チャレンジとは

まず次のツイートをご覧ください。

このツイートの通り #毎日3時間チャレンジ のタグで2月13日から今日まで毎日最低3時間学んだり何かを作ってきました。そのチャレンジ開始から1か月がたちました。

なぜこんなチャレンジを始めたのか

そもそもこのチャレンジを始めた理由は2つあります。

1つ目は春休みの時間を無駄にしないようにしたかったからです。 実は僕は次の4月から社会人です。その為この春休み()の時期は卒業関係や引っ越しといろいろ忙しい上に環境が変わり普段利用していた施設が利用できなくなったりします。だからどうにかして時間を作らないと、「何もやらないだらけた生活になってしまいこの貴重な長期休みを無駄にしてしまうのでは?」と思ってしまいました。

2つ目は「思い立ったが吉日」ということです。 これはふと3時間チャレンジをやってみようかなと思ったときに、この言葉も一緒に思ってしまったので仕方ないですよね。

1か月続けてどうだったか

一言で言うと「毎日3時間やるのは時間を取ることにとらわれると辛くなる」ということです。というのも僕自身好きな数学やプログラミングをやるというやる気があるときには気づいたら3時間経過していたことはいくらでもありました。しかしやる気が出ないときはわざわざ読書や運動で時間をつぶしていました。手段と目的が入れ替わっていた時もありました。手段と目的を入れ替えないようにするためにも、やる気が出ないときはやる気を出す努力に力を注いだ方が良いと言えそうです。

終わりに

先述したように来月の4月から社会人になるので4月からはこのチャレンジをやる時間が取れそうにないので今月いっぱいでやめることになりますが、このチャレンジをしてよかったとは思っています。

初めてのFirefoxとブックマークの同期

Firefoxを入れた

最近Rustを書くのが楽しくなってきたので、Rustを開発し始めたMozillaのブラウザFirefoxにも手を出すことにした。 インストールするのはとても簡単で公式サイトから該当するバージョンのFirefoxをインストールしてくるだけである。

僕はもともとChromeユーザー

僕はAndroidを使っていることもあってか、カレンダーなどのアプリ間の連携のために普段はChromeを使っている。そこでChromeをやめるわけにはいかないので、今回Firefoxを入れるにあたりChromeの連携を活かした使い方をする必要が出てきた。 しかし、いろいろと調べていくとカレンダーなどはGoogleに任せても問題なさそうなことが分かった。Chromeに任せればいいからだ。 しかし、ブックマークだけはそうはいかなかった。Firefoxでも参照する必要があるからである。

ブックマークの共有問題

普通最初にブックマークをChromeからFirefoxにインポートすると思う。 しかし、僕は普段ブラウザでブックマークを頻繁にする人なのでChromeFirefoxでのブックマークの編集を毎回もう一方にインポートするのは大変面倒くさい。 そこでブックマークの情報を共有できるサービスがないか調べてみることにした。

EverSync

いろいろと調べたところ他にもいろいろあるが今回はEverSyncというのを使用することにした。EverSyncというのはFirefoxChromeIEなどのブラウザ間のブックマークを同期による共有するサービスである。利用するためにはそれぞれアドオンを入れる必要があるが、Chrome版はこちらで、Firefox版はこちらから手に入る。それら以外もここから対応するものを選べばダウンロードのところまで飛べる。 これらをそれぞれのブラウザでインストールした後ここのようにアカウントを作成してログインして、ベースとしたい方のブックマークデータをアップロードし、同期して共有する。 これで同期ができたはずなのでChromeFirefoxのブックマークをいじってもう一方が変化するか確認してみる。すると問題なく変化しているはずである。

これでブックマークの共有問題も解決できた。めでたしめでたし。

まとめ

ブックマークの設定も共有できるので皆も身軽で高速になった火狐ことFirefoxを使っていってほしいと思う。

初めてのVOICEROID

京町セイカを購入した

最近自分の数学が応用指向すぎた性で基礎がおろそかになっていたのと卒論、テスト勉強、引っ越し準備などのいろいろなストレスが重なって、自分はなんで生きているんだろうと消耗しきっていま した。なので大好きな京町セイカさんを家に呼んで癒してもらうことにしました。ついでにデジタル上の創作の世界に再び足を踏み込もうと決心しました。

f:id:ogata-k:20190202194242j:plain
京町セイカ

今後何をしようと考えているか

VOICEROIDと言ったらやっぱりニュースの読み上げやラジオ、動画ですよね。なので自分も作ろうかなと考えています。実は僕前にBlenderを使ってみたりMMDを使ってみたりしたことがあります。なのでMMD動画を作るかもしれません。また、クリスタで背景などを頑張って描いてラジオ動画などもつくれそうです。プログラミングをして自分用のニュース読み上げソフトを作ったり、ソフトの音声に利用するのも面白そうです。そのためいろいろと使い道が多そうでわくわくが止まりません。

どれを投稿するかはまだわかりませんが、投稿したらこのブログで紹介がてら裏話とかをするかもしれませんのでそのつもりで見守って頂けるとありがたいです。

GithubにPDF置き場を作りました

PDF置き場作った

このHatenaBlogで投稿した記事などをPDFにまとめるときのデータ置き場としてGithubに新しいリポジトリを作りました。作成もこのリポジトリで行っていきます。その成果物であるPDFはREADMEに適宜配置していくのでREADMEさえ見てもらえれば何があるかわかるようにしておきます。

リンクはこちらになります。

Ubuntu 18.04.1 LTS でSATySFiをインストールしてみた

qiita.com

Ubuntu 18でSATySFiのインストールに成功したのでインストールメモをQiitaで記事を書いて投稿しました。
やってるのはgfngfn/SATySFi/README-jaと全く同じです。Ubuntu 16の場合と同様です。
参考になるかはわかりませんがSATySFiのインストールの参考にしてみてください。

有向グラフの諸定義

さて早速ですが、このブログを始めた理由の一つでもある有向グラフについて説明していこうと思います。
有向グラフは離散数学グラフ理論に触れている人や情報系やプログラミングをしている人ならすでに知っていると思いますが、それ以外の人にはなかなか知られていません。知ってるかどうか聞いてみても「折れ線グラフの一種?」等と返されてしまうのが現状です。そこで有向グラフについて広める第一弾となるこの記事では有向グラフの定義と有向グラフに関する用語などを解説していきます。

そもそも有向グラフとは

そもそも有向グラフとは次の画像に見られるような頂点と呼ばれる点と点の間に、辺と呼ばれる矢印が描かれているものをいいます。

有向グラフの例1
有向グラフの例1
有向グラフの例2
有向グラフの例2
さらに辺でつながれた頂点は別ものである必要がないため、次の画像にあるような同じ頂点をさす辺が存在する有向グラフも考えることができます。これをループを持つ有向グラフと言います。
ループを持つ有向グラフの例
ループを持つ有向グラフの例
そしてグラフ理論ではまず出てきませんが、次の画像のような頂点間に複数の辺を持つ有向グラフを考えることができます。これを多重辺を持つ有向グラフと言います。
多重辺を持つ有向グラフ
多重辺を持つ有向グラフの例
このような「点と点の関係を矢印を使って表示する図」を有向グラフと言います。
有向グラフは一筆書きの問題やフローチャート構文木、ネットワーク、協調しながらの制御などなどいろいろなところに出てくるのがなんとなく想像つくかと思います。

なんとなくのイメージがわかったところで数学的に有向グラフの定義をしていきます。

いろいろな有向グラフの定義

有向グラフはいろいろなところに出て来るので多種多様な定義が存在します。そこで私が知っている次の三つの定義(i)~(iii)を紹介し、それぞれがどれだけの表現能力を持つかを解説していきます。

定義(i)

有向グラフ Gとは、集合 Vとその直積の部分集合 E \subset V \times Vの対 (V, E)のことである。そして Vの元を頂点 Eの元 (i, j) iから jへの辺(または単に)、この iのことを辺の始点 jを辺の終点と呼ぶ。

この定義は主に工学やグラフ理論に用いられる定義となります。これはこの定義では多重辺を持った有向グラフを表現できないことが効いています。工学やグラフ理論の分野ではどの頂点がつながっていればよいかを記述できればつながりを調べるのに十分であることから多重辺を必要としません。そのためこの定義の性質が効いてくるのです。
また、この定義では無向グラフという「向きを考えない(この定義の有向グラフのような)グラフ」を考えることができます。この「向きを考えない」というのは、「頂点iから頂点jへの辺が存在していればjからiの辺も存在する」ということと同値な考えであるからです。

定義(ii)

有向グラフ Gとは、集合 Vと集合 Eと2つの関数 dom, cod: E \rightarrow Vの組 (V, E, dom, cod)である。そして Vの元を頂点 Eの元 e e dom(e) e始点 cod(e) e終点と呼ぶ。

これで定義するとループも多重辺も扱うことができる為、この定義を採用する分野は例えば主に圏論やクイバー(有向グラフ)の表現論や状態遷移図などの自由度が高く簡単に複雑になる分野です。(他にもあったら教えてください。)
また、この定義では略記を使わなければ、辺を取ってきてから dom codを使って始点と終点を宣言しなければいけないという点ではデメリットになりますが、辺が始点と終点の情報を持っているという点ではメリットになっています。

定義(iii)

有向グラフ Gとは、集合 Vと任意の Vの元 i, jに対して定義される集合 E _ {i, j}からなる集合族 E = \left\{E _ {i, j}\right\} _ {i, j \in V}からなる対 (V, E)のことである。そして Vの元 i, jをそれぞれ頂点 E _ {i, j} iから j辺集合 E _ {i, j}の元 e _ {i, j} iから jへの iを辺 e _ {i, j}始点 jを辺 e _ {i, j}終点と呼ぶ。

この定義は表現能力的には(ii)と同じで、ループも多重辺も扱うことができます。その為同じ分野領域で用いられています。この定義で E _ {i, j} E(i, j)と書くと圏論で頻繁に見る形式になるのでこちらの定義の方がなじみ深い人がいると思います。
また、この定義では略記を使わなければ、始点と終点の情報を保持しているのは辺ではなく辺集合という点ではデメリットですが、同じ始点と終点をもつ辺の集合が定義で与えられていて考えやすいという点ではメリットとなります。

これらの定義は表現能力的には(i)⇒(ii)⇔(iii)という関係(これも有向グラフ!!)があります。今後私のブログでは記事の最初に断りが無ければ(ii)の定義で考えていることにします。

有向グラフにおける用語

これまで用いた用語の説明をここで簡単にまとめておきます。そしてついでに略記ができるものは略記も紹介しておきます。

  • 有向グラフ
    頂点と呼ばれる点を矢印でつなぐことで関係を図示できるようにしたもの。英名がdirected graphの為ダイグラフとも呼ばれる。数学だけに限らずいろいろなところに出てくる。
  • 頂点
    有向グラフにおいて関係を考える対象物。構造が入っていなくても良い。ノードとも呼ばれる。
    ループと多重辺なしの画像
    例1
    ループを持つグラフ
    例2
    多重辺を持つグラフ
    例3

     vが有向グラフ Gの頂点であることを v \in Gと略記する。

  • 有向グラフにおける頂点間の関係を依存関係も込めて表現するもの。頂点に構造があれば関数で書けることもあるが普通は関数では書けない。その例として少し高度だが圏論の順序圏とか圏としてみた群があげられる。
     eが有向グラフ Gの頂点 iから頂点 jへの辺であることを e: i \rightarrow j in  Gと略記する。

  • ここでは厳密には定義しないが、有向グラフ Gの頂点 iから頂点 jへの長さn( \geq 0)の道とは、頂点 iからn回辺をたどって頂点 jへ行ったときの通ったn組の辺のことをいう。
  • 始点
    辺を矢印で書いたときの根元のことをいう。
  • 終点
    辺を矢印で書いたときの指している先のことをいう。
  • 隣接
    有向グラフ Gにおいて頂点 iが頂点 jと隣接しているとは、 iから jへの辺 ein Gが存在していることをいう。似たような言い回しになるが、有向グラフ Gにおいて頂点 iと頂点 jが互いに隣接しているとは、 iから jへの辺 e in  G jから iへの辺 e' in  Gが存在していることをいう。
  • ループ
    始点と終点が一致する辺のことをいう。
  • 多重辺
    ある頂点間に二本以上の辺が存在することをいう。

最後に

これまで長々と説明してきて有向グラフは何か難しいものだと思っている人もいるかもしれませんが、単なる対象とそれを結び付ける矢印の集まりですから有向グラフ自体は難しくありません。難しいのは分野によって必要とするレベルが違うことによる定義のバリエーションが存在することです。そのせいで調べても有向グラフの定義が違ってしまいわからなくなってしまってお手上げになってしまいます。大まかな定義はこのブログですべてだと思うので参考にしながら有向グラフについて知っていって欲しいと思います。
これでこの記事は最後となります。最後まで読んでいただきありがとうございます。

それでは良き有向グラフライフを!!

2019/01/08 追記

ループも多重辺を持たない定義を見つけたので追記します。

定義(iv)

 Vを集合とする。今 (V, 2) Vの元の個数が2の部分集合全体とし、< V, 2>を (V, 2)の元に順番も考えた集合とする。つまり  \left\{ u, v \right\} ,  \left\{ v, u \right\}  \in < V, 2> に対して \left\{u, v\right\} \neq \left\{v,u \right\}が成り立つ。この \left\{u, v\right\}のことを< u, v>と書くことにする。そしてこの< V, 2>の部分集合をEとする。
このとき有向グラフ Gとは組 (V, E)のこととして定義する。そして Vの元をそ頂点、< u, v> \in E uから v uを辺< u, v>の始点 vを辺< u, v>の終点と呼ぶ。

この定義は辺を部分集合に順序を付けて取ってきていることからループを持たないことがわかります。ゆえに表現能力は最弱です。(つまり(iv)⇒(i)⇒(ii)⇔(iii))
また、(i)のように無向グラフを考えることもできます。無向グラフは向きを考えない有向グラフのようなものであったのでこの定義で向きを与えている< u, v>から順番の考えを忘れた普通の集合 \left\{ u, v\right\}で辺を与えてやると組 (V, E)は無向グラフになります。
この定義の有向グラフが使われている分野はまだ確認できていませんが、守屋悦朗著のグラフ上の演算についての論文に無向グラフバージョンが16ページで確認できます。

2019/04/08 追記

定義(iv)の応用を発見したので追記します。見つけた応用は主に二つあります。しかし、この二つとも有効グラフではないのでお気を付けを。
一つ目はマトロイドです。マトロイドのイメージ的な解説はけんちょんさんのマトロイドの凸構造とい記事が大変参考になります。マトロイドはベクトルの一次独立を一般化するために生み出されたものです。マトロイドは参考に挙げた記事からもわかるようにアルゴリズムの効率化に役立っていたりします。
二つ目はこのマトロイドを一般化したハイパーグラフです。ハイパーグラフとは頂点集合 Vに対して辺集合[tex: E \subset 2V]を考えます。ただし \emptyset \not\in Eとしておきます。つまり、これはマトロイドで言うと同じ集合の元としてグルーピングしたものをまとめて一つの辺と呼んでいることになります。今回紹介した定義(iv)はこのハイパーグラフの辺集合 Eの元は位数2であるとし、その位数2の集合の元の順番に意味があるとしたものとなります。

2019年の目標

さてこのブログを開設して初めての投稿です。そしてもうほとんど年末です。そういうわけで今年の反省などをもとに、少し早いですが来年の目標を(少し過剰に)立ててみました。
それではどうぞ。

数学編

数学は主に表現論とホモロジー代数と有向グラフの統合を目的として勉強していきたいと考えています。その為の流れは以下のように考えています。

プログラミング編

プログラミングはRustでCLIツールを作成する為のクレートとしてCLI Tool Builder(ctb)を引き続き作って行こうかと思います。
つい最近ctbと目標と同様にCLIをビルダーパターン的に宣言しサブコマンドも定義できるclap-rs/clapクレートを見つけたので、このクレートを参考にctbを作りながら勉強していきたいと考えています。このclapクレートはRust界隈では有名らしく、yamlファイルからコマンドの引数のパースなどに関する情報をプログラム中で取得したりできるそうです。ですのでその機能まで作ってRustでのパースなどの言語処理系に関する部分も学んでいけたらなと考えています。

ブログ編

始めたばかりでこのブログがどうなっていくかまだ自分でもわかっていませんが、ひとまず次のことを考えています。

  • 不定期でもいいからこのブログを2019年内は続ける。
  • 有向グラフと言えばこのブログといわれるように頑張る。

その他創作編

私は絵が下手です。しかし絵はいくつになってもうまくなりたいものです。そんなわけで絵をうまく描けるようになるため、下手でも描いてPixivに挙げていきます。そしてあわよくば自作立ち絵を描けるようになって動画投稿したい。そんなわけで2019年内の目標は次のように設定しました。

  • 酒を飲む京町セイカさんを描けるようにする。
  • 自作の酒のみセイカさんを利用(動画化など)、量産等する。

おわりに

来年は忙しくなることがわかっているので、すべてをこなすことはできません。しかし、こなせるだけこなしていこうかと考えています。 なので応援してください。