dijkstra (#16) - Different stopping conditions/preserving Dijkstra tree (#146) - Message List

Different stopping conditions/preserving Dijkstra tree

Hi!

I have a similar problem related with “Preserving Dijkstra Tree”. The question can be formulated in the following way: I want to get the shortest path from vertex vx (which is know and defined by its integer id) to vy (defined as the first vertex that appears in the tree having attribute/class/category: w). This is a well known problem in landscape ecology and can be translated into this: find the closest vertex vy (class: ‘forest’) from vx (with the same class as vy: ‘forest’). This is known as Functional Nearest Neighbor. Accessing the tree would be very useful and also knowing the class type for each predecessor vertex inserted. At this point I just need to be aware if solving this problem needs digging into the routing library because that goes away beyond my coding skills.

Thanks!

  • Message #497

    If I understood it well, you need to keep the tree of predecessors from the Dijkstra search result to calculate the distance in meters to the nearest neighbor along the shortest path, right?

    It is interesting. Unfortunately, the shortest path implementations we have now in pgRouting don't take any class type from the database. But, of course, it can be changed.

    Can you provide me with any papers or articles describing FNN problem (I couldn't find any)?

    • Message #498

      Hi! Thanks for taking some time to delve into this problem. Yes, you got the right impression of the question. The idea for keeping the tree is being able to trigger a process that asks the vertices dataset if the class/category of the inserted predecessor vertex has got the same class/category as the start vertex, and in that case stops the process. In other words the nearest neighbor in the shortest path tree having the same class/category as the start vertex. FNN can also be described as the Dijkstra Nearest Neighbor where both start and end vertexes share the same class/category type. I have some interesting pictures for the graph implementation but I’m not sure were/how to post them. Regarding the documentation it’s easier to find material in books however in Fragstats (the de facto software for landscape analysis in raster format) FNN has a good definition that follows:

      FNN = hij*

      (hij* distance (m) from patch ij to its nearest neighboring patch of the same type (class), based on least cost path edge-to-edge distance, computed from cell center to cell center.)

      Description

      FNN equals the distance (m) to the nearest neighboring patch of the same type, based on the least cost path edge-to-edge distance. Note that the edge-to-edge distances are from cell center to cell center. Range

      FNN > 0, without limit.

      FNN approaches 0 as the distance to the nearest neighbor decreases. The minimum FNN is constrained by the cell size, and is equal to twice the cell size when the 8-neighbor patch rule is used or the distance between diagonal neighbors when the 4-neighbor rule is used. The upper limit is constrained by the extent of the landscape. FNN is undefined and reported as "N/A" in the “basename”.patch file if the patch has no neighbors (i.e., no other patches of the same class).

      Comments

      Functional nearest-neighbor distance accounts for one of the major shortcomings of using Euclidean distance to assess ecological relationships; namely, that the shortest geographic distance may not be the shortest ecological distance as perceived by an organism or process.

      I’ll try to find more material meanwhile. There are some articles with restricted access due to faculty license limitations it’s a damn drag. Please keep me posted!

      :: kamo

      • Message #499

        Can you please send all pictures and papers you have to anton <at> orkney <dot> co <dot> jp ? I would be glad to look at them.

        based on least cost path edge-to-edge distance, computed from cell center to cell center

        How to define cells?

        • Message #500

          Hi!

          Using the strict definition from Fragstats is a completely different approach mainly because it’s based on raster data formats however the principle remains. Setting up an analysis matrix with cells (=pixels) could be hard to tackle and changes the focus of the work from vector/graph formats to raster. The idea is to bring up new analysis methodologies into landscape ecology.

          I think I can narrow down the problem with some low level stuff. The shortest_path() function looks like this when I want to find the route from vertex 1 to 25:

          SELECT * FROM shortest_path(

          'SELECT gid AS id,

          source::int4 AS source, target::int4 AS target, length::double precision AS cost FROM public.nlm_graph_full',1, 25, false, false)

          For FNN analysis the target vertex should be a set in this form:

          SELECT a.gid FROM public.nlm_graph_full a WHERE a.class = (SELECT b.class

          FROM public.nlm_graph_full b WHERE b.gid = Source_Vertex_GID::integer)

          AND a.gid <> Source_Vertex_GID::integer

          At the routing library there should be a way to stop the Dijkstra algorithm when any single vertex in the target set (query above) is reached/matched. Path and cost extraction should follow starting from the source to the previously mentioned vertex found by the algorithm.

          This kind of graph I’m working is a very special one, first because it’s based uppon vectorial data based on computer generated landscapes and second because all vertexes can be reached from a source one. This also represents more computational density.

          Best regards :: kamo

          • Message #501

            Thanks for the explanation, it is much more clear now.

            Please, file a feature request and I will put FNN into the plan.

            • Message #502

              Done! Also filed a ticket for Win32 installer update and improvement. Can you make an estimate for the required time needed to insert this feature(s)/ request(s)?

              • Message #504

                Thank you!

                Well, FNN can be implemented in few weeks. The only problem is that I'll spend next week at the hospital and then one month sitting at home. I can only promise to try FNN if I would have some time next month. What about win32 installer, we don't have windows engineers here in Orkney and nobody ever made installers here. Now we can only compile pgRouting for win32 (or you can do it with MinGW).

                • Message #505

                  That’s good news!

                  It means that I’ll be able to use these new features in my Msc work. So far I’ve been using an implementation of the Dijkstra algorithm (in php) 10 to 100 times’s slower compared with pgRouting. So it means processing more data in less time with the best performance possible.

                  Regarding the win32 compilation it would be more straightforward for me if this is done by specialists, this is due to my lack of knowledge regarding the use of MinGW, and also related with the fact that I’ve never received formal programming instruction. However with the right guidance I would be pleased to learn it. Win32 installers are great for lame guys (like me) who use this environment (combined with open-source/free tools) for development, and I got the feeling there are many out there so I suppose it’s a good bet.

                  By the way my best wishes for a speedy recovery.

                  • Message #521

                    Hi!

                    Any progress with FNN implementation?

                    • Message #522

                      Sorry, but no progress so far. I'm still sitting at home and quite busy with another task - long distance routing.

                      • Message #523

                        It seems interesting, is it algorithm optimization for dense/long graphs? Please keep me posted for any progress in FNN.

                        • Message #524

                          Exactly. The main bottleneck we have here is data loading. So, I'm trying to find a way how to reduce the number of data to load. I hope that HH* algorithm is the solution. Did you ever hear about that?

                          • Message #525

                            Sorry Anton, but that's a bit out of my league! Does HH stands for Hybrid Hash? Do you have any documentation? With some keywords I could use me faculty's vpn to fetch for papers or related resources.

                            • Message #526

                              No, HH is for Highways Hierarchy. It was invented by Dominik Schultes from University of Karlsruhe. If you try to google it you will find a lot of papers.

                          • Message #527

                            Seems promising I'll have a look at it. I'm always trying to translate algorithmic behaviour into ecologically significant questions so I tend to focus more on top level stuff and less in optimization and implementation. If anything helpfull pops up I'll post it. Seems a great tool to add to pgRouting.