True if the given sorting conforms to the given partial ordering.
(tuples, sorted_elements)
| 102 | |
| 103 | |
| 104 | def conforms_partial_ordering(tuples, sorted_elements): |
| 105 | """True if the given sorting conforms to the given partial ordering.""" |
| 106 | |
| 107 | deps = defaultdict(set) |
| 108 | for parent, child in tuples: |
| 109 | deps[parent].add(child) |
| 110 | for i, node in enumerate(sorted_elements): |
| 111 | for n in sorted_elements[i:]: |
| 112 | if node in deps[n]: |
| 113 | return False |
| 114 | else: |
| 115 | return True |
| 116 | |
| 117 | |
| 118 | def all_partial_orderings(tuples, elements): |