Version:

Solve Graph - Multiple Routing (Seattle)

The following is a complete example, using the Python API, of solving a graph created with Seattle road network data for a multiple routing problem via the /solve/graph endpoint. For more information on network graph solvers, see Network Graphs Solver Concepts.

Prerequisites

The prerequisites for running the multiple routing solve graph example are listed below:

Python API Installation

The native Kinetica Python API is accessible through the following means:

  • For development on the Kinetica server:
  • For development not on the Kinetica server:

Kinetica RPM

In default Kinetica installations, the native Python API is located in the /opt/gpudb/api/python directory. The /opt/gpudb/bin/gpudb_python wrapper script is provided, which sets the execution environment appropriately.

Test the installation:

/opt/gpudb/bin/gpudb_python /opt/gpudb/api/python/examples/example.py

Important

When developing on the Kinetica server, use /opt/gpudb/bin/gpudb_python to run Python programs and /opt/gpudb/bin/gpudb_pip to install dependent libraries.

Git

Python 2.7 (or greater) is necessary for downloading the API from GitHub:

  1. In the desired directory, run the following but be sure to replace <kinetica-version> with the name of the installed Kinetica version, e.g., v7.0:

    git clone -b release/<kinetica-version> --single-branch https://github.com/kineticadb/kinetica-api-python.git
    
  2. Change directory into the newly downloaded repository:

    cd kinetica-api-python
    
  3. In the root directory of the unzipped repository, install the Kinetica API:

    sudo python setup.py install
    
  4. Test the installation:

    python examples/example.py
    

PyPI

The Python package manager, pip, is required to install the API from PyPI.

  1. Install the API:

    pip install gpudb --upgrade
    
  2. Test the installation:

    python -c "import gpudb;print('Import Successful')"
    

    If Import Successful is displayed, the API has been installed as is ready for use.

Data File

The example script makes reference to a road_weights.csv data file in the current directory. This can be updated to point to a valid path on the host where the file will be located, or the script can be run with the data file in the current directory.

CSV = "road_weights.csv"

Script Detail

This example is going to demonstrate solving for the shortest possible route between destination points and a source point located in a Seattle road network.

Constants

Several constants are defined at the beginning of the script:

  • HOST / PORT -- host and port values for the database
  • OPTION_NO_ERROR -- reference to a /clear/table option for ease of use and repeatability
  • TABLE_SRN -- the name of the table into which the Seattle road network dataset is loaded
  • GRAPH_S -- the Seattle road network graph
  • GRAPH_S_MRSOLVED -- the solved Seattle road network graph using the MULTIPLE_ROUTING solver type
HOST = "127.0.0.1"
PORT = "9191"

OPTION_NO_ERROR = {"no_error_if_not_exists": "true"}

TABLE_SRN = "seattle_road_network"

GRAPH_S = TABLE_SRN + "_graph"
GRAPH_S_MRSOLVED = GRAPH_S + "_multiple_routing_solved"

Graph Creation

One graph is used for the multiple routing solve graph example utilized in the script: seattle_road_network_graph, a graph based on the Seattle road network dataset (the CSV file mentioned in Prerequisites).

The seattle_road_network_graph graph is created with the following characteristics:

  • It is directed because the roads in the graph have directionality (one-way and two-way roads)
  • It has no explicitly defined nodes because the example relies on implicit nodes attached to the defined edges
  • The edges are represented using WKT LINESTRINGs in the WKTLINE column of the seattle_road_network table (EDGE_WKTLINE). The road segments' directionality is derived from the TwoWay column of the seattle_road_network table (EDGE_DIRECTION).
  • The weights are represented using the time taken to travel the segment found in the time column of the seattle_road_network table (WEIGHTS_VALUESPECIFIED). The weights are matched to the edges using the same WKTLINE column as edges (WEIGHTS_EDGE_WKTLINE) and the same TwoWay column as the edge direction (WEIGHTS_EDGE_DIRECTION.
  • It has no inherent restrictions for any of the nodes or edges in the graph
  • It will be replaced with this instance of the graph if a graph of the same name exists (recreate)
print("Creating {}".format(GRAPH_S))
create_s_graph_response = kinetica.create_graph(
    graph_name=GRAPH_S,
    directed_graph=True,
    nodes=[],
    edges=[
        TABLE_SRN + ".WKTLINE AS EDGE_WKTLINE",
        TABLE_SRN + ".TwoWay AS EDGE_DIRECTION"
    ],
    weights=[
        TABLE_SRN + ".WKTLINE AS WEIGHTS_EDGE_WKTLINE",
        TABLE_SRN + ".TwoWay AS WEIGHTS_EDGE_DIRECTION",
        TABLE_SRN + ".time AS WEIGHTS_VALUESPECIFIED"
    ],
    restrictions=[],
    options={
        "recreate": "true"
    }
)

Multiple Routing

Before the seattle_road_network_graph graph is solved, the source node and destination nodes are defined.

source_node = "POINT(-122.1792501 47.2113606)"
destination_nodes = [
    "POINT(-122.2221 47.5707)", 
    "POINT(-122.541017 47.809121)",
    "POINT(-122.520440 47.624725)", 
    "POINT(-122.467915 47.427280)"
]

Next, the graph is solved with the node type being set to WKTPOINT and the solve results being exported to the response:

solve_s_mrgraph_response = kinetica.solve_graph(
    graph_name=GRAPH_S,
    solver_type="MULTIPLE_ROUTING",
    node_type="NODE_WKTPOINT",
    source_node_id=0,
    destination_node_ids=[],
    source_node=source_node,
    destination_nodes=destination_nodes,
    solution_table=GRAPH_S_MRSOLVED,
    options={"export_solve_results": "true"}
)["result_per_destination_node"][0]

The cost for the source node to visit the destination nodes is represented as time in minutes:

Cost (in minutes) for source node ID POINT(-122.1792501 47.2113606) to visit destination node IDs
['POINT(-122.2221 47.5707)', 'POINT(-122.541017 47.809121)', 'POINT(-122.520440 47.624725)', 'POINT(-122.467915 47.427280)']: 240.35945638

The solution output to WMS:

../../_images/seattle_mr_solved.png

Download & Run

Included below is a complete example containing all the above requests, the data files, and output.

To run the complete sample, ensure the solve_graph_seattle_multi_route.py and road_weights.csv files are in the same directory (assuming the locations were not changed in the solve_graph_seattle_multi_route.py script); then switch to that directory and do the following:

  • If on the Kinetica host:

    /opt/gpudb/bin/gpudb_python solve_graph_seattle_multi_route.py
    
  • If running after using PyPI or GitHub to install the Python API:

    python solve_graph_seattle_multi_route.py