フラットファイルとリレーショナルデータベースは、構造化データをシリアル化するためのメカニズムを提供します。 XMLは構造化されていないツリー状のデータをシリアライズするのに優れています。グラフ構造をシリアル化する方法は？
しかし、多くの問題はグラフで最もよく表されます。熱シミュレーションプログラムは、例えば、抵抗エッジを介して互いに接続された温度ノードで動作します。
グラフ構造をシリアル化する最も良い方法は何ですか？ XMLは、ある程度、リレーショナルデータベースがオブジェクトの複雑なウェブを直列化できるのと同じように、ある程度行うことができます。通常は動作しますが、簡単には醜いことがあります。
私はgraphvizプログラムで使用されているドット言語について知っていますが、これを行うにはこれが最善の方法であるかどうかはわかりません。この質問はおそらく学界が取り組んでいることのようなものであり、私はこれについて議論している論文を参照したいと思っています。
どのようにグラフをメモリに表現しますか？
基本的には2（良い）のオプションがあります。
、および密グラフの行列表現を。
このような表現を使用した場合、代わりにそれらの表現を直列化できます。
人間が読めるでもにする必要がある場合でも、独自のシリアル化アルゴリズムを作成することができます。ちょうどそのようにそれに列と行、およびすべてのデータをプリントアウト：
1 2 3
1 #t #f #f
2 #f #f #t
3 #f #t #f
（これは非ですたとえば、あなたが任意の「正常な」マトリックスとするだろうのような行列表現を下に書くことができます重み付けされていない表現であるが、有向グラフに使用することができる）
XMLは非常に冗長です。私がそれをするたびに、私は自分自身を転がす。ここでは、3ノードの有向非循環グラフの例を示します。それはかなりコンパクトだし、私はそれを行うために必要なすべてを行います。以下、学術、より実用的なノートで
0: foo
1: bar
2: bat
----
0 1
0 2
1 2
あなたがよく知っている例の1つは、Javaのシリアル化です。これは、各オブジェクトインスタンスがノードであり、各基準がエッジであるグラフによって事実上直列化される。使用されるアルゴリズムは再帰的ですが、重複はスキップされます。そう擬似コードは次のようになります
serialize(x):
done - a set of serialized objects
if(serialized(x, done)) then return
otherwise:
record properties of x
record x as serialized in done
for each neighbour/child of x: serialize(child)
コースの別の方法はXMLとして、または任意の他の好適な直列化形式で、または隣接行列として行うことができるノードおよびエッジのリストの通りです。
通常、XMLの関係は親子関係によって示されます。 XMLはグラフデータを処理できますが、この方法では処理できません。 XMLのグラフを処理するには、xs:IDとxs:IDREFのスキーマタイプを使用する必要があります。
例では、node/@ idがxs：IDタイプであり、そのリンク/ @ refがxs：IDREFタイプであるとします。次のXMLは、3つのノード1のサイクルを示し - > 2 - > 3 - > 1.
<data>
<node id="1">
<link ref="2"/>
</node>
<node id="2">
<link ref="3"/>
</node>
<node id="3">
<link ref="1"/>
</node>
</data>
多くの開発ツールがあまりにもIDとIDREFのサポートを持っています。私はあなたがプレーンなJavaオブジェクトを使用してグラフを構築し、XMLへの実際のシリアル化を処理するためにJAXBを使用することができます。これは、@XmlIDと@XmlIDREF注釈を通じて、これらをサポートしています。JavaのJAXB（JavaのXMLのバインディングを使用していた。
隣接リストおよび隣接行列はメモリ内のグラフを表現する2つの一般的な方法です。これらの2つの間で決定する際に最初に決定する必要があるのは、最適化するものです。一方、エッジ存在のテストやマルコフ連鎖のグラフ表現をしている場合、おそらく隣接行列を好むでしょう。
次の質問はあなたです考慮すべきことは、あなたがどれだけ記憶に収まる必要があるかです。ほとんどの場合、グラフ内の辺の数が可能な辺の総数よりはるかに少ない場合、実際に存在する辺を保存するだけで済むので、隣接リストがより効率的になります。幸いな媒体は、非ゼロのエントリのベクトルを左上から右下に保持する圧縮スパース行形式の隣接行列を表現することです。対応するベクトルは、非ゼロのエントリを見つけることができる列を示します。列エントリベクトル内の各行の開始を示す第3のベクトル。
[[0.0, 0.0, 0.3, 0.1]
[0.1, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.5, 0.2, 0.0, 0.3]]
のように表すことができる。
vals: [0.3, 0.1, 0.1, 0.5, 0.2, 0.3]
cols: [2, 3, 0, 0, 1, 4]
rows: [0, 2, null, 4]
圧縮スパース行を効果的に隣接リストである（列インデックスは同じように機能する）が、フォーマットは、行列演算にもう少しきれいに役立ちます。
グラフをシリアル化するためにJavaシリアル化を使用しようとしました。しかし、私はスタックオーバーフローの例外を取得します。明らかに一般的な苦情であり、 "readObject（）/ writeObject（）"をオーバーライドするための低レベルのコードを書くことをお勧めします。より良い方法がありますか？ –
私はこれを見ていません。 Javaでは、同じオブジェクトが2回記録されるのを防ぐので、各ノードを自分でシリアル化しないで、Javaを1回の呼び出しでグラフ化することが重要です。あなたは別の質問で小さなコードサンプルを与えることができますか？ –