This discussion is archived
4 Replies Latest reply: Sep 18, 2013 1:55 AM by Luc Van Linden RSS

Populating Path$ and Path_Link$ tables / Implementing Turn Restrictions

Mike_987654321 Newbie
Currently Being Moderated

Hi,

 

I'm currently doing a network tracing application using A Star Shortest Path in network data model.

An example of my network is below:

 

           /     L1     \               /     L4     \               /     L7     -     E1

C1     -     L2     -     M1     -     L5     -     M2     -     L8     -     E2

          \     L3     /               \     L6     /               \     L9     -     E3

 

note: cost per link = 1

NODESLINKS

C1

M1

M2

L1

L2

L3

L4

L5

L6

L7

L8

L9

E1

E2

E3

C1 - L1

C1 - L2

C1 - L3

L1 - M1

L2 - M1

L3 - M1

M1 - L4

M1 - L5

M1 - L6

L4 - M2

L5 - M2

L6 - M2

M2 - L7

M2 - L8

M2 - L9

L7 - E1

L8 - E2

L9 - E3

 

My problem is how do I populate the Path and Path Link Table so when I trace I would be getting the following results?

C1 to E1:

     C1 - L1 - M1 - L4 - M2 - L7 - E1

C1 to E2:

     C1 - L2 - M1 - L5 - M2 - L8 - E2

C1 to E3:

     C1 - L3 - M1 - L6 - M2 - L9 - E3

 

When I do a shortest path trace for example C1 to E1, the result I get is :C1 - L2 - M1 - L4 - M2 - L8 - E1 which is not the correct path that I wanted.

The only way that I think to do this is to populate the Path and Path Link tables. But how would I do that? I can't find any samples in Oracle Documentation on how would I populate these 2 tables.

 

Also, I also found this document http://download.oracle.com/otndocs/products/spatial/pdf/oow2010/spatial/spatialoow10_bldgappsndm.pdf

Turn Restriction is presented on page 37 - 39 but I don't know how would I implement this.

Should I just alter my LINK$ table and add RESTRICTED_LINKS column then Java API for NDM will be able to implement the turn restriction constraint?

Giving me sample codes and references to do this would greatly help me.

Thank you very much.

  • 1. Re: Populating Path$ and Path_Link$ tables / Implementing Turn Restrictions
    Luc Van Linden Pro
    Currently Being Moderated

    HI Mike

     

    You gave a clear situation on your data-example, however what you are trying to achieve or what your business question is, is not clear at all to me.

     

    Given your network layout, your link cost (all = 1) and no other restrictions on the node, will make all paths from C1 to E1; E2, E3 valid shortest paths.

     

    What are you drivers to get your path being THE shortest path?

    What would be the turn restrictions in your case?

     

    Yes you could populate the Path and Path link table yourself, however this is what normally the network analysis will give you as a (persistent) result if you need so.

     

    You could also set the node cost in that way that your path will be returned, however the question remains what does your data really represents and what are you actually trying to achieve?

     

     

    Luc

  • 2. Re: Populating Path$ and Path_Link$ tables / Implementing Turn Restrictions
    Mike_987654321 Newbie
    Currently Being Moderated

    Hi Luc,

    Thanks for the reply.

     

    I guess populating the Path and Path Link tables is not a good Idea.

     

    Maybe I should go for the Turn Restrictions. As for my example, the turn restriction that I would want for my data will be as follows:

               /     L1     \               /     L4     \               /     L7     -     E1

    C1     -     L2     -     M1     -     L5     -     M2     -     L8     -     E2

              \     L3     /               \     L6     /               \     L9     -     E3

     

    L1-M1 is restricted to M1-L4

    L2-M1 is restricted to M1-L5

    L3-M1 is restricted to M1-L6

     

    L4-M2 is restricted to M2-L7

    L5-M2 is restricted to M2-L8

    L6-M2 is restricted to M2-L9

     

    Through this restriction I will be able to do a network trace like this (This is what I am trying to achieve):

    C1 to E1:

         C1 - L1 - M1 - L4 - M2 - L7 - E1

    C1 to E2:

         C1 - L2 - M1 - L5 - M2 - L8 - E2

    C1 to E3:

         C1 - L3 - M1 - L6 - M2 - L9 - E3

     

    My question now will be, how would I implement this in my LOD-NDM Java API? I can't find any samples on how to implement this.

    based on the pdf link on my previous message, they have a field named RESTRICTED_LINKS in their LINK$ table. Is this added by just altering the LINK$ table or do I need to execute a command for RESTRICTED_LINKS to be added to my LINK$ table?

    How will I also be able to use this RESTRICTED_LINKS field for my LOD-NDM java API in LODNetworkConstraints? I'll be really glad if someone could provide me sample codes on how to implement this.

     

    Thank you very much

  • 3. Re: Populating Path$ and Path_Link$ tables / Implementing Turn Restrictions
    Luc Van Linden Pro
    Currently Being Moderated

    Hi Mike

     

    If (turn) restrictions is what your use-case demands then yes you will have to implement this.:

     

    Here you will find the ndm_tutorial with good examples: NDM Graph Sample Code

     

    You will find the example

    Shortest Path Analysis With Turn Restrictions

     

    In short, you will have to implement a java class which is a Network constraint.

    This needs to follow the implementation of Network constraint.which requires you to give it minimum of 5 methods (11R2, believe earlier versions required only isSatified if recall well).

    This is explained on page 37 of the pdf doc you mentioned.

     

    So in your networkLink table you need to add a column that stores for those links a string delimited comma list of target id which will be used during the network analysis.

    You do so by implementing the method isSatified which must return Boolean TRUE or FALSE.

    In your implementation of this method (as part of your network constraint), you will build you logic to validate if for a link the candidate target links can be reached or not.

    This means you can store those list target id's, either as a restriction (you can only go there) or as exclusion (you cannot go there). It is in the isSatified method that you will take care of your logic in combination with your data.

     

    The example on page 39 of the pdf doc, stores for link 1 the ID's '7,8', which in this case means from link 1 you CANNOT go to link 7 nor to link 8. (explained on page 38)

    This will be analyzed during the network analysis. The example Shortest Path Analysis With Turn Restrictions,

    has a network constraint ProhibitedTurnConstraint class, which in turn has a method isSatified which will take care of such rule returning TRUE or False to the network analysis.

     

    It does so by creating a hashMap and a specific isTurnValid methos, being called by the isSatified method.

     

    The java API documentation can be found here:

     

    Oracle Spatial Java API Reference

     

    I hope this give you a push in teh right direction. IF you think so maybe you can add some rewarding points

     

    Good luck

     

    Luc

  • 4. Re: Populating Path$ and Path_Link$ tables / Implementing Turn Restrictions
    Luc Van Linden Pro
    Currently Being Moderated

    In addition

     

    yes you will have to add your USER DATA column using an alter table statement.

     

    explained here in section 5.9 second alinea: Network Data Model Overview

     

    Then you need to register this as explained to make it accesible in the java api:

     

    explained in section 5.13.6: 5.13.6 User-Defined Data Example (PL/SQL and Java)

     

    Note: as far as I can see, this getUserData is not shown in teh above mentioned example, but should go in the logic where the pTurnMap is created.

     

    Luc

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points