Performs topological sort on the given graph. Args: g: the graph. Returns: A pair where the first element indicates if the topological sort succeeded (True if there is no cycle found; False if a cycle is found) and the second element is either the sorted list of nodes
(g)
| 54 | |
| 55 | |
| 56 | def topological_sort(g): |
| 57 | """Performs topological sort on the given graph. |
| 58 | |
| 59 | Args: |
| 60 | g: the graph. |
| 61 | |
| 62 | Returns: |
| 63 | A pair where the first element indicates if the topological |
| 64 | sort succeeded (True if there is no cycle found; False if a |
| 65 | cycle is found) and the second element is either the sorted |
| 66 | list of nodes or the cycle of nodes found. |
| 67 | """ |
| 68 | def _is_loop_edge(op): |
| 69 | """Returns true if the op is the end of a while-loop creating a cycle.""" |
| 70 | return op.type in ['NextIteration'] |
| 71 | |
| 72 | def _in_op_degree(op): |
| 73 | """Returns the number of incoming edges to the given op. |
| 74 | |
| 75 | The edge calculation skips the edges that come from 'NextIteration' ops. |
| 76 | NextIteration creates a cycle in the graph. We break cycles by treating |
| 77 | this op as 'sink' and ignoring all outgoing edges from it. |
| 78 | Args: |
| 79 | op: Tf.Operation |
| 80 | Returns: |
| 81 | the number of incoming edges. |
| 82 | """ |
| 83 | count = 0 |
| 84 | for op in op.control_inputs + [in_tensor.op for in_tensor in op.inputs]: |
| 85 | if not _is_loop_edge(op): |
| 86 | count += 1 |
| 87 | return count |
| 88 | |
| 89 | sorted_ops = [] |
| 90 | op_in_degree = {op: _in_op_degree(op) for op in g.get_operations()} |
| 91 | |
| 92 | frontier = [op for (op, degree) in op_in_degree.items() if degree == 0] |
| 93 | frontier.sort(key=lambda op: op.name) |
| 94 | while frontier: |
| 95 | op = frontier.pop() |
| 96 | # Remove the op from graph, and remove its outgoing edges. |
| 97 | sorted_ops.append(op) |
| 98 | if _is_loop_edge(op): |
| 99 | continue |
| 100 | # pylint: disable=protected-access |
| 101 | consumers = list(op._control_outputs) |
| 102 | # pylint: enable=protected-access |
| 103 | for out_tensor in op.outputs: |
| 104 | consumers += [consumer_op for consumer_op in out_tensor.consumers()] |
| 105 | consumers.sort(key=lambda op: op.name) |
| 106 | for consumer in consumers: |
| 107 | # For each deleted edge shift the bucket of the vertex. |
| 108 | op_in_degree[consumer] -= 1 |
| 109 | if op_in_degree[consumer] == 0: |
| 110 | frontier.append(consumer) |
| 111 | if op_in_degree[consumer] < 0: |
| 112 | raise ValueError('consumer:%s degree mismatch'%consumer.name) |
| 113 |
no test coverage detected