Network OptimizationTopological Ordering2Preliminary to Topological SortingLEMMA. If each node has at least one arc going out, then the first inadmissible arc of a depth first search determines a directed cycle. 1 4 6 73COROLLARY 1. If G has no directed cycle, then there is a node in G with no arcs going. And there is at least one node in G with no arcs coming in.COROLLARY 2. If G has no directed cycle, then one can relabel the nodes so that for each arc (i,j), i < j.3Initialization1245 36782 2 3 2 1 1 0 21 2 3 4 5 6 7 8NodeIndegreeDetermine the indegree diof each node i.LIST = {i : di= 0}LIST74Initialization1245 3678next11 2 3 4 5 6 7 82 2 3 2 1 1 0 2NodeIndegree“Next” will be the label of nodes in the topological order.LIST75Select a node from LISTnext01 2 3 4 5 7 82 2 3 2 1 0 2NodeIndegreeSelect Node 7.LIST7111245 3678761Order(7) := 1Delete node 7.6Updatesnext01 2 3 5 82 2 3 1 1 2NodeIndegreeLIST7update “next”111245 367870526421update indegreesupdate LIST7Select node 5next01 2 3 5 82 2 3 1 2NodeIndegreeLIST7111245 36787055264212Select Node 5.Order(5) := 2Delete node 5.8Updatesnext01 2 3 82 2 3 1 2NodeIndegreeLIST7111245 3678755216042102463update “next”update indegreesupdate LIST9Select Node 6 (or 4)next01 2 3 82 2 3 2NodeIndegreeLIST7111245 367875521604210246633Select Node 6.Order(6) := 3Delete node 6.10Updatesnext01 2 3 82 2 3 2NodeIndegreeLIST7111245 367875521421024630123update “next”update indegreesupdate LIST411Select Node 2 (or 4)next02 3 82 3 2NodeIndegreeLIST7111245 3678755242102466302211434Select Node 2.Order(2) := 4Delete node 2.12Updatesnext03 82 3 2NodeIndegreeLIST7111245 36787552421024663211434update “next”update indegreesupdate LIST50113Select node 4 (or 1)next03 82 3 2NodeIndegreeLIST7111245 367875524024663211434501Select Node 4.Order(4) := 5Delete node 4.4514Updatesnext03 82 3 2NodeIndegreeLIST7111245 36787552266321143450145update “next”update indegreesupdate LIST2 1615Select Node 1next03 83 2NodeIndegreeLIST7111245 36787552266321434501452 16Select Node 1.Order(1) := 6Delete node 1.1616Updatesnext03 83 2NodeIndegreeLIST7111245 36787552286324345452 1616update “next”update indegreesupdate LIST71 017Select Node 8next03 83NodeIndegreeLIST7111245 3678755228632434545261671 08Select Node 8.Order(8) := 7Delete node 8.718Updatesnext033NodeIndegreeLIST7111245 367875522363243454526167187update “next”update indegreesupdate LIST8019Select node 3next03NodeIndegreeLIST7111245 367875522363243454561678780Select Node 3.Order(3) := 8Delete node 3.38List is empty.The algorithm terminates with a topological order of the nodesMIT OpenCourseWarehttp://ocw.mit.edu 15.082J / 6.855J / ESD.78J Network OptimizationFall 2010 For information about citing these materials or our Terms of Use, visit:
View Full Document
Unlocking...