Приветствую всех читателей Хабра! Решив написать эту статью, я обнаружил на Хабре много материалов по графам и, в частности, по топологической сортировке. Например, здесь довольно подробно описана теоретическая часть и приведены примеры основных алгоритмов. Поэтому не буду повторяться, а расскажу о практической области применения Topological sorting, а точнее, хочу поделиться личным опытом применения этого метода при разработке продуктов DevExpress. Из статьи станут понятны мотивы и причины, побудившие к использованию этого алгоритма. В конце я приведу наш вариант реализации алгоритма для сортировки зависимых объектов.
Область применения алгоритма сортировки в DevExpress
В одной из предыдущих статей мы рассказывали о планировщике XtraScheduler и его расширении для печати. Он включает в себя дизайнер отчетов, работающий с визуальными элементами. При проектировании в дизайнере внешнего вида печатной формы необходимо устанавливать связи между визуальными элементами отчета по принципу «главный-подчиненный». Эти зависимости должны определять способ передачи данных между элементами. Для внутренней реализации это подразумевает формирование правильного приоритета печати этих объектов.
Элементы по своей сути представляли ориентированный граф объектов, т.к. опции этих контролов однозначно определяли направление зависимости, задавая ссылку на главный объект.
Алгоритм топологической сортировки как нельзя лучше подходил для того, чтобы перед печатью выстроить зависимые объекты в нужном порядке, проанализировав связи между ними. Кроме того, зависимые контролы при выводе на печать использовали данные рендеринга главных контролов. Поэтому алгоритм был также применен для организации внутренних объектов кеширования данных, содержащих главный объект-итератор по данным и связанный с ним подчиненный список.
Где еще мы применяли алгоритм?
Немного позднее, в проекте XtraRichEdit при разработке импорта и экспорта стилей для документов в RTF и DOC форматах также возникла необходимость в правильном порядке получать объекты, содержащие зависимости между собой. Описанный алгоритм был обобщен и успешно применен и в этом случае.
Алгоритм-Т
Перейдем к нашей реализации алгоритма сортировки. В основе ее лежит описанный Алгоритм-Т из книги «Искусство программирования» Дональда Кнута (том 1 гл. 2.2.3). Поэтому, о деталях алгоритма вы можете почитать в оригинале, здесь я лишь приведу схему алгоритма для общего понимания идеи.
Почему мы выбрали этот алгоритм? Просто позволю себе немного процитировать автора.
«Анализ алгоритма Т достаточно просто можно выполнить с помощью закона Кирхгофа. Используя этот закон, время выполнения можно приблизительно оценить с помощью формулы с1*m + c2*n, где m — количество введенных отношений, n — количество объектов, а с1 и с2 — константы. Более быстрый алгоритм для решения этой задачи просто невозможно себе представить!»
Реализованный алгоритм расположен в сборке DevExpress.Data.dll в классе Algorithms, который наряду с топологической сортировкой содержит ряд других полезных алгоритмов.
namespace DevExpress.Utils {
public static class Algorithms {
public static IList<T> TopologicalSort<T>(IList<T> sourceObjects, IComparer<T> comparer) {
TopologicalSorter<T> sorter = new TopologicalSorter<T>();
return sorter.Sort(sourceObjects, comparer);
}
}
Использовать алгоритм крайне просто. Достаточно вызвать статический метод класса, передав ему необходимые параметры. Пример вызова выглядит следующим образом:
protected virtual IList<XRControl> SortControls(List<XRControl> sourceControls) {
return Algorithms.TopologicalSort<XRControl>(sourceControls, new ReportViewControlComparer());
}
Можно обойтись и без вызова статического метода, явно создав экземпляр объекта-сортировщика.
Исходный код класса-сортировщика, реализующего алгоритм я приведу в конце статьи.
Как видно из параметров, помимо списка объектов в метод передается специализированный объект-компарер. Если он не указан, то будет использоваться объект, заданный по умолчанию. На практике, объект-компарер обычно задан, так как именно в нем определяется логика сравнения, которая может опираться на свойства сравниваемых объектов. Кроме того, такой объект может реализовывать несколько интерфейсов IComparer одновременно для нескольких наследуемых типов.
В качестве примера подобного класса, приведу наш ReportViewControlComparer, который используется в XtraScheduler.Reporting библиотеке:
public class ReportViewControlComparer : IComparer<XRControl>, IComparer<ReportViewControlBase> {
#region IComparer<XRControl> Members
public int Compare(XRControl x, XRControl y) {
return CompareCore(x as ReportRelatedControlBase, y as ReportViewControlBase);
}
#endregion
#region IComparer<ReportViewControlBase> Members
public int Compare(ReportViewControlBase x, ReportViewControlBase y) {
return CompareCore(x as ReportRelatedControlBase, y);
}
#endregion
int CompareCore(ReportRelatedControlBase slave, ReportViewControlBase master) {
if (slave != null && master != null) {
if (slave.LayoutOptionsHorizontal.MasterControl == master ||
slave.LayoutOptionsVertical.MasterControl == master)
return 1;
}
return 0;
}
}
Пример работы в приложении
Для демонстрации работы алгоритма создадим консольное приложение. В качестве примера графа возьмем простой граф из 5 узлов (см. рисунок в начале статьи).
G=({a,b,c,d,e}, {(a,b), (a,c),(a, d), (a, e),(b, d), (c, d), (c, e), (d, e)})
Для представления графа будет использоваться простой класс, определяющий узел со списком связанных с ним других узлов.
public class GraphNode {
List<GraphNode> linkedNodes = new List<GraphNode>();
object id;
public GraphNode(object id) {
this.id = id;
}
public List<GraphNode> LinkedNodes { get { return linkedNodes; } }
public object Id { get { return id; } }
}
Код самого приложения приведен ниже:
class Program {
static void Main(string[] args) {
DoDXTopologicalSort();
}
private static void DoDXTopologicalSort() {
GraphNode[] list = PrepareNodes();
Console.WriteLine("DX Topological Sorter");
Console.WriteLine(new string('-', 21));
Console.WriteLine("Nodes:");
GraphNode[] list = PrepareNodes();
PrintNodes(list);
IComparer<GraphNode> comparer = new GraphNodeComparer();
IList<GraphNode> sortedNodes = DevExpress.Utils.Algorithms.TopologicalSort<GraphNode>(list, comparer);
Console.WriteLine("Sorted nodes:");
PrintNodes(sortedNodes);
Console.Read();
}
static GraphNode[] PrepareNodes() {
GraphNode nodeA = new GraphNode("A");
GraphNode nodeB = new GraphNode("B");
GraphNode nodeC = new GraphNode("C");
GraphNode nodeD = new GraphNode("D");
GraphNode nodeE = new GraphNode("E");
nodeA.LinkedNodes.AddRange(new GraphNode[] { nodeB, nodeC, nodeE });
nodeB.LinkedNodes.Add(nodeD);
nodeC.LinkedNodes.AddRange(new GraphNode[] { nodeD, nodeE });
nodeD.LinkedNodes.Add(nodeE);
return new GraphNode[] { nodeD, nodeA, nodeC, nodeE, nodeB };
}
static void PrintNodes(IList<GraphNode> list) {
for (int i = 0; i < list.Count; i++) {
string s = string.Empty;
if (i > 0)
s = "->";
s += list[i].Id.ToString();
Console.Write(s);
}
Console.WriteLine("\r\n");
}
}
Непосредственно связи графа задаются в методе PrepareNodes. В данном случае зависимости созданы произвольным образом.
Для сравнения узлов потребуется еще класс GraphNodeComparer
public class GraphNodeComparer : IComparer<GraphNode> {
public int Compare(GraphNode x, GraphNode y) {
if (x.LinkedNodes.Contains(y))
return -1;
if (y.LinkedNodes.Contains(x))
return 1;
return 0;
}
}
После запуска приложения мы получим отсортированный список узлов и в консоль будет выведено
A->B->C->D->E.
Результат работы программы показан на рисунке ниже:
Исходный код сортировщика
Как я обещал выше, привожу код реализации алгоритма топологической сортировки.
namespace DevExpress.Utils.Implementation {
#region TopologicalSorter
public class TopologicalSorter<T> {
#region Node
public class Node {
int refCount;
Node next;
public Node(int refCount, Node next) {
this.refCount = refCount;
this.next = next;
}
public int RefCount { get { return refCount; } }
public Node Next { get { return next; } }
}
#endregion
#region Fields
int[] qLink;
Node[] nodes;
IList<T> sourceObjects;
IComparer<T> comparer;
#endregion
#region Properties
protected internal Node[] Nodes { get { return nodes; } }
protected internal int[] QLink { get { return qLink; } }
protected IComparer<T> Comparer { get { return comparer; } }
protected internal IList<T> SourceObjects { get { return sourceObjects; } }
#endregion
protected IComparer<T> GetComparer() {
return Comparer != null ? Comparer : System.Collections.Generic.Comparer<T>.Default;
}
protected bool IsDependOn(T x, T y) {
return GetComparer().Compare(x, y) > 0;
}
public IList<T> Sort(IList<T> sourceObjects, IComparer<T> comparer) {
this.comparer = comparer;
return Sort(sourceObjects);
}
public IList<T> Sort(IList<T> sourceObjects) {
this.sourceObjects = sourceObjects;
int n = sourceObjects.Count;
if (n < 2)
return sourceObjects;
Initialize(n);
CalculateRelations(sourceObjects);
int r = FindNonRelatedNodeIndex();
IList<T> result = ProcessNodes(r);
return result.Count > 0 ? result : sourceObjects;
}
protected internal void Initialize(int n) {
int count = n + 1;
this.qLink = new int[count];
this.nodes = new Node[count];
}
protected internal void CalculateRelations(IList<T> sourceObjects) {
int n = sourceObjects.Count;
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
if (!IsDependOn(sourceObjects[y], sourceObjects[x]))
continue;
int minIndex = x + 1;
int maxIndex = y + 1;
QLink[maxIndex]++;
Nodes[minIndex] = new Node(maxIndex, Nodes[minIndex]);
}
}
}
protected internal int FindNonRelatedNodeIndex() {
int r = 0;
int n = SourceObjects.Count;
for (int i = 0; i <= n; i++) {
if (QLink[i] == 0) {
QLink[r] = i;
r = i;
}
}
return r;
}
protected virtual IList<T> ProcessNodes(int r) {
int n = sourceObjects.Count;
int k = n;
int f = QLink[0];
List<T> result = new List<T>(n);
while (f > 0) {
result.Add(sourceObjects[f - 1]);
k--;
Node node = Nodes[f];
while (node != null) {
node = RemoveRelation(node, ref r);
}
f = QLink[f];
}
return result;
}
Node RemoveRelation(Node node, ref int r) {
int suc_p = node.RefCount;
QLink[suc_p]--;
if (QLink[suc_p] == 0) {
QLink[r] = suc_p;
r = suc_p;
}
return node.Next;
}
}
#endregion
* This source code was highlighted with Source Code Highlighter.Выводы
При необходимости в определенном порядке обработки зависимых друг от друга объектов, их можно предварительно упорядочить, применив алгоритм топологической сортировки. В результате строится корректная последовательность объектов и выполнения действий над ними.
Предложенный в статье алгоритм предоставляет следующие преимущества:
- использование обобщения (generic), т.е. он может быть применен для сортировки объектов различных типов
- возможность задания своего класса Comparer, т.е он позволяет реализовать различную логику сравнения объектов.
- линейность алгоритма, алгоритм не рекурсивный
Пример с исходным текстом доступен здесь.
Надеюсь, приведенный материал окажется вам полезным в будущих проектах.
