interfaz para definir la relación de orden parcial:
interface IPartialComparer<T> {
int? Compare(T x, T y);
}
Compare deberían volver -1 si x < y, 0 si x = y, 1 si y < x y null si x y y son No es comparable.
Nuestro objetivo es devolver un orden de los elementos en el orden parcial que respeta la enumeración. Es decir, buscamos una secuencia e_1, e_2, e_3, ..., e_n de los elementos en el orden parcial tal que si i <= j y e_i es comparable a e_j entonces e_i <= e_j. Haré esto usando una búsqueda en profundidad.
clase que implementa clasificación topológica utilizando primero en profundidad de búsqueda:
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();
}
}
Clase auxiliar necesaria para el marcado de los nodos como visitado mientras se hace primero en profundidad de búsqueda:
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();
}
}
No pretendo que este es la mejor implementación del algoritmo, pero creo que es una implementación correcta. Además, no me vuelvo un IOrderedEnumerable como usted pidió pero que es fácil de hacer una vez que estamos en este punto.
El algoritmo funciona haciendo una búsqueda en profundidad a través de los elementos de la adición de un elemento e a la ordenación lineal (representado por _sorted en el algoritmo) si ya hemos añadido todos los predecesores de e ya se han agregado a la ordenación . Por lo tanto, para cada elemento e, si todavía no hemos visitado, visitar sus predecesores y luego añadir e. Por lo tanto, este es el núcleo del 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);
}
}
Como ejemplo, considerar la parcial-pedido definido en subconjuntos de {1, 2, 3} donde X < Y si X es un subconjunto de Y. Implemento esto como sigue:
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;
}
}
Luego, con sets definida como la lista de subconjuntos de {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());
Esto resulta en la Orden:
{}, {2}, {3}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}
que respeta el orden parcial.
Eso fue muy divertido. Gracias.
I would ag ree, esta es la forma más razonable de representar el orden parcial. Incluso si tuviéramos una forma de ver si los elementos son comparables o no, no estaría claro dónde poner algo en relación con algo que no está relacionado. La igualdad parece ser la forma más directa de hacerlo – luke
Gracias por la respuesta. No tengo tiempo para examinarlo profundamente todavía. A primera vista, me temo que el uso de esos 'predeterminados' puede ocultar algunos errores. Por ejemplo, 'default (int)' es cero, y apenas es el valor int mínimo. ¿Has probado los valores negativos? De todos modos, lo intentaré mañana por la mañana. – jpbochi
Ok, el código funciona a pesar de los 'predeterminados'. Cualquier valor puesto inicialmente en las variables 'mínimas' se sobrescribe en el primer 'foreach'. Por cierto, el primer "foreach" se puede descartar con bastante facilidad. Estoy probando algunas posibles optimizaciones en tu código. Funciona de todos modos de todos modos. :) – jpbochi