RIA Shanghai | Adobe上海用户组

OSGi defines a very good module management system. The modules mainly communicate with the framework instead of messing around one another. However, there are cases that a module depends on other modules. Consider the modules in the diagram below (the arrow points to the depending module). Module C depends on A and D; module A, D and W depend on B. In order to run C, we need to run all of its depending modules first, for instance, one possible execution order is B, A, D, C. How to determine the order? It's easy. The answer is Topological sort.

The idea of topological sort is simple yet powerful. You use DFS to traverse the whole graph, i.e., all the vertices. The topological order is the same as the visiting finish order of vertices.

My implementation of finding all the depending modules for a given module (module_) and putting everything in topo sorted order:

// Topological sort.

// 0. Clear visit status
clearGraphVisit();

// 1. direct DFS - discover connected nodes and perform DFS at the same time.
var sortedOrder:Array = new Array(); // to order nodes.
dfsVisit(module_, sortedOrder);

Required functions:

/**
* Sets the visit mode of all modules to NO_VISIT.
*/
private function clearGraphVisit():void {
   for each(var m:Module in _idToModuleMapping) {
      m.visitStatus = Module.NO_VISIT;
   }
}

/**
* Visits the given module in DFS and inserts finished node to the order array.
* @param module_ the node to be visited, which should be in Module.NO_VISIT mode.
* @param graph the collection of all the vertices in the graph
* @param sortedOrder the 
*/
private function dfsVisit(module_:Module, sortedOrder:Array):void {
   if(module_.visitStatus != Module.NO_VISIT) {
      throw new Error("Invalid visit status - must be in NO_VISIT");
   }

   module_.visitStatus = Module.VISIT_BEGIN;

   for(var i:int = 0; module_.dependingModules != null && i < module_.dependingModules.length; i++) {
      var m:Module = module_.dependingModules.getItemAt(i) as Module;
      if(m.visitStatus == Module.NO_VISIT) {
         dfsVisit(m, sortedOrder);
      }else if(m.visitStatus == Module.VISIT_BEGIN) {
         throw new Error("Cyclic DAG! ");
      }else if(m.visitStatus == Module.VISIT_END) {
         // skip.
      }else{
         throw new Error("Invalid visit status: " + m.visitStatus);
      }
   }

   module_.visitStatus = Module.VISIT_END;
   sortedOrder.push(module_);
}

In less than twenty lines, you can get the topo order, know whether the graph is cyclic (e.g., C -> A -> C). That's why DFS is one of my favorite algorithms :)