How does this Python function returns number but also a dictionary? -
below assignment algorithm class learning nodes, paths, etc. code designed check if 1 node reachable another. code below works unclear why. g "graph" containing each node key values = nodes connects to. mark_component function below returns number of nodes given node.
however in function check_connection designed return true if 2 nodes reachable, calls mark_component function , tests see if node in dictionary.
what not check_connection starts empty dictionary "marked" , calls mark_component using dictionary. nodes added it. mark_component returns number how check_connection function able "read" in marked? far function concerned, thought marked still empty. guess assumed marked local variable containing dictionary apparently can passed function , changed.
can please explain me? many thanks
def mark_component(g, node, marked): marked[node] = true total_marked = 1 neighbor in g[node]: if neighbor not in marked: total_marked += mark_component(g, neighbor, marked) return total_marked def check_connection(g, v1, v2): # return true if v1 connected v2 in g # or false if otherwise marked = {} mark_component(g, v1, marked) return 'a' in marked g = {'a': {'d': 1, 'g': 1}, 'c': {'g': 1}, 'b': {'f': 1}, 'e': {'h': 1, 'f': 1}, 'd': {'a': 1, 'g': 1}, 'g': {'a': 1, 'c': 1, 'd': 1}, 'f': {'b': 1, 'e': 1}, 'h': {'e': 1}} print check_connection(g,'a', 'b')
yes, marked mutable data structure, meaning contents can changed outside of original scope. when marked passed mark_component function, latter receives reference marked object, , able update content accessing reference using indexer (i.e. marked[node]).
the function check_connection however, still has reference marked object in memory stored in variable marked. when expression 'a' in marked executed, marked refers object updated mark_component function.
this concept similar pointers concept (aka int * pointer) in other languages c, , c++.
Comments
Post a Comment