TopologicalSort.cmake
Go to the documentation of this file.
00001 ############################################################################## 00002 # @file TopologicalSort.cmake 00003 # @brief CMake implementation of topological sorting algorithm. 00004 # 00005 # Perform a reverse topological sort on the given LIST. 00006 # 00007 # topological_sort(my_list "MY_" "_EDGES") 00008 # 00009 # LIST is the name of a variable containing a list of elements to be 00010 # sorted in reverse topological order. Each element in the list has a 00011 # set of outgoing edges (for example, those other list elements that 00012 # it depends on). In the resulting reverse topological ordering 00013 # (written back into the variable named LIST), an element will come 00014 # later in the list than any of the elements that can be reached by 00015 # following its outgoing edges and the outgoing edges of any vertices 00016 # they target, recursively. Thus, if the edges represent dependencies 00017 # on build targets, for example, the reverse topological ordering is 00018 # the order in which one would build those targets. 00019 # 00020 # For each element E in this list, the edges for E are contained in 00021 # the variable named ${PREFIX}${E}${SUFFIX}. If no such variable 00022 # exists, then it is assumed that there are no edges. For example, if 00023 # my_list contains a, b, and c, one could provide a dependency graph 00024 # using the following variables: 00025 # 00026 # MY_A_EDGES b 00027 # MY_B_EDGES 00028 # MY_C_EDGES a b 00029 # 00030 # With the involcation of topological_sort shown above and these 00031 # variables, the resulting reverse topological ordering will be b, a, c. 00032 # 00033 # @verbatim 00034 ############################################################################## 00035 # Modified from Boost Utilities 00036 # 00037 # Copyright 2010 Kitware, Inc. 00038 ############################################################################## 00039 # Copyright 2007 Douglas Gregor <doug.gregor@gmail.com> 00040 # Copyright 2007 Troy Straszheim 00041 # 00042 # Distributed under the Boost Software License, Version 1.0. 00043 ############################################################################## 00044 # Boost Software License - Version 1.0 - August 17th, 2003 00045 # 00046 # Permission is hereby granted, free of charge, to any person or organization 00047 # obtaining a copy of the software and accompanying documentation covered by 00048 # this license (the "Software") to use, reproduce, display, distribute, 00049 # execute, and transmit the Software, and to prepare derivative works of the 00050 # Software, and to permit third-parties to whom the Software is furnished to 00051 # do so, all subject to the following: 00052 # 00053 # The copyright notices in the Software and this entire statement, including 00054 # the above license grant, this restriction and the following disclaimer, 00055 # must be included in all copies of the Software, in whole or in part, and 00056 # all derivative works of the Software, unless such copies or derivative 00057 # works are solely in the form of machine-executable object code generated by 00058 # a source language processor. 00059 # 00060 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 00061 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 00062 # FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT 00063 # SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE 00064 # FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, 00065 # ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 00066 # DEALINGS IN THE SOFTWARE. 00067 ############################################################################## 00068 # @endverbatim 00069 # 00070 # @ingroup CMakeUtilities 00071 ############################################################################## 00072 00073 function(topological_sort LIST PREFIX SUFFIX) 00074 # Clear the stack and output variable 00075 set(VERTICES "${${LIST}}") 00076 set(STACK) 00077 set(${LIST}) 00078 00079 # Loop over all of the vertices, starting the topological sort from 00080 # each one. 00081 foreach(VERTEX ${VERTICES}) 00082 00083 # If we haven't already processed this vertex, start a depth-first 00084 # search from where. 00085 if (NOT FOUND_${VERTEX}) 00086 # Push this vertex onto the stack with all of its outgoing edges 00087 string(REPLACE ";" " " NEW_ELEMENT 00088 "${VERTEX};${${PREFIX}${VERTEX}${SUFFIX}}") 00089 list(APPEND STACK ${NEW_ELEMENT}) 00090 00091 # We've now seen this vertex 00092 set(FOUND_${VERTEX} TRUE) 00093 00094 # While the depth-first search stack is not empty 00095 list(LENGTH STACK STACK_LENGTH) 00096 while(STACK_LENGTH GREATER 0) 00097 # Remove the vertex and its remaining out-edges from the top 00098 # of the stack 00099 list(GET STACK -1 OUT_EDGES) 00100 list(REMOVE_AT STACK -1) 00101 00102 # Get the source vertex and the list of out-edges 00103 separate_arguments(OUT_EDGES) 00104 list(GET OUT_EDGES 0 SOURCE) 00105 list(REMOVE_AT OUT_EDGES 0) 00106 00107 # While there are still out-edges remaining 00108 list(LENGTH OUT_EDGES OUT_DEGREE) 00109 while (OUT_DEGREE GREATER 0) 00110 # Pull off the first outgoing edge 00111 list(GET OUT_EDGES 0 TARGET) 00112 list(REMOVE_AT OUT_EDGES 0) 00113 00114 if (NOT FOUND_${TARGET}) 00115 # We have not seen the target before, so we will traverse 00116 # its outgoing edges before coming back to our 00117 # source. This is the key to the depth-first traversal. 00118 00119 # We've now seen this vertex 00120 set(FOUND_${TARGET} TRUE) 00121 00122 # Push the remaining edges for the current vertex onto the 00123 # stack 00124 string(REPLACE ";" " " NEW_ELEMENT 00125 "${SOURCE};${OUT_EDGES}") 00126 list(APPEND STACK ${NEW_ELEMENT}) 00127 00128 # Setup the new source and outgoing edges 00129 set(SOURCE ${TARGET}) 00130 set(OUT_EDGES 00131 ${${PREFIX}${SOURCE}${SUFFIX}}) 00132 endif(NOT FOUND_${TARGET}) 00133 00134 list(LENGTH OUT_EDGES OUT_DEGREE) 00135 endwhile (OUT_DEGREE GREATER 0) 00136 00137 # We have finished all of the outgoing edges for 00138 # SOURCE; add it to the resulting list. 00139 list(APPEND ${LIST} ${SOURCE}) 00140 00141 # Check the length of the stack 00142 list(LENGTH STACK STACK_LENGTH) 00143 endwhile(STACK_LENGTH GREATER 0) 00144 endif (NOT FOUND_${VERTEX}) 00145 endforeach(VERTEX) 00146 00147 set(${LIST} ${${LIST}} PARENT_SCOPE) 00148 endfunction(topological_sort)