Author gdr@garethrees.org
Recipients belopolsky, christian.heimes, eric.smith, gdr@garethrees.org, martin.panter, pablogsal, remi.lapeyre, rhettinger, terry.reedy, tshepang
Date 2019-01-18.21:09:37
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1547845777.48.0.128474567438.issue17005@roundup.psfhosted.org>
In-reply-to
Content
Just to elaborate on what I mean by "bug magnet". (I'm sure Pablo understands this, but there may be other readers who would like to see it spelled out.)

Suppose that you have a directed graph represented as a mapping from a vertex to an iterable of its out-neighbours. Then the "obvious" way to get a total order on the vertices in the graph would be to generate the edges and pass them to topsort:

    def edges(graph):
        return ((v, w) for v, ww in graph.items() for w in ww)
    order = topsort(edges(graph))

This will appear to work fine if it is never tested with a graph that has isolated vertices (which would be an all too easy omission).

To handle isolated vertices you have to remember to write something like this:

    reversed_graph = {v: [] for v in graph}
    for v, ww in graph.items():
        for w in ww:
            reversed_graph[w].append(v)
    order = topsort(edges(graph)) + [
          v for v, ww in graph.items() if not ww and not reversed_graph[v]]

I think it likely that beginner programmers will forget to do this and be surprised later on when their total order is missing some of the vertices.
History
Date User Action Args
2019-01-18 21:09:39gdr@garethrees.orgsetrecipients: + gdr@garethrees.org, rhettinger, terry.reedy, belopolsky, eric.smith, christian.heimes, tshepang, martin.panter, pablogsal, remi.lapeyre
2019-01-18 21:09:37gdr@garethrees.orgsetmessageid: <1547845777.48.0.128474567438.issue17005@roundup.psfhosted.org>
2019-01-18 21:09:37gdr@garethrees.orglinkissue17005 messages
2019-01-18 21:09:37gdr@garethrees.orgcreate