1

私はpythonグラフライブラリに取り組んでおり、隣接リストを使用しています。xml を使用して隣接リストを表すことを考えているので、グラフへの保存やグラフからの読み取りが簡単になります。このようなグラフの場合:

  A
  |\
  | \
  |  \
  B---C

隣接関係は次のようになります

A:[B,C]

B:[A,C]

タクシー]

ここで問題が発生します。これをどのように xml に変換しますか? 私は（非常に）限られたxmlの知識しか持っていないので、私のものは次のようになります：

<graph>
     <node>
     A
     <realtedto>[B,C]</relatedto>
     </node>
     ...
</graph>

あなたにはこれが正しいように見えますか？また、グラフが単純でない、または方向性がないという問題にどのように対処しますか?

4

1 に答える 1

2

次のようにリンクを保存できます。

<graph>
 <node id="A" />
 <node id="B" />
 <node id="C" />
 <links>
  <link first="A" second="B" />
  <link first="A" second="C" />
 </links>
</graph>

でも、「A、BはB、Aと同じですか？」という奇妙な状況がありますか？あなたがルックアップをしているなら。私はおそらく上記の方法で行くことはありません。一方、そのようにすると、重複した情報を保存することはありません。(場合によっては、取り消しを防ぐために検証する場合)。有向グラフの場合、その副作用は機能である可能性があります。その場合、A、B ISは B、A とは異なるためです。

xml は暗黙的に物事を階層に格納し、グラフは変換のない階層であるとは限らないことに注意してください。そのため、何らかのゆがみなしに「直接」表現することは不可能です。私はおそらく次のようなことをするでしょう：

<graph>
<node id="A">
  <neighbors>
   <neighbor id="B" />
   <neighbor id="C" />
  </neighbors>
</node>
<node id="B">
  <neighbors>
   <neighbor id="A" />
  </neighbors>
</node>
<node id="C">
  <neighbors>
   <neighbor id="A" />
  </neighbors>
</node>
</graph>

残念ながら、情報が重複していますが、順序付けの問題を回避できます。逆シリアル化すると、トラバーサルのために常にノードのネイバーへの参照が得られます。有向グラフにしたい場合は、 と に分けることが でき<neighbors>ます。または、逆方向にトラバースできることを気にしない場合は、アウトレット側にタグを付けるだけです。<inlets><outlets><neighbor>

リンクを反復できるようにする場合は、2 つのアプローチを組み合わせることができます。

それはすべて、データに持たせたい機能にかかっています。

于 2013-01-28T19:15:49.363 に答える