Graphhopper: Wrong subnetwork detections&removal leads to a more disconnected graph

[karussell]

There is a problem (for motor vehicles only) here and here, screenshots:

No connection found although no access restriction nor barrier node was found which could causing this. I can also not reproduce this when downloading the whole island (works as expected) so it could be some subnetwork-removal bug or a data issue which is now already cleaned up. Does someone know how to get the OSM of a certain time? For now closing here, as the specific road also contained a oneway bug which is now removed and will very likely fix the problem

[karussell]

I can reproduce it now via localhost

[oblonski]

Do you know the reason for this already?

[karussell]

It incorrectly detects the part of the road (and connected roads) as oneway-subnetwork and removes it from the graph. But what exactly goes wrong I do not know yet ... still debugging ...

[karussell]

Ok, can now reproduce it in a unit test and understood what is going on. The long oneway 'Route du Sud' causes several legs on right and left being treated as subnetworks, they would be removed as they are small and all would be fine i.e. the target 'half-island' (eastern area) which is only reachable through this single road would be still reachable.

But these two nodes connect the corresponding two right&left subnetworks into one network which leads to the removal of the two edges of the 'Route du Sud' in-between (which leads to surrounding edges being disconnected too and removed until the bridge and towards the 'Rue Algaoué')

At the moment I only guess that one could probably fix this with an edge-based Tarjan search but as this is a rare issue this is probably not a higher priority. Also not even in this case something is really wrong as when the tagging is fixed everything should be fine.

    @Test
    public void testTarjan_issue761()
    {
        GraphHopperStorage g = createStorage(em);
        // oneway main road
        g.edge(0, 1, 1, true);
        g.edge(1, 2, 1, true);
        g.edge(2, 3, 1, false);
        g.edge(3, 4, 1, false);
        g.edge(4, 5, 1, false);

        // component 1
        g.edge(3, 6, 1, true);
        g.edge(6, 7, 1, true);
        g.edge(7, 8, 1, true);

        // component 2 which makes the two nodes 2 and 4 'critical'
        g.edge(4, 9, 1, true);
        g.edge(9, 10, 1, true);
        g.edge(10, 11, 1, true);
        g.edge(11, 2, 1, true);

        // component 3
        g.edge(5, 12, 1, true);
        g.edge(12, 13, 1, true);
        g.edge(13, 14, 1, true);
        g.edge(14, 15, 1, true);
        g.edge(15, 13, 1, true);
        g.edge(15, 16, 1, true);

        final EdgeFilter filter = new DefaultEdgeFilter(carFlagEncoder, false, true);
        TarjansSCCAlgorithm tarjan = new TarjansSCCAlgorithm(g, new GHBitSetImpl(), filter);
        List<TIntArrayList> components = tarjan.findComponents();
        assertEquals(2, components.size());
        // component 3
        assertEquals(new TIntArrayList(new int[]
        {
            14, 16, 15, 13, 12, 5
        }), components.get(0));

        // component 2 and 1 should not merge into one. But they do and even merge
        // with the main road leading to removal of several edges of the main road
        assertNotEquals(new TIntArrayList(new int[]
        {
            8, 7, 6, 3, 4, 9, 10, 11, 2, 1, 0
        }), components.get(1));
    }

[michaz]

Do we still think this is a bug? Because I don't.

The two components found by Tarjan's algorithm seem correct to me. It doesn't know what a main road is -- the biggest component will survive, and removing the others shouldn't change the connectedness of the biggest one.

So in this case, 14, 16, 15, 13, 12, 5 should be removed.

[easbar]

Yes I agree with @michaz here. Here is the graph from above unit test:

        //     11-10-9
        //     |     |
        // 0-1-2->3->4->5
        //        |     |
        //        6     12
        //        |     |
        //        7     13-14
        //        |       \|
        //        8        15-16

It has two strongly connected components and the one in the East (separated by the rest of the graph by the directed edge 4->5) is the smaller one here.

component 2 and 1 should not merge into one.

Why not? For the nodes 3,6,7,8,4,9,10,11,2 we can go inbetween any pair of nodes, so they belong to the same component.

and even merge with the main road leading to removal of several edges of the main road

Why does merging some components to each other lead to the removal of some edges? The bigger a component is the less likely it is that it will be removed (depending on the min network size parameter).

I think the confusion is maybe because of the BFS we are using to detect subnetworks. This is just not the right thing todo in a directed graph. The size of the components might depend on the order we inspect the nodes this way. For example if we started the BFS at node 0 here we would find a single component, but if we started it at node 5 we would find two. I am currently in the process of fixing this.

[karussell]

Ok let's close here (I do not understand the original issue anymore :/ )