Skip to content
Snippets Groups Projects
  1. Jun 15, 2016
    • Vasileios Karakasis's avatar
      Low-level algorithms for manipulating cell trees. · 526953b5
      Vasileios Karakasis authored
      At this low level a cell tree is just a sequence of parent indices,
      where each parent index is the parent of the current index in the
      sequence. There four basic algorithms:
      
      1. child_count(parent_index):
         Computes the number of children for each node in parent_index
         	Time: O(N), Space: O(1)
      2. branches(parent_index):
         Returns a set of the branching nodes in parent_index, last branch
         index equals the parent_index's size.
      	 Time: O(N), Space: O(N)
      3. expand_branches(branch_index):
         Takes a branch_index (result from branches()) and expands it at the
         size of the original tree with all the nodes inside a branch having
         the same number.
               Time: O(parent_index), Space: O(1)
      4. make_parent_index(parent_index, branch_index):
         Return a compacted tree (single node per branch) from parent_index
         and its corresponding branch_index.
      	Time: O(N), Space: O(N)
      
      There is another utility function as well:
      
      find_branch(branch_index, nid):
          Returns the id of the branch where nid belongs to.
      	Time: O(N), Space: O(1)
      526953b5
  2. Jun 11, 2016
  3. Jun 10, 2016
  4. Jun 09, 2016
  5. Jun 08, 2016
  6. Jun 07, 2016
  7. Jun 06, 2016
  8. May 25, 2016