Topological Sort in Report SharpShooter

 
Normally sorting is simple: you just need to tell which one of the two elements is larger. However, it’s not always the case – sometimes the items don’t have linear structure, and pairwise comparison is not possible. So let me piggyback on the hot topic of graph search and show you a useful and beautiful trick for sorting items in a SharpShooter report.
 
Which tasks you may need this for?
 
Well, think about plugins ecosystem in your app where a plugin could depend on other plugins, so you need to come up with the correct loading order:
 

 
Or you might be creating an online learning app and need to list course prerequisites for any given course:
 

 
Or consider project management: after finishing a task you can work on either one of its children, so listing all the tasks “properly sorted” in a report wouldn’t be that easy! Say, below is a simplified version of a startup project – if you where to present all tasks in a sorted list, will you place “setup legal entity” before “bugfixing” or after it?
 

 
The answer to this and other similar questions is topological sort and in this post we’d see how to implement it in a SharpShooter report.

Topological Sort guts.

To make the story even more useful, let me briefly digress to explain how Topological Sort works.
 
It traverses the graph using Depth First Search, which means for any given node it goes as far as it can: marks the node as explored, selects one of its unexplored children (if any), and repeats until there’s nothing to explore. Below is the workhorse code:

   var stack = new Stack<Node>();
   stack.Push(startNode);

   while (stack.Count != 0) {
      var node = stack.Pop();
      node.IsExplored = true;

      var unexploredChild = node.GetUnexploredChildren().FirstOrDefault();
      if (unexploredChild != null) {
         unexploredChild.IsExplored = true;
         stack.Push(node);		//push as there may be more unexplored children
         stack.Push(unexploredChild);	//push to DFS it on the next step
         continue;
      }
      process(node);
   }

The above code is exactly DFS in all its glory, and we use process action which will be called on every node in the order we want. So, as our goal is to assign order numbers to each node, and as our action will be called on the furthermost node first, we need to give it the biggest score and decrease the score by one as we move on:

   int order = nodes.Count;
   var dfs = new DepthFirstSearch();
   foreach (var node in nodes.Where(x => !x.IsExplored)) {
      dfs.Run(node, x => {
         x.Order = order;
         if (!x.GetUnexploredChildren().Any()) { order--; }
      });
   }

..and that’s it! Let’s see how we can use that in a SharpShooter report.

SharpShooter report implementation.

(Note that you can always find source code here on bitbucket, and below is a write-up with nice screenshots )
 
So we create a WinForms app, and then drag-n-drop ReportManager and ReportViewer on the main form:
 

 
Then we create a FileReportSlot and apply it to the viewer (otherwise it wouldn’t know what to display):
 

 
Then we setup the data source:

   public Form1()
   {
	...
	var graph = CreateGraph();  //graph as per the "startup example" on the top
	graph.TopologicalSort();    //already explained

	reportManager1.DataSources.Add("Tasks", graph.Nodes);
	fileReportSlot1.DesignTemplate(false);

	reportViewer1.RefreshReport();
   }

In the last three lines, we

• add a new data source to our ReportManager
• open Report Designer (the data is available at runtime only, so we need to start the application in order to use the data source). Now it’s important to note that this works only because we created FileReportSlot: when done with the report template, we save it under the name specified while creating the file report slot, and this will allow report viewer to automatically pick it up.
• refresh report on the viewer (this will not happen until we close the designer, which is exactly what we want)

 
Then we hit Ctrl+F5 and run the application. As expected, Report Designer pops up, and so we create a new blank report there, drag-n-drop a DataBand and select our data source for it:
 

 
So far so good – next step is sorting! We select Sort property of the DataBand adding the right item to its collection:
 

 
Believe it or not, that’s it. After we closed Report Designer, all startup project tasks get displayed in a sorted order:
 

 

Summary.

You cannot always dissuade your users and clients of weird sorting requirements – and when you get confronted with one of them, try to apply graph based sorting.
 
There’s a striking number of real world tasks which can benefit from using graphs, and in this post we implemented one of them and now you’re armed with knowledge and source code for Depth First Search and Topological Sort. If you feel like playing with this a bit more – make sure you grab this post’s project here at bitbucket!