1#!/usr/bin/env python 2 3''' 4This program takes a list of module files and creates a (possibly disjoint) 5directed graph of the modules and their dependencies. Arrows on the 6directed graph point to the dependent module. 7 8Typical usage would be as follows: 9 VisualizeModuleDependencies.py VTKSourceDir vtkFiltersSources,vtkInteractionStyle,vtkRenderingOpenGL2 10 11''' 12 13import os, sys 14from collections import defaultdict 15import vtk 16 17def GetProgramParameters(): 18 import argparse 19 description = 'Creates a directed graph of the modules and their dependencies.' 20 epilogue = ''' 21 This program takes a list of module files and creates a 22 (possibly disjoint) directed graph of the modules and their 23 dependencies. Arrows on the directed graph point to the dependent module. 24 By default, dependencies of a given module are followed to their maximum 25 depth. However you can restrict the depth by specifying the depth to 26 which dependent modules are searched. 27 The moduleList is a comma-separated list of module names with no 28 spaces between the names. 29 The treeDepth defaults to 0, this means that for a given module all 30 dependent modules will be found. If non-zero, then trees will be only 31 searched to that depth. 32 ''' 33 parser = argparse.ArgumentParser(description=description, epilog=epilogue) 34 parser.add_argument('vtkSourceDir', help='The path to the vtk Source Directory.') 35 parser.add_argument('moduleList', help='The list of modules.') 36 parser.add_argument('moduleTreeDepth', help='The depth of the module trees', nargs='?', default=0, type=int) 37 args = parser.parse_args() 38 vtkSourceDir = args.vtkSourceDir 39 moduleList = [x.strip() for x in args.moduleList.split(',')] 40 moduleTreeDepth = args.moduleTreeDepth 41 return (vtkSourceDir, moduleList, moduleTreeDepth) 42 43def GetProgramParametersOld(): 44 ''' 45 Used for Python versions < 2.7 46 ''' 47 if len(sys.argv) < 3: 48 s = 'Usage: ' + sys.argv[0] + ' vtkSourceDir moduleList [moduleTreeDepth]' 49 print(s) 50 exit(0) 51 args = dict() 52 args['vtkSourceDir'] = sys.argv[1] 53 args['moduleList'] = sys.argv[2] 54 args['moduleTreeDepth'] = 0 55 if len(sys.argv) > 3: 56 args['moduleTreeDepth'] = int(sys.argv[3]) 57 vtkSourceDir = args['vtkSourceDir'] 58 moduleList = [x.strip() for x in args['moduleList'].split(',')] 59 moduleTreeDepth = args['moduleTreeDepth'] 60 return (vtkSourceDir, moduleList, moduleTreeDepth) 61 62def FindModuleFiles(path): 63 ''' 64 Get a list of module files in the VTK directory. 65 ''' 66 moduleFiles = [os.path.join(root, name) 67 for root, dirs, files in os.walk(path) 68 for name in files 69 if name == ("module.cmake")] 70 return moduleFiles 71 72def ParseModuleFile(fileName): 73 ''' 74 Read each module file returning the module name and what 75 it depends on or implements. 76 ''' 77 fh = open(fileName, 'rb') 78 lines = [] 79 for line in fh: 80 line = line.strip() 81 if line.startswith('$'): # Skip CMake variable names 82 continue 83 if line.startswith('#'): 84 continue 85 line = line.split('#')[0].strip() # inline comments 86 if line == "": 87 continue 88 line = line.split(')')[0].strip() # closing brace with no space 89 if line == "": 90 continue 91 for l in line.split(" "): 92 lines.append(l) 93 languages = ['PYTHON', 'JAVA'] 94 keywords = ['BACKEND', 'COMPILE_DEPENDS', 'DEPENDS', 'EXCLUDE_FROM_ALL', 95 'EXCLUDE_FROM_WRAPPING', 'GROUPS', 'IMPLEMENTS', 'KIT', 'LEGACY', 96 'PRIVATE_DEPENDS', 'TEST_DEPENDS', 'OPTIONAL_PYTHON_LINK' 97 'IMPLEMENTATION_REQUIRED_BY_BACKEND'] + \ 98 map(lambda l: 'EXCLUDE_FROM_%s_WRAPPING' % l, languages) 99 moduleName = "" 100 depends = [] 101 implements = [] 102 state = "START"; 103 for item in lines: 104 if state == "START" and item.startswith("vtk_module("): 105 moduleName = item.split("(")[1] 106 continue 107 if item in keywords: 108 state = item 109 continue 110 if state == 'DEPENDS' and item != ')': 111 depends.append(item) 112 continue 113 if state == 'IMPLEMENTS' and item != ')': 114 implements.append(item) 115 continue 116 return [moduleName, depends + implements] 117 118def FindAllNeededModules(modules, foundModules, moduleDepencencies): 119 ''' 120 Recursively search moduleDependencies finding all modules. 121 ''' 122 if modules != None and len(modules) > 0: 123 for m in modules: 124 foundModules.add(m) 125 foundModules = foundModules | set(moduleDepencencies[m]) # Set union 126 foundModules = FindAllNeededModules(moduleDepencencies[m], 127 foundModules, moduleDepencencies) 128 return foundModules 129 130def MakeModuleTree(module, index, tree, moduleDependencies, treeDepth, level=0): 131 ''' 132 For a given module make a tree with the module as the root and the 133 dependent modules as children. 134 ''' 135 if module: 136 index = index + [module] 137 if treeDepth == 0 or level < treeDepth: 138 for m in moduleDependencies[module]: 139 level += 1 140 MakeModuleTree(m, index, tree, moduleDependencies, treeDepth, level) 141 level -= 1 142 Add(tree, index) 143 144# One-line Tree in Python 145# See: https:gist.github.com/hrldcpr/2012250 146def Tree(): return defaultdict(Tree) 147 148def Add(tree, keys): 149 for key in keys: 150 tree = tree[key] 151 152def PrettyPrint(tree, level=0): 153 ''' 154 Useful to visualize the tree. 155 ''' 156 result = '' 157 for k, v in tree.iteritems(): 158 s = ' ' * level + k + '\n' 159 result += s 160 level += 1 161 result += PrettyPrint(v, level) 162 level -= 1 163 return result 164 165def GetAllKeys(tree): 166 ''' 167 Return all the modules in the tree as a set. 168 ''' 169 modules = set() 170 for key in tree: 171 modules = set(list(modules) + [key] + list(GetAllKeys(tree[key]))) 172 return modules 173 174def MakeEdgeList(t): 175 ''' 176 Return a set that represents the edges in the tree. 177 ''' 178 edgeList = set() 179 for k, v in t.iteritems(): 180 subKeys = v.keys() 181 if subKeys: 182 for kk in subKeys: 183 edgeList.add((k, kk)) 184 edg = MakeEdgeList(v) 185 if edg: 186 edgeList.update(edg) 187 return edgeList 188 189def MakeGraph(t, parent='', level=0): 190 ''' 191 Returns a list that has two elements, the vertices and the edge list. 192 ''' 193 return [GetAllKeys(t), MakeEdgeList(t)] 194 195def GenerateGraph(moduleList, moduleDepencencies, moduleTreeDepth): 196 ''' 197 Generate a graph from the module list. 198 The resultant graph is a list consisting of two sets, the first set 199 is the set of vertices and the second set is the edge list. 200 ''' 201 graph = [set(), set()] 202 for m in moduleList: 203 t = Tree() 204 MakeModuleTree(m, [], t, moduleDepencencies, moduleTreeDepth) 205 g = MakeGraph(t) 206 graph[0].update(g[0]) 207 if g[1]: 208 graph[1].update(g[1]) 209 return graph 210 211def GenerateVTKGraph(graph): 212 ''' 213 Take the vertices and edge list in the graph parameter 214 and return a VTK graph. 215 ''' 216 g = vtk.vtkMutableDirectedGraph() 217 # Label the vertices 218 labels = vtk.vtkStringArray() 219 labels.SetNumberOfComponents(1) 220 labels.SetName("Labels") 221 222 index = dict() 223 l = list(graph[0]) 224 # Make the vertex labels and create a dictionary with the 225 # keys as labels and the vertex ids as the values. 226 for i in range(0, len(l)): 227 # Set the vertex labels 228 labels.InsertNextValue(l[i]) 229 index[l[i]] = g.AddVertex() 230 g.GetVertexData().AddArray(labels) 231 # Add edges 232 l = list(graph[1]) 233 for i in range(0, len(l)): 234 ll = list(l[i]) 235 g.AddGraphEdge(index[ll[0]], index[ll[1]]) 236# g.Dump() 237 return g 238 239def DisplayGraph(graph): 240 ''' 241 Display the graph. 242 ''' 243 theme = vtk.vtkViewTheme() 244 theme.SetBackgroundColor(0, 0, .1) 245 theme.SetBackgroundColor2(0, 0, .5) 246 247 # Layout the graph 248 # Pick a strategy you like. 249 # strategy = vtk.vtkCircularLayoutStrategy() 250 strategy = vtk.vtkSimple2DLayoutStrategy() 251 # strategy = vtk.vtkRandomLayoutStrategy() 252 layout = vtk.vtkGraphLayout() 253 layout.SetLayoutStrategy(strategy) 254 layout.SetInputData(graph) 255 256 view = vtk.vtkGraphLayoutView() 257 view.AddRepresentationFromInputConnection(layout.GetOutputPort()) 258 # Tell the view to use the vertex layout we provide. 259 view.SetLayoutStrategyToPassThrough() 260 view.SetEdgeLabelVisibility(True) 261 view.SetVertexLabelArrayName("Labels") 262 view.SetVertexLabelVisibility(True) 263 view.ApplyViewTheme(theme) 264 265 # Manually create an actor containing the glyphed arrows. 266 # Get the edge geometry 267 edgeGeom = vtk.vtkGraphToPolyData() 268 edgeGeom.SetInputConnection(layout.GetOutputPort()) 269 edgeGeom.EdgeGlyphOutputOn() 270 271 # Set the position (0: edge start, 1: edge end) where 272 # the edge arrows should go. 273# edgeGeom.SetEdgeGlyphPosition(0.8) 274 edgeGeom.SetEdgeGlyphPosition(0.85) 275 276 # Make a simple edge arrow for glyphing. 277# arrowSource = vtk.vtkGlyphSource2D() 278# arrowSource.SetGlyphTypeToEdgeArrow() 279# arrowSource.SetScale(0.075) 280 # Or use a cone. 281 coneSource = vtk.vtkConeSource() 282 coneSource.SetRadius(0.025) 283 coneSource.SetHeight(0.1) 284 coneSource.SetResolution(12) 285 286 # Use Glyph3D to repeat the glyph on all edges. 287 arrowGlyph = vtk.vtkGlyph3D() 288 arrowGlyph.SetInputConnection(0, edgeGeom.GetOutputPort(1)) 289# arrowGlyph.SetInputConnection(1, arrowSource.GetOutputPort()) 290 arrowGlyph.SetInputConnection(1, coneSource.GetOutputPort()) 291 292 # Add the edge arrow actor to the view. 293 arrowMapper = vtk.vtkPolyDataMapper() 294 arrowMapper.SetInputConnection(arrowGlyph.GetOutputPort()) 295 arrowActor = vtk.vtkActor() 296 arrowActor.SetMapper(arrowMapper) 297 view.GetRenderer().AddActor(arrowActor) 298 299 view.ResetCamera() 300 view.Render() 301 302 view.SetInteractionModeTo3D() 303 view.GetInteractor().Initialize() 304 view.GetInteractor().Start() 305 306def main(): 307 ver = list(sys.version_info[0:2]) 308 ver = ver[0] + ver[1] / 10.0 309 if ver >= 2.7: 310 vtkSourceDir, moduleList, moduleTreeDepth = GetProgramParameters() 311 else: 312 vtkSourceDir, moduleList, moduleTreeDepth = GetProgramParametersOld() 313 314 # Parse the module files making a dictionary of each module and its 315 # dependencies or what it implements. 316 moduleDepencencies = dict() 317 moduleFiles = FindModuleFiles(vtkSourceDir + "/") 318 for fname in moduleFiles: 319 m = ParseModuleFile(fname) 320 moduleDepencencies[m[0]] = m[1] 321 322 # Generate a graph from the module list. 323 graph = GenerateGraph(moduleList, moduleDepencencies, moduleTreeDepth) 324 325 # Now build a vtk graph. 326 g = GenerateVTKGraph(graph) 327 328 # Display it. 329 DisplayGraph(g) 330 331if __name__ == '__main__': 332 main() 333