Graph Modelling Languageとは？わかりやすく解説

GML
開発者	Graph Drawing
初版	1995年 (30年前)
種別	データ記述言語
拡張	GraphML
オープン; フォーマット	yes
ウェブサイト	graphml.graphdrawing.org

Graph Modelling Language (GML)は、グラフをモデリングするためのASCII形式の階層型マークアップ言語である。グラフメタ言語とも呼ばれる。 GMLはGraphletやGravistoの主要なファイル形式であり、他のいくつかのグラフ描画システムでもサポートされている。

頂点と辺の定義だけでなく、ラベルなどの属性も定義可能である。属性を自由に追加可能であり、ツールによっては追加属性を読み取って使用することがある。

入力ファイル形式

GMLは、キーと値のペアで構成される。

キー

キーは以下の種類に分けられる。

大域的に定義されたもの
グラフ用に定義されたもの
ユーザーが定義するもの

また、safe/unsafeの区別が存在する。safe属性は小文字で、unsafe属性は大文字で始まる。

safe: グラフが変更されても変更されない
unsafe: グラフが変更されると削除される

キーの最大長は254である。

値

値は以下の種類に分けられる。

整数 - 符号付き32ビット(これを超える場合、文字列として表現する)
浮動小数点数 - 倍精度
文字列
リスト

リストは、キーと値のペアで構成される。同じリスト内での重複キーは有効であり、読み取りおよび書き込み中にこれらの重複順序が保持されることが保証される。これにより、配列およびリストのデータ構造を表すことができる。

簡単なグラフの例

グラフ用のキーとして、graph、node、edge等が定義済みである。

グラフ: 最上位キーgraphで表され、その値はnodeキーとedgeキーを含むリストである。
ノード: 全てのnodeには、グラフ内で一意のidを与える必要がある。
エッジ: 全てのedgeには、sourceとtargetを与える必要がある。このsourceとtargetの値は、nodeのidである。

graph [
	comment "これはグラフの例です。"
	directed 1
	id 42
	label "Graph"
	node [
		id 1
		label "A"
		WeiteresAttribut 42
	]
	node [
		id 2
		label "B"
		WeiteresAttribut 43
	]
	node [
		id 3
		label "C"
		WeiteresAttribut 44
	]
	edge [
		source 1
		target 2
		label "辺 AB"
	]
	edge [
		source 2
		target 3
		label "辺 BC"
	]
	edge [
		source 3
		target 1
		label "辺 CA"
	]
]

歴史

1995年にパッサウで開催されたGraph Drawingで始まり、 1996年にバークレーで開催されたGraph Drawingで終了した取り組みの成果である。

当時は独自のデータ形式が乱立しており、グラフ構造を視覚化・分析する研究やツールのための共通形式を提供するため開発された。

現在ではより厳密に定義可能なフォーマットが登場しており、用途によって使い分けられている。

外部リンク

Michael Himsolt (2010/11/30), GML: ポータブルグラフファイル形式
Matthew Roughan; Jonathan Tuke (2015), Unravelling Graph-Exchange File Formats, https://arxiv.org/pdf/1503.02781.pdf

Graph Modelling Languageとは？わかりやすく解説