[GraphHopper] There must be bug on the subnetwork removal

Wed Jul 29 23:53:55 UTC 2015

Hi Peter,

I verified in the Bay area osm data, it indeed fix this weird "problem".

*Best Regards,*
*ZhiQiang ZHAO*

On Wed, Jul 29, 2015 at 4:57 AM, Peter <graphhopper at gmx.de> wrote:

>  Hi ZhiQiang,
>
> it is indeed the case that such single nodes are SCC and this is not a bug
> in our current algorithm. And it could therefor indeed lead to a
> disconnected areas like you observed. Also your proposed fix of executing
> the oneway removal first would make sense. I've create an issue for this:
> https://github.com/graphhopper/graphhopper/issues/481
>
> Would this solve your original issue too?
>
> Regards,
> Peter
>
>
>
> On 29.07.2015 12:39, John Zhao wrote:
>
> Hi Peter,
>
>  A possible solution could be:
> run oneway network removal first, then run findSubNetwork().
>
>  *Best Regards,*
> *ZhiQiang ZHAO*
>
> On Wed, Jul 29, 2015 at 3:38 AM, John Zhao <johnthu at gmail.com> wrote:
>
>> Hi Peter,
>>
>>  The test case could be:
>>
>>  clique A ---> node c ---> clique B
>>
>>  Clique means SCC, like all connected graph.
>> node c is a SCC, if we assume a node can reach itself.
>>
>>  Actually, an extreme case could be:
>> node a ---> node b ---> node c
>>
>>  each node is a SCC.
>>
>>
>>
>>
>>
>>  *Best Regards,*
>> *ZhiQiang ZHAO*
>>
>>  On Wed, Jul 29, 2015 at 3:24 AM, Peter <graphhopper at gmx.de> wrote:
>>
>>>   Hi ZhiQiang,
>>>
>>> the examples you show are SCC of only 1 node, but the original example
>>> is not a SCC I think, as you have an outgoing and an incoming edge. So I
>>> guess this is a bug or something. Maybe you can provide a failing and small
>>> unit test for this so that I can have a look?
>>>
>>> Also the step 4 is indeed only for informational purposes but will print
>>> new information if the step 3 changed the subnetworks.
>>>
>>> Regards,
>>> Peter
>>>
>>>
>>> On 29.07.2015 11:44, John Zhao wrote:
>>>
>>> Hi Peter,
>>>
>>>  There are a lot of SCC with only 1 node, like:
>>> http://www.openstreetmap.org/node/1707762331
>>>  http://www.openstreetmap.org/node/386885888
>>>  http://www.openstreetmap.org/node/364825950
>>>
>>>  Step 4 is only to findSubnetwork(), and print some info, not removal
>>> them.
>>> So, step 4 is optional.
>>>
>>>  Now I only understand why this happen. :(
>>>
>>>
>>>  *Best Regards,*
>>> *ZhiQiang ZHAO*
>>>
>>> On Wed, Jul 29, 2015 at 2:28 AM, Peter <graphhopper at gmx.de> wrote:
>>>
>>>>  Hi ZhiQiang,
>>>>
>>>> > And the http://www.openstreetmap.org/node/678314919 itself is a SCC.
>>>> size is 1.
>>>>
>>>>  It shouldn't be a SCC im my opinion - is there a bug?
>>>> If it is not a bug - do you have a suggestion for this, like avoiding
>>>> step 4?
>>>>
>>>> Regards,
>>>> Peter
>>>>
>>>>
>>>>
>>>> On 29.07.2015 11:18, John Zhao wrote:
>>>>
>>>> Hi Peter,
>>>>
>>>>  The parameter I set are minOnewayNetworkSize = 20, minNetworkSize =
>>>> 200
>>>>
>>>>  on step 3, despite the node
>>>> http://www.openstreetmap.org/node/678314919, the inside island is a
>>>> SCC, and the size is larger than 20.
>>>> So, this island is kept, instead of removal.
>>>> And the http://www.openstreetmap.org/node/678314919 itself is a SCC.
>>>> size is 1. Then it was removed.
>>>>
>>>>  Then on step 4, the island is recognized as a subnetwork, which has
>>>> size less than 200.
>>>>
>>>>  *Best Regards,*
>>>> *ZhiQiang ZHAO*
>>>>
>>>> On Wed, Jul 29, 2015 at 1:04 AM, Peter <graphhopper at gmx.de> wrote:
>>>>
>>>>>  Hi ZhiQiang,
>>>>>
>>>>> you mean the oneway procedure (step 3) removes nodes+edges leading to
>>>>> further normal subnetwork removal in step 4? This should not happen. The
>>>>> subnetwork should be removed already in step 3.
>>>>>
>>>>> > On step 2, although there is a gate
>>>>> http://www.openstreetmap.org/node/703042503
>>>>> > on http://www.openstreetmap.org/way/6374339
>>>>>  > And gate block that edge.
>>>>>
>>>>>  Because of this gate the island is a oneway subnetwork (!) and should
>>>>> get entirely removed in step 2 IMO.
>>>>>
>>>>> > On step 3, a very important point are removed due to oneway
>>>>>
>>>>>  If just one edge/node is removed there is something wrong. The whole
>>>>> island should be removed.
>>>>>
>>>>> Kind Regards,
>>>>> Peter
>>>>>
>>>>>
>>>>> On 29.07.2015 09:50, John Zhao wrote:
>>>>>
>>>>> Hi Peter,
>>>>>
>>>>>  I know the difference between subnetworks and oneway-subnetworks.
>>>>> I am talking about the step 2 and step 4, not step 3.
>>>>>
>>>>>  step 2 and step 4 are both findSubnetwork() with the same parameter.
>>>>>   minOnewayNetworkSize = 20, minNetworkSize = 200
>>>>>
>>>>>  I think I figure out why this discrepancy occurs.
>>>>> One case is a island in SF bay area. The island has 2 oneway roads
>>>>> connected to the main network.
>>>>> http://www.openstreetmap.org/way/53726398
>>>>>  http://www.openstreetmap.org/way/6374339
>>>>>
>>>>>  On step 2, although there is a gate
>>>>> http://www.openstreetmap.org/node/703042503 on
>>>>> http://www.openstreetmap.org/way/6374339
>>>>> And gate block that edge.
>>>>> The other oneway is connected
>>>>> http://www.openstreetmap.org/way/53726398.
>>>>> So, this island is connected to the whole network.
>>>>>
>>>>>  On step 3, a very important point are removed due to oneway:
>>>>> http://www.openstreetmap.org/node/678314919
>>>>>
>>>>>  Then on step 4, the island are not connected to the main network.
>>>>>
>>>>>  *Best Regards,*
>>>>> *ZhiQiang ZHAO*
>>>>>
>>>>> On Tue, Jul 28, 2015 at 11:12 PM, Peter <graphhopper at gmx.de> wrote:
>>>>>
>>>>>>  Hi ZhiQiang,
>>>>>>
>>>>>> hmmh, not sure if I understand what is unknown at your side.
>>>>>>
>>>>>> Subnetworks are different things than oneway-subnetworks. For example
>>>>>> 4-5 is a oneway subnetwork if connect with a oneway to the main graph only:
>>>>>> mainGraph->4-5
>>>>>>
>>>>>> And this cannot be detected in step 2.
>>>>>>
>>>>>> Please have a look at the unit tests to see more examples for the
>>>>>> different scenes
>>>>>>
>>>>>> Regards,
>>>>>> Peter
>>>>>>
>>>>>>
>>>>>> On 28.07.2015 20:05, John Zhao wrote:
>>>>>>
>>>>>> Hi Peter,
>>>>>>
>>>>>>  the result I posted is not the result of oneway-subnetwork
>>>>>> procedure.
>>>>>>
>>>>>>  The total procedures include:
>>>>>> 1. remove zero-degree node
>>>>>> 2. findSubnetwork
>>>>>> 3. oneway-subnetwork procedure
>>>>>> 4. findSubnetwork again on graphhopper.cleanup()
>>>>>>
>>>>>>  My question is, why those islands are recognized on step 4, but not
>>>>>> on step 2?
>>>>>>
>>>>>>
>>>>>>
>>>>>>  *Best Regards,*
>>>>>> *ZhiQiang ZHAO*
>>>>>>
>>>>>> On Tue, Jul 28, 2015 at 12:02 AM, Peter <graphhopper at gmx.de> wrote:
>>>>>>
>>>>>>>  Hi ZhiQiang,
>>>>>>>
>>>>>>> I think it is because both networks are oneway subnetworks not found
>>>>>>> by the normal subnetwork procedure (but by the oneway-subnetwork procedure)
>>>>>>> and you defined the oneway minimum size to 20
>>>>>>>
>>>>>>> Regards,
>>>>>>> Peter
>>>>>>>
>>>>>>>
>>>>>>> On 28.07.2015 03:13, John Zhao wrote:
>>>>>>>
>>>>>>> Hi Peter,
>>>>>>>
>>>>>>>  What I do is:
>>>>>>> 1. minOnewayNetworkSize = 20, minNetworkSize = 200
>>>>>>> 2. build san francisco bay area osm data
>>>>>>> 3. I print out the subnetworks result of the second call.
>>>>>>>
>>>>>>> int remainingSubnetworks = preparation.findSubnetworks().size();
>>>>>>>
>>>>>>> 4. I found the subnetwork has some smaller than 200, like:
>>>>>>>
>>>>>>> subnetwork start from: 37.32611992939085,-121.9961998312816 size: 24
>>>>>>>
>>>>>>> subnetwork start from: 37.78373608999855,-122.25065187925067 size: 34
>>>>>>>
>>>>>>>  5. I can't understand why the subnetworks with 24 nodes and 34 nodes are not removed by preparation.doWork();
>>>>>>>
>>>>>>> It call the same method:
>>>>>>>
>>>>>>> Map map = this.findSubnetworks();
>>>>>>>
>>>>>>>
>>>>>>>  *Best Regards,*
>>>>>>> *ZhiQiang ZHAO*
>>>>>>>
>>>>>>> On Mon, Jul 27, 2015 at 12:54 PM, Peter <graphhopper at gmx.de> wrote:
>>>>>>>
>>>>>>>>  Hi John,
>>>>>>>>
>>>>>>>> sorry, I do not understand your problem or question here. Would you
>>>>>>>> describe it again step by step for me :) ?
>>>>>>>>
>>>>>>>> Kind Regards,
>>>>>>>> Peter
>>>>>>>>
>>>>>>>>
>>>>>>>> On 27.07.2015 21:45, John Zhao wrote:
>>>>>>>>
>>>>>>>> Hi Peter,
>>>>>>>>
>>>>>>>>  Thanks.
>>>>>>>> Actually I only have 1 flagEncoder in the EncodingManager.
>>>>>>>> The call is exact same, preparation.findSubnetworks()
>>>>>>>>
>>>>>>>> preparation.findSubnetworks() using edgeFilter which is also from singleEncoder.
>>>>>>>>
>>>>>>>>
>>>>>>>>  *Best Regards,*
>>>>>>>> *ZhiQiang ZHAO*
>>>>>>>>
>>>>>>>> On Sun, Jul 26, 2015 at 7:56 AM, Peter <graphhopper at gmx.de> wrote:
>>>>>>>>
>>>>>>>>>  Hi John,
>>>>>>>>>
>>>>>>>>> it should not be related to calling these method twice. It is just
>>>>>>>>> one time where you calculate the subnetworks independent of any FlagEncoder
>>>>>>>>> or direction via findSubnetworks and the second pass is FlagEncoder- and
>>>>>>>>> access-dependent via removeDeadEndUnvisitedNetworks.
>>>>>>>>>
>>>>>>>>> Regards,
>>>>>>>>> Peter
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On 24.07.2015 21:16, John Zhao wrote:
>>>>>>>>>
>>>>>>>>> Hi Peter,
>>>>>>>>>
>>>>>>>>>  I am still confused.
>>>>>>>>> at first we call
>>>>>>>>> map = findSubnetworks();
>>>>>>>>>
>>>>>>>>>  after the cleanup, we call the same method in Graphhopper.
>>>>>>>>>
>>>>>>>>> int remainingSubnetworks = preparation.findSubnetworks().size();
>>>>>>>>>
>>>>>>>>> Why the subnetwork was recognized the latter time, but not the first time?
>>>>>>>>>
>>>>>>>>> we remove some edges make it not connected?
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>  *Best Regards,*
>>>>>>>>> *ZhiQiang ZHAO*
>>>>>>>>>
>>>>>>>>> On Thu, Jul 23, 2015 at 2:22 PM, Peter <graphhopper at gmx.de> wrote:
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>  Hi ZhiQiang,
>>>>>>>>>>
>>>>>>>>>> yes, according to the wiki this is wrongly mapped:
>>>>>>>>>> * Avoid tagging highway intersections as that does not make clear
>>>>>>>>>> which way has the impediment. *
>>>>>>>>>>
>>>>>>>>>> http://wiki.openstreetmap.org/wiki/Tag:barrier%3Dgate
>>>>>>>>>>
>>>>>>>>>> Peter
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On 23.07.2015 23:16, John Zhao wrote:
>>>>>>>>>>
>>>>>>>>>> Hi Peter,
>>>>>>>>>>
>>>>>>>>>>  Maybe the following one related with
>>>>>>>>>> https://github.com/graphhopper/graphhopper/issues/388#issuecomment-88066385
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>  I have a look at 37.32611992939085,-121.9961998312816.
>>>>>>>>>> It seesm related with barrier=gate at intersection.
>>>>>>>>>> http://www.openstreetmap.org/node/1126492194
>>>>>>>>>>
>>>>>>>>>>  *Best Regards,*
>>>>>>>>>> *ZhiQiang ZHAO*
>>>>>>>>>>
>>>>>>>>>> On Thu, Jul 23, 2015 at 2:11 PM, Peter <graphhopper at gmx.de>
>>>>>>>>>> wrote:
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>  There are two types of subnetworks and the smaller ones seems
>>>>>>>>>>> to be 'one-way subnetworks' which means they are eg. only reachable as
>>>>>>>>>>> destination or start. But if you would start from a destination-only
>>>>>>>>>>> subnetwork you'll get 'not found' for all points outside of this network.
>>>>>>>>>>>
>>>>>>>>>>> Regards,
>>>>>>>>>>> Peter
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> On 23.07.2015 23:03, John Zhao wrote:
>>>>>>>>>>>
>>>>>>>>>>>  Interesting,
>>>>>>>>>>> when I increase minOnewayNetworkSize from 20 to 50, the
>>>>>>>>>>> following two disappeared.
>>>>>>>>>>>  subnetwork start from: 37.32611992939085,-121.9961998312816
>>>>>>>>>>> size: 24
>>>>>>>>>>> subnetwork start from: 37.78373608999855,-122.25065187925067
>>>>>>>>>>> size: 34
>>>>>>>>>>>
>>>>>>>>>>>  *Best Regards,*
>>>>>>>>>>> *ZhiQiang ZHAO*
>>>>>>>>>>>
>>>>>>>>>>> On Thu, Jul 23, 2015 at 1:55 PM, John Zhao <johnthu at gmail.com>
>>>>>>>>>>> wrote:
>>>>>>>>>>>
>>>>>>>>>>>> Hi,
>>>>>>>>>>>>
>>>>>>>>>>>>  I tried car flag encoder with following parameter on San
>>>>>>>>>>>> Francisco bay area data from mapzen.
>>>>>>>>>>>>
>>>>>>>>>>>> https://s3.amazonaws.com/metro-extracts.mapzen.com/san-francisco-bay_california.osm.pbf
>>>>>>>>>>>>
>>>>>>>>>>>>  minNetworkSize=200
>>>>>>>>>>>> minOnewayNetworkSize=20
>>>>>>>>>>>>
>>>>>>>>>>>>  I printed all the remaining subnetworks.
>>>>>>>>>>>>  edges: 591932, nodes 437420, there were 3496 subnetworks.
>>>>>>>>>>>> removed them => 13121 less nodes. Remaining subnetworks:5
>>>>>>>>>>>> The remaining subnetworks are:
>>>>>>>>>>>> subnetwork start from: 37.32611992939085,-121.9961998312816
>>>>>>>>>>>> size: 24
>>>>>>>>>>>> subnetwork start from: 37.56018439442332,-122.30257814308803
>>>>>>>>>>>> size: 436637
>>>>>>>>>>>> subnetwork start from: 37.78373608999855,-122.25065187925067
>>>>>>>>>>>> size: 34
>>>>>>>>>>>> subnetwork start from: 38.180185962770565,-121.70631393878864
>>>>>>>>>>>> size: 301
>>>>>>>>>>>> subnetwork start from: 37.85717050411933,-122.07633641532816
>>>>>>>>>>>> size: 424
>>>>>>>>>>>>
>>>>>>>>>>>>  I don't understand why there is still subnetwork less than
>>>>>>>>>>>> 200 nodes.
>>>>>>>>>>>>
>>>>>>>>>>>>  I have a look at 37.32611992939085,-121.9961998312816.
>>>>>>>>>>>> It seesm related with barrier=gate at intersection.
>>>>>>>>>>>> http://www.openstreetmap.org/node/1126492194
>>>>>>>>>>>>
>>>>>>>>>>>>   *Best Regards,*
>>>>>>>>>>>> *ZhiQiang ZHAO*
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>
>
> _______________________________________________
> GraphHopper mailing list
> GraphHopper at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/graphhopper
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20150729/26f6224d/attachment.html>