1. Spatial Topology and Network Data Model Developer's Guide
  2. Network Data Model
  3. Network Data Model Overview
  4. Network Management and Analysis Using Contraction Hierarchies

5.12 Network Management and Analysis Using Contraction Hierarchies

Contraction hierarchies can be used to find the shortest path in a graph, potentially providing better performance than traditional shortest path algorithms like Dijkstra or A*.

Thus, effective with Release 21c, Spatial provides two approaches for using the network data model:

  • Load on demand (LOD) to support customization with business rules and data.
  • Contraction hierarchies, including a REST API for easy web services development and deployment with static networks.

The contraction hierarchies approach does the following:

  • Precomputes and stores the node order (importance) and shortcut links in a set of files.
  • Finds the shortest path with shortcut links by skipping unimportant nodes during queries.
  • Maps the shortcut links back to the original graph representation.

Using contraction hierarchies involves using a contraction hierarchies REST API for model management and analysis with contraction hierarchies.

Subtopics include:

  • Contraction Hierarchies REST API
  • Contraction Hierarchies REST API Examples
  • Contraction Hierarchies Model Management
  • Contraction Hierarchies Analysis
  • Using the Contraction Hierarchies REST API (including the Web Demo)
  • REST API Reference Information

Contraction Hierarchies REST API

You can use the contraction hierarchies REST API to manage contraction hierarchies models and perform analysis on the models. You can issue requests and receive responses using HTTP and HTTPS protocols. Both JSON and XML formats are supported.

The following figure shows the contraction hierarchies REST API architecture.

Figure 5-4 Contraction Hierarchies REST API Architecture

Description of Figure 5-4 follows
Description of "Figure 5-4 Contraction Hierarchies REST API Architecture"
In the preceding figure:

  • The user's application uses the contraction hierarchies REST API to send requests and receive responses from the contraction hierarchies REST service.

  • When the contraction hierarchies REST service receives a model management request, it passes it to the network data models logic for processing, and receives information back.

    When the REST service receives an analysis request, it passes it to the contraction hierarchies models for processing, and receives information back.

  • The NDM models logic updates the models as needed, communicates information back to the contraction hierarchies REST service, and updates the file(s) containing the relevant contraction hierarchies models.

  • When any updates to contraction hierarchies models are received, the relevant model files are updated.

Several components of the architecture are described in more detail later in this topic.

Contraction Hierarchies REST API Examples

RESTful JSON request for creating a contraction hierarchies network model under a preconfigured directory: 

{"createNetworkRequest":
    {
        "chName":"my_example",
        "networkName":"MY_NETWORK_NAME",
        "dbUrl":"jdbc:oracle:thin:@<host>:<port>:<sid>",
        "dbUser":"my_username",
        "dbPassword":"my_password",
        "processGeometry":true,
        "processTurnRestrictions":false,
        "primaryLinkCostColumn":"LENGTH",
        "primaryCostUnit":"meter",
        "primaryCostScaleFactor":10,
        "secondaryLinkCostColumns":["LENGTH/S"],
        "secondaryCostUnits":["second"],
        "secondaryCostScaleFactors":[10]
    }
}

RESTful JSON request for loading a contraction hierarchies network model into memory: 

{"loadNetworkRequest":
    {
        "chName":"my_example",
        "networkName":"MY_NETWORK_NAME",
        "considerTurnRestrictions":false
    }
}

RESTful JSON request for a shortest path analysis: 

{
    "chName":"my_example",
    "shortestPathRequest":{
        "startPoints" : { "pointOnNet" : [ 
            { "linkId" : 238135, "percentage" : 0.28 } 
        ] }, 
        "endPoints" : { "pointOnNet" : [ 
            { "linkId" : 261315, "percentage" : 0.93 }
        ] },         
        "geometry":true
    }
}

RESTful JSON response for a shortest path analysis (reformatted for readability): 

{
  "shortestPathResponse" : {
    "cost" : 2906.6,
    "geometry" : "{\"type\":\"LineString\",\"coordinates\":[[-74.00501,40.70583],[-74.00457,40.70549],[-74.00447,40.70541],[-74.00418,40.70559],[-74.00386,40.70579],[-74.00361,40.70595],[-74.00346,40.70605],[-74.00335,40.70611],[-74.00318,40.70621],[-74.00231,40.7067],[-74.00274,40.70722],[-74.00311,40.70767],[-74.00336,40.708],[-74.00345,40.70808],[-74.00407,40.70745],[-74.00412,40.70757],[-74.00433,40.70783],[-74.00477,40.70841],[-74.00505,40.70876],[-74.00513,40.70885],[-74.00524,40.70893],[-74.00532,40.70899],[-74.00547,40.70909],[-74.00643,40.70956],[-74.00705,40.70987],[-74.00774,40.71022],[-74.00906,40.71089],[-74.01046,40.71153],[-74.01013,40.71209],[-74.00967,40.71274],[-74.00927,40.71326],[-74.00902,40.71359],[-74.00885,40.71381],[-74.0084,40.71437],[-74.00795,40.71494],[-74.00755,40.71544],[-74.00882,40.71602],[-74.0092,40.71619],[-74.00911,40.71692],[-74.00906,40.71726],[-74.009,40.7176],[-74.00894,40.71793],[-74.00888,40.71827],[-74.00882,40.71864],[-74.00875,40.71903],[-74.0087,40.7193],[-74.00858,40.71996],[-74.00847,40.72065],[-74.00842,40.72089],[-74.00837,40.7212],[-74.00834,40.72133],[-74.00823,40.72198],[-74.00812,40.72264],[-74.00801,40.72328],[-74.00795,40.72365],[-74.00793,40.72376],[-74.00786,40.72382],[-74.00777,40.72388],[-74.00773,40.72392],[-74.00771,40.72393],[-74.00745,40.72412],[-74.00736,40.72417],[-74.00728,40.72424],[-74.00723,40.72429],[-74.0071,40.72441],[-74.00703,40.7245]]}",
    "linkIds" : [ 238135, 69834, 69856, 187992, 39327, 39328, 18867, 189084, 189085, 189086, 189087, 142716, 142717, 142718, 142719, 142720, 193362, 193363, 54588, 54589, 54657, 153376, 68912, 61331, 61332, 177603, 177604, 177605, 177606, 177607, 106801, 96723, 96724, 96725, 96726, 65028, 176816, 176817, 65012, 65013, 65014, 65015, 261314, 261315 ],
    "nodeIds" : [ 42427254, 42427256, 42440356, 3350498747, 42452620, 42457292, 42444271, 42440270, 42440271, 673008453, 42440278, 42440280, 42440282, 42440284, 42440287, 42428385, 42440290, 42453943, 42453952, 42430004, 42429562, 42449597, 42431611, 42445356, 42445357, 42436322, 42430571, 42430529, 42429833, 42436326, 42436327, 42436330, 42436333, 42436335, 42436336, 42424610, 1104165608, 42436308, 42424408, 42436340, 42436014, 4142105822, 42424619, 42424630, 42423514 ],
    "startIndex" : 0,
    "startPercentage" : 0.28,
    "endIndex" : 43,
    "endPercentage" : 0.93
  },
  "unit" : "meter"
}

Contraction Hierarchies Model Management

You can create a contraction hierarchies model from any Spatial network data model in the database. Each model is stored as a set of files under a specific directory.

After creating the model, you can load it into memory and perform analysis.

Contraction Hierarchies Analysis

Several contraction hierarchies analysis functions are supported, including:

  • Shortest Path: the shortest path between two points
  • Multi-Stop Shortest Path: the shortest paths between a sequence of points
  • Cost Matrix: the costs of N start points to M end points in a matrix form (N by M)
  • Traveling Salesperson Path: the shortest path that visits all given points
  • Alternative Paths: K alternative paths with no more than a specific percentage of path overlapping
  • Secondary Cost: get all available secondary costs of a path

Additional analysis information such as path geometry can also be obtained using the REST API.

Using the Contraction Hierarchies REST API

You can use the following steps to develop your application with Contraction Hierarchies REST API:

  1. Deploy the contraction hierarchies ear file (chrest.ear) to any J2EE container.

    This deploys the contraction hierarchies service to handle the REST API.

  2. Create a contraction hierarchies model from a Spatial Network Data Model model in the database, and store the contraction hierarchies model on the file system.

  3. Perform analysis by loading a contraction hierarchies model into memory.

The chrest.ear file also comes with a demo that shows how to use the REST API. To use this demo, go to this URL: 

https://<host>:<port>/chrest/

The Contraction Hierarchies Web Demo main page lets you query logical and spatial network data stored in files, to perform analysis functions of the Spatial Network Data Model.

The available links in this demo include:

  • Documentation & Schema
  • Contraction Hierarchies Network Analysis
  • Visualization Demo
  • Configuration

REST API Reference Information

For reference information about the REST API for contraction hierarchies support, see REST API for Oracle Spatial.

Parent topic: Network Data Model Overview