search

jamespfennell / transiter

Web service for transit data
https://demo.transiter.dev
MIT License
65 stars 7 forks source link

New graph util functions are non-deterministic #50

Closed jamespfennell closed 4 years ago

jamespfennell commented 4 years ago

The following code/test randomly fails:

raw_paths = [
    ("a", "b", "c"),
    ("a", "c", "d"),
    ("x", "y", "z")
]

path_1 = datastructures.Graph.build_from_edge_label_tuples(
    [("a", "b"), ("b", "c"), ("c", "d")]
)
path_2 = datastructures.Graph.build_from_edge_label_tuples(
    [("x", "y"), ("y", "z")]
)

graphs = servicemapmanager._build_sorted_graph_from_paths(
    set(raw_paths)
)

assert [path_1, path_2] == graphs or [path_2, path_1] == graphs

The edge sets are different: sometimes graphs contains the edge (a,c).

It's probably to do with the transitive reduction. I think the immutable/mutable idea has been a failure and it should be cleaned up because it's leading to weird subtle bugs.

jamespfennell commented 4 years ago

Think the code is actually buggy: path_1 should contain the edge (a,c).