2022-0227 実装会レビュー

[Reputeless]

• MTX フォーマットについて再確認

  • 1-origin ? https://networkrepository.com/mtx-matrix-market-format.html

• サンプルでの Reseed の使用は非推奨

  • DefaultRNG{ 123456789ull } を入れる

• const FilePath& path → FilePathView path

• それぞれのクラス、関数をどうファイル分割するか（計画をください）。以下例

  • GraphDrawing/Common.hpp
    • XX クラス
  • GraphDrawing/MTX.hpp
    • XX 関数
  • GraphDrawing/~~Layout.hpp

• クラスの依存関係を .hpp / .ipp 分割でうまく回避

  • Siv3D の 2DShapes.hpp の構成が参考になる
  • Siv3D/GraphDrawing/ にも 2DShapes.hpp 的な役割をするヘッダが必要になる

• ゲーム感を感じるサンプル

  • @Reputeless アイデア: 町の座標固定、その間のフィールドのポイントと道を自動生成
  • マップがあって、そこに町を建てて、それぞれの町どうしの交易をグラフビューで表示する的なサンプル？

• 単純な実装のも入れて良いのでは

  • 例: https://agehama.hatenablog.com/entry/2018/07/15/151206

• ForceDirectedConfig のサンプルとしてマインドマップ

• ユーザが .mtx を生成する手段 / ツールのサンプル提供（現状だと、サンプル動かして終わりなので、実際に使ってもらうため）

  • Web API / 手動でグラフ作る / 実世界データ

• アート / エフェクトとしてのグラフ（自動生成）

[agehama]

@Reputeless
とりあえず計画を立てました。
こんな感じでどうでしょうか？

ファイル分割案

• /GraphEdge.hpp + /detail/GraphEdge.ipp
  • struct GraphEdge
• /ConnectedGraph.hpp + /detail/ConnectedGraph.ipp
  • class ConnectedGraph
• /GraphSet.hpp + /detail/GraphSet.ipp
  • class GraphSet
• /Visualizer.hpp + /detail/Visualizer.ipp
  • struct IGraphVisualizer
  • class BasicGraphVisualizer
• /GraphLoader.hpp + /detail/GraphLoader.ipp
  • ReadMMCoordinateFormat()
  • ReadEdgeListText()
  • DecomposeConnectingComponents()
  • ShrinkVertices()
• /LayoutForceDirected.hpp + /detail/LayoutForceDirected.ipp
  • struct ForceDirectedConfig
  • class LayoutForceDirected
  • class LayoutForceDirectedLargeScale（←追加）
• /LayoutCircular.hpp + /detail/LayoutCircular.ipp
  • class LayoutCircular
• /detail/SparseMat.hpp
  • struct SparseEntry
  • enum class SparseFormat
  • SortEntries()
  • class SparseMat
• /detail/QuadTreeVertices.hpp
  • class QuadTreeVertices
• /detail/GraphTransform.hpp
  • class GraphTransform
• /GraphDrawing.hpp
  • ↓

GraphDrawing.hpp

# pragma once
# include "GraphEdge.hpp"
# include "ConnectedGraph.hpp"
# include "GraphSet.hpp"
# include "GraphEdge.hpp"
# include "GraphEdge.hpp"
# include "Visualizer.hpp"
# include "GraphLoader.hpp"
# include "LayoutForceDirected.hpp"
# include "LayoutCircular.hpp"
# include "detail/SparseMat.hpp"
# include "detail/QuadTreeVertices.hpp"
# include "detail/GraphTransform.hpp"
# include "detail/GraphEdge.ipp"
# include "detail/ConnectedGraph.ipp"
# include "detail/GraphSet.ipp"
# include "detail/Visualizer.ipp"
# include "detail/GraphLoader.ipp"
# include "detail/LayoutForceDirected.ipp"
# include "detail/LayoutCircular.ipp"

LayoutForceDirected 改善案

今の LayoutForceDirected は Graph coarsening という手法を使っているのですが、これのせいで座標の固定や頂点の動的追加などをサポートするのが難しい状態です。今後の改善案は、現在の実装を LayoutForceDirectedLargeScale という名前に置き換えた上で、この処理から Graph coarsening を省いた機能として LayoutForceDirected クラスを新しく作って、代わりにこちらでグラフの動的変更をサポートしたいと考えています。

補足：以前実装した↓が Graph coarsening 無し版です。
https://twitter.com/agehama_/status/1188355905051475969
有り版より速度も品質も低いですが、数百ノード程度までならこっちでも十分そうという印象です。

[Reputeless]

見通しが良くなりました！ ありがとうございます。
struct IGraphVisualizer; と class BasicGraphVisualizer;
だけは分けましょうか。
IGraphVisualizer.hpp に struct IGraphVisualizer だけあれば、継承クラスを実装するときに読みやすいので。
OpenSiv3D にも I～.hpp というヘッダが多くあります。
◆
GraphDrawing.hpp はそのような感じで OK です。
◆
ReadMMCoordinateFormat() と ReadEdgeListText() は、GraphSet の static メンバ関数にして
GraphSet g = GraphSet::LoadMM(U"test.mtx") にするという（今思いついた）アイデア、どう思いますか？
将来支障が出たりするでしょうか。
さらに進んで GraphSet g{ U"test.mtx" }; とするのも良いかもしれません。
◆
あと ReadEdgeListText() は独自形式でしたよね？
その場合、公式 API で関数を用意するより、ユーザに実装してもらったほうが良いので、
.txt とその関数を使っていたサンプルは、データをプログラムに直接ハードコーディングして、それを使うのが良いと思います。
それを外部ファイル化したいユーザは、自力で読み取りプログラムを作れば ok という感じに。
◆
LargeScale という名前では、ラージスケールの基準がユーザに伝わらないので、片方に性質由来の名前を付けると良さそうです。で、ドキュメントに、推奨上限ノード数など書けばよいです。
例えば Fixed / Static / Dynamic etc. など
◆
あと、LayoutForceDirected は ForceDirectedLayout にしましょう。そのほうが英語としても自然です。
ネーミングはこのライブラリが参考になるかも？

• https://gojs.net/latest/api/symbols/ForceDirectedLayout.html

とりあえずさくっとコメントです。

[agehama]

ありがとうございます。
LayoutForceDirectedLargeScale -> ForceDirectedLayoutStatic にしようと思います。

ReadEdgeListText() について

確かに規格が定められてるわけでは無いですが、エッジリスト形式自体は広く使われていて、サポートしているライブラリも多いです（若干の表記揺れはあります）。

• igraph
  https://igraph.org/c/doc/igraph-Foreign.html#simple-edge-list-and-similar-formats

int igraph_read_graph_edgelist(igraph_t *graph, FILE *instream, igraph_integer_t n, igraph_bool_t directed);

This format is simply a series of an even number of non-negative integers separated by whitespace. The integers represent vertex IDs. Placing each edge (i.e. pair of integers) on a separate line is not required, but it is recommended for readability. Edges of directed graphs are assumed to be in "from, to" order.

• NetworkX
  https://networkx.org/documentation/stable/reference/readwrite/generated/networkx.readwrite.edgelist.parse_edgelist.html#networkx.readwrite.edgelist.parse_edgelist

parse_edgelist(lines, comments='#', delimiter=None, create_using=None, nodetype=None, data=True)

Examples
Edgelist with no data:

>>> lines = ["1 2", "2 3", "3 4"]
>>> G = nx.parse_edgelist(lines, nodetype=int)
>>> list(G)
[1, 2, 3, 4]
>>> list(G.edges())
[(1, 2), (2, 3), (3, 4)]

• Gephi
  https://gephi.org/users/supported-graph-formats/csv-format/

Edge List
The CSV example below represents a graph with two edges: “a” -> “b” and “b” -> “c”.

a;b
b;c

ついでに以下のデータセットは ReadEdgeListText() でそのまま読める形式です。

• High school contact and friendship networks « SocioPatterns.org
  http://www.sociopatterns.org/datasets/high-school-contact-and-friendship-networks/
  Directed, unweighted friendship network from surveys, space separated, 2KB

• SNAP: Network datasets: Social circles
  http://snap.stanford.edu/data/ego-Facebook.html
  facebook_combined.txt.gz

このように広く認知はされていて、シンプルで使いやすいのでサポートはしておきたいです。
ただ表記揺れは問題だと思うので、NetworkX のように揺れを吸収するためのパラメータを追加した方が良いと思いました。

GraphSet ReadEdgeList(FilePathView path, StringView delimiter = U" \r\n"_sv, StringView commentPrefix = U"#"_sv)

これならエッジリスト形式は大体カバーできると思いますがどうでしょうか？