A Shortest Path graph solver example with the Python API
The following is a complete example, using the Python API, of solving a graph
created with Seattle road network data for a shortest path problem via the
/solve/graph endpoint. For more information on
Network Graphs & Solvers, see Network Graphs & Solvers Concepts.
Prerequisites
The prerequisites for running the shortest path solve graph example are
listed below:
Change directory into the newly downloaded repository:
1
cd kinetica-api-python
In the root directory of the unzipped repository, install the Kinetica API:
1
sudo python setup.py install
Test the installation (Python 2.7 (or greater) is necessary for running the
API example):
1
python examples/example.py
Data File
The example script references the road_weights.csv data file,
mentioned in the Prerequisites, in the current local directory, by default.
This directory can specified as a parameter when running the example script.
Script Detail
This example is going to demonstrate solving (both individual and batch solve)
for the shortest path between source points and several destination points
located within a road network in Seattle.
Constants
Several constants are defined at the beginning of the script:
SCHEMA -- the name of the schema in which the tables supporting the
graph creation and match operations will be created
Important
The schema is created during the table setup portion of the
script because the schema must exist prior to creating the
tables that will later support the graph creation and match
operations.
TABLE_SRN -- the name of the table into which the Seattle road network
dataset is loaded
One graph is used for the shortest path solve graph example utilized in the
script: seattle_road_network_graph, a graph based on the road_weights
dataset (the CSV file mentioned in Prerequisites).
The GRAPH_S 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 identified by WKTLINE, using WKT LINESTRINGs from the
WKTLINE column of the seattle_road_network table. The road segments'
directionality (DIRECTION) is derived from the TwoWay column of the
seattle_road_network table.
The weights (VALUESPECIFIED) are represented using the time taken to
travel the segment found in the time column of the
seattle_road_network table. The weights are matched to the edges using
the same WKTLINE column as edges (EDGE_WKTLINE) and the same
TwoWay column as the edge direction (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)
create_s_graph_response=kdb.create_graph(graph_name=GRAPH_S,directed_graph=True,nodes=[],edges=[TABLE_SRN+".WKTLINE AS WKTLINE",TABLE_SRN+".TwoWay AS DIRECTION"],weights=[TABLE_SRN+".WKTLINE AS EDGE_WKTLINE",TABLE_SRN+".TwoWay AS EDGE_DIRECTION",TABLE_SRN+".time AS VALUESPECIFIED"],restrictions=[],options={"recreate":"true","enable_graph_draw":"true","graph_table":"seattle_graph_debug"})
Shortest Path
Single Source to Single Destination
The first example illustrates a simple shortest path solve from a single
source node to a single destination node. First, the source node and destination
node are defined.
The cost for the source node to visit the destination node is represented as
time in minutes:
Solve Graph for Shortest Path Solution
1
2
3
4
5
6
Cost per destination node when source node = ['POINT(-122.1792501 47.2113606)']:
+--------------------------+---------------------+
| Destination Node | Cost (in minutes) |
+==========================+=====================+
| POINT(-122.2221 47.5707) | 40.6214 |
+--------------------------+---------------------+
The solution output to WMS:
Single Source to Many Destinations
The second example illustrates a shortest path solve from a single source node
to many destination nodes. First, the source node and destination nodes are
defined. When one source node and many destination nodes are provided, the graph
solver will calculate a shortest path solve for each destination node.
The third example illustrates a shortest path solve from a many source nodes
to many destination nodes. First, the source node and destination nodes are
defined. If many source node and many destination nodes are provided, the graph
solver will pair the source and destination node by list index and calculate a
shortest path solve for each pair. For this example, there are two starting
points (POINT(-122.1792501 47.2113606) and
POINT(-122.375180125237 47.8122103214264)) and paths will be calculated from
the first source to two different destinations and from the second source to two
other destinations.
Important
Calculations from multiple unique sources are faster and more
efficient than calculations with one unique source, but results
may differ slightly between multiple unique source calculations
and single unique source calculations (less than ~1% variance).