| 237 | node.linear_edges.append((''.join(s), child)) |
| 238 | |
| 239 | def _topological_order(self): |
| 240 | # compute reachable linear nodes, and the set of incoming edges for each node |
| 241 | order = [] |
| 242 | stack = [self.root] |
| 243 | seen = set() |
| 244 | while stack: |
| 245 | # depth first traversal |
| 246 | node = stack.pop() |
| 247 | if node.id in seen: |
| 248 | continue |
| 249 | seen.add(node.id) |
| 250 | order.append(node) |
| 251 | for label, child in node.linear_edges: |
| 252 | stack.append(child) |
| 253 | |
| 254 | # do a (slightly bad) topological sort |
| 255 | incoming = defaultdict(set) |
| 256 | for node in order: |
| 257 | for label, child in node.linear_edges: |
| 258 | incoming[child].add((label, node)) |
| 259 | no_incoming = [order[0]] |
| 260 | topoorder = [] |
| 261 | positions = {} |
| 262 | while no_incoming: |
| 263 | node = no_incoming.pop() |
| 264 | topoorder.append(node) |
| 265 | positions[node] = len(topoorder) |
| 266 | # use "reversed" to make sure that the linear_edges get reorderd |
| 267 | # from their alphabetical order as little as necessary (no_incoming |
| 268 | # is LIFO) |
| 269 | for label, child in reversed(node.linear_edges): |
| 270 | incoming[child].discard((label, node)) |
| 271 | if not incoming[child]: |
| 272 | no_incoming.append(child) |
| 273 | del incoming[child] |
| 274 | # check result |
| 275 | assert set(topoorder) == set(order) |
| 276 | assert len(set(topoorder)) == len(topoorder) |
| 277 | |
| 278 | for node in order: |
| 279 | node.linear_edges.sort(key=lambda element: positions[element[1]]) |
| 280 | |
| 281 | for node in order: |
| 282 | for label, child in node.linear_edges: |
| 283 | assert positions[child] > positions[node] |
| 284 | # number the nodes. afterwards every input string in the set has a |
| 285 | # unique number in the 0 <= number < len(data). We then put the data in |
| 286 | # self.data into a linear list using these numbers as indexes. |
| 287 | topoorder[0].num_reachable_linear |
| 288 | linear_data = [None] * len(self.data) |
| 289 | inverse = {} # maps value back to index |
| 290 | for word, value in self.data.items(): |
| 291 | index = self._lookup(word) |
| 292 | linear_data[index] = value |
| 293 | inverse[value] = index |
| 294 | |
| 295 | return topoorder, linear_data, inverse |
| 296 | |