31

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

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

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

Graphviz プログラムで使用されるドット言語については知っていますが、これが最適な方法かどうかはわかりません。この質問は、おそらく学界が取り組んでいるようなものであり、これについて議論している論文への参照があれば幸いです.

4

6 に答える 6

15

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

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

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

人間が読めるようにする必要がある場合でも、独自のシリアル化アルゴリズムを作成することを選択できます。たとえば、「通常の」マトリックスで行うように、マトリックス表現を書き留めることができます。列と行、およびその中のすべてのデータを次のように出力するだけです。

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

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

于 2008-09-09T13:04:14.093 に答える
8

通常、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 への実際のシリアル化を処理できます。

于 2008-09-09T13:12:52.640 に答える
5

XML は非常に冗長です。私がそれをするときはいつでも、私は自分自身を転がします。以下は、3 ノード有向非循環グラフの例です。それは非常にコンパクトで、私がする必要があるすべてを行います:

0: foo
1: bar
2: bat
----
0 1
0 2
1 2
于 2008-09-09T12:58:56.417 に答える
1

隣接リストと隣接行列は、メモリ内のグラフを表す 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]

圧縮されたスパース行は実質的に隣接リストです (列インデックスは同じように機能します) が、この形式は行列演算により適しています。

于 2008-09-28T03:07:21.917 に答える
1

よく知られている 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、その他の優先シリアル化形式、または隣接行列として実行できます。

于 2008-09-09T13:03:53.627 に答える
0

より学術的ではなく、より実用的なメモとして、CubicTestではXstream (Java)を使用して、テストを xml との間でシリアル化します。Xstream はグラフ構造のオブジェクト関係を処理するため、そのソースと結果の xml を見て、1 つまたは 2 つのことを学ぶことができます。あなたは醜い部分については正しいですが、生成されたxmlファイルはきれいに見えません。

于 2008-09-09T13:01:23.150 に答える