問題タブ [topological-sort]

おそらく、小さな例で最もよく説明されています。
関係を考えると

正しい出力は

つまり、特定の関係が成立する順序はすべて有効です。

実装が最も簡単なソリューションに最も興味がありますが、速度と時間の点で最高のO（n）も興味深いものです。

PriorityQueueを使用して、グラフのトポロジカルソートを実行したいと思います。簡潔にするために、コンパレータには匿名の内部クラスを使用したいと思います。ただし、g見ているノードの程度を判断するには、グラフにアクセスする必要があります。これは可能ですか？

修正されたコード

半順序関係を持つアイテムのリストがあります。e、リストは半順序集合と見なすことができます。この質問と同じ方法でこのリストを並べ替えたいと思います。そこで正しく答えられているように、これはトポロジカルソートとして知られています。

問題を解決するためのかなり単純な既知のアルゴリズムがあります。LINQのような実装が必要です。

すでにOrderBy拡張法を使ってみましたが、トポロジカルソートはできないと思います。問題は、IComparer<TKey>インターフェースが半順序を表すことができないことです。これは、Compareメソッドが基本的に3種類の値を返すことができるために発生します。つまり、ゼロ、負、正の3種類の値を返します。つまり、それぞれ、等しい、より小さい、より大きいという意味 です。有効な解決策は、関係のないものを返す方法があった場合にのみ可能です。

私の偏った見方からすると、私が探している答えは、次のIPartialOrderComparer<T>ようなインターフェースと拡張メソッドによって構成されている可能性があります。

これはどのように実装されますか？IPartialOrderComparer<T>インターフェイスはどのようになりますか？別のアプローチをお勧めしますか？見たいです。半順序を表すためのより良い方法があるかもしれませんが、私にはわかりません。

職場のインフラストラクチャを svn の代わりに git を使用するように変換しています。全体的な移行は順調に進んでいますが、SQL スキーマの移行を行うために開発したツールがあります。

個々のスキーマ変更の依存関係に対処するために、移行スクリプトは subversion キーワード置換を使用して、最後に変更されたリビジョン番号をスキーマに入れました。git では、改訂履歴が非線形であるため、同じ考え方を使用することはできません (そして、分岐機能を完全に利用するつもりです)。

したがって、コミット ID のトポロジ的にソートされたリストを git から取得するにはどうすればよいですか? それを除けば、この問題を処理する方法について誰かがより良いアイデアを持っていますか?

データベース内のテーブル間のいくつかの依存関係をソートするソース削除アルゴリズムを作成しましたが、サイクルがあることがわかりました。簡単にするために、テーブル A、B、C、および D があるとします。エッジは次のようになります。

ご覧のとおり、ここには 2 つのサイクルがあります。1 つは A と B の間にあり、もう 1 つは 4 つすべての間にあります。このタイプの並べ替えは、常に最大のサイクルで停止しますか? それとも必ずしもそうとは限りませんか？

私のガールフレンドはインタビューでこの質問を受けました. 私はそれがとても好きだったので、それを共有したいと思いました... 辞書 (単語の配列) を受け取るアルゴリズムを書きます. 配列は辞書順でソートされますが、abc の順序は何でもかまいません。たとえば、z、y、x、..、c、b、a などです。または、完全にめちゃくちゃになる可能性があります: d、g、w、y、... すべての abc 文字を含める必要さえなく、最終的には文字である必要はまったくありません。文字列を形成する任意の記号である可能性があります。たとえば、5、α、!、@、θ で構成されている可能性があります。文字が何であるかを発見するのはあなたのアルゴリズム次第です (簡単な部分)。

アルゴリズムは、シンボルの正しい辞書式順序を返す必要があります。

注/考慮事項: 1. 特定の辞書について、常にすべての文字の完全な順序を見つけることができますか? 単語が 1 つしかなく、記号が 1 つ以上ある辞書を考えてみましょう... 2. 辞書にエラーがないことを想定することはできません。アルゴリズムは、辞書に矛盾が含まれているかどうかを判断し、エラーがあることを出力する必要があります。3. ヒント: シンボル間の関係を表すのに適したデータ構造を考えてください。これにより、問題がはるかに簡単になります。

おそらく明日、解決策を投稿します。決してそれが最も効率的だと主張しているわけではありません。他の人の考えをまず見てみたい。質問をお楽しみください

PSソリューションを投稿するのに最適な形式は疑似コードを使用することだと思いますが、これはあなたの考慮に任せます

タプルのリストを上に示しました。次のロジックで並べ替える必要があります。各タプルの2番目の要素は1番目の要素に依存します。たとえば、（コース、セッション）->セッションはコースに依存します。

依存関係の優先度に基づいてソートされたリストが必要です。少ないオブジェクトまたは独立したオブジェクトが最初に来るので、出力は次のようになります。

トポロジカル ソートを実行する必要がある一連のデータがあり、いくつかの仮定と制約があり、これに適した既存の効率的なアルゴリズムを誰かが知っているかどうか疑問に思っていました。

• データの関係は、DAG を形成することが知られています (したがって、心配する循環はありません)。
• A から B へのエッジは、A が B に依存していることを示しているため、B はトポロジー順序で A の前に表示される必要があります。
• グラフは必ずしも接続されているわけではありません。つまり、任意の 2 つのノード N と M について、エッジをたどって N から M に到達する方法がない場合があります (エッジの方向を無視しても)。
• データの関係は単独でリンクされています。これは、A から B に向かうエッジがある場合、A ノードだけがエッジの存在に関する情報を含むことを意味します。

問題は次のように定式化できます。

入ってくるエッジを持つ場合と持たない場合があるSグラフG内のノードのセットが与えられた場合、セット内の任意のノードから到達可能な(エッジ方向に従う)内のすべてのノードで構成されるサブグラフのトポロジー順序を見つけます。G'GS

Sこれは、セット内のノードに着信エッジがないことを必要とするため、トポロジカルソートの通常のアプローチを混乱させます。これは、私の場合には当てはまりません。病理学的ケースは次のとおりです。

どこでS = {B, C}。適切な順序付けは になりますD, B, Cが、通常のトポロジカル ソート アルゴリズムがたまたまB前に考慮した場合、C最終的には になりC, D, Bます。これは完全に間違っています。A(は から到達できないため、結果の順序には表示されないことに注意してくださいS。これは、 のすべてのノードにS着信エッジがある可能性がある例を示すためにあります)

さて、これは長い間解決されてきた問題であると想像しなければなりません。なぜなら、これは本質的に、1 つのインストール コマンドで複数のパッケージを指定するときにプログラムが好むものであり、実行しなければならないaptものだからです。yumただし、「依存関係解決アルゴリズム」などのキーフレーズを検索すると、この特定のケースを処理しない通常のトポロジカル ソートを説明する結果が得られます。

これを行う方法はいくつか考えられますが、どれも特に洗練されているとは思えません。誰かが適切なアルゴリズムへのポインタを持っているかどうか、できればデータを 1 回のパスで操作できるアルゴリズムを持っているかどうか疑問に思っていました。

Java Jung2 グラフ ライブラリが、開始ベクトルを指定して Digraph (有向グラフ) をトラバースする組み込み機能を提供するかどうかを知っている人はいますか? BFSDistanceLabeler距離のマップを返すクラスがあることがわかりましたが、それは可能ですが、値を並べ替え (最大距離が最初)、並べ替えられたセットを反復処理する必要があります。

Maven を使用して Javascript の依存関係管理機能を作成しているので、Jung2 を使用して依存関係グラフを維持することを考えていました。

私はコレクションを持っています：

ペアの最初のアイテムは何らかのオブジェクト (アイテム) であり、2 番目のアイテムは最初のアイテムが依存する同じタイプのオブジェクトのコレクションです。依存関係を順番に取得したいList<Item>ので、最初の要素などに依存するアイテムはありません (循環依存関係はありません!)。

入力：

結果：

ありがとうございました。

解決：

トポロジカル ソーティング( Loïc Févrierのアイデアに感謝)

と

C#の例、Javaの例 (素晴らしい例を提供してくれたxcudに 感謝)