Schnittstelle partielle Ordnung Beziehung zu definieren:
interface IPartialComparer<T> {
int? Compare(T x, T y);
}
Compare-1 wenn x < y zurückkehren sollte, 0 wenn x = y, 1 wenn y < x und null wenn x und y sind nicht vergleichbar.
Unser Ziel ist es, eine Reihenfolge der Elemente in der Teilaufordnung zurückzugeben, die die Aufzählung berücksichtigt. Das heißt, wir suchen eine Sequenz e_1, e_2, e_3, ..., e_n der Elemente in der Teilaufordnung, so dass, wenn i <= j und e_i vergleichbar ist mit e_j dann e_i <= e_j. Ich mache das mit einer Tiefensuche.
Klasse, die topologische Sortierung mittels Tiefensuche implementiert:
class TopologicalSorter {
class DepthFirstSearch<TElement, TKey> {
readonly IEnumerable<TElement> _elements;
readonly Func<TElement, TKey> _selector;
readonly IPartialComparer<TKey> _comparer;
HashSet<TElement> _visited;
Dictionary<TElement, TKey> _keys;
List<TElement> _sorted;
public DepthFirstSearch(
IEnumerable<TElement> elements,
Func<TElement, TKey> selector,
IPartialComparer<TKey> comparer
) {
_elements = elements;
_selector = selector;
_comparer = comparer;
var referenceComparer = new ReferenceEqualityComparer<TElement>();
_visited = new HashSet<TElement>(referenceComparer);
_keys = elements.ToDictionary(
e => e,
e => _selector(e),
referenceComparer
);
_sorted = new List<TElement>();
}
public IEnumerable<TElement> VisitAll() {
foreach (var element in _elements) {
Visit(element);
}
return _sorted;
}
void Visit(TElement element) {
if (!_visited.Contains(element)) {
_visited.Add(element);
var predecessors = _elements.Where(
e => _comparer.Compare(_keys[e], _keys[element]) < 0
);
foreach (var e in predecessors) {
Visit(e);
}
_sorted.Add(element);
}
}
}
public IEnumerable<TElement> ToplogicalSort<TElement, TKey>(
IEnumerable<TElement> elements,
Func<TElement, TKey> selector, IPartialComparer<TKey> comparer
) {
var search = new DepthFirstSearch<TElement, TKey>(
elements,
selector,
comparer
);
return search.VisitAll();
}
}
Helper-Klasse, die für Knoten Markierung als besucht, während der Tiefensuche zu tun:
class ReferenceEqualityComparer<T> : IEqualityComparer<T> {
public bool Equals(T x, T y) {
return Object.ReferenceEquals(x, y);
}
public int GetHashCode(T obj) {
return obj.GetHashCode();
}
}
Ich mache keinen Anspruch, dass diese ist die beste Implementierung des Algorithmus, aber ich glaube, dass es eine korrekte Implementierung ist. Außerdem habe ich keine IOrderedEnumerable wie gewünscht zurückgeben, aber das ist einfach zu tun, sobald wir an diesem Punkt sind.
Der Algorithmus arbeitet durch eine Tiefensuche durch die Elemente tun ein Element e auf die lineare Ordnung Zugabe (von _sorted im Algorithmus dargestellt), wenn wir schon alle Vorgänger von e hinzugefügt haben bereits auf die Bestellung hinzugefügt . Daher sollten Sie für jedes Element e, wenn wir es nicht bereits besucht haben, seine Vorgänger aufrufen und dann e hinzufügen. Somit ist dies der Kern des Algorithmus:
public void Visit(TElement element) {
// if we haven't already visited the element
if (!_visited.Contains(element)) {
// mark it as visited
_visited.Add(element);
var predecessors = _elements.Where(
e => _comparer.Compare(_keys[e], _keys[element]) < 0
);
// visit its predecessors
foreach (var e in predecessors) {
Visit(e);
}
// add it to the ordering
// at this point we are certain that
// its predecessors are already in the ordering
_sorted.Add(element);
}
}
Als Beispiel betrachte man die Teilordnungs definiert auf Teilmengen von {1, 2, 3} wo X < Y wenn eine Teilmenge von XY ist. Ich dies wie folgt implementieren:
public class SetComparer : IPartialComparer<HashSet<int>> {
public int? Compare(HashSet<int> x, HashSet<int> y) {
bool xSubsety = x.All(i => y.Contains(i));
bool ySubsetx = y.All(i => x.Contains(i));
if (xSubsety) {
if (ySubsetx) {
return 0;
}
return -1;
}
if (ySubsetx) {
return 1;
}
return null;
}
}
dann mit sets als Liste definiert von Teilmengen von {1, 2, 3}
List<HashSet<int>> sets = new List<HashSet<int>>() {
new HashSet<int>(new List<int>() {}),
new HashSet<int>(new List<int>() { 1, 2, 3 }),
new HashSet<int>(new List<int>() { 2 }),
new HashSet<int>(new List<int>() { 2, 3}),
new HashSet<int>(new List<int>() { 3 }),
new HashSet<int>(new List<int>() { 1, 3 }),
new HashSet<int>(new List<int>() { 1, 2 }),
new HashSet<int>(new List<int>() { 1 })
};
TopologicalSorter s = new TopologicalSorter();
var sorted = s.ToplogicalSort(sets, set => set, new SetComparer());
Daraus ergibt sich die Reihenfolge:
{}, {2}, {3}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}
, die die partielle Ordnung respektiert.
Das war eine Menge Spaß. Vielen Dank.
Ich würde ag ree, das ist der vernünftigste Weg, die Teilaufordnung zu repräsentieren. Selbst wenn wir einen Weg hätten, also zu sehen, ob Elemente vergleichbar sind oder nicht, wäre es nicht klar, wo etwas in Beziehung zu etwas steht, mit dem es nicht verwandt ist. Gleichheit scheint der einfachste Weg zu sein, dies zu tun – luke
Danke für die Antwort. Ich habe noch keine Zeit, es noch einmal gründlich zu untersuchen. Auf den ersten Blick fürchte ich, dass die Verwendung dieser 'Standard's einige Bugs verbergen könnte. Zum Beispiel ist 'default (int)' gleich null und es ist kaum der minimale int-Wert. Hast du Negativwerte probiert? Jedenfalls werde ich es morgen früh versuchen. – jpbochi
Ok, der Code funktioniert trotz der 'default's. Jeder anfänglich auf die 'Minimum'-Variablen gesetzte Wert wird in der ersten' foreach 'überschrieben. BTW, die erste 'foreach' kann ziemlich leicht verworfen werden. Ich teste einige mögliche Optimierungen für Ihren Code. Funktioniert sowieso sehr gut. :) – jpbochi