Network Graphs & Solvers Concepts

Solvers

Graph Problems

Solving Common Problems

Graph Problems

×

Components and Identifiers

Graph Components

Modeling Graphs

Graph Components

×

Components for create, solve, query, and match operations can be identified in three ways:

• Aliasing existing table columns, e.g., table_name.column_name AS WKTPOINT
• Using expressions, e.g., ST_LENGTH(wkt) AS VALUESPECIFIED
• Using constant values, where strings & WKTs are single-quoted, non-decimal numbers will be given an int or long type according to their size (or can be coerced to long by using an L suffix, like 1L), and decimal numbers will be given the double type; e.g.:
  • {0} AS ONOFFCOMPARED
  • {1L, 2, 3L, 4, 5} AS ID
  • {1.1, 12.345689, 123.456789456789} AS NODE1_X
  • {'name1', 'name2'} AS NAME
  • {'POINT(10 15)'} AS WKTPOINT

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

create_s_graph_response = kinetica.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"
    }
)

Weights

Graph Weights

Modeling Weighted Graphs

Graph 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(X1 Y1 [Z1], X1 Y1 [Z1])) and a static cost value or a cost multiplier. Each edge is associated with one weight, but there can be many edges between two nodes in a graph with directionality (EDGE_DIRECTION), 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.

For graphs that define edges using complex WKT linestrings (e.g., linestrings with more than two points), weights are applied consistently to each segment of the linestring. For example, if LINESTRING(0 0, 1 3, 4 5) is provided as an edge source and a weight of 5 is assigned to that source, the resulting graph would have two edges, LINESTRING(0 0, 1 3) and LINESTRING(1 3, 4 5), that would both have a weight of 5. See Fitting Road Network Data to a Graph for more information.

Note

If DIRECTION is specified for an edge in a directed graph, the weight will be the same going in each direction.

Identifier	Supported Types	Description
EDGE_DIRECTION	int	A number representing what direction the edge can be traveled: 0: forward one-way edge (node 1 ‣ node 2) 1: two-way edge (node 1 ‣ node 2 and node 2 ‣ node 1) 2: backward one-way edge (node 2 ‣ node 1)
EDGE_ID	int, long	A number representing a weight's associated edge identifier
EDGE_NODE1_ID	int, long	A number representing a weight's associated edge's first node
EDGE_NODE1_NAME	string	A string value representing a weight's associated edge's first node's name
EDGE_NODE2_ID	int, long	A number representing a weight's associated edge's second node
EDGE_NODE2_NAME	string	A string value representing a weight's associated edge's second node's name
EDGE_PARTITION	long	A number representing a weight's associated edge's partition ID
EDGE_WKTLINE	wkt	A WKT string representing a weight's associated edge geospatial line; e.g., LINESTRING(X1 Y1 [Z1], X2 Y2 [Z2]) See Geospatial Objects for more information on WKTs.
FACTORSPECIFIED	float, double, int, long	A number representing how much incoming cost values will be multiplied
FROM_EDGE_ID	int, long	A number representing a weight's associated edge identifier that signifies the start of a turn; paired with TO_EDGE_ID to define additionally-weighted traversal from one edge to another through any single node Note Only applicable if the add_turns option was set to true during /create/graph. This identifier can be used to locally override any *_turn_penalty and/or intersection_penalty options previously set. See Using Turn-based Weights & Restrictions for more information.
TO_EDGE_ID	int, long	A number representing a weight's associated edge identifier that signifies the end of a turn; paired with FROM_EDGE_ID to define additionally-weighted traversal from one edge to another through any single node Note Only applicable if the add_turns option was set to true during /create/graph. This identifier can be used to locally override any *_turn_penalty and/or intersection_penalty options previously set. See Using Turn-based Weights & Restrictions for more information.
WKTPOINT	wkt	A WKT string representing a weight's associated WKT point Note Used exclusively in conjunction with FACTORSPECIFIED to create a combination for graphing weights by the inverse distance weighted averaging of WKT points composing a graph.
VALUESPECIFIED	float, double, int, long	A number representing the weight's value

Important

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

Identifier Combinations

For each component, there's a minimum set 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 node combination of ID and NAME must both use the same table. The columns must also not be nullable. Identifier types across components should match where possible.

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

1
2
3

nodes = [
    TABLE_TAXI_N + ".id AS ID"
],

The edges identifier combination should include a match for the node ID. The following edge combination would match correctly with the node combination; note that matching node point(s) to edge endpoint(s) requires two edge endpoints to make an implicit edge between the points:

1
2
3
4

edges = [
    TABLE_TAXI_E + ".pickup_id AS NODE1_ID",
    TABLE_TAXI_E + ".dropoff_id AS NODE2_ID"
],

If using multiple groups of combinations while creating, solving, querying, or matching a graph, the combinations must be separated by empty quotes ("") in the respective array, e.g.:

1
2
3
4
5

queries = [
    "{'Jane'} AS NODE_NAME",
    "",
    "{'chess'} AS TARGET_NODE_LABEL"
],

If specifying identifier combinations as raw values, the number of values within each identifier must match across the combination group, e.g.:

"{'Bill', 'Alex'} AS NODE_NAME",
"{0, 0} AS ONOFFCOMPARED"

Using Labels

Labels are a type of identifier that provide additional context to a node or edge and can act as a target for a query. Labels are paired with another identifier in several valid combinations listed above, but each unique label must be part of its own combination; i.e., there cannot be two labels in the same identifier combination. For example, this is a valid multi-label configuration:

1
2
3
4
5
6
7

nodes = [
    TABLE_P + ".name AS NAME",
    TABLE_P + ".interest AS LABEL",
    "",
    TABLE_P + ".name AS NAME",
    TABLE_P + ".gender AS LABEL"
],

But this example is invalid:

1
2
3
4
5

nodes = [
  TABLE_P + ".name AS NAME",
  TABLE_P + ".interest AS LABEL",
  TABLE_P + ".gender AS LABEL"
],

There are several types of labels, some of which can only be referenced in the context of the /query/graph endpoint. See the sections below for more information.

1
2
3
4
5

edges = [
    TABLE_K + ".name1 AS NODE1_NAME",
    TABLE_K + ".name2 AS NODE2_NAME",
    TABLE_K + ".relation AS LABEL"
],

1
2
3
4

restrictions = [
    "{'family'} AS EDGE_LABEL",
    "{0} AS ONOFFCOMPARED"
],

1
2
3

queries = [
    "{'male'} AS NODE_LABEL"
],

1
2
3
4

nodes = [
    TABLE_P + ".name AS NAME",
    TABLE_P + ".interest AS LABEL",
],

1
2
3
4
5

queries = [
    "{'Jane'} AS NODE_NAME",
    "",
    "{'chess'} AS TARGET_NODE_LABEL"
],

1
2
3
4
5
6
7

+------------------------+------------------------+--------------------------+--------------------------+-----------+
|   QUERY_NODE_ID_SOURCE |   QUERY_NODE_ID_TARGET | QUERY_NODE_NAME_SOURCE   | QUERY_NODE_NAME_TARGET   |   RING_ID |
+========================+========================+==========================+==========================+===========+
|                      4 |                      3 | Jane                     | Alex                     |         3 |
+------------------------+------------------------+--------------------------+--------------------------+-----------+
|                      4 |                      5 | Jane                     | Tom                      |         4 |
+------------------------+------------------------+--------------------------+--------------------------+-----------+

Using Turn-based Weights & Restrictions

Turn-based weights and restrictions are used to add a cost to solutions utilizing turn types implemented during graph creation or modification. If the add_turns option is set to true during /create/graph or /modify/graph operations, dummy pillowed edges will be added to each intersection of edges in a graph to mimic realistic turns. These dummy edges will not have any weight by default and will have the coordinates of their origin point. The available turn types are as follows:

• Left turns -- turning left from one edge on to another
• Right turns -- turning right from one edge on to another
• Intersection -- continuing through an intersection of edges (e.g., a stoplight)
• Sharp turns -- turning sharply left or right or a u-turn; a sharp turn or u-turn attribution is determined by the angle of the turn (the turn_angle setting)

For example, say you have a dataset featuring the intersection (designated by the traffic light) below:

Road 1 is a one-way road going north. Road 2 is a one-way road going west. If you were to create a graph from this dataset with add_turns set to false, the edges might look like this:

A solution containing the left turn from road 1 on to road 2 using this graph would incorporate edge 1 ‣ edge 3.

On the other hand, if you were to create a graph from this dataset with add_turns set to true, the edges might look like this instead (note the two additional dummy edges designated by the dotted lines):

The L and the X associated with the dummy edges designate a left turn and intersection respectively, but these attributions could change depending on the turn angle set. A solution containing the left turn from road 1 on to road 2 using this graph instead would incorporate edge 1 ‣ edge 4 ‣ edge 3.

Once turns have been enabled and the turn angle has been set, turn penalties can be incurred via the /solve/graph or the /match/graph endpoints using two methods:

• Setting penalties uniformly per turn type across the graph using the left_turn_penalty, right_turn_penalty, intersection_penalty, or sharp_turn_penalty options

• Setting penalties on a per-edge basis using the following weight identifier combinations:

  FROM_EDGE_ID, TO_EDGE_ID, VALUESPECIFIED

• Setting restrictions on a per-edge basis using the following restriction identifier combinations:

  FROM_EDGE_ID, TO_EDGE_ID, ONOFFCOMPARED

For more information on using turn penalties and restrictions, see the turn penalties and restrictions graph example.

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.

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 (for most solver types)

A graph name must adhere to the standard naming criteria. Each graph exists within a schema and follows the standard name resolution rules for tables.

Directed Graphs

Whether a graph is directed or not can determine how a graph is solved or queried. Using Components and Identifiers and Identifier Combinations for context, edges connect two nodes together ("node 1" and "node 2"). When a graph is directed, these nodes that comprise a given edge have an implicit direction: "node 1" to "node 2". Regardless if these nodes have a spatial context, Kinetica will treat "node 2" as if it must be traveled to directly from "node 1" (whatever their underlying values may be: Jim and George , POINT(0 0) and POINT(9 10), 32 and 45, etc.).

For example, given the below non-directed graph:

Shortest Path Solver

Dijkstra Algorithm

Shortest Path Solver

×

Attempting to solve for the shortest path from node F to node A would result in a SOLVERS_EDGE_PATH of F, E, D, C, B, A. Querying for other nodes attached to node E would result in two adjacencies: F and D.

On the other hand, given the below directed graph:

Attempting to solve for the shortest path from node F to node A would be unsuccessful because there are only edges going toward F (and none leading away from F and subsequently toward A). Querying for other nodes attached to node E would result in a single adjacency: F.

Modifying a Graph

Modifying a graph is serviced by the /modify/graph endpoint; this involves using given node(s), edge(s), weight(s), restriction(s), and option(s) to update an existing graph. All parameters and options available to /modify/graph are also available to /create/graph; as such, many of the same principles apply to using /modify/graph.

Requirements for modifying a graph include:

• name for the existing graph
• components/identifiers and options used to modify the graph

Solving a Graph

Page Rank

Solve for Importance

Page Rank

×

Requirements for solving a graph include:

• name of the graph to solve
• solution type

There are several solution types to choose from:

+--------+--------+
| SOURCE | TARGET |
+========+========+
| node_1 | dest_1 |
+--------+--------+
| node_2 | dest_2 |
+--------+--------+
| node_3 | dest_3 |
+--------+--------+

+--------+--------+
| SOURCE | TARGET |
+========+========+
| node_1 | dest_1 |
+--------+--------+
| node_1 | dest_2 |
+--------+--------+
| node_1 | dest_3 |
+--------+--------+
| node_2 | dest_1 |
+--------+--------+
| node_2 | dest_2 |
+--------+--------+
| node_2 | dest_3 |
+--------+--------+

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

source_nodes=[
    "node1", "node1", "node1",
    "node2", "node2", "node2",
    "node3", "node3", "node3"
],
destination_nodes=[
    "dest_1", "dest_2", "dest_3",
    "dest_1", "dest_2", "dest_3",
    "dest_1", "dest_2", "dest_3"
],

+--------+--------+
| SOURCE | TARGET |
+========+========+
| node_1 | dest_1 |
+--------+--------+
| node_1 | dest_2 |
+--------+--------+
| node_1 | dest_3 |
+--------+--------+
| node_2 | dest_1 |
+--------+--------+
| node_2 | dest_2 |
+--------+--------+
| node_2 | dest_3 |
+--------+--------+
| node_3 | dest_1 |
+--------+--------+
| node_3 | dest_2 |
+--------+--------+
| node_3 | dest_3 |
+--------+--------+

Querying a Graph

Querying Graphs

A Simple Example

Querying Graphs

×

Requirements for querying a graph include:

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

Query Identifiers

Querying Graphs

Advanced Example

Querying Graphs

×

Nodes or edges to be queried can be identified using any of the query-specific identifiers below.

Important

Consult Components and Identifiers and Identifier Combinations for general information on identifiers and combinations. Note that the same limitations that apply to /create/graph and /solve/graph identifiers also apply to /query/graph identifiers

Identifier	Supported Types	Description
EDGE_ID	int, long	Defines the edge ID value that will be matched against in the source graph to determine the source for the query
EDGE_LABEL	string	Defines the edge LABEL value that will be matched against in the source graph to determine the source(s) for the query See Using Labels for more information.
EDGE_WKTLINE	wkt	Defines the edge WKTLINE value that will be matched against in the source graph to determine the source for the query
NODE_ID	int, long	Defines the node ID value that will be matched against in the source graph to determine the source for the query
NODE_LABEL	string	Defines the node LABEL value that will be matched against in the source graph to determine the source(s) for the query See Using Labels for more information.
NODE_NAME	string	Defines the node NAME value that will be matched against in the the source graph to determine the source for the query
NODE_WKTPOINT	wkt	Defines the node WKTPOINT value that will be matched against in the source graph to determine the source for the query
NODE1_ID	int, long	Defines the node ID value that will be matched against in the source graph (in conjunction with NODE2_ID) to determine the source for the query
NODE1_NAME	string	Defines the node NAME value that will be matched against in the source graph (in conjunction with NODE2_NAME) to determine the source for the query
NODE1_WKTPOINT	wkt	Defines the node WKTPOINT value that will be matched against in the source graph (in conjunction with NODE2_WKTPOINT) to determine the source for the query
NODE2_ID	int, long	Defines the node ID value that will be matched against in the source graph (in conjunction with NODE1_ID) to determine the source for the query
NODE2_NAME	string	Defines the node NAME value that will be matched against in the source graph (in conjunction with NODE1_NAME) to determine the source for the query
NODE2_WKTPOINT	wkt	Defines the node WKTPOINT value that will be matched against in the source graph (in conjunction with NODE1_WKTPOINT) to determine the source for the query
TARGET_NODE_LABEL	string	Defines the node LABEL value that will be matched against in the source graph to determine the destination for the query as well as the path taken through the graph to arrive at the destination

Using Query Identifiers

Social Graphs

Creating Social Graphs

Social Graphs

×

Pair one value with an appropriate identifier to query for features connected to the given value within the provided number of rings:

Query Identifier Example (Single Key Search)

1 2 3

queries = [ "{'male'} AS NODE_LABEL" ],

Pair multiple values with a single appropriate identifier to query for features connected to each value independently (effectively an OR) within the provided number of rings:

Query Identifier Example (Multiple Key Search, X OR Y)

1 2 3

queries = [ "{'female', 'chess'} AS NODE_LABEL", ],

Important

A rings value of 0 will return features that match the provided query exactly; in this case, the query would return nodes that have a label of female or chess

Providing any combination with the TARGET_NODE_LABEL identifier (separated by an empty string) will effectively produce a source-destination query where the first combination is the source and the TARGET_NODE_LABEL is the destination (assuming the destination is within the provided number of rings):

Query Identifier Example (Single Target Search)

1 2 3 4 5

queries = [ "{'Jane'} AS NODE_NAME", "", "{'chess'} AS TARGET_NODE_LABEL" ],

Important

Implicitly defined nodes, e.g., from graphs defined with just edges and/or weights, cannot be queried.

Matching a Graph

Matching a graph is serviced by the /match/graph endpoint; this involves matching a directed route implied by a given set of latitude/longitude points to an existing underlying road network graph using a given solution type. The solution is then calculated and output to two tables (consult /match/graph for more information):

1. A table containing track information and the mean square error score -- the lower the number, the more accurate a match.
2. A table containing the coordinate information and how it relates to the track information and segment from the underlying graph.

Requirements for matching a graph include:

• name of the graph to match
• sample points
• solution type

Solution types available:

Showing a Graph

Using /show/graph will provide detailed information about a graph, including number of nodes and edges in the graph, whether the graph is directed or persisted, and more.

Workbench also provides a mechanism to view all graphs, and map geospatial graphs.

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).

Managing Permissions for a Graph

Graph permissions can be managed either through SQL or through the native API.

Examples

For detailed usage of the graph capability, see AWS Guides:

• All Graph Guides
• Graph Matching
• Graph Querying
• Graph Solving

Limitations and Cautions

• Groups of valid identifier combinations must be from the same table, e.g., node ID & 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 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 & 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 VALUESPECIFIED identifier) or multiplied (if one or both are using the FACTORSPECIFIED identifier) together.
• A node or edge can have up to 64 unique labels.