Generating a sink tree for debugging

[skinkie]

While actively working with datasets I sometimes fall in the trap that a nearest node is chosen that is can't be routed from/to, or is part of some island. Is there a simple trick to generate a sink tree from a certain point? I came up with below, but if there is something easier around, I am all ears.

if (debug_target != nullptr) {
    reply = {{"type", "FeatureCollection"}, {"features", nullptr}};

    unsigned x = debug_target;
    for(unsigned xy=pedestrian_graph.first_out[x]; xy<pedestrian_graph.first_out[x+1]; ++xy) {
        unsigned y = pedestrian_graph.head[xy];
        json feature = {{"type", "Feature"}, {"properties", {{"mode", "pedestrian"}}}, {"geometry", { {"type", "LineString"}, {"coordinates", {{pedestrian_graph.longitude[x], pedestrian_graph.latitude[x]}, {pedestrian_graph.longitude[y], pedestrian_graph.latitude[y]} }} } }}; 
        reply["features"].push_back(feature);
    }
}

[ben-strasser]

Hi,

While actively working with datasets I sometimes fall in the trap that a nearest node is chosen that is can't be routed from/to, or is part of some island. Is there a simple trick to generate a sink tree from a certain point? What do you mean by "sink tree"?

A "trick" that is often done (at least in academia) is to remove unreachable nodes is to just remove all nodes (and incident arcs) from the graph that are not part of the largest (in terms of nodes) strongly connected component. However, this will also remove stuff that one might want to keep such as highways going towards the border of the extracted map.

Best Regards Ben Strasser

PS: I wont have time before Wednesday to fully look at your other posts. :)

[skinkie]

What do you mean by "sink tree"?

Iterate over all edges departing (and preferable also: arriving) at the point of interest, to a certain degree, typically the way how a Dijkstra search is visualised. The intention is to sport the area covered by this island.

A "trick" that is often done (at least in academia) is to remove unreachable nodes is to just remove all nodes (and incident arcs) from the graph that are not part of the largest (in terms of nodes) strongly connected component. However, this will also remove stuff that one might want to keep such as highways going towards the border of the extracted map.

How to determine the largest strongly connected component? Or better put: is it possible to make it discrete?

PS: I wont have time before Wednesday to fully look at your other posts. :)

Not to worry. The Netherlands Enterprise Agency send that our project definition to incorporate and improve RoutingKit might be a reason to reject the support grant because for them it is more important that you write on how new any shiny something is, opposed to contributing, improving, extending on academic work. Guess what I'll be doing instead.

[skinkie]

I am toying with the code below.

pedestrian_ch_query.reset().add_source(0);
std::vector<GeoPositionToNode::NearestNeighborhoodQueryResult> pedestrian_result = pedestrian_map_geo_position.find_all_nodes_within_radius(latitude, longitude, 1000);
if (pedestrian_result.size() > 0) {
    pedestrian_ch_query.reset_target();
    for (auto it:pedestrian_result) pedestrian_ch_query.add_target(it.id, it.distance * 1000);
    unsigned pedestrian_target = pedestrian_ch_query.run().get_used_target();
    if (pedestrian_target != invalid_id) {
        pedestrian_map_stops[pedestrian_target] = stopidx++;
        stop_quaycode.push_back(quaycoderef);
        stop_latitude.push_back(latitude);
        stop_longitude.push_back(longitude);
        stop_pedestrian.push_back(pedestrian_target);
        stop_pedestrian_distance.push_back(geo_dist(pedestrian_graph.latitude[pedestrian_target], pedestrian_graph.longitude[pedestrian_target], latitude, longitude));
    }   
}

[ben-strasser]

How to determine the largest strongly connected component? Or better put: is it possible to make it discrete?

https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

Attached is some code that I have in a different non-RoutingKit code base and that computes among other things strongly connected components. I unfortunately do not have the time to adapt it. However, if someone has the time... Patches are welcome. :)

scc.txt