interfaccia per definire rapporti ordine parziale:
interface IPartialComparer<T> {
int? Compare(T x, T y);
}
Compare dovrebbe restituire -1 se x < y, 0 se x = y, 1 se y < x e null se x e y sono non comparabile.
Il nostro obiettivo è quello di restituire un ordinamento degli elementi nell'ordine parziale, che rispetta l'enumerazione. Cioè, cerchiamo una sequenza e_1, e_2, e_3, ..., e_n degli elementi nell'ordine parziale tale che se i <= j e e_i è paragonabile a e_j quindi e_i <= e_j. Farò questo utilizzando una ricerca in profondità.
classe che implementa ordinamento topologico utilizzando in profondità di ricerca:
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();
}
}
classe Helper necessaria per la marcatura di nodi come visitato mentre si fa in profondità di ricerca:
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();
}
}
faccio alcuna pretesa che questo è la migliore implementazione dell'algoritmo ma credo che sia una corretta implementazione. Inoltre, non ho restituito un IOrderedEnumerable come richiesto ma è facile farlo una volta arrivati a questo punto.
L'algoritmo funziona facendo una ricerca in profondità attraverso gli elementi che aggiungono un elemento e per l'ordinamento lineare (rappresentato da _sorted nell'algoritmo) se abbiamo già aggiunto tutti i predecessori di e sono già stati aggiunti alla ordinazione . Quindi, per ogni elemento e, se non lo abbiamo già visitato, visitare i suoi predecessori e quindi aggiungere e. Così, questo è il nucleo dell'algoritmo:
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);
}
}
Come esempio, si consideri la parziale ordinamento definite su sottoinsiemi di {1, 2, 3} dove X < Y se X è un sottoinsieme di Y. A implementare ciò come segue:
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;
}
}
Poi con sets definita come l'elenco di sottoinsiemi di {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());
Ciò provoca l'ordine:
{}, {2}, {3}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}
che rispetta l'ordine parziale.
E 'stato molto divertente. Grazie.
Vorrei ree, questo è il modo più ragionevole per rappresentare l'ordine parziale. Anche se avessimo un modo per vedere se gli elementi sono comparabili o meno, non sarebbe chiaro dove mettere qualcosa in relazione a qualcosa a cui non è correlato. L'uguaglianza sembra essere il modo più semplice per fare questo – luke
Grazie per la risposta. Non ho ancora il tempo di esaminarlo profondamente. A prima vista, temo che l'uso di questi "default" potrebbe nascondere alcuni bug. Ad esempio, 'default (int)' è zero, ed è difficilmente il valore int minimo. Hai provato i valori negativi? Ad ogni modo, ci proverò domani mattina. – jpbochi
Ok, il codice funziona nonostante i "default". Qualsiasi valore inizialmente messo sulle variabili 'minime' viene sovrascritto nel primo 'foreach'. A proposito, il primo 'foreach' può essere scartato abbastanza facilmente. Sto testando alcune possibili ottimizzazioni sul tuo codice. Funziona molto comunque. :) – jpbochi