ノードがソートされたリストに格納されているグラフがあるとします。トポロジーの順序が定義されていない元の順序を維持しながら、このグラフをトポロジー的に並べ替えたいと思います。これに適したアルゴリズムはありますか?
5166 次
6 に答える
17
1 つの可能性は、辞書編集的に最小のトポロジー次数を計算することです。このアルゴリズムは、(まだ処理されていないノードに対して) 有効なインディグリーがゼロであるノードを含む優先キューを維持することです。最小のラベルを持つノードを繰り返しキューから取り出し、それを順序に追加し、後続ノードの有効なイン次数を減らし、イン次数がゼロになったノードをキューに追加します。これにより、btilly の例では 1234567890 が生成されますが、通常、反転は最小化されません。
このアルゴリズムについて私が気に入っている特性は、出力が明確な定義を持ち、明らかに 1 つの順序だけで満たされることと、反転 (x < y にもかかわらずノード x がノード y の後に現れる) がある場合は常に、x の最大の依存関係が y の最大の依存関係よりも大きいことです。これは、x と y を反転するための一種の「言い訳」です。必然的に、制約がない場合、lex の最小順序はソート順になります。
于 2012-06-27T23:09:34.187 に答える
6
問題は 2 つあります。
- トポロジカルソート
- 安定ソート
多くのエラーと試行錯誤の末、バブル ソートに似ているがトポロジカルな順序基準を持つ単純なアルゴリズムを思いつきました。
完全なエッジの組み合わせを使用して完全なグラフでアルゴリズムを徹底的にテストしたので、証明済みと見なすことができます。
循環依存は許容され、元の要素の順序に従って解決されます。結果の順序は完全であり、可能な限り最も近い一致を表しています。
C# のソース コードは次のとおりです。
static class TopologicalSort
{
/// <summary>
/// Delegate definition for dependency function.
/// </summary>
/// <typeparam name="T">The type.</typeparam>
/// <param name="a">The A.</param>
/// <param name="b">The B.</param>
/// <returns>
/// Returns <c>true</c> when A depends on B. Otherwise, <c>false</c>.
/// </returns>
public delegate bool TopologicalDependencyFunction<in T>(T a, T b);
/// <summary>
/// Sorts the elements of a sequence in dependency order according to comparison function with Gapotchenko algorithm.
/// The sort is stable. Cyclic dependencies are tolerated and resolved according to original order of elements in sequence.
/// </summary>
/// <typeparam name="T">The type of the elements of source.</typeparam>
/// <param name="source">A sequence of values to order.</param>
/// <param name="dependencyFunction">The dependency function.</param>
/// <param name="equalityComparer">The equality comparer.</param>
/// <returns>The ordered sequence.</returns>
public static IEnumerable<T> StableOrder<T>(
IEnumerable<T> source,
TopologicalDependencyFunction<T> dependencyFunction,
IEqualityComparer<T> equalityComparer)
{
if (source == null)
throw new ArgumentNullException("source");
if (dependencyFunction == null)
throw new ArgumentNullException("dependencyFunction");
if (equalityComparer == null)
throw new ArgumentNullException("equalityComparer");
var graph = DependencyGraph<T>.TryCreate(source, dependencyFunction, equalityComparer);
if (graph == null)
return source;
var list = source.ToList();
int n = list.Count;
Restart:
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < i; ++j)
{
if (graph.DoesXHaveDirectDependencyOnY(list[j], list[i]))
{
bool jOnI = graph.DoesXHaveTransientDependencyOnY(list[j], list[i]);
bool iOnJ = graph.DoesXHaveTransientDependencyOnY(list[i], list[j]);
bool circularDependency = jOnI && iOnJ;
if (!circularDependency)
{
var t = list[i];
list.RemoveAt(i);
list.Insert(j, t);
goto Restart;
}
}
}
}
return list;
}
/// <summary>
/// Sorts the elements of a sequence in dependency order according to comparison function with Gapotchenko algorithm.
/// The sort is stable. Cyclic dependencies are tolerated and resolved according to original order of elements in sequence.
/// </summary>
/// <typeparam name="T">The type of the elements of source.</typeparam>
/// <param name="source">A sequence of values to order.</param>
/// <param name="dependencyFunction">The dependency function.</param>
/// <returns>The ordered sequence.</returns>
public static IEnumerable<T> StableOrder<T>(
IEnumerable<T> source,
TopologicalDependencyFunction<T> dependencyFunction)
{
return StableOrder(source, dependencyFunction, EqualityComparer<T>.Default);
}
sealed class DependencyGraph<T>
{
private DependencyGraph()
{
}
public IEqualityComparer<T> EqualityComparer
{
get;
private set;
}
public sealed class Node
{
public int Position
{
get;
set;
}
List<T> _Children = new List<T>();
public IList<T> Children
{
get
{
return _Children;
}
}
}
public IDictionary<T, Node> Nodes
{
get;
private set;
}
public static DependencyGraph<T> TryCreate(
IEnumerable<T> source,
TopologicalDependencyFunction<T> dependencyFunction,
IEqualityComparer<T> equalityComparer)
{
var list = source as IList<T>;
if (list == null)
list = source.ToArray();
int n = list.Count;
if (n < 2)
return null;
var graph = new DependencyGraph<T>();
graph.EqualityComparer = equalityComparer;
graph.Nodes = new Dictionary<T, Node>(n, equalityComparer);
bool hasDependencies = false;
for (int position = 0; position < n; ++position)
{
var element = list[position];
Node node;
if (!graph.Nodes.TryGetValue(element, out node))
{
node = new Node();
node.Position = position;
graph.Nodes.Add(element, node);
}
foreach (var anotherElement in list)
{
if (equalityComparer.Equals(element, anotherElement))
continue;
if (dependencyFunction(element, anotherElement))
{
node.Children.Add(anotherElement);
hasDependencies = true;
}
}
}
if (!hasDependencies)
return null;
return graph;
}
public bool DoesXHaveDirectDependencyOnY(T x, T y)
{
Node node;
if (Nodes.TryGetValue(x, out node))
{
if (node.Children.Contains(y, EqualityComparer))
return true;
}
return false;
}
sealed class DependencyTraverser
{
public DependencyTraverser(DependencyGraph<T> graph)
{
_Graph = graph;
_VisitedNodes = new HashSet<T>(graph.EqualityComparer);
}
DependencyGraph<T> _Graph;
HashSet<T> _VisitedNodes;
public bool DoesXHaveTransientDependencyOnY(T x, T y)
{
if (!_VisitedNodes.Add(x))
return false;
Node node;
if (_Graph.Nodes.TryGetValue(x, out node))
{
if (node.Children.Contains(y, _Graph.EqualityComparer))
return true;
foreach (var i in node.Children)
{
if (DoesXHaveTransientDependencyOnY(i, y))
return true;
}
}
return false;
}
}
public bool DoesXHaveTransientDependencyOnY(T x, T y)
{
var traverser = new DependencyTraverser(this);
return traverser.DoesXHaveTransientDependencyOnY(x, y);
}
}
}
そして、小さなサンプル アプリケーション:
class Program
{
static bool DependencyFunction(char a, char b)
{
switch (a + " depends on " + b)
{
case "A depends on B":
return true;
case "B depends on D":
return true;
default:
return false;
}
}
static void Main(string[] args)
{
var source = "ABCDEF";
var result = TopologicalSort.StableOrder(source.ToCharArray(), DependencyFunction);
Console.WriteLine(string.Concat(result));
}
}
入力要素 {A, B, C, D, E, F} を指定すると、A は B に依存し、B は D に依存します。出力は {D, B, A, C, E, F} です。
更新:安定したトポロジカル ソートの目的、アルゴリズム、およびその証明に関する小さな記事 を書きました。これがより多くの説明を提供し、開発者や研究者に役立つことを願っています.
于 2014-07-09T17:11:55.197 に答える
3
探しているものを指定するには基準が不十分です。たとえば、有向成分が 2 つあるグラフを考えてみましょう。
1 -> 2 -> 3 -> 4 -> 5
6 -> 7 -> 8 -> 9 -> 0
次の種類のうち、どれが好きですか?
6, 7, 8, 9, 0, 1, 2, 3, 4, 5
1, 2, 3, 4, 5, 6, 7, 8, 9, 0
最初の結果は、最下位のノードをリストの先頭にできるだけ近づけることによって、すべての関係を断ち切った結果です。よって0勝。2 番目の結果は、トポロジカル ソートで A < B および B が A の前に現れる回数を最小限に抑えようとする結果です。どちらも合理的な答えです。2番目はおそらくもっと楽しいです。
最初のアルゴリズムを簡単に作成できます。まず、最下位のノードを取得し、幅優先検索を実行して、最短のルート ノードまでの距離を特定します。同点の場合は、そのような最短パスに表示される可能性のあるノードのセットを特定します。そのセットの最下位のノードを取り、そこからルートまでの可能な限り最良のパスを配置し、開始した最下位のノードからルートまでの可能な限り最良のパスを配置します。トポロジカル ソートにまだ含まれていない、次に低いノードを検索し、続行します。
より快適なバージョンのアルゴリズムを作成することは、はるかに難しいようです。実際に NP 完全であることを強く示唆する関連問題については、http://en.wikipedia.org/wiki/Feedback_arc_setを参照してください。
于 2012-06-27T18:20:39.983 に答える