Интерфейс для определения отношения частичного порядка:
interface IPartialComparer<T> {
int? Compare(T x, T y);
}
Compare должен возвращать -1 если x < y, 0 если x = y, 1 если y < x и null если x и y являются не сопоставимы.
Наша цель - вернуть порядок элементов в частичном порядке, который соответствует перечислению. То есть, мы ищем последовательность элементов в частичном порядке, так что если i <= j и e_i сопоставимо с e_j, то e_i <= e_j. Я сделаю это, используя поиск по глубине.
Класс, который реализует топологическую сортировку с помощью поиска в глубину:
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();
}
}
вспомогательный класс, необходимый для маркировки узлов как посещенные при выполнении поиска в глубину:
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();
}
}
Я не утверждаю, что это является наилучшей реализацией алгоритма, но я считаю, что это правильная реализация. Кроме того, я не возвращал IOrderedEnumerable, как вы просили, но это легко сделать, когда мы находимся на этом этапе.
Алгоритм работы, выполнив поиска в глубину через элементы добавления элемента e в линейном порядке (в лице _sorted в алгоритме), если мы уже добавили все предшественники e уже были добавлены к порядку , Следовательно, для каждого элемента e, если мы его еще не посетили, посетите его предшественники, а затем добавьте e. Таким образом, это является ядром алгоритма:
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);
}
}
В качестве примера, рассмотрим частичную упорядоченность, определенную на подмножествах {1, 2, 3} где X < Y, если X является подмножеством Y. Я реализовать это следующим образом:
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;
}
}
Затем с sets определяется как список подмножеств из {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());
Это приводит к упорядочению:
{}, {2}, {3}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}
, уважающее частичный порядок.
Это было очень весело. Благодарю.
Я бы ag ree, это самый разумный способ представить частичный порядок. Даже если бы у нас был такой способ, чтобы увидеть, сопоставимы ли элементы или нет, было бы неясно, где поставить что-то по отношению к чему-то, к чему это не связано. Равенство, кажется, самый простой способ сделать это – luke
Спасибо за ответ. У меня нет времени изучать его глубоко. На первый взгляд, я боюсь, что использование этих 'default' там может скрыть некоторые ошибки. Например, 'default (int)' равно нулю, и это вряд ли минимальное значение int. Вы пробовали отрицательные значения? Во всяком случае, я попробую завтра утром. – jpbochi
Хорошо, код работает, несмотря на 'default'. Любое значение, первоначально заданное на «минимальных» переменных, перезаписывается в первом 'foreach'. BTW, первый «foreach» можно легко отбросить. Я тестирую некоторые возможные варианты оптимизации вашего кода. Работает в любом случае. :) – jpbochi