[GraphHopper] There must be bug on the subnetwork removal
Peter
graphhopper at gmx.de
Wed Jul 29 09:28:59 UTC 2015
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
> <mailto: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
>> <mailto: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
>>> <mailto: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 <mailto: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 <mailto: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
>>>>>> <mailto: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
>>>>>>> <mailto: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
>>>>>>>> <mailto: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*
>>>>>>>>
>>>>>>>>
>>>>>
>>>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20150729/28175e7a/attachment.html>
More information about the GraphHopper
mailing list