Message334010
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. |
|
Date |
User |
Action |
Args |
2019-01-18 21:09:39 | gdr@garethrees.org | set | recipients:
+ gdr@garethrees.org, rhettinger, terry.reedy, belopolsky, eric.smith, christian.heimes, tshepang, martin.panter, pablogsal, remi.lapeyre |
2019-01-18 21:09:37 | gdr@garethrees.org | set | messageid: <1547845777.48.0.128474567438.issue17005@roundup.psfhosted.org> |
2019-01-18 21:09:37 | gdr@garethrees.org | link | issue17005 messages |
2019-01-18 21:09:37 | gdr@garethrees.org | create | |
|