0

データ交換の目的で、XML 形式の有限深度グラフと見なすことができる表現を調べています。問題点は、エッジタグでどのようにノードを参照するかです。私が見る 2 つの戦略は、a) 一意の識別子を使用するか、b) パスを使用することです。

一意の ID:

<graph id="g0">
  <node id="n0"/>
  <node id="n1"/>
  <edge from="n1" to="n0"/>
</graph>
<graph id="g1">
  <node id="n2"/>
</graph>
<edge from="n2" to="n1"/>

パス:

<graph id="0">
  <node id="0"/>
  <node id="1"/>
  <node id="2"/>
  <edge from="1" to="0"/>
  <edge from="2" to="1"/>
</graph>
<graph id="1">
  <node id="0"/>
</graph>
<edge from="1:0" to="0:2"/>

これらの種類のものの標準的な手順は何ですか? 私が集めたものから、一意の識別子のアプローチがより広まっているようです。それに関する私の問題は、グラフが非常に大きくなったときです。

  • XML ファイルとの間でエッジを読み書きする目的で、オブジェクトを ID にマップする非常に大きなハッシュ テーブルの必要性
  • エッジがグラフの内部にある場合、冗長なパス コンポーネントを省略できないため、ファイル自体はパスを使用して書き込まれたものよりも大きくなります。

考え？

更新 1 :

1 つの平坦なグラフではないことに注意してください。相互接続された 1 つまたは複数のグラフ。それらはそれぞれローカルにインデックス化された要素を持っていますが、それらをすべて平坦化し、それら全体のエッジを追跡するのは少し面倒です。

更新 1.1 : GraphML のサブグラフでは、実際にはローカル ノード ID をグローバル ノード ID から分離できるようにする複雑なキーを使用していることに気付きました。

更新 2 :

はい、明らかにこれは整形式の XML ではなく、タグやあらゆる種類のスキーマ宣言が欠落しています。

4

2 に答える 2

3

このようなグラフを記述するスキーマがあります: GraphMLを参照してください

例：

<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"  
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns
     http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
  <graph id="G" edgedefault="undirected">
    <node id="n0"/>
    <node id="n1"/>
    <node id="n2"/>
    <node id="n3"/>
    <node id="n4"/>
    <node id="n5"/>
    <node id="n6"/>
    <node id="n7"/>
    <node id="n8"/>
    <node id="n9"/>
    <node id="n10"/>
    <edge source="n0" target="n2"/>
    <edge source="n1" target="n2"/>
    <edge source="n2" target="n3"/>
    <edge source="n3" target="n5"/>
    <edge source="n3" target="n4"/>
    <edge source="n4" target="n6"/>
    <edge source="n6" target="n5"/>
    <edge source="n5" target="n7"/>
    <edge source="n6" target="n8"/>
    <edge source="n8" target="n7"/>
    <edge source="n8" target="n9"/>
    <edge source="n8" target="n10"/>
  </graph>
</graphml>
于 2009-07-06T19:07:28.957 に答える
0

エッジがグラフの内部にある場合、冗長なパス コンポーネントを省略できないため、ファイル自体はパスを使用して書き込まれたものよりも大きくなります。

この点は時期尚早の最適化です。XML パーサー/ライターは大きなファイルを処理しません。また、ストレージ サイズが問題になる場合、XML は通常、ZIP で非常にうまく圧縮されます。

XML ファイルとの間でエッジを読み書きする目的で、オブジェクトを ID にマップする非常に大きなハッシュ テーブルの必要性

それは実装上の懸念です。別の構造でマッピングを維持しようとするのではなく、XML 読み取り/書き込みルーチンをグラフ、ノード、およびエッジ クラス自体に記述すれば、このような大きなハッシュ テーブルを持つことを確実に回避できます。グラフはシリアライズとデシリアライズが非常に簡単です。

一意の ID は、おそらく進むべき道です。提案した階層的な方法と同様の方法で ID を構造化すると、XML の目標の 1 つである、比較的人間が判読できるものになります。

于 2009-07-06T19:09:21.887 に答える