gradle-swagger-generator-pluginにOpenAPI Generator対応のPRがマージされた

OpenAPI / Swagger関連の勉強をしていて、gradle-swagger-generator-pluginを見つけました。

gradle-swagger-generator-pluginはOpenAPI文書から、Swagger UI, ReDocなどのHTMLやコード生成を行ってくれます。

コード生成の有名どころだとswagger-code-genとopenapi-generatorが、OpenAPI文書からコード生成をしてくれます。
gradle-swagger-generator-pluginでは、コード生成はバックエンドとして、swagger-code-genのCLIを使用しています。

openapi-generatorはもともとはswagger-code-genからフォークしたものらしいのですが、
機能としてはswagger-code-genにはバリデーションがないけれど、openapi-generatorにはバリデーションがあるという状況で、
gradle-swagger-generator-pluginは独自にJSON Schemaを使用したバリデーションも提供しています。

ただし、OpenAPI 3.0のほうのバリデーションは行ってくれません。これはまだOpenAPI 3.0のスキーマファイルは作業中だからだそうです。


いろいろ試した結果、gradle-swagger-generator-pluginのほうが、DSLが私の好みだったが、バックエンドとしてはopenapi-generatorが使いたいという状況だったので、
コード生成にOpenAPI Generatorを使用する変更を行ってPRしていました。

github.com

無事マージされてよかったです。

下記のような学びがあって、やってよかったなと思います。

  • gradle自体の理解 / これまでも使ってはいましたが、汎用ビルドシステムとしての理解は深まっていませんでした。Project / Task / Artifact / Dependencyなどの概念がだいぶ頭に入ってきました。
  • gradleプラグインの作り方 / Gradleにおけるプラグインとは何か? またGradle Test Kitの存在をしりました。
  • Groovyのテストフレームワーク Spock / パラメータの違うテストを一つにまとめるのは本当に便利でした。やってみると「おなじテストを複数回実行する」から見るSpockのUnrollの世界 - Qiitaがすごく実感できます。
  • OpenAPIの仕様や議論/問題点などの把握 / OpenAPI 3.0はXMLを返すAPIスキーマ(Relax NGXML Scheme)なども実は議論のなかにあるということを知りました。その辺いらないよとは思います。
  • GitHubのPRの実際 / これまでは自身のリポジトリにPRから自己解決マージするみたいのをやっていましたが、初めてPRしたのでやっぱりいろいろ戸惑いました。下記2つの記事は読んでおくべきです。

hnw.hatenablog.com
stackoverflow.com

グラフの密度

k-coreが気になるのでDensity-friendly graph decomposition ( https://users.ics.aalto.fi/gionis/friendly.pdf )を読む。超訳


Abstract

最新のグラフマイニングツールでは、k-core分析によりグラフを階層構造に分解するのは標準的な操作です。

k-core分解は次数の分布によってグラフを分析する、単純ですが効率的な方法です。
中心にむかって連結性が増加するように、グラフ内の領域を識別し、構成を明らかにします。

k-core分析は頂点の次数に依存しますが、k-coreは自然な密度特性を満たしません。簡単に言えば、最も中央のk-coreが、必ずしも最も密度の高いサブグラフであるとは限りません。
k-coreとグラフの密度のこの不一致が我々の研究の土台です。

サブグラフが局所的に密集している(locally-dense)ということを定義することから始め、私たちの定義にはk-coreと同様にグラフのネストされたチェーン分解が必要であることを示します。
この分解の結果、密度が増加する順に構成されます。

グラフ G=(V,E)に対するこのような局所的に密な分解は多項式時間で計算できることを示します。
正確な分解アルゴリズムの実行時間はO(|V|^2|E|)ですが、実際にはかなり速い。さらに、局所的に最適な最適分解に第2因子近似を提供する線形アルゴリズムも開発しました。
またk-core分解が第2因子近似であることを示します。

しかし、我々の実験評価によって示されるように、実際にはk-coreは局所的に密なサブグラフとは構造が異なり、理論によって予測されるように、k-coreは必ずしもグラフ密度とよく一致するとは限りません。

INTRODUCTION

高密度サブグラフとコミュニティを見つけることは、グラフマイニングで最もよく研​​究されている問題の1つです。
高密度サブグラフを識別する技術は、生物学からウェブマイニング、社会および情報ネットワークの分析まで多数の応用分野で使用されている。
高密度サブグラフを発見するために提案された多くの概念の中でk-coreは、その定義の単純さと線形時間で識別できるために特に魅力的です。

グラフのk-coreは、すべての頂点がそのサブグラフ内の少なくともk個の他の頂点に接続されている最大部分グラフとして定義されます。
k-core分解は、サブグラフのネストされたシーケンスを形成するという素晴らしい特性があり、グラフを分析するのに有用なツールになります。

グラフのk-core分解が、内側コアの頂点の度数が高いサブグラフの連鎖を与えるという事実は、内側コアが特定の意味では、外側コアよりも密度が高く接続されていることを期待させますが、この記述は真実ではありません。この論文では上記が真である、すなわち分解の内側の部分グラフが外側のグラフよりも密度が高いグラフ分解を得る方法を示します。

密度を定量化するために、densest-subgraph問題で使用される古典的な概念を採用します。密度は、サブグラフのエッジと頂点の比として定義されます。
この密度の定義は、平均次数を2で割ったものとして見ることもできます。

我々の動機づけは、この密度の定義に従ってk-coreが順序付けされていないことである。
次の例は、最も内側のコアが必ずしも最も密なサブグラフではないことを示しています。実際、頂点を追加または削除することで密度を上げることができます。



例1 6つの頂点と9つの辺からなる図1のグラフG1(画像は略) を考えてみましょう。
グラフ全体の密度は9/6 = 1.5です。
このグラフには、3つのkコアがあります。C1としてマークされた3コア、C2としてマークされた2コア、および1コアであり、グラフ全体に対応し、C3としてマークされています。
コアC1は密度6/4 = 1.5(6つのエッジと4つの頂点を含む)を有し、コアC2は密度8/5 = 1.6(8つのエッジと5つの頂点を含む)を有する。
言い換えれば、C1は内部コアであるにもかかわらずC2よりも密度が低い。

図1に示すG2(画像は略)について考えてみましょう。

このグラフには、単一のコア、つまり2コアがあり、グラフ全体が含まれています。
このコアの密度は11/8 = 1.375に等しい。しかし、サブグラフB1は7つのエッジと5つの頂点を含み、密度7/5 = 1.4を与え、これは唯一のコアの密度よりも高い。
この例では、より密度の高い代替のグラフ分解を定義するよう動機づけています。このグラフような分解を局所的分解と呼びます。

私たちは次を満たすような分解に興味があります。
(i)内側サブグラフの密度が外側サブグラフの密度よりも高く、
(ii)最も内側のサブグラフは最も細いサブグラフに対応し、
(iii)分解を効率的に計算または近似することができる。

局所的に密集した部分グラフを定義することで目標を達成します。本質的には、頂点を追加したり削除して密度を上げることはできません。
これらの部分グラフは、外側の部分グラフに行くにつれて密度が減少し、最も内側の部分グラフが実際には最も細い部分グラフであるような階層に配置されることを示す。
この階層を発見するための2つの効率的なアルゴリズムを提供します。


最初のアルゴリズムは、Goldberg [15]によって与えられた最も密なサブグラフを発見するための正確なアルゴリズムを拡張する。
このアルゴリズムは、パラメータαに依存する特定のグラフ上の最小カット問題を解くことに基づいている。
Goldbergは、ある値α(バイナリサーチで見つかる)に対して、最小カットは最も細いサブグラフを回復することを示した。
我々の貢献の1つは、ゴールドバーグのアルゴリズムをより明らかにし、同様の構成がαを変化させることによってすべての局所的に密な部分グラフを発見することを可能にすることである。

我々の第2のアルゴリズムは、密集した部分グラフを近似するためのCharikarによる線形時間アルゴリズムを拡張する[13]。
このアルゴリズムは、最初に最小次数の頂点を繰り返し削除することによって頂点を順序付けし、次にその順序を考慮して最も細いサブグラフを選択する。
この考え方は、同じ順序を使用して、順序を考慮した最初の最も細いサブグラフを見つけ、最初のサブグラフを含む2番目に細かいサブグラフを繰り返し検索するなどして拡張します。
このアルゴリズムは線形時間で実行可能であり、第2因子近似保証を達成することを示す。

Charikarのアルゴリズムとk-core分解を発見するためのアルゴリズムは非常に似ています。それらは両方とも、最小次数の頂点を削除することによって頂点を順序付けます。この接続が深いことを示し、k-core分解が局所的に密な分解のための第2因子近似を提供することを示す。



一方、実際にはk-coreは局所的に密なサブグラフとは構造が異なり、k-coreは必ずしもグラフ密度とよく一致するとは限らないことを理論的に示します。

論文の残りは次のように編成されている。第2節では予備的表記法を用いる。
3章で局所的な部分グラフを紹介し、セクション4の部分グラフを発見するための現在のアルゴリズム、セクション5のkコア分解への接続について説明します。
6章で関連する作業を提示し、7章で実験を提示する。最後に、8章で議論した論文を締めくくる。

Git LFSは別にリポジトリサーバー側で対応が必要なわけではなくて、LFSサーバーが必要なだけ

GitHubやbitbucketのLFS対応もなんかストレージの料金がすごい高いなぁとおもっていて、リポジトリをホストするサーバーで対応が必要とおもっていたのですが、調べてみるとどうやら違うようでした。

ydkk.hateblo.jp

LFSサーバーをAWS Lambdaに構築して、S3をストレージにする実装

仕組みとしてはLFS サーバーとして、ラージファイルを保存した/保存できるURLを提供する。
git lfsのコマンドがpull / pushの時にLFSサーバーと連携して、オブジェクト(LFS track対象のファイル)をLFSサーバーが返すURLにGET / PUTするという仕組みでした。

他にもLFSサーバーと連携しないstandalone transfer agentの仕組みなどがあるようです。
https://github.com/git-lfs/git-lfs/blob/master/docs/custom-transfers.md


LFSサーバーなしでS3をストレージにする実装としては、下記のようなものがありました。
github.com


なんか不思議な感じです。

GitHubやbitbucketもAPIトークンを登録するとか、AzureのBlog StorageのSASトークンを登録することで、クラウド上で提供されているストレージをLFSのバックエンドとして使わせるとかできるはずなのになんでしないんだろうという感じです。
みんながほしいソリューションはそっちじゃなかろうかとおもうのです。

TCP over websocket

仕事の関係でKeycloakとその下回りであるJBoss/WildFlyを調べていて面白い記事を見つけました。

EJB呼び出しなどは以前はRMI/IIOPのようなTCP/IP上のプロトコルを使っていたが、いまはWebSocket上で行っている(TCP over WebSocket)という記事です。これはWildFly8の頃で、現在の12ではまた別のプロトコルに代わっています。

これと並行してKeycloakでWebSocketを保護できるという話を見つけました。

OAuth2のアクセストークンの期限切れをwebsocketに反映させるとかはできないけど、認証だけならアダプタ入れるだけでできるよという話です。
プロトコル的にはまずHTTP 1.1 GETと一緒にUpgrade要求をするので、その間にOAuth2の認可フローを差し込めるというのがプロトコル上の理解です。

上記のような話題からウェブサーバーとしてOpenID connect / OAuth2などと連携するVPN/トンネリング製品ができるなとおもっていたのですが、https://kaazing.com/ というのがまさにそういう製品のようです。

chisel(https://github.com/jpillora/chisel)というgoで作られた、やはり同様のOSSがあったのですが、保護までしてくれないようだったのですが、chiselもApacheのmod_wstunnel / mod_auth_openidcとかと組み合わせればいけそうな気がします。

すこしこのあたりに興味がわいてきました。

俺のFPTの理解

FPTにおいては幅とパラメータが存在する。

たとえば幅をk-coreとすることができるというのが、最大クリーク問題つづき - 高温処理済みコースケの話。
k-クリーク判定では幅hに対しての組み合わせになるので二項定理から {}_{h}\mathrm{C}_{k} = {}_{h}\mathrm{C}_{h-k}なので、 min(k,h-k)を用いて h^{min(k,h-k)}のオーダーで上限を決めることができる。

今回、最大クリーク問題の幅をk-coreとしたが、その幅は彩色数の近似にもできる。
k-coreの順序で貪欲彩色することにより、k-core + 1以下の彩色結果が得られるので、それを幅にしてもよい。
その場合でも上限は幅をもとに計算することができる。

W[1]-completeとはおそらくこの幅hとパラメータkの2変数により f(h,k)p(n)となるものだと考える。幅はアルゴリズム上設定されたもので、kは判定問題に与えられるパラメータ。これが指数関数しかないのか、多項式のものもあるのかはまだわからない。探索木を多項式時間で検索できればよい。結構制限はあるなかでの探索なのでもしかすると多項式時間のアルゴリズムがあるかもしれない。

指数時間アルゴリズム入門だと100万頂点からサイズ30以下の頂点被覆を求めることが可能ってなってたけど、補グラフの最大クリークのサイズをnから引いたものが頂点被覆なわけだから、幅hに対してk,h-kが小さければ、もっと全然できるはず。

Clique problem - Wikipedia 英語のWikiPediaの記事でDegeneracyをつかって最大クリーク問題ができるのが書いてあるな。

指数時間アルゴリズム入門だとkに対してと書いてあるので、2変数はちがうんだろうなとおもう。

最大クリーク問題つづき

グラフのDegeneracyをkとすると前処理後、おおまか 2^{k}n  で最大クリークが求まるな。

Degeneracyのページにしたがって、最大出次数を最小化するように、無向グラフ G(V,E)を順序付け、辺を向き付けし、有向グラフに変換する。これは多項式時間でできる。

最大出次数を \Delta_+とする。

頂点が順序付けされたので、 vを始点とするクリーク集合というのが扱えるようになった。
頂点 vとその出力辺からなる隣接集合から誘導される部分グラフH_v vを始点とするクリーク集合がすべて含まれる。

このH_vvを除く頂点の組み合わせをすべて試せば、vを含むクリークの最大サイズがわかる。
 \Delta_+は最小化されていて、n頂点すべてについて行うので、大まか 2^{\Delta_+} n でもとまる。

もうすこしアルゴリズムとして分解することにする。

頂点の冪集合P(V)のうち、特にサイズがkのものを P_k(V) \subset P(V)と書く。
fをサイズkの頂点集合がクリークであればkを、そうでなければ-1を返すものとする。これは誘導部分グラフを作成し、頂点数と辺数から決めることができ多項式時間である。
 \displaystyle f: P_k(V) \rightarrow \{k,-1\}

 T_vをある頂点vの出力辺から作成される隣接集合とすると、最大クリークをもとめる \omega(G)は下記のような形になる。

 \displaystyle \omega(G) = \max_{v \in V} \max_{k=0,1,\cdots} \max\{\max \{ f(\{v\} \cup T_v \setminus X),\> f(\{v\} \cup X)\} |  X \in P_{k}(T_v) \}

上記の式は下限、上限から挟み撃ちにしている。

 f(\{v\} \cup T \setminus X) > 0となるときは、明らかに vを始点とする最大クリークであり、次の頂点に移ればよい。最も内側のmax式が-1の時は、下でクリークが見つからないわけなので、そこまでに見つかった最大クリークサイズを返して、やはり次の頂点に移る。*1

判定式のほうはkを求めるクリークサイズとすると d_+(v) - k,kの小さいほうを使用する。これを k'とするとおおまか計算量は {}_{\Delta_+}\mathrm{C}_{k'} nになる。
もちろん k > \Delta_+であれば解はない。

 \displaystyle 
\begin{eqnarray}
\omega(G,k) & = & \max_{v \in V} \max_{X \in P_{k}(T_v)} f(\{v\} \cup X) & \hspace{1cm} & (d_+(v) - t \ge k) \\
                 & = & \max_{v \in V} \max_{X \in P_{k'}(T_v)} f(\{v\} \cup T_v \setminus X) & \hspace{1cm} & (d_+(v) - t \lt k)
\end{eqnarray}

最悪のケースは \frac{\Delta_+}{2} = \omega(G)のときで、例えば K_2が50個あるようなグラフの補グラフだと思う。サイズ50のクリークが2^{50}個あって、98正則グラフなので \Delta_+ = 98。正確に半分ではないけどイメージは伝わると思う。これは補グラフが連結ではないことが頂点数、辺数からわかるので状況に合わせて必要な処理を組み込むことで平均的な時間はもっと高速化できる。
おそらくこのアルゴリズムはZPPである。
まとめ

自分の理解ではおそらくNP困難問題である最大クリーク問題がPであり、NP完全問題であるk-クリーク問題がFPTになった。
もし違う観点があるとすれば、最大クリーク問題が f(\Delta_+)p(n)のFPTで、k-クリーク問題が f(\Delta_+,k)p(n)のFPTという感じ。

最大次数やk-core数なんてデータの入力長に依存しないのでPだと思っている。が、アルゴリズムで設定された幅とみれば、それは指数時間なのかもしれない。

その他
従来のFTPの議論では最大クリークや最大独立集合にFPTがないといわれていたが、次数から引くというとのが盲点だったのかなと思った。
ただ無向グラフでvを含むクリークの最大を全部数えるでも、おそらくここに行きつくので最大次数は最小化できないという意味で有向グラフに変換するというが転換だったなのかなと思う。

(以下、全部 たぶん)

P≠NP予想は否定したとおもう。
#PもPである。P=NPであったので多項式階層はすべて潰れた

そしてP=ZPPである。P=ZPPからZPP≠EXPTIMEになる。
P=NPなのでETH, SETHも否定した。


参考 : NP困難 - Wikipedia
参考: #P - Wikipedia
参考: P≠NP予想 - Wikipedia
参考: 多項式階層 - Wikipedia
参考 : Fixed Parameter Algorithms Open lectures for PhD students in computer science
参考: ZPP - Wikipedia

*1:ただ、なんとなく中央まで行くのではなくて、3分の1進めたところで下限のほうのクリークの集合から2つ選んで最大クリークを探すほうが良い気がする。