| 23 | |
| 24 | |
| 25 | class DawgNode: |
| 26 | |
| 27 | def __init__(self, dawg): |
| 28 | self.id = dawg.next_id |
| 29 | dawg.next_id += 1 |
| 30 | self.final = False |
| 31 | self.edges = {} |
| 32 | |
| 33 | self.linear_edges = None # later: list of (string, next_state) |
| 34 | |
| 35 | def __str__(self): |
| 36 | if self.final: |
| 37 | arr = ["1"] |
| 38 | else: |
| 39 | arr = ["0"] |
| 40 | |
| 41 | for (label, node) in sorted(self.edges.items()): |
| 42 | arr.append(label) |
| 43 | arr.append(str(node.id)) |
| 44 | |
| 45 | return "_".join(arr) |
| 46 | __repr__ = __str__ |
| 47 | |
| 48 | def _as_tuple(self): |
| 49 | edges = sorted(self.edges.items()) |
| 50 | edge_tuple = tuple((label, node.id) for label, node in edges) |
| 51 | return (self.final, edge_tuple) |
| 52 | |
| 53 | def __hash__(self): |
| 54 | return hash(self._as_tuple()) |
| 55 | |
| 56 | def __eq__(self, other): |
| 57 | return self._as_tuple() == other._as_tuple() |
| 58 | |
| 59 | @cached_property |
| 60 | def num_reachable_linear(self): |
| 61 | # returns the number of different paths to final nodes reachable from |
| 62 | # this one |
| 63 | |
| 64 | count = 0 |
| 65 | # staying at self counts as a path if self is final |
| 66 | if self.final: |
| 67 | count += 1 |
| 68 | for label, node in self.linear_edges: |
| 69 | count += node.num_reachable_linear |
| 70 | |
| 71 | return count |
| 72 | |
| 73 | |
| 74 | class Dawg: |