April 20, 2011 at 11:00And again about topological sorting ...
Greetings to all readers of Habr! Having decided to write this article, I found on Habré a lot of materials on graphs, and, in particular, on topological sorting . For example, here the theoretical part is described in rather detail and examples of basic algorithms are given. Therefore, I will not repeat myself, but will talk about the practical field of application of Topological sorting , or rather, I want to share my personal experience with this method when developing DevExpress products . From the article, the motives and reasons that prompted the use of this algorithm will become clear. At the end I will give our version of the algorithm for sorting dependent objects.
Scope of the sorting algorithm in DevExpress
In a previous article, we talked about the XtraScheduler scheduler and its print extension. It includes a report designer that works with visual elements. When designing the appearance of a printed form in a designer, it is necessary to establish links between the visual elements of the report on the principle of “master-subordinate”. These dependencies should determine how data is transferred between the elements. For internal implementation, this implies the formation of the correct print priority for these objects.
Elements in essence represented a directed graph of objects, because the options of these controls uniquely determined the direction of the dependency by setting a link to the main object.
The topological sorting algorithm was the best suited to build dependent objects in the right order before printing, analyzing the relationships between them. In addition, the dependent controls used to print the main controls when printing. Therefore, the algorithm was also used to organize internal data caching objects containing the main iterator object according to the data and a subordinate list associated with it.
Where else have we applied the algorithm?
A little later, in the XtraRichEdit project , when developing the import and export of styles for documents in RTF and DOC formats, it also became necessary to receive objects containing dependencies in the correct order. The described algorithm was generalized and successfully applied in this case.
Algorithm-T
Let's move on to our implementation of the sorting algorithm. It is based on the described Algorithm-T from the book "The Art of Programming" by Donald Knuth (Volume 1 of Chapter 2.2.3). Therefore, you can read about the details of the algorithm in the original, here I will only give a diagram of the algorithm for a general understanding of the idea.
Why did we choose this algorithm? Just let me quote the author a little.
“An analysis of the T algorithm can be quite simply done using Kirchhoff’s law. Using this law, the execution time can be estimated using the formula c1 * m + c2 * n, where m is the number of entered relations, n is the number of objects, and c1 and c2 are constants. A faster algorithm to solve this problem is simply impossible to imagine! ”
The implemented algorithm is located in the DevExpress.Data.dll assembly in the Algorithms class , which along with topological sorting contains a number of other useful algorithms.
namespace DevExpress.Utils {
public static class Algorithms {
public static IList TopologicalSort(IList sourceObjects, IComparer comparer) {
TopologicalSorter sorter = new TopologicalSorter();
return sorter.Sort(sourceObjects, comparer);
}
}
Using the algorithm is extremely simple. It is enough to call the static method of the class, passing it the necessary parameters. An example call is as follows:
protected virtual IList SortControls(List sourceControls) {
return Algorithms.TopologicalSort(sourceControls, new ReportViewControlComparer());
}
You can do without calling the static method by explicitly creating an instance of the sorter object.
The source code of the sorter class that implements the algorithm will be given at the end of the article.
As can be seen from the parameters, in addition to the list of objects, a specialized comparator object is passed to the method. If it is not specified, then the default object will be used. In practice, the comparator object is usually defined, since it is in it that the comparison logic is determined, which can be based on the properties of the compared objects. In addition, such an object can implement several IComparer interfaces simultaneously for several inherited types.
As an example of such a class, I’ll give our ReportViewControlComparer, which is used in the XtraScheduler.Reporting library:
public class ReportViewControlComparer : IComparer, IComparer {
#region IComparer Members
public int Compare(XRControl x, XRControl y) {
return CompareCore(x as ReportRelatedControlBase, y as ReportViewControlBase);
}
#endregion
#region IComparer 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;
}
}
Application example
To demonstrate the operation of the algorithm, we will create a console application. As an example of a graph, take a simple graph of 5 nodes (see the figure at the beginning of the article).
G = ({a, b, c, d, e}, {(a, b), (a, c), (a, d), (a, e), (b, d), (c, d ), (c, e), (d, e)})
To represent the graph, we will use a simple class that defines a node with a list of other nodes associated with it.
public class GraphNode {
List linkedNodes = new List();
object id;
public GraphNode(object id) {
this.id = id;
}
public List LinkedNodes { get { return linkedNodes; } }
public object Id { get { return id; } }
}
The code for the application itself is shown below:
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 comparer = new GraphNodeComparer();
IList sortedNodes = DevExpress.Utils.Algorithms.TopologicalSort(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 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");
}
}
Direct graph relationships are set in the PrepareNodes method . In this case, dependencies are created arbitrarily.
To compare nodes, you will also need the GraphNodeComparer class
public class GraphNodeComparer : IComparer {
public int Compare(GraphNode x, GraphNode y) {
if (x.LinkedNodes.Contains(y))
return -1;
if (y.LinkedNodes.Contains(x))
return 1;
return 0;
}
}
After starting the application, we will get a sorted list of nodes and
A-> B-> C-> D-> E will be displayed in the console .
The result of the program is shown in the figure below:
Sorter Source Code
As I promised above, I give the code for implementing the topological sorting algorithm.
namespace DevExpress.Utils.Implementation {
#region TopologicalSorter
public class TopologicalSorter {
#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 sourceObjects;
IComparer comparer;
#endregion
#region Properties
protected internal Node[] Nodes { get { return nodes; } }
protected internal int[] QLink { get { return qLink; } }
protected IComparer Comparer { get { return comparer; } }
protected internal IList SourceObjects { get { return sourceObjects; } }
#endregion
protected IComparer GetComparer() {
return Comparer != null ? Comparer : System.Collections.Generic.Comparer.Default;
}
protected bool IsDependOn(T x, T y) {
return GetComparer().Compare(x, y) > 0;
}
public IList Sort(IList sourceObjects, IComparer comparer) {
this.comparer = comparer;
return Sort(sourceObjects);
}
public IList Sort(IList sourceObjects) {
this.sourceObjects = sourceObjects;
int n = sourceObjects.Count;
if (n < 2)
return sourceObjects;
Initialize(n);
CalculateRelations(sourceObjects);
int r = FindNonRelatedNodeIndex();
IList 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 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 ProcessNodes(int r) {
int n = sourceObjects.Count;
int k = n;
int f = QLink[0];
List result = new List(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. conclusions
If necessary, in a certain order of processing objects dependent on each other, they can be pre-ordered using the topological sorting algorithm. As a result, the correct sequence of objects and the execution of actions on them is built.
The algorithm proposed in the article provides the following advantages:
- using generic, i.e. it can be used to sort objects of various types
- the ability to define your own Comparer class, that is, it allows you to implement different logic for comparing objects.
- linearity of the algorithm, the algorithm is not recursive
An example with source code is available here .
I hope this material will be useful to you in future projects.