0

I am writing the dfs in Python with discovery and finish time, etc. And the code below works fine:

def depth_first_search(graph, s):
    p = dict.fromkeys(graph.keys())  # parent pointers
    d = dict.fromkeys(graph.keys())  # discovery time
    f = dict.fromkeys(graph.keys())  # finish time
    visited = []

    time = [0]
    def dfs(node):
        visited.append(node)
        time[0] += 1
        d[node] = time[0]
        for v in graph[node]:
            if v not in visited:
                p[v] = node
                dfs(v)
        time[0] += 1
        f[node] = time[0]

    dfs(s)

    return (p, d, f, visited)

However, when I change time = [0] to time = 0. The code breaks and says "local variable 'time' referenced before assignment".

My question is, why there is no same error when I use the time var as a list?

I tried the time var to be both a list and a single var.

Charles Duffy
  • 280,126
  • 43
  • 390
  • 441
caleb
  • 1
  • @CharlesDuffy moving the `time = 0` will give the wrong answer though. I am using Python 3.10.8 – caleb Feb 01 '23 at 19:33
  • The `time` variable is used to measure the timing of the node visits from the beginning. So, it has to be outside of the function `dfs`. What baffles me is that using `time` as a one element list would work but if I change `time` from list to a single variable, then there is error (`UnboundLocalError: local variable 'time' referenced before assignment`) – caleb Feb 01 '23 at 19:37
  • 2
    Here you go, a much simpler reproducer: https://ideone.com/PoKrX1 – Charles Duffy Feb 01 '23 at 19:39
  • 1
    ...and that gives our answer: Add the line `nonlocal time` inside `def dfs(node):`, as described in the duplicate linked at [Is it possible to modify a variable in python that is in an outer (enclosing), but not global, scope?](https://stackoverflow.com/questions/8447947/is-it-possible-to-modify-a-variable-in-python-that-is-in-an-outer-enclosing-b) – Charles Duffy Feb 01 '23 at 19:44
  • ...[here's](https://stackoverflow.com/questions/9264763/why-does-this-unboundlocalerror-occur-closure) another example with a particularly concise answer on why `time` needs to be `nonlocal` or `global` here. – Aaron Feb 01 '23 at 19:46
  • I understand now that adding `nonlocal time` inside `dfs` function will solve the problem. However, it seems strange that if `time` is mutable, for example a list here as I used, then assignment to `time` inside `dfs` function will mask the outer scope and we can makes changes to it without the `nonlocal`. why is that? – caleb Feb 01 '23 at 19:53
  • ...because that's how the language is defined. ["Why" questions about language design are generally not on-topic here.](https://meta.stackexchange.com/questions/170394/what-is-the-rationale-for-closing-why-questions-on-a-language-design); our job is to describe _what_ the rules of the language are and how to work within them, not _why_ its designers made the decisions they did. That said, I'll note that Python's current behavior allows compile-time checking for errors that would otherwise happen at runtime. – Charles Duffy Feb 02 '23 at 22:24
  • If you want to dig into design history, though, you'd probably best read the relevant PEPs, and the mailing list history &c behind them. Maybe start with the references section of [PEP-3104](https://peps.python.org/pep-3104/). – Charles Duffy Feb 02 '23 at 22:28
  • (and notice how the oldest link in that references section, from 1994, indicates that the decision was already made by that time! Sometimes a decision happens while something is being built from first principles before there's real-world experience with how it'll work out, and by the time the impact is seen it's too late to change) – Charles Duffy Feb 02 '23 at 22:34
  • Added an additional question, "Read/Write Python Closures", to the duplicate list; the OP there was explicitly looking for history, and some of the answers oblige (IMHO, the best explanation given there is the one pulled from the PEP linked above). The ruling that "why" questions on language design are disallowed isn't always evenly applied; sometimes one slips through. :) – Charles Duffy Feb 02 '23 at 22:36
  • (that said, I think that the linked duplicate is a good example of _why_ we don't allow "why" questions: it's not a question with an objective answer; instead, it's mostly historical speculation of what was in peoples' heads many decades ago; speculation with references to back it, sure, but opinion/interpretation/speculation nonetheless). – Charles Duffy Feb 02 '23 at 22:40

0 Answers0