shootingstar (#18) - Stranger behaviour with rule involving more than one segment (#397) - Message List

Stranger behaviour with rule involving more than one segment

I have been playing for a while with pgrouting. For most of the part, I have a clear understanding of what you can do and what you can not do, but there is something I found out that I don't really have any answer for.

Here is the situation : A, B, C and D belong to the same street. I want for example to turn from B to D via F and also put a cost from G to D via F.It works if I create only one of the rule. However, both turn restrictions cannot exist together. Implementing one means that the other one won't be taken into account.

| | | |

C | |A

| |

E ---------F-------------- G

| |

D| |B

| | | |

Related to another topic, I already modified the source code so that more than one rule can indeed be applied to the same segment. This situation of having two rules coming from different segment also work fine when all the segment have a rule referring to only 1 segment (Whereas in this case, we refer to two segment) .

First question : has someone already noticed this issue? Second question : is there a way to overcome the situation without manipulating two much the segments?

Regards

flivingstone

PS : I forgot to mention : of course, two rule means two rows having the same information except rule and to_cost. And also, I am using the latest version of PGRouting (1.03, not from svn)

flivingstone_the_sec
10/28/10 02:35:43 (3 weeks ago)
Tree View Flat View (newer first) Flat View (older first)
  • Message #1727

    | | | |

    C | |A

    | |

    E-----F------- G

    | |

    D| |B

    | | | |

    Here is the drawing, if it is not reshaped :-)

    flivingstone_the_sec
    10/28/10 02:39:24 (3 weeks ago)
  • Message #1729

    Hi,

    Actually you always could assign two or more rules to D, since version 1.02 I think. In your case you need to create 2 rows for edge D, one with rule value 'B, F' and another one with rule 'G,F' - both with different to_cost vlaues. One condition is your rows select query must be ordered by gid.

    I hope I understood you correctly.

    Cheers, Anton.

    anton
    10/28/10 13:34:32 (3 weeks ago)
    • Message #1730

      Thanks Anton.

      So far so good. This already what I have done : to put my description in other words, what I have is

      gid|rule|to_cost

      D|'B,F|'|10000

      D|'G,F|'|10000

      As soon as I add the rule G,F, the rule B,F is no longer taken into account. But I can confirm that my version of PGRouting can handle multiple rule on one segment, because if I configure my rule like this, both rules are taken into account

      D|'C|'|10000

      D|'F|'|10000

      So, in order to recap the problem : multiple turn restriction work fine, but not when it involves rules having more than one segments. At least, that the conclusion I have from my test. The chance that my code modification affected it are very small, but I cannot completely exclude it... So that why I am asking if someone has already noticed that problem.

      Regards

      flivingstone

      flivingstone_the_sec
      10/28/10 22:28:20 (3 weeks ago)
      • Message #1731

        Ah! Now I got it.

        It must be a bug, but yes, you're the first person who noticed this behavior.

        Thanks,

        Anton.

        anton
        10/29/10 11:53:29 (3 weeks ago)
        • Message #1735

          Ok, I'll just create a test scenario a try it with the original version of PGRouting and mine. This way, I 'll make sure MY modifications don't wreak the havoc in something that is working fine.

          If it really something related to PGRouting, I should be able to describe exactly how this bug happens, and I hope to come back with either a solution, or at least an accurate description.

          Cheers

          flivingstone

          flivingstone_the_sec
          11/01/10 21:48:11 (3 weeks ago)
          • Message #1737

            That would be great if you could help with this[[BR]] pgRouting is currently looking for a new place for the code repository and it is likely to become a Git repository, which should make it easier for everyone to commit improvements.

            daniel
            11/01/10 23:56:52 (3 weeks ago)
            • Message #1741

              It sounds great. I am really glad if I can help in any way. Still so far,I am not sure where the problem is coming from. Some of my queries were not ordered by id. It is a starting point, but it doesn't solve everything. I got back to my testing with the original version of PGRouting, and I am building every possible scenario. I'll let you know, it can be helpful for the community.

              Still, I have one additionnal question, because some results include a U-Turn on the same segment... I thought it was not supposed to happen. Am I right?

              Fabien

              flivingstone_the_sec
              11/02/10 11:48:03 (3 weeks ago)
              • Message #1743

                Can you please be more specific about U-turns? I didn't get it.

                anton
                11/02/10 22:21:46 (3 weeks ago)
                • Message #1750

                  Ok, so after some testing here is the problem and the solution : For the U-Turns. Let me describe it in another way :

                  You have a big street A. Each side is represented by separated segments with oneway restrictions.

                  The big street A crosses B. A segment of B connects for segments of A. Let's say you have traffic light. At the intersection between A and B. So going straight on A has a cost. Goint from B to A has a cost. Doing a U-Turn on A is forbidden, and you can turn Left from B to A.

                  You need for example one rule involving one segment for going right from B to A, or going straight on A. But you need a rule involving two segments for describing left from B to A and U-Turns between each side of A without ambiguity.

                  But U-Turns and Left Turn share one segment in common. This is where the code in shooting_star_relax is wrong... Well it misses something actually.. See the variable contains???? Lets say I have the segment 3. Doing one of the U-Turn fro street A is descibed by the rule : 1,2. Turning Left is 4,2. So 2 is a segment used in both rules

                  id 3 rule '1,2' id 3 rule '4,2'

                  Let's say we arrive on 3 by passing via 1,2, so U-Turn.What's happening in the relax process : START

                  Step 0 : i = 0

                  Step 1 : Start checking rule 1,2 Step 2: Find the rule for 3 with first element of rule = 2. Step 3 : Get predecessor of the segment 3.... It is 2 :Contains = i Step 4 :Find the rule for 3 with second element of rule = 3. Contains = i Step 5 : Get predecessor of the segment 2.... It is 1 :Contains = i

                  Step 6 : i =1

                  Step 7 : Start checking rule 4,2 Step 8: Find the rule for 3 with first element of rule = 2. Step 9 : Get predecessor of the segment 3....Is is 2 Contains = i Step 10 :Find the rule for 3 with first second of rule = 4. Contains = i Step 11 : Get predecessor of the segment 2.... It is 1 :Contains = -1

                  END And kaboom!!! the rule that we found at step 5 is lost because the variable 'contains' returns to the NO MATCH value... So I haven`t been allowed to give you the code, but I can give you the trick. Create another variable that stores when a rule is found. If contains is reinitiallized after that, use this variable to check that you went through the rule and that contains has been initialized... Am I understandable? Let me know if you are confused... This was quite complex to find and describe ;-)

                  Cheers

                  flivingstone

                  flivingstone_the_sec
                  11/11/10 12:49:30 (9 days ago)
                  • Message #1751

                    Oups.. For my explanation about u-turns. B is a street with both side for driving are represented by one segment.

                    flivingstone_the_sec
                    11/11/10 13:12:30 (9 days ago)
Tree View Flat View (newer first) Flat View (older first)