Version:

Network Graph Solvers

Kinetica provides a generic and extensible design of networks with the aim of being tailored or used for various real-life applications, such as transportation, utility, social, and geospatial. Networks comprise a graph and a solver. A graph represents topological relationships via nodes that are connected by edges; a solver represents the type of solution appropriate for the issue the graph was made to illustrate. Kinetica includes a graph server in default setups. Using several API endpoints, a user can create a graph from several components, solve the graph using one of several solver types, and query the solved graph. The graph server is enabled by default; it can be managed via standard Kinetica Service Management. Graph server logs are available in /opt/gpudb/graph/logs. See the Configuration Reference for more information on configuring the graph server.

../_images/graph_solver_definitions.png

Components and Identifiers

Graph components (e.g., nodes, edges, weights, and/or restrictions) must be defined with varying combinations of the identifiers listed in the tables below to create a graph successfully. Identifiers are flagged aliases that the database knows to look for; existing source columns can be used as identifiers. Note that it will often be the case that source columns are reused for different identifiers because the components must naturally be linked together to create a network graph. For example, source table seattle_road_network has columns WKTLINE (a wkt column), TwoWay (an integer column), and time (also an integer column); these columns could be identified via /create/graph like so:

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 + ".time AS WEIGHTS_VALUESPECIFIED"
    ],
    restrictions=[],
    options={
        "recreate": "true"
    }
)

Important

Identifiers with string supported type can be any type of string column type, e.g., char1 - char256 or unrestricted string.

Nodes

Nodes represent fundamental topological units of a graph. Nodes can be defined with an integer ID, a string name, or geospatial information, e.g., WKT point ("POINT(X Y)") or XY pair. Nodes are optional, as the start and end points of an edge can implicitly be used as nodes.

Identifier Supported Types Description
NODE_ID int, long A number representing a node identifier.
NODE_X float, double, int, long A number representing a node's X or longitude value.
NODE_Y float, double, int, long A number representing a node's Y or latitude value.
NODE_NAME string A string value representing a node's name.
NODE_WKTPOINT wkt A WKT string representing a node's geospatial point, e.g., "POINT(X Y)". See Geospatial Objects for more information on WKTs.

Edges

Edges represent the required fundamental topological unit of a graph that typically connect nodes. Edges can be defined with an integer ID, string name, or geospatial information, e.g., WKT point ("POINT(X Y)"), line ("LINESTRING(X1 Y1, X2 Y2)"), or XY pairs. An edge can be implicitly drawn between two nodes. If an edge is defined using WKT LINESTRINGs, the graph server is capable of splitting many LINESTRING segments into multiple, separate LINESTRINGs, thus creating one edge per LINESTRING segment.

Identifier Supported Types Description
EDGE_ID int, long A number representing an edge identifier.
EDGE_NODE1_ID int, long A number representing the first of the edge's nodes.
EDGE_NODE2_ID int, long A number representing the second of the edge's nodes.
EDGE_WKTLINE wkt A WKT string representing an edge's geospatial line, e.g., "LINESTRING(X1 Y1, X2 Y2)". See Geospatial Objects for more information on WKTs.
EDGE_NODE1_X float, double, int, long A number representing the first of the edge's nodes' X or longitude value.
EDGE_NODE1_Y float, double, int, long A number representing the first of the edge's nodes' Y or latitude value.
EDGE_NODE2_X float, double, int, long A number representing the second of the edge's nodes' X or longitude value.
EDGE_NODE2_Y float, double, int, long A number representing the second of the edge's nodes' Y or latitude value.
EDGE_NODE1_WKTPOINT wkt A WKT string representing the first of the edge's nodes' geospatial point, e.g., "POINT(X1, Y1)". See Geospatial Objects for more information on WKTs.
EDGE_NODE2_WKTPOINT wkt A WKT string representing the second of the edge's nodes' geospatial point, e.g., "POINT(X2, Y2)". See Geospatial Objects for more information on WKTs.
EDGE_NODE1_NAME string A string value representing the first of the edge's nodes' name.
EDGE_NODE2_NAME string A string value representing the second of the edge's nodes' name.
EDGE_DIRECTION int A number representing what direction the edge can be traveled; 0 being a forward one-way edge (node 1 to node 2), 1 being a two-way edge (node 1 to node 2 or node 2 to node 1), and 2 being a backward one-way edge (node 2 to node 1).

Important

Each edge is associated with one weight. If EDGE_DIRECTION is specified for an edge in a directed graph, the weight will be the same going in each direction. There can be many edges between two nodes in a directed graph, allowing for many different weights along the same edge, which can have useful applications in real-world examples, e.g., different lanes between two junctions may have different speeds of travel.

Weights

Weights represent a method of informing the graph solver of the cost of including a given edge in a solution. Weights can be defined using an integer ID, string node names, or spatial information ("LINESTRING(X Y, X Y)") and a static cost value or a cost multiplier.

Identifier Supported Types Description
WEIGHTS_EDGE_ID int, long A number representing a weight's associated edge identifier.
WEIGHTS_EDGE_WKTLINE wkt A WKT string reprenting a weight's associated edge geospatial line, e.g., "LINESTRING(X1 Y1, X2 Y2)". See Geospatial Objects for more information on WKTs.
WEIGHTS_EDGE_NODE1_ID int, long A number representing the first of a weight's associated edge's nodes.
WEIGHTS_EDGE_NODE2_ID int, long A number representing the second of a weight's associated edge's nodes.
WEIGHTS_EDGE_NODE1_NAME string A string value representing the first of a weight's associated edge's nodes' name.
WEIGHTS_EDGE_NODE2_NAME string A string value representing the second of a weight's associated edge's nodes' name.
WEIGHTS_VALUESPECIFIED float, double, int, long A number representing the weight's value.
WEIGHTS_FACTORSPECIFIED float, double, int, long A number representing how much incoming cost values will be multiplied.

Important

Currently, WEIGHTS_FACTORSPECIFIED will only affect the cost if the edge has a WEIGHTS_VALUESPECIFIED already established. This means that WEIGHTS_FACTORSPECIFIED should only be used in /solve/graph or in conjunction with a WEIGHTS_VALUESPECIFIED during /create/graph

Restrictions

Restrictions represent a method of informing the graph solver which edges and/or nodes should be ignored for the solution. Restrictions can be defined using an integer ID and a value or as a switch (on or off).

Identifier Supported Types Description
RESTRICTIONS_NODE_ID int, long A number representing the restriction's associated node identifier.
RESTRICTIONS_EDGE_ID int, long A number representing the restriction's associated edge identifier.
RESTRICTIONS_NODE_WKTPOINT wkt A WKT string representing the restriction's associated node's geospatial point, e.g., "POINT(X, Y)". See Geospatial Objects for more information on WKTs.
RESTRICTIONS_NODE_NAME string A string value representing the restriction's associated node.
RESTRICTIONS_EDGE_WKTLINE wkt A WKT string reprenting a weight's associated edge geospatial line, e.g., "LINESTRING(X1 Y1, X2 Y2)". See Geospatial Objects for more information on WKTs.
RESTRICTIONS_VALUECOMPARED float, double, int, long A number representing the value incoming costs will be compared against.
RESTRICTIONS_ONOFFCOMPARED int A number representing if the associated node or edge cannot be traversed, with 1 meaning it can be traversed and 0 meaning it cannot.

Note

When using RESTRICTIONS_VALUECOMPARED, solvers will not use the given node or edge if the current cost is less than the restriction value. When using RESTRICTIONS_ONOFFCOMPARED, solvers will not use the given node or edge if the RESTRICTIONS_ONOFFCOMPARED value is set to 0 (off).

Identifier Combinations

For each component, there's a minimum amount of identifiers that must be used to properly create a graph. Each component's identifier combinations must reference columns from the same table, e.g., the combination NODE_ID and NODE_NAME must both use the same table. Identifier types across components should match where possible.

Important

WKT identifiers can be matched to X/Y identifiers (and vice versa) within a user-specified tolerance (merge_tolerance under the /create/graph endpoint's options map). Using ID or NAME identifiers relies on exact matching. The WKTLINE identifiers will use the line's start and end points to map to an XY pair or WKTPOINT.

For example, if the identifier combination used for nodes is:


The edges identifier combination should include some match for the NODE_ID, the NODE_WKTPOINT, or both. Any one of the following example edge combinations would match correctly with the node combination; note that matching node point(s) to edge point(s) requires two edge points to make an implicit edge between the points:

# EDGE_NODE2_X, and EDGE_NODE2_Y
edges=[
    "edges_table.eid AS EDGE_ID", "edges_table.x AS EDGE_NODE1_X",
    "edges_table.y AS EDGE_NODE1_Y", "edges_table.z AS EDGE_NODE2_X",
    "edges_table.q AS EDGE_NODE2_Y"
]

# Example 2 - Matching NODE_ID with EDGE_NODE1_ID and EDGE_NODE2_ID
edges=[
    "edges_table.eid AS EDGE_ID",
    "edges_table.nid1 AS EDGE_NODE1_ID",
    "edges_table.nid2 AS EDGE_NODE2_ID"
]

# Example 3 - Matching NODE_WKTPOINT with EDGE_NODE1_WKTPOINT and
# EDGE_NODE2_WKTPOINT
edges=[
    "edges_table.pnt1 AS EDGE_NODE1_WKTPOINT",
    "edge_table.pnt2 as EDGE_NODE2_WKTPOINT"
]

Note

The above examples are not the only edge combinations available for the NODE_ID / NODE_WKTPOINT identifier combination.

Nodes

  • NODE_ID
  • NODE_ID, NODE_NAME
  • NODE_ID, NODE_WKTPOINT
  • NODE_ID, NODE_X, NODE_Y
  • NODE_NAME, NODE_WKTPOINT
  • NODE_NAME, NODE_X, NODE_Y
  • NODE_WKTPOINT
  • NODE_X, NODE_Y

Edges

  • EDGE_ID, EDGE_NODE1_ID, EDGE_NODE2_ID
  • EDGE_ID, EDGE_NODE1_ID, EDGE_NODE2_ID, EDGE_DIRECTION
  • EDGE_ID, EDGE_NODE1_NAME, EDGE_NODE2_NAME
  • EDGE_ID, EDGE_WKTLINE
  • EDGE_ID, EDGE_NODE1_WKTPOINT, EDGE_NODE2_WKTPOINT
  • EDGE_ID, EDGE_NODE1_X, EDGE_NODE1_Y, EDGE_NODE2_X, EDGE_NODE2_Y
  • EDGE_NODE1_ID, EDGE_NODE2_ID
  • EDGE_NODE1_NAME, EDGE_NODE2_NAME
  • EDGE_NODE1_WKTPOINT, EDGE_NODE2_WKTPOINT
  • EDGE_NODE1_X, EDGE_NODE1_Y, EDGE_NODE2_X, EDGE_NODE2_Y
  • EDGE_WKTLINE
  • EDGE_WKTLINE, EDGE_DIRECTION

Weights

  • WEIGHTS_EDGE_ID, WEIGHTS_VALUESPECIFIED
  • WEIGHTS_EDGE_ID, WEIGHTS_FACTORSPECIFIED
  • WEIGHTS_EDGE_WKTLINE, WEIGHTS_VALUESPECIFIED
  • WEIGHTS_EDGE_WKTLINE, WEIGHTS_FACTORSPECIFIED
  • WEIGHTS_EDGE_NODE1_NAME, WEIGHTS_EDGE_NODE2_NAME, WEIGHTS_VALUESPECIFIED
  • WEIGHTS_EDGE_NODE1_NAME, WEIGHTS_EDGE_NODE2_NAME, WEIGHTS_FACTORSPECIFIED
  • WEIGHTS_EDGE_NODE1_ID, WEIGHTS_EDGE_NODE2_ID, WEIGHTS_VALUESPECIFIED
  • WEIGHTS_EDGE_NODE1_ID, WEIGHTS_EDGE_NODE2_ID, WEIGHTS_FACTORSPECIFIED

Restrictions

  • RESTRICTIONS_EDGE_ID, RESTRICTIONS_ONOFFCOMPARED
  • RESTRICTIONS_EDGE_ID, RESTRICTIONS_VALUECOMPARED
  • RESTRICTIONS_EDGE_WKTLINE, RESTRICTIONS_VALUECOMPARED
  • RESTRICTIONS_EDGE_WKTLINE, RESTRICTIONS_ONOFFCOMPARED
  • RESTRICTIONS_NODE_ID, RESTRICTIONS_ONOFFCOMPARED
  • RESTRICTIONS_NODE_ID, RESTRICTIONS_VALUECOMPARED
  • RESTRICTIONS_NODE_NAME, RESTRICTIONS_VALUECOMPARED
  • RESTRICTIONS_NODE_NAME, RESTRICTIONS_ONOFFCOMPARED
  • RESTRICTIONS_NODE_WKTPOINT, RESTRICTIONS_VALUECOMPARED
  • RESTRICTIONS_NODE_WKTPOINT, RESTRICTIONS_ONOFFCOMPARED

Creating a Graph

Creating a graph is serviced by the /create/graph endpoint; this involves reading from tables with annotated component identifiers and drawing relationships between given nodes and/or edges on a graph, taking into account nodes or edges between nodes that should be favored or ignored. Components can be identified in two ways:

  • Aliasing existing table columns, e.g., table_name.column_name AS NODE_WKTPOINT
  • Using expressions, e.g., ST_LENGTH(wkt) AS WEIGHTS_VALUESPECIFIED

Note

Though it's recommended edges and weights are kept in the same table, it's not required.

Once the components are setup, the graph can be created. Requirements for creating a graph include:

  • name for the graph
  • if the graph is directed or not
  • edges
  • weights

Important

Nodes and restrictions are not required to create a graph. If nodes are included, however, they should be kept separate from edges and weights. If restrictions are included, they can exist in either the nodes table and/or edges/weights table(s) or in an entirely separate table.

Solving a Graph

Solving a graph is serviced by the /solve/graph endpoint; this involves using a given source node, destination node(s), and any weights or restrictions from an existing graph to calculate a given solution type. Off-graph spatial locations are accepted in all solvers, with the results being corrected to snap locations. The calculated solution is then placed in a table in Kinetica; note that many concurrent solves over the same graph are possible. The source node determines from which node the graph solution routing is started (except in the case of a BACKHAUL_ROUTING solution in which the source node determines the number of fixed asset nodes--see /solve/graph for more information); the destination node(s) determines at which node the graph solution will complete routes. Source/destination node(s) can be an ID, name, or WKT point.

Requirements for solving a graph include:

  • name of the graph to solve
  • solution type

Important

Additional weights and restrictions beyond those defined in the graph creation stage can also be provided. Any provided weights will be added (in the case of WEIGHTS_VALUESPECIFIED) to or multiplied with (in the case of WEIGHTS_FACTORSPECIFIED) the existing weight(s). These components can be identified in two ways:

  • Aliasing existing table columns, e.g., table_name.column_name AS RESTRICTIONS_NODE_WKTPOINT
  • Using expressions, e.g., ST_LENGTH(wkt) AS WEIGHTS_VALUESPECIFIED

There are several solution types to choose from:

Solver Description CPU Parallel GPU Parallel
SHORTEST_PATH Determines the shortest path upstream using single-source routing. X X
PAGE_RANK Calculates how connected the nodes are and determines which nodes are the most important. X X
CENTRALITY Calculates the betweenness of the nodes   X
MULTIPLE_ROUTING Calculates the shortest possible route between the nodes and returns to the origin node -- also known as the travelling salesman X X
INVERSE_SHORTEST_PATH Determines the shortest path downstream using multiple technician routing X X
BACKHAUL_ROUTING Determines the optimal routes between remote asset nodes and fixed asset nodes X X

Querying a Graph

Querying a graph is serviced by the /query/graph endpoint; this involves querying a graph for adjacent nodes (if provided edges) or adjacent edges (if provided nodes) using provided IDs, names, or WKT information. Additional adjacent rings around the specified nodes/edges can also be queried. Results can be exported to a table in Kinetica.

Requirements for querying a graph include:

  • name of the graph to query
  • a list of edge or node IDs, names, or WKTs

Listing a Graph

Listing a graph is serviced by the /list/graph endpoint; this involves providing a graph name (or none) to view information about the provided graph (or all graphs) on the graph server.

Deleting a Graph

Deleting a graph is serviced by the /delete/graph endpoint; this involves providing a graph name to delete the graph from the graph server (memory) and persist (if applicable).

Tip

If a graph was saved to persist upon creation and then was deleted from the server (but NOT persist), it can be reloaded from persist by recreating the graph using the same graph_name.

Examples

The following network graph solver type examples are detailed below:

Prerequisites

  1. These examples utilize the Kinetica Python API. To learn more about installing and using the Python API, review the Python Developer Manual.
  2. The example script makes reference to two CSV files in the current directory. This path 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.

Graph Creation

Three graphs are used for the solvers utilized in the example script:

  • GRAPH_T1 -- a graph utilizing WKT based on a modified version of the standard nyctaxi dataset included with Kinetica installations
  • GRAPH_T2 -- a graph utilizing IDs based on a modified version of the standard nyctaxi dataset included with Kinetica installations
  • GRAPH_S -- a graph based on the road_weights dataset (one of the CSV file mentioned in Prerequisites)

To filter out data that could skew graphs GRAPH_T1 and GRAPH_T2, the nyc_neighborhood dataset must be inserted into Kinetica and joined to the nyctaxi dataset using STXY_CONTAINS:

print(
    "Joining {} to {} to filter out data that could skew the taxi "
    "graphs.".format(TABLE_TAXI, JOIN_TAXI)
)
join_taxi_tables_response = kinetica.create_join_table(
    join_table_name=JOIN_TAXI,
    table_names=[TABLE_TAXI + " as t", TABLE_NYC_N + " as n"],
    column_names=[
        "CONCAT(CHAR32(pickup_longitude), CHAR32(pickup_latitude)) as "
        "pickup_name",
        "t.pickup_longitude", "t.pickup_latitude",
        "HASH(t.pickup_longitude + t.pickup_latitude) as pickup_id",
        "CONCAT(CHAR32(dropoff_longitude), CHAR32(dropoff_latitude)) as "
        "dropoff_name",
        "t.dropoff_longitude", "t.dropoff_latitude",
        "HASH(t.dropoff_longitude + t.dropoff_latitude) as dropoff_id",
        "t.total_amount"
    ],
    expressions=[
        "(STXY_CONTAINS(n.geom, t.pickup_longitude, t.pickup_latitude)) "
        "AND (STXY_CONTAINS(n.geom, t.dropoff_longitude, "
        "t.dropoff_latitude)) "
    ]
)["status_info"]["status"]

Before GRAPH_T1 can be created, the edges must be derived from the JOIN_TAXI dataset's XY pickup and dropoff pairs:

print(
    "Creating a projection from {} to contain the {} edges.".format(
        JOIN_TAXI, GRAPH_T1
    )
)
edges_wkt_response = kinetica.create_projection(
    table_name=JOIN_TAXI,
    projection_name=TABLE_TAXI_EW1,
    column_names=[
        "remove_nullable(ST_MAKELINE("
        "ST_MAKEPOINT(pickup_longitude, pickup_latitude), "
        "ST_MAKEPOINT(dropoff_longitude, dropoff_latitude))) AS tripwkt",
        "total_amount"
    ],
    options={}
)["status_info"]["status"]

Before GRAPH_T2 can be created, the nodes and edges must also be derived from the JOIN_TAXI dataset:

# Union the JOIN_TAXI view to itself to collapse pickup & dropoff
# locations into a unified set of endpoint locations to serve as node IDs
print(
    "Unioning {} to itself contain the graph's nodes.".format(
        JOIN_TAXI
    )
)
sql = "CREATE TABLE " + TABLE_TAXI_N + " AS (SELECT pickup_id as id," \
                                       " pickup_longitude as lon," \
                                       " pickup_latitude as lat FROM " + \
      JOIN_TAXI + " UNION SELECT dropoff_id, dropoff_longitude, " \
                  "dropoff_latitude FROM " + \
      JOIN_TAXI + ")"
nodes_response = kinetica.execute_sql(
    statement=sql,
    offset=0,
    limit=gpudb.GPUdb.END_OF_SET,
    encoding="json",
    options={}
)["status_info"]["status"]

# Create a projection to contain the graph edges (based on NODE_ID)
print(
    "Creating a projection from {} to contain the graph's edges.".format(
        JOIN_TAXI
    )
)
edges_id_response = kinetica.create_projection(
    table_name=JOIN_TAXI,
    projection_name=TABLE_TAXI_EW2,
    column_names=[
        "pickup_id", "dropoff_id"
    ]
)["status_info"]["status"]

Then the graphs are created. The GRAPH_T1 graph is created with the following characteristics:

  • It is not directed (node 0 to node 1, node 1 to node 2, etc.)
  • It has no explicitly defined nodes
  • Its edges are defined using the tripwkt column as the EDGE_WKTLINE identifier
  • Its weights are defined using the tripwkt column as the WEIGHTS_EDGE_WKTLINE identifier and the total_amount as the WEIGHTS_VALUESPECIFIED identifier
  • It has no restrictions
  • It will be recreated if a graph of the same name exists
  • It has a merge tolerance of 0.01
print("Creating {}.".format(GRAPH_T1))
create_t1_graph_response = kinetica.create_graph(
    graph_name=GRAPH_T1,
    directed_graph=False,
    nodes=[],
    edges=[
        TABLE_TAXI_EW1 + ".tripwkt AS EDGE_WKTLINE"
    ],
    weights=[
        TABLE_TAXI_EW1 + ".tripwkt AS WEIGHTS_EDGE_WKTLINE",
        TABLE_TAXI_EW1 + ".total_amount AS WEIGHTS_VALUESPECIFIED"
    ],
    restrictions=[],
    options={
        "recreate": "true",
        "merge_tolerance": "0.01"
    }
)

The GRAPH_T2 graph is created with the following characteristics:

  • It is directed (node 0 to node 1, node 1 to node 2, etc.)
  • Its nodes are defined using the id column as the NODE_ID identifier
  • Its edges are defined using the pickup_id and dropoff_id columns as the EDGE_NODE1_ID and EDGE_NODE2_ID identifiers respectively
  • It has no weights or restrictions
  • It will be recreated if a graph of the same name exists
print("Creating {}.".format(GRAPH_T2))
create_t2_graph_response = kinetica.create_graph(
    graph_name=GRAPH_T2,
    directed_graph=True,
    nodes=[
        TABLE_TAXI_N + ".id AS NODE_ID"
    ],
    edges=[
        TABLE_TAXI_EW2 + ".pickup_id AS EDGE_NODE1_ID",
        TABLE_TAXI_EW2 + ".dropoff_id AS EDGE_NODE2_ID"
    ],
    weights=[],
    restrictions=[],
    options={
        "recreate": "true"
    }
)

The GRAPH_S graph is created with the following characteristics:

  • It is directed
  • It has no explicitly defined nodes
  • Its edges are defined using the WKTLINE and TwoWay columns as the EDGE_WKTLINE and EDGE_DIRECTION identifiers respectively
  • Its weights are defined using the WKTLINE column as the WEIGHTS_EDGE_WKTLINE identifier and the time column as the WEIGHTS_VALUESPECIFIED identifier
  • It has no restrictions
  • It will be recreated if a graph of the same name exists
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 + ".time AS WEIGHTS_VALUESPECIFIED"
    ],
    restrictions=[],
    options={
        "recreate": "true"
    }
)

Backhaul Routing

First, the source node ID, fixed assets, and remote assets are set. As noted on /solve/graph, when the solver type is set to BACKHAUL_ROUTING, the source_node_id parameter represents how many nodes in the destination_node_ids list are fixed assets.

source_node_id = 24
fixed_assets = [
    "POINT(-122.37694377950754 47.69058183874783)",
    "POINT(-122.37591381124582 47.6947415132984)",
    "POINT(-122.3635541921052 47.70005617015495)",
    "POINT(-122.35565776876535 47.70583235665686)",
    "POINT(-122.35531444601145 47.72477375603093)",
    "POINT(-122.33540172628489 47.72361898977214)",
    "POINT(-122.32407207540598 47.72408089934756)",
    "POINT(-122.32647533468332 47.73562730759159)",
    "POINT(-122.32922191671457 47.74209217807247)",
    "POINT(-122.31205577901926 47.741399551774876)",
    "POINT(-122.31274242452707 47.737705389219734)",
    "POINT(-122.29935283712473 47.73701270455902)",
    "POINT(-122.2976362233552 47.73262548770682)",
    "POINT(-122.2921430592927 47.73354914302527)",
    "POINT(-122.29179973653879 47.72200227400312)",
    "POINT(-122.30003948263254 47.712531931184785)",
    "POINT(-122.30278606466379 47.701442513285734)",
    "POINT(-122.30518932394114 47.694048257248284)",
    "POINT(-122.30244274190989 47.68827076507089)",
    "POINT(-122.31514568380442 47.68480396253861)",
    "POINT(-122.32750530294504 47.68711518982914)",
    "POINT(-122.3474180226716 47.687577422998146)",
    "POINT(-122.37763042501535 47.686421832395006)",
    "POINT(-122.37694377950754 47.69058183874783)"
]
remote_assets = [
    "POINT(-122.324612 47.725231)", "POINT(-122.362112 47.696131)",
    "POINT(-122.356212 47.74173099999999)", "POINT(-122.341512 47.702631)",
    "POINT(-122.327412 47.737131)", "POINT(-122.344912 47.727531)",
    "POINT(-122.291612 47.65763099999999)", "POINT(-122.324512 47.703831)",
    "POINT(-122.297712 47.731231)", "POINT(-122.317912 47.699431)",
    "POINT(-122.351412 47.713731)", "POINT(-122.295612 47.670531)",
    "POINT(-122.321812 47.672731)", "POINT(-122.295612 47.697531)",
    "POINT(-122.333012 47.689831)", "POINT(-122.298812 47.711731)",
    "POINT(-122.309612 47.684931)", "POINT(-122.359712 47.716431)",
    "POINT(-122.360612 47.659231)", "POINT(-122.299012 47.707431)",
    "POINT(-122.311612 47.66683099999999)", "POINT(-122.315912 47.724631)",
    "POINT(-122.316912 47.709531)", "POINT(-122.313212 47.685731)",
    "POINT(-122.321712 47.721231)", "POINT(-122.339512 47.695031)",
    "POINT(-122.310512 47.692531)", "POINT(-122.326512 47.679731)",
    "POINT(-122.358112 47.705731)", "POINT(-122.352812 47.715931)",
    "POINT(-122.291612 47.67753099999999)", "POINT(-122.295712 47.666731)",
    "POINT(-122.303712 47.681531)", "POINT(-122.362312 47.732231)",
    "POINT(-122.347712 47.740431)", "POINT(-122.343512 47.68523099999999)",
    "POINT(-122.326412 47.730631)", "POINT(-122.357812 47.67003099999999)",
    "POINT(-122.321012 47.694531)", "POINT(-122.353312 47.737131)",
    "POINT(-122.323412 47.67903099999999)", "POINT(-122.351012 47.701731)",
    "POINT(-122.349112 47.735931)", "POINT(-122.361612 47.675031)",
    "POINT(-122.320912 47.70193099999999)", "POINT(-122.345412 47.693331)",
    "POINT(-122.357112 47.669631)", "POINT(-122.352912 47.685131)",
    "POINT(-122.361712 47.681331)", "POINT(-122.346312 47.722231)"
]
destination_nodes = fixed_assets + remote_assets

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

solve_s_bgraph_response = kinetica.solve_graph(
    graph_name=GRAPH_S,
    solver_type="BACKHAUL_ROUTING",
    node_type="NODE_WKTPOINT",
    source_node_id=source_node_id,
    destination_node_ids=[],
    source_node="",
    destination_nodes=destination_nodes,
    solution_table=GRAPH_S_BSOLVED,
    options={"export_solve_results": "true"}
)["result_per_destination_node"]

The cost for each remote to travel to the nearest fixed asset is output:

Cost for each remote asset to travel to nearest fixed asset:
Remote Asset                           Cost (in minutes)
=====================================  =================
POINT(-122.324612 47.725231)           0.865516
POINT(-122.362112 47.696131)           0.758842
POINT(-122.356212 47.74173099999999)   1.084458
POINT(-122.341512 47.702631)           1.246927
POINT(-122.327412 47.737131)           0.218491
POINT(-122.344912 47.727531)           0.730477
POINT(-122.291612 47.65763099999999)   2.578740
POINT(-122.324512 47.703831)           0.985759
POINT(-122.297712 47.731231)           0.761547
POINT(-122.317912 47.699431)           1.088295
POINT(-122.351412 47.713731)           0.781952
POINT(-122.295612 47.670531)           1.331788
POINT(-122.321812 47.672731)           1.958484
POINT(-122.295612 47.697531)           1.966542
POINT(-122.333012 47.689831)           1.346219
POINT(-122.298812 47.711731)           0.349077
POINT(-122.309612 47.684931)           0.431795
POINT(-122.359712 47.716431)           0.822105
POINT(-122.360612 47.659231)           2.150527
POINT(-122.299012 47.707431)           0.845038
POINT(-122.311612 47.66683099999999)   2.373925
POINT(-122.315912 47.724631)           2.599283
POINT(-122.316912 47.709531)           1.695174
POINT(-122.313212 47.685731)           0.251388
POINT(-122.321712 47.721231)           0.786522
POINT(-122.339512 47.695031)           1.121402
POINT(-122.310512 47.692531)           0.724923
POINT(-122.326512 47.679731)           0.452152
POINT(-122.358112 47.705731)           0.461203
POINT(-122.352812 47.715931)           1.164492
POINT(-122.291612 47.67753099999999)   2.552220
POINT(-122.295712 47.666731)           2.504816
POINT(-122.303712 47.681531)           1.311244
POINT(-122.362312 47.732231)           1.250877
POINT(-122.347712 47.740431)           0.616612
POINT(-122.343512 47.68523099999999)   1.167451
POINT(-122.326412 47.730631)           1.249203
POINT(-122.357812 47.67003099999999)   1.425482
POINT(-122.321012 47.694531)           1.741059
POINT(-122.353312 47.737131)           1.464322
POINT(-122.323412 47.67903099999999)   1.690359
POINT(-122.351012 47.701731)           0.978331
POINT(-122.349112 47.735931)           0.652920
POINT(-122.361612 47.675031)           1.161741
POINT(-122.320912 47.70193099999999)   0.810048
POINT(-122.345412 47.693331)           1.174176
POINT(-122.357112 47.669631)           0.283823
POINT(-122.352912 47.685131)           1.114293
POINT(-122.361712 47.681331)           1.756808
POINT(-122.346312 47.722231)           1.190125

The solution output to WMS:

../_images/seattle_bh_solved.png

Tip

To demonstrate how the remote assets are routed back to the fixed assets, the fixed assets can be arbitrarily linked together in a LINESTRING and mapped together with the solution. The picture below represents this; the fixed assets LINESTRING is dark blue while remote assets are linked to the fixed assets using any other color.

../_images/seattle_bh_solved_w_fixed.png

Multiple Routing

Taxi Example

The first multiple routing example uses the GRAPH_T1 graph. Before the graph is solved, the source node ID and destination node IDs are defined.

source_node_id = 2
destination_node_ids = [5, 7, 3]

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

solve_t1_mrgraph_response = kinetica.solve_graph(
    graph_name=GRAPH_T1,
    solver_type="MULTIPLE_ROUTING",
    node_type="NODE_ID",
    source_node_id=source_node_id,
    destination_node_ids=destination_node_ids,
    source_node="",
    destination_nodes=[],
    solution_table=GRAPH_T1_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 total amount in dollars:

Cost for source node ID 2 to visit destination node IDs [5, 7, 3]: $417.88

The solution output to WMS:

../_images/nyctaxi_mr_solved.png

Seattle Example

The second multiple routing example uses the GRAPH_S graph. Before the graph is solved, the source node and destination nodes are defined.

print("Solving {} using MULTIPLE_ROUTING solver type.".format(GRAPH_S))
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

Page Rank

The graph is solved with the node type being set to ID:

solve_pr_graph_response = kinetica.solve_graph(
    graph_name=GRAPH_T2,
    solver_type="PAGE_RANK",
    node_type="NODE_ID",
    source_node_id=0,
    source_node="",
    destination_node_ids=[],
    destination_nodes=[],
    solution_table=GRAPH_T2_PRSOLVED,
    options={}
)["status_info"]["status"]

Next the nodes union created earlier is sharded so it can be joined:

nodes_sharded_response = kinetica.create_projection(
    table_name=TABLE_TAXI_N,
    projection_name=TABLE_TAXI_N_S,
    column_names=[
        "id", "lon", "lat"
    ],
    options={"shard_key": "id"}
)["status_info"]["status"]

Then the Page Rank graph results are also sharded so it can be joined to the nodes union:

graph_sharded_response = kinetica.create_projection(
    table_name=GRAPH_T2_PRSOLVED,
    projection_name=GRAPH_T2_PRSOLVED_S,
    column_names=[
        "SOLVERS_NODE_ID", "SOLVERS_NODE_COSTS"
    ],
    options={"shard_key": "SOLVERS_NODE_ID"}
)["status_info"]["status"]

The union and graph results table are joined on ID:

# Join the TABLE_TAXI_N_S and GRAPH_T2_PRSOLVED_S tables to pair the page
# rank results IDs and costs with the longitude/latitude pair of the node
join_pr_response = kinetica.create_join_table(
    join_table_name=JOIN_PR_RESULTS,
    table_names=[
        TABLE_TAXI_N_S + " as n",
        GRAPH_T2_PRSOLVED_S + " as s"
    ],
    column_names=[
        "n.lon", "n.lat", "s.SOLVERS_NODE_ID", "s.SOLVERS_NODE_COSTS"
    ],
    expressions=["n.id = s.SOLVERS_NODE_ID"],
    options={}
)["status_info"]["status"]

The top 10 nodes (sorted by descending cost) is retrieved:

Top 10 nodes sorted by cost (highest to lowest):
Longitude Latitude                   ID            Cost
========= ======== ==================== ===============
-73.77626 40.64528   604253160911565069    8.330557e-05
-73.77636 40.64537   604253160911565069    8.330557e-05
-73.77635 40.64537   177847872587046296    8.330557e-05
-73.77625 40.64528   177847872587046296    8.330557e-05
-73.78194 40.64474  8317696840145447245    6.294312e-05
-73.93784 40.75837   556296061431802422    6.082348e-05
-73.93759 40.75812   556296061431802422    6.082348e-05
-73.96732  40.7611 -8958362439748163101    5.946924e-05
-73.96189 40.75567 -8958362439748163101    5.946924e-05
-73.78255 40.64443 -7632965045835930460    5.934975e-05

Shortest Path

First, 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_spgraph_response = kinetica.solve_graph(
    graph_name=GRAPH_S,
    solver_type="SHORTEST_PATH",
    node_type="NODE_WKTPOINT",
    source_node_id=0,
    destination_node_ids=[0],
    source_node=source_node,
    destination_nodes=destination_nodes,
    solution_table=GRAPH_S_SPSOLVED,
    options={"export_solve_results": "true"}
)["result_per_destination_node"]

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

Cost per destination node when source node = POINT(-122.1792501 47.2113606):
Destination Node              Cost (in minutes)
============================  =================
POINT(-122.2221 47.5707)      40.621415
POINT(-122.541017 47.809121)  90.293384
POINT(-122.520440 47.624725)  79.734196
POINT(-122.467915 47.427280)  69.035693

The solution output to WMS:

../_images/seattle_sp_solved.png

Download & Run

Included below is the complete script containing all the above examples, the CSV files, and output.

Important

The graph_solvers.py file assumes Kinetica is available locally (127.0.0.1:9191) These can be changed via the HOST and PORT constants in the file.

To run the complete sample, ensure the graph_solvers.py, nyc_neighborhood.csv, and road_weights.csv are in the same directory, then switch to that directory and run:

python graph_solvers.py

Limitations and Cautions

  • Groups of valid identifier combinations must be from the same table, e.g., NODE_ID and NODE_NAME must reference columns from the same table
  • Node, edge, weight, and optional restriction identifiers should be matched to yield a useful graph (NODE_ID --> EDGE_NODE1_ID and EDGE_NODE2_ID / EDGE_ID --> WEIGHTS_EDGE_ID, etc.)
  • Groups of valid numerical identifier combinations must be the same type, e.g., if EDGE_ID is identified from an int column, both EDGE_NODE1_ID and EDGE_NODE2_ID must also be int
  • Graphs cannot be created using columns with the nullable property
  • If no ID identifier is provided, weights will be matched with edges by table row, e.g., the first record in the weight table will be used for the first record in the edge table (should the weights and edges be separate). If two weights are specified for the same edge, the weights are added (if both are using the WEIGHTS_VALUESPECIFIED identifier) or multiplied (if one or both are using the WEIGHTS_FACTORSPECIFIED identifier) together.