The dictionary returned unexpected result

Question

Dears,

After running, my code would generate a dictionary dfn={f: 6, e: 5, c: 4, d: 3, b: 2, a: 1}. This dictionary is the order in which each vertex is discovered by DFS traversal.

However, when the vertex is e and the u is vertex f(in the following snippet), the dfn[u] doesn't return 6. It returns 3 instead. Could you please tell me why?

for e in g.incident_edges(vertex):
            u = e.opposite(vertex)
            print("opposite",u)
            print("opposite",dfn[u])

from cmath import inf
from tkinter import N
import graph
import operator

def DFS(g,u,discovered):
    for e in g.incident_edges(u):
        v = e.opposite(u)
        if v not in discovered:
            discovered[v]=e
            DFS(g,v,discovered)
        else:
            if e not in discovered.values(): # if the explored edge is a back edge, mark it as 0.
                e._element=0
    print(g.edges())
    return discovered

def find_articulation_point(g):
    discovered ={a:None}
    discovered = DFS(g,a,discovered)
    print(discovered)

    # to construct a dic that shows the order in each each vertex is discovered.
    dfn = discovered
    n = 1
    for k in discovered.keys():
        dfn[k]= n 
        n+=1
    print("dfn original",dfn)
    dfn = dict(sorted(dfn.items(), key=operator.itemgetter(1),reverse=True))
    print("dfn new",dfn)
    # to construct a dic that shows the vertex with the least dfn that is reachable from each vertex.
    lowest = dfn
    for vertex in dfn.keys():
        print("iteration",vertex)
        order = dfn[vertex]
        # find the least reachable of its children
        children = []
        nodes_reachable_by_back_edges =[]
        for e in g.incident_edges(vertex):
            u = e.opposite(vertex)
            print("opposite",u)
            print("opposite",dfn[u])
            if e.element() != 0:
                print("opposite","vertex",dfn[u],dfn[vertex])
                if dfn[u]>dfn[vertex]:
                    children.append(u)
            else:
                if dfn[vertex]>dfn[u]:
                    nodes_reachable_by_back_edges.append(u)
        print(children)
        print(nodes_reachable_by_back_edges)
        if children:
            lowest_of_children = min(lowest[c]for c in children)
        else:
            lowest_of_children = float("inf")
        if nodes_reachable_by_back_edges:
            lowest_of_backedges = min (dfn[node] for node in nodes_reachable_by_back_edges)
        else:
            lowest_of_backedges = float("inf")
        lowest_dfn_reachable = min(order,lowest_of_children,lowest_of_backedges) 
        lowest[vertex]= lowest_dfn_reachable
    print("lowest",lowest)

    


if __name__=="__main__":
    g = graph.Graph()
    a=g.insert_vertex("a")
    b=g.insert_vertex("b")
    c=g.insert_vertex("c")
    d=g.insert_vertex("d")
    e=g.insert_vertex("e")
    f=g.insert_vertex("f")
    g.insert_edge(a,b,"edge1")
    g.insert_edge(b,d,"edge2")
    g.insert_edge(c,d,"edge3")
    g.insert_edge(c,a,"edge4")
    g.insert_edge(d,e,"edge5")
    g.insert_edge(d,f,"edge6")
    g.insert_edge(e,f,"edge7")

find_articulation_point(g)

Answer 1

I think the problem is that I used the vertex object as the key for the dictionary and the vertex object is a mutable object. However, it's forbidden to use a mutable objects as keys in dictionaries.