guohanghui/graph-theory

1from examples.graphs import london_underground2 3"""4The problem of deciding the exact place in a community where a school or a fire station should be located,5is classified as the facility location problem.6 7If the facility is a school, it is desirable to locate it so that the sum 8of distances travelled by all members of the communty is as short as possible. 9This is the minimum of sum - or in short `minsum` of the graph.10 11If the facility is a firestation, it is desirable to locate it so that the distance from the firestation12to the farthest point in the community is minimized. 13This is the minimum of max distances - or in short `minmax` of the graph.14"""15 16 17def test_minsum():18    g = london_underground()19    stations = g.minsum()20    assert len(stations) == 121    station_list = [g.node(s) for s in stations]22    assert station_list == [(51.515, -0.1415, 'Oxford Circus')]23 24 25def test_minmax():26    g = london_underground()27    stations = g.minmax()28    assert len(stations) == 329    station_list = [g.node(s) for s in stations]30    assert station_list == [(51.5226, -0.1571, 'Baker Street'),31                            (51.5142, -0.1494, 'Bond Street'),32                            (51.5234, -0.1466, "Regent's Park")]33