2

各ノードがカテゴリに属する​​ DAG が与えられた場合、このグラフを各カテゴリの列を持つテーブルに変換するにはどうすればよいでしょうか? 変換は可逆的である必要はありませんが、グラフの構造に関する有用な情報を保持する必要があります。グラフとテーブルを見ている人がどの行にも驚かされないという意味で、「自然な」変換である必要があります。また、コンパクトにする必要があります。つまり、行がほとんどありません。

たとえば、エッジ a1->b1、a1->b2、b1->c1、b2->c1 を持つノード a1、b1、b2、c1 のグラフ (つまり、ひし形のグラフ) が与えられた場合、次のようになると予想されます。テーブル：

a  b  c
--------
a1 b1 c1
a1 b2 c1

私はこの問題についてかなり考えましたが、特定のグラフで直感的な結果が得られるアルゴリズムを思いつくのに苦労しています。エッジ a1->c1、b1->c1 を持つグラフ a1、b1、c1 を考えてみましょう。アルゴリズムでこのテーブルを生成したいと思います:

a  b  c 
--------
a1 b1 c1

しかし、代わりにこれを生成する必要があります。

a  b  c 
--------
a1    c1
a1 b1

問題に対する創造的なアイデアと洞察を探しています。役立つと思われる場合は、問題を単純化または制限するために自由に変更してください。

ブレインストーミングしましょう！

編集：

行の順序は関係ありませんが、変換では常に同じ行セットが生成されます。

テーブルは、Excel などを使用して並べ替えやフィルタリングを行うときに適切に動作するはずです。つまり、複数のノードをテーブルの 1 つのセルにパックすることはできません。セルごとに 1 つのノードのみです。

4

4 に答える 4

2

必要なのは、トポロジカル ソートのバリエーションです。これは、a---->bエッジがa > b. グラフは DAG であるため、循環はなく、この>関係は推移的であるため、少なくとも 1 つの並べ替え順序が存在します。

ひし形のグラフには、次の 2 つの位相順序が存在します。

a1 b1 b2 c1
a1 b2 b1 c1

b1また、b2項目は間接的であっても接続されていないため、任意の順序で配置できます。

グラフを並べ替えると、おおよその順序がわかります。私の提案は、テーブルを簡単な方法 (1 行に 1 つの頂点) で埋めてから、テーブルを「圧縮」することです。ソートを実行し、出力として取得したシーケンスを選択します。テーブルを上から下に塗りつぶし、頂点を関連する列に割り当てます。

a  b  c
--------
a1 
   b2 
   b1
      c1

次に、上から下に移動してテーブルを圧縮します (次に、同様に下から上に移動します)。各反復で、「現在の」行 ( としてマークされている=>) と「次の」行を詳しく調べます。

  1. 現在のノードと次のノードの列ノードが異なる場合、この列には何もしません。

         from     ---->      to
   X  b  c            X  b  c
   --------           --------
=> X1 .  .           X1 .  .
   X2 .  .        => X2 .  .

  2. 次の行の列Xに頂点がなく (表のセルが空)、現在の行に頂点X1がある場合、この空のセルを現在の行の頂点で埋める必要がある場合があります。しかし、常にではありません: テーブルを論理的にしたいと思いませんか? したがって、現在の行のすべての頂点にエッジb--->X1、などがない場合にのみ、頂点をコピーします。c--->X1

         from     --->      to
   X  b  c           X  b  c
   --------          --------
=> X1 b  c           X1 b  c
      b1 c1       => X1 b1 c1

(編集:) 1 回目 (順方向) および 2 回目 (逆方向) のパスの後、次のようなテーブルが作成されます。

 first       second
a  b  c     a  b  c 
--------    --------
a1          a1 b2 c1     
a1 b2       a1 b2 c1  
a1 b1       a1 b1 c1  
a1 b1 c1    a1 b1 c1

次に、等しい行を削除するだけで完了です。

a  b  c 
--------
a1 b2 c1  
a1 b1 c1

そして、あなたは素敵なテーブルを手に入れる必要があります。O(n^2)。

于 2009-11-20T20:38:25.493 に答える
0

これが私がやったことです：

  • インエッジのないノードから発するすべてのパスを見つけます。（一部のグラフでは高価になる可能性がありますが、私の場合はうまくいきます）
  • 各パスをたどって値の行を収集します
  • 行を圧縮する

行の圧縮は次のように行われます。

  • 列 x,y の各ペアについて
    • x のすべての値から y の可能な値へのマップを作成します
    • 別のマップを作成する y の個別の値が 1 つしかないエントリの場合、x の値を y の単一の値にマッピングします。
  • これらのマップを使用して空白を埋めます。値を入力するときは、入力できる関連する空白を確認してください。

これにより、非常にコンパクトな出力が得られ、私のすべての要件を満たしているようです。

于 2009-11-24T16:12:40.603 に答える
0

1 つのノードから到達可能なすべてのノードを 1 つのセルにまとめるのはどうですか? たとえば、最初の DAG は次のようになります。

a   b        c
---------------
a1  [b1,b2]  
    b1       c1
    b2       c1
于 2009-11-20T20:24:23.217 に答える
0

ゾーン (a、b、c) 内に駅がある鉄道システム マップのように聞こえます。

一方向のすべての可能なルートのテーブルを生成できます。その場合、「a1、b1、c1」は a1->b1 を暗示しているように見えるため、a1->c1、b1->c1 しかない場合はそのようにフォーマットしないでください。

ゾーン a から始まり、各エッジを 1 回だけ使用し、残りの短いルートで終わる最長のルートをリストすることで、表を作成することができます。または、エッジが未使用のエッジを接続するか、ルートを延長する場合にのみ、エッジの再利用を許可します。

つまり、深さ優先検索を実行し、エッジを再利用しないようにします (未使用のエッジを含まないパスを拒否し、必要に応じてエンドポイントで使用済みのエッジをトリミングします)。

于 2009-11-20T20:52:16.557 に答える