import matplotlib.pyplot as plt
import networkx as nx

def searchGraph(graph, node):
    reachables= nx.ancestors(graph, node)
    return reachables
def nfaToDfa(graph, node, ancestors):
    inE= list()
    inE2 = graph.in_edges(graph.nodes())
    inE=inE2
    print(inE)
    for eS in inE:
        if "char" in graph[eS[0]][eS[1]]:
            source, target = eS
            print(target)
            B = nx.dag.ancestors(graph, graph.nodes[target])
            break
    source, target = inE[0]
    B=nx.dag.ancestors(graph,graph.nodes[target])
    return B
DG = nx.DiGraph()
DG.add_edges_from([(8,6),(8,9),(6,1), (6,4),(1,2, {'char': 'a'}),(2,3,{'char': 'b'}),(3,7)
    ,(4,5,{'char':'c'}),(5,7),(7,6),(7,9)])
DG.nodes[8]["starting"]=True
DG.nodes[9]["accepting"]=True
plt.subplot(111)
#NG = nfaToDfa(DG)
d = nx.dag.ancestors(DG, DG.nodes[8]["starting"])
H=DG.subgraph(d)
print(d)
listOfLists = []
listOfLists.append(nfaToDfa(H, H.nodes[8], d))
print(listOfLists)
#nx.draw(DG, with_labels=True, font_weight="bold")
pos = nx.spring_layout(DG, scale=2)
nx.draw(H, pos, with_labels=True)
nx.draw_networkx_edge_labels(H, pos, labels=nx.get_edge_attributes(DG, 'char'))

plt.show()