[GraphHopper] There must be bug on the subnetwork removal

Wed Jul 29 07:50:02 UTC 2015

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
>>
>>
>
>
> _______________________________________________
> GraphHopper mailing listGraphHopper at openstreetmap.orghttps://lists.openstreetmap.org/listinfo/graphhopper
>
>
>
> _______________________________________________
> 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/bb486d69/attachment.html>