[GraphHopper] There must be bug on the subnetwork removal
Peter
graphhopper at gmx.de
Wed Jul 29 10:24:10 UTC 2015
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
> <mailto: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
>> <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/4cc1928b/attachment.html>
More information about the GraphHopper
mailing list