Create 2015-1-11-topsort.md

gothere · gothere · commit 82b3f5d10147 · 2015-01-12T14:09:38.000-05:00
topological sorting code
diff --git a/_posts/2015-1-11-topsort.md b/_posts/2015-1-11-topsort.md
@@ -0,0 +1,40 @@
+---
+layout: post
+title: Topological Sort (coffeescript)
+published: true
+category: nosql
+tags: [algorithm, maizi]
+---
+
+{% highlight coffeescript %}
+    # topological sort
+    top_sort:()->
+      result = [] #sort result
+      
+      node_wrapers = {} #sorting data structure
+      for node in @nodes 
+        node_wrapers[node.id] = #initialize the data stucture of each node
+          node : node
+          to : [] #the nodes that has an edge from this node
+          visit: 0 #not visited
+      for link in @links
+        node_wrapers[link.source.id].to.push node_wrapers[link.target.id]
+
+      #visit function for top sort
+      visit = (node)->
+        if node.visit is 1 #has a temporary mark
+           throw "Found a circle"
+        if node.visit == 0
+          node.visit = 1 #mark n temporarily
+          for to_node in node.to
+            visit to_node
+          node.visit = 2 #mark n permanently
+          result.push node.node
+
+
+      for node_id, node of node_wrapers
+        if(node.visit == 0)
+          visit(node)
+      return result
+
+{% endhighlight %}
