グラフ構造をシリアル化するにはどうすればよいですか?

StackOverflow https://stackoverflow.com/questions/51783

  •  09-06-2019
  •  | 
  •  

質問

フラット ファイルとリレーショナル データベースは、構造化データをシリアル化するメカニズムを提供します。XML は、非構造化ツリー状データをシリアル化するのに最適です。

しかし、多くの問題はグラフで表現するのが最も適切です。たとえば、熱シミュレーション プログラムは、抵抗エッジを介して相互に接続された温度ノードを操作します。

では、グラフ構造をシリアル化する最良の方法は何でしょうか?リレーショナル データベースがオブジェクトの複雑な Web をシリアル化できるのと同じ方法で、XML がある程度それを実行できることはわかっています。通常は機能しますが、簡単に醜くなる可能性があります。

graphviz プログラムで使用されるドット言語については知っていますが、これが最善の方法であるかどうかはわかりません。この問題はおそらく学術界が取り組んでいる類のものであり、これについて議論している論文があればぜひ参考にしたいと思っています。

役に立ちましたか？

解決

メモリ内でグラフをどのように表現しますか?
基本的には 2 つの (良い) オプションがあります。

ここで、隣接リスト表現は疎グラフに最適に使用され、行列表現は密グラフに最適に使用されます。

このような表現を使用した場合は、代わりにそれらの表現をシリアル化することができます。

そうでなければならない場合 人間が読める 独自のシリアル化アルゴリズムを作成することもできます。たとえば、「通常の」行列の場合と同様に、行列表現を書き留めることができます。次のように列と行、およびその中のすべてのデータを出力するだけです。

   1  2  3
1 #t #f #f
2 #f #f #t
3 #f #t #f

(これは最適化されておらず、重み付けされていない表現ですが、有向グラフに使用できます)

他のヒント

通常、XML の関係は親子関係によって示されます。XML ではグラフ データを処理できますが、この方法では処理できません。XML でグラフを処理するには、 xs:ID そして xs:IDREF スキーマの種類。

例では、node/@id が xs:ID タイプであり、link/@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のJAXB（Java XML Binding）を使用しました。これらをサポートします。 @XmlID そしてその @XmlIDREF 注釈。プレーン Java オブジェクトを使用してグラフを構築し、JAXB を使用して XML への実際のシリアル化を処理できます。

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)

もちろん、もう 1 つの方法は、ノードとエッジのリストとして使用する方法です。これは、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) XML との間でテストをシリアル化します。Xstream はグラフ構造のオブジェクト関係を処理するため、そのソースと結果の XML を見ることで 1 つか 2 つのことを学べるかもしれません。あなたは正しいです 醜い ただし、生成された XML ファイルは見栄えがよくありません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top