def _acceptable_subgraph(self): # type: () -> nx.MultiDiGraph
graph = self.as_multidigraph
reachable_states = nx.descendants(graph, self.start) | {self.start}
graph = graph.subgraph(reachable_states)
reachable_accepting_states = reachable_states & {
node for node in graph.node if graph.node[node]['accepting']
}
# Add a "sink" node with an in-edge from every accepting state. This is
# is solely done because the networkx API makes it easier to find the
# ancestor of a node than a set of nodes.
sink = object()
graph.add_node(sink)
for state in reachable_accepting_states:
graph.add_edge(state, sink)
acceptable_sates = nx.ancestors(graph, sink)
return graph.subgraph(acceptable_sates)
评论列表
文章目录