Source Code for Module visgraph.pathcore

  1  ''' 
  2  Paths are enumerated threads through a particular graph.  They 
  3  are implemented as an optimized hierarchical graph using python 
  4  primitives to save memory and processing time... 
  5   
  6  Each "leaf" node may be tracked back for it's entire path by 
  7  tracking back to parents. 
  8  ''' 
  9   
 10 -def newPathNode(parent=None, **kwargs): 
 11      ''' 
 12      Create a new path node with the given properties 
 13      ''' 
 14      ret = (parent, [], kwargs) 
 15      if parent != None: 
 16          parent[1].append(ret) 
 17      return ret 
 18   
 19 -def getNodeParent(pnode): 
 20      return pnode[0] 
 21   
 22 -def delPathNode(pnode): 
 23      ''' 
 24      Prune (remove) this node from the parent... 
 25      ''' 
 26      p = getNodeParent(pnode) 
 27      if p != None: 
 28          p[1].remove(pnode) 
 29   
 30 -def getNodeIndex(pnode): 
 31      p = getNodeParent(pnode) 
 32      if p != None: 
 33          return p[1].index(pnode) 
 34      return None 
 35   
 36 -def getNodeKids(pnode): 
 37      ''' 
 38      Return the list of children nodes for the specified 
 39      node. 
 40   
 41      Example: for knode in getNodeKids(pnode): 
 42      ''' 
 43      return pnode[1] 
 44   
 45 -def getRootNode(pnode): 
 46      ''' 
 47      Get the root node for the path tree which contains 
 48      pnode. 
 49   
 50      Example: root = getRootNode(branchnode) 
 51      ''' 
 52      ret = pnode 
 53      while pnode[0] != None: 
 54          pnode = pnode[0] 
 55      return pnode 
 56   
 57 -def getLeafNodes(pnode): 
 58      ''' 
 59      Get all the leaf nodes for the path tree which contains 
 60      the pnode. 
 61   
 62      Example: for leaf in getLeafNodes(root): 
 63      ''' 
 64      root = getRootNode(pnode) 
 65      ret = [] 
 66      todo = [root, ] 
 67      while len(todo): 
 68          x = todo.pop() 
 69          if len(x[1]) == 0: 
 70              ret.append(x) 
 71              continue 
 72          for n in x[1]: 
 73              todo.append(n) 
 74      return ret 
 75   
 76 -def getPathToNode(pnode): 
 77      ''' 
 78      Return a list of the path nodes which lead from the 
 79      root node to the specified path node. 
 80      ''' 
 81      path = [] 
 82      while pnode != None: 
 83          path.append(pnode) 
 84          pnode = pnode[0] 
 85   
 86      path.reverse() 
 87      return path 
 88   
 89 -def getAllPaths(pnode): 
 90      ''' 
 91      Get a list of lists which has each path flattened out. 
 92   
 93      Example: for path in getAllPaths(pnode): 
 94                   print 'Found A Path:' 
 95                   for node in path: 
 96                      doStuff() 
 97      ''' 
 98      leafs = getLeafNodes(pnode) 
 99      paths = [] 
100      for leaf in leafs: 
101          path = getPathToNode(leaf) 
102          paths.append(path) 
103      return paths 
104   
105 -def getNodeProp(pnode, key, default=None): 
106      ''' 
107      Get a property from the given node, returning 
108      default in the case that the specified property is 
109      not present. 
110   
111      Example: 
112          name = getNodeProp(pnode, 'name', 'Unknown') 
113      ''' 
114      return pnode[2].get(key, default) 
115   
116 -def getPathProp(pnode, key, default=None): 
117      ''' 
118      Retrieve the specified property by walking the give 
119      path backward until the property is found.  Returns 
120      the specified default if the specified key is not found 
121      as a property of any node in the given path. 
122   
123      Example: 
124          name = getPathProp(pnode, 'name', 'Unknown') 
125      ''' 
126      parent = pnode 
127      while parent != None: 
128          parent, kids, props = parent 
129          x = props.get(key) 
130          if x != None: 
131              return x 
132      return default 
133   
134 -def setNodeProp(pnode, key, value): 
135      ''' 
136      Set a spcified property on the given path node. 
137   
138      Example: 
139          setNodeProp(pnode, 'name', 'woot') 
140      ''' 
141      pnode[2][key] = value 
142   
143 -def isPathLoop(pnode, key, value): 
144      ''' 
145      Assuming you have some identifier property (such as graph node id) 
146      being set on the path nodes, you may use this API to determine if 
147      the current path has a node with the specified key/value property. 
148   
149      Example: 
150          if searchPathLoop(pnode, 'nid', 5): 
151              continue 
152      ''' 
153      parent = pnode 
154      while parent != None: 
155          parent, kids, props = parent 
156          if props.get(key) == value: 
157              return True 
158      return False 
159   
160 -def getPathLoopCount(pnode, key, value): 
161      ''' 
162      Assuming that the key is unique, walk the current path and see how 
163      many times "key" has the specified value.  This will be how many instances 
164      of a loop have been encountered. 
165      ''' 
166      count = 0 
167      parent = pnode 
168      while parent != None: 
169          parent, kids, props = parent 
170          if props.get(key) == value: 
171              count += 1 
172      return count 
173