Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Already on GitHub? Sign in to your account

Improved logic to the Prune Floating Islands #947

Open
benmoovit opened this Issue Dec 31, 2012 · 20 comments

Comments

Projects
None yet
5 participants
Contributor

benmoovit commented Dec 31, 2012

Hi
I have updated the Prune Floating Islands method so it will distinguish three types of islands
1a. small island with one or more stops
1b. big island with more then one stop
2. islands without stops

After testing some examples, It's look like that only the first type need to be removed from the graph, since it create a trap.
for example in case of a platform (at a train station) we will get a small island the the stop is connected to it and there is no way walking in or out of it.

this model is also create an csv file that display (generally, not detailed) the islands in the graph.
I'll be happy to hear yours opinion on this.

Thanks

Contributor

novalis commented Dec 31, 2012

The description of this patch does not seem to match the contents of the patch.

Contributor

benmoovit commented Dec 31, 2012

yes I know I'm have hard time with git, trying to fix this

@benmoovit benmoovit added a commit to benmoovit/OpenTripPlanner that referenced this issue Dec 31, 2012

@benmoovit benmoovit fix #947
improved_logic_in_the_prune_isolated_islands_considering_islands_with_stops
dcfe6b5
Contributor

benmoovit commented Dec 31, 2012

OK now its here, I'll be happy to hear yours opinion

Contributor

novalis commented Dec 31, 2012

Overall, looks good. If you can get rid of the "Created with IntelliJ IDEA" cruft, and add a license notice to Subgraph.java, that would be nice.

Contributor

novalis commented Dec 31, 2012

(also, feel free to submit a pull request that I can merge)

@benmoovit benmoovit added a commit to benmoovit/OpenTripPlanner that referenced this issue Jan 1, 2013

@benmoovit benmoovit fix #947
license notice added to subgarph class
a2627c5

@novalis novalis closed this in 2dbc0a6 Jan 1, 2013

Contributor

skywave commented Jan 4, 2013

I'm getting an error:
Exception in thread "main" java.lang.NullPointerException
at org.opentripplanner.graph_builder.impl.PruneFloatingIslands.buildGraph(PruneFloatingIslands.java:63)
at org.opentripplanner.graph_builder.GraphBuilderTask.run(GraphBuilderTask.java:127)
at org.opentripplanner.graph_builder.GraphBuilderMain.main(GraphBuilderMain.java:51)

I'm seeing the same error as skywave when graph building on Singapore data.

Contributor

benmoovit commented Jan 5, 2013

Hi
It's looks like you missing a components in the graph_builder.xml
Can you please send it?

Hi, the only change to my graph_builder.xml is to comment out the prune floating islands stuff, as that's the only way I can build without a crash.

Regards

Jon

<bean id="transitStreetLink" class="org.opentripplanner.graph_builder.impl.TransitToStreetNetworkGraphBuilderImpl"/>
<bean id="checkGeometry" class="org.opentripplanner.graph_builder.impl.CheckGeometryGraphBuilderImpl"/>
<bean id="raptorBuilder" class="org.opentripplanner.graph_builder.impl.raptor.RaptorDataBuilder"/>
<bean id="transitComputer" class="org.opentripplanner.graph_builder.impl.transit_local_streets.TransitLocalStreetComputer"/>
<bean id="mapBuilder" class="org.opentripplanner.graph_builder.impl.map.MapBuilder"/>
<!-- <bean id="pruneBuilder" class="org.opentripplanner.graph_builder.impl.PruneFloatingIslands"/>-->
<bean id="graphBuilderTask" class="org.opentripplanner.graph_builder.GraphBuilderTask">
    <!-- typical config -->
    <property name="path" value="/Users/jon/github/sggtfs/graphs/singapore"/>
    <property name="graphBuilders">
        <list>
            <ref bean="gtfsBuilder"/>
            <ref bean="osmBuilder"/>
            <ref bean="mapBuilder"/>
            <!--<ref bean="pruneBuilder"/>-->
            <ref bean="transitStreetLink"/>
            <ref bean="checkGeometry"/>
            <ref bean="raptorBuilder"/>
            <ref bean="transitComputer"/>
        </list>
    </property>
</bean>
Contributor

benmoovit commented Jan 6, 2013

Hello,
Try this bean for the PruneFloatingIslands

<bean id="pruneBuilder" class="org.opentripplanner.graph_builder.impl.PruneFloatingIslands"> <property name="maxIslandSize" value="1000 "/> <property name="islandLogFile" value="island.csv"/> <property name="islandWithStopMaxSize" value="20"/> <property name="transitToStreetNetwork" ref ="transitStreetLink"/> </bean>

I've update the bean in the graph-config.xml in the samples folder, should I add this in any others places ?
I'll improve the log massage in such cases and commit soon.

Contributor

skywave commented Jan 6, 2013

Your bean is hidden by the github markup try apostrophe s

Contributor

benmoovit commented Jan 6, 2013

One more thing if you wont the process to detect islands with stops the process should run after transitStreetLink, so the order in the graphBuilderTask sould be:

    <list>
          <ref bean="gtfsBuilder"/>
          <ref bean="osmBuilder"/>
          <ref bean="mapBuilder"/>
          <ref bean="transitStreetLink"/>
          <ref bean="pruneBuilder"/>
          <ref bean="checkGeometry"/>
          <ref bean="raptorBuilder"/>
          <ref bean="transitComputer"/>
    </list>

The unconnected stop should be reconnected at the end of the process

Contributor

benmoovit commented Jan 6, 2013

I have made small changes so this should not appear again.
I didn't know if to force the process to run after street linking (see note in line 53) or to leave it to the user (in the bean).
I'll be happy to hear some opinions before asking to pull this patch.
Thanks

Contributor

novalis commented Jan 7, 2013

I would say that it should not be forced to run after linking, because street-only networks still want floating island pruned, but won't have linking.

@novalis novalis reopened this Jan 7, 2013

Contributor

benmoovit commented Jan 7, 2013

So, I will leave it as is if anyone wont to run it on a street only network she can use the following configuration:

<bean id="pruneBuilder" class="org.opentripplanner.graph_builder.impl.PruneFloatingIslands">
   <property name="maxIslandSize" value="40 "/>
</bean>

@benmoovit benmoovit referenced this issue Jan 7, 2013

Merged

fix #947 #954

@novalis novalis closed this in a5e3066 Jan 7, 2013

@benmoovit benmoovit added a commit to benmoovit/OpenTripPlanner that referenced this issue Jan 13, 2013

@benmoovit benmoovit bug fix in #947, removed unused StreetTransitLink 76febd1

@benmoovit benmoovit added a commit to benmoovit/OpenTripPlanner that referenced this issue Jan 13, 2013

@benmoovit benmoovit bug fix in #947, removed unused StreetTransitLink (cherry picked from…
… commit 76febd1)
b712e95

@benmoovit benmoovit added a commit to benmoovit/OpenTripPlanner that referenced this issue Jan 13, 2013

@benmoovit benmoovit bug fix in #947, removed unused StreetTransitLink (cherry picked from…
… commit 76febd1)
6bf586f

@novalis novalis added a commit that referenced this issue Jan 13, 2013

@novalis novalis Merge pull request #960 from benmoovit/FixPruneIslands
bug fix in #947, removed unused StreetTransitLink
5b7b1c9
Owner

abyrd commented Jan 23, 2013

I'm jumping into this conversation a bit late since I just compared the code to the comments. At a glance it appears that the code removes disconnected components of the graph below a certain size, with separate size parameters for islands containing stops and those not containing stops.

The initial ticket mentions something different: removing only islands below a certain size that do contain stops. Can you explain whether this is your intent, and if so the reason for intentionally leaving small disconnected islands in the graph?

I ask because up until now my usual practice was to simply do the pruning first, then link the stops to the streets. This automatically avoids having any stops connected to small islands.

Also, can you add javadoc to the PruneFloatingIslands class to explain the behavior and the parameters, both in the case where linking is performed before pruning and where linking is performed after pruning? It is clear from the names that maxIslandSize and islandWithStopMaxSize are thresholds of some kind, but not whether they are upper limits for deletion or retention, and maxIslandSize implies it should apply to all islands, whether they have stops or not.

@abyrd abyrd reopened this Jan 23, 2013

Contributor

benmoovit commented Jan 28, 2013

I'm sorry if the ticket wasn't informational enough, I will try to explain my intention again.
So, I distinguish between three types of islands
1a. small island with one or more stops, for example disconnected rail platforms.
1b. big island with one or more stops, for example a real world island (in the sea :-) ) or small town that is disconnected because the highway that lead to id or missing feathers in the map.
2. islands without stops
while working on osm data I've found that islands form type 1a should be pruned, otherwise stops are connected to platforms and have no way in or out.
In the case of 1b the island should not be pruned since it is a part of the transit network.
up until now the old logic was good enough but if we build an transit network there is no need to save islands with no stops since they not a part of the network and can trap pedestrians, meaning that if a user start or end a trip from this island she will not get any trip, therefore I rather to remove this island from the graph.
I figured that the best way to find if an island contains stop would be by using the network linker. the code is reconnect the detached stop form the small islands by running the network linker again after pruning the islands.
The configuration allowed to run this component before or after the network linker. by using the following configuration it will run exactly like before without the need to run the network linker.

<bean id="pruneBuilder" class="org.opentripplanner.graph_builder.impl.PruneFloatingIslands">
   <property name="maxIslandSize" value="40 "/>
</bean>

I hope that this explain the main idea in this.
I'll be happy to answer any other questions in regards, and when I have a few spare moments I'll write the java docs

Owner

abyrd commented Jan 29, 2013

On 01/28/2013 05:06 PM, benmoovit wrote:

while working on osm data I've found that islands form type 1a should be
pruned, otherwise stops are connected to platforms and have no way in or
out.
In the case of 1b the island should not be pruned since it is a part of
the transit network.

Thanks for your reply. I understand the reason that we keep large
islands and remove small islands. What I do not understand is how the
presence of transit stops affects whether an island is judged to be a
"real" island (large islands) or a connectivity error in OSM (small
islands).

Am I understanding you correctly that your intent is to retain islands
of category 1B, but to remove 1A and 2, i.e. remove ALL islands that do
not contain stops? Your original message implies that you want to retain
all islands of any size that do not contain stops: "only the first type
need to be removed from the graph, since it create a trap". I am
pointing out that without transit stops, tiny islands still create a
trap and are often errors in OSM. By simply removing them before
linking, they will never be linked to transit and no traps are created.

The breakdown into categories and stated goal do not seem to correspond
to the configuration properties, which are two different size cutoffs if
I'm not mistaken. Is it correct to say that the purpose is to set a
different size cutoff for transit-served islands than for pedestrian
islands?

Again, it is of course fine for us to support special use cases but we
need to keep the parameters and purpose clear to other users.

I figured that the best way to find if an island contains stop would be
by using the network linker. the code is reconnect the detached stop
form the small islands by running the network linker again after pruning
the islands.

Yes, this does make sense as a way to determine whether a place is
served by transit.

Contributor

benmoovit commented Feb 19, 2013

The breakdown into categories and stated goal do not seem to correspond
to the configuration properties, which are two different size cutoffs if
I'm not mistaken. Is it correct to say that the purpose is to set a
different size cutoff for transit-served islands than for pedestrian
islands?

There are two main parameters in the configuration:

  1. maxIslandSize, this is the maximum size for island without stops, Islands that do not contains stops under this size will be prune.
  2. islandWithStopMaxSize, this is the maximum size for island with stops, then again island with stops under this size will be prune.

The second parameter distinguish between 1a and 1b types. From my explanation before one could understand that there is no use in the first parameter since island without stops should be prune anyway,so, the first parameter was left in order to allow the previous behavior that was prune any island under N size. Btw, In my configuration it is set to infinite.

If this process will run before the network linker and the first parameter will be set to N the behavior should be identical to the previous one.

One more thing that was added is output of the island, the output is written to a csv file with WKT field for the geometry (which is approximately duo the using in nodes), and the parameter to set the file name is : islandLogFile.

I hope this clarifies the matter, sorry for the inconvenience.

Owner

abyrd commented Feb 26, 2013

No problem, thanks for the explanation. Please change the parameter names so they are consistent with one another and with their purpose, and provide comments and/or documentation of these changes.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment