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.
Tip
Graphs can be created, queried, solved, and matched via the GAdmin graph interface. See Graphs for details.
Kinetica has several different solvers available for presenting solutions to various types of network graph problems. Note that some solvers are only available to /solve/graph and likewise for /match/graph. Consult Solving a Graph or Matching a Graph for more information on the desired operation.
Solver | Description | CPU Parallel | GPU Parallel |
---|---|---|---|
SHORTEST_PATH |
Determines the shortest path upstream between given source(s) and destination(s). | X | X |
PAGE_RANK |
Calculates how connected the nodes are and determines which nodes are the most important. Weights are not required. | X | |
PROBABILITY_RANK |
Calculates the probability of a node being connected to another node using hidden Markov chains. | 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 |
ALLPATHS |
Determines all reasonable paths between a source and destination pair. | X | X |
Solver | Description |
---|---|
MARKOV_CHAIN |
Matches sample points to the graph using the Hidden Markov Model (HMM)-based method, which conducts a range-tree closest-edge search to find the best combinations of possible road segments for each sample point to create the best route. The route is secured one point at a time, so the prediction is corrected after each point. This solution type is the most accurate but also the most computationally intensive. |
MATCH_OD_PAIRS |
Matches sample points to find the most probable path between origin and destination (OD) pairs with given cost constraints. |
MATCH_SUPPLY_DEMAND |
Matches sample generic supply depots to generic demand points using abstract transportation (referred to as trucks). Each route is determined by a truck's ability (size) to service demand at each demand point. |
MATCH_BATCH_SOLVES |
Matches each provided sample source and destination pair using the shortest path between the points |
Graph components (e.g., nodes, edges, weights, and/or restrictions) must be defined with varying combinations of the identifiers listed in the tables below.
Components for create, solve, query, and match operations can be identified in three ways:
table_name.column_name AS NODE_WKTPOINT
ST_LENGTH(wkt) AS WEIGHTS_VALUESPECIFIED
{0} AS RESTRICTIONS_ONOFFCOMPARED
{'name1', 'name2'} AS NODE_NAME
{'POINT(10 15)'} AS NODE_WKTPOINT
Note
There are separate identifiers and combinations for
/solve/graph, /query/graph, and
/match/graph. See below for /solve/graph
identifiers; see the associated Querying a Graph and Matching a Graph
sections for their respective endpoint identifiers.
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 + ".TwoWay AS WEIGHTS_EDGE_DIRECTION",
TABLE_SRN + ".time AS WEIGHTS_VALUESPECIFIED"
],
restrictions=[],
options={
"recreate": "true"
}
)
Important
Identifiers with string
as a supported type can be any string
column type, e.g., char1
- char256
or unrestricted string
.
Identifiers with wkt
as a supported type can include optional z-level
values for the provided WKT shape but note that graphs only support z-levels
ranging from -4
to +5
.
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 [Z])") 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 [Z])". See Geospatial Objects for more information on WKTs. |
NODE_LABEL |
string |
A string value representing a node's label. |
Edges represent the required fundamental topological units 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 [Z])"), line ("LINESTRING(X1 Y1 [Z1], X2 Y2 [Z2])"), 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 [Z1], X2 Y2 [Z2])". 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 [Z1])". 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 [Z2])". 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). |
EDGE_LABEL |
string |
A string value representing an edge's label. |
EDGE_WEIGHT_VALUESPECIFIED |
int |
A number representing the edge's associated weight value. If this identifier is provided, additional weights do not need to be specified. |
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 Tutorial (DC) for more information.
Note
If EDGE_DIRECTION
is specified for an edge in a directed graph,
the weight will be the same going in each direction.
Identifier | Supported Types | Description |
---|---|---|
WEIGHTS_EDGE_ID |
int , long |
A number representing a weight's associated edge identifier. |
WEIGHTS_EDGE_DIRECTION |
int |
A number representing what direction the weight's associated 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). |
WEIGHTS_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. |
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_FROM_EDGE_ID |
int , long |
A number representing a weight's associated edge identifier that
signifies the start of a turn. Paired with Note Only applicable if the |
WEIGHTS_TO_EDGE_ID |
int , long |
A number representing a weight's associated edge identifier that
signifies the end of a turn. Paired with Note Only applicable if the |
WEIGHTS_WKTPOINT |
wkt |
A WKT string representing a weight's associated WKT POINT. Note Used exclusively in conjunction with
|
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 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 [Z])". 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 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. |
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. |
RESTRICTIONS_EDGE_NODE1_NAME |
string |
A string value representing the first of a restriction's associated edge's nodes. |
RESTRICTIONS_EDGE_NODE2_NAME |
string |
A string value representing the second of a restriction's associated edge's nodes. |
RESTRICTIONS_EDGE_NODE1_ID |
int , long |
A number representing the first of a restriction's associated edge's nodes. |
RESTRICTIONS_EDGE_NODE2_ID |
int , long |
A number representing the second of a restriction's associated edge's nodes. |
RESTRICTIONS_NODE_LABEL |
string |
A string value referring to a node label for restrictive purposes. |
RESTRICTIONS_EDGE_LABEL |
string |
A string value referring to an edge label for restrictive purposes. |
RESTRICTIONS_EDGE_DIRECTION |
int |
A number representing what direction the restriction's associated 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). |
RESTRICTIONS_FROM_EDGE_ID |
int , long |
A number representing the restriction's associated edge identifier that
signifies the start of a turn. Paired with Note Only applicable if the |
RESTRICTIONS_TO_EDGE_ID |
int , long |
A number representing the restriction's associated edge identifier that
signifies the end of a turn. Paired with Note Only applicable if the |
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
).
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 combination NODE_ID
and
NODE_NAME
must both use the same table. The columns must also not be
nullable. 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:
nodes=[
TABLE_TAXI_N + ".id AS NODE_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:
edges=[
TABLE_TAXI_EW + ".pickup_id AS EDGE_NODE1_ID",
TABLE_TAXI_EW + ".dropoff_id AS EDGE_NODE2_ID"
],
Note
The above example is not the only edge combinations available
for the NODE_ID
identifier combination. See the Edges
section below for other combinations.
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.:
"{'Jane'} AS QUERY_NODE_NAME",
"",
"{'chess'} AS QUERY_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 RESTRICTIONS_NODE_NAME",
"{0, 0} AS RESTRICTIONS_ONOFFCOMPARED"
NODE_ID
NODE_ID
, NODE_NAME
NODE_ID
, NODE_WKTPOINT
NODE_ID
, NODE_X
, NODE_Y
NODE_NAME
NODE_NAME
, NODE_LABEL
NODE_NAME
, NODE_WKTPOINT
NODE_NAME
, NODE_X
, NODE_Y
NODE_WKTPOINT
NODE_X
, NODE_Y
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_NODE1_WKTPOINT
, EDGE_NODE2_WKTPOINT
EDGE_ID
, EDGE_NODE1_X
, EDGE_NODE1_Y
, EDGE_NODE2_X
,
EDGE_NODE2_Y
EDGE_ID
, EDGE_WKTLINE
EDGE_ID
, EDGE_WKTLINE
, EDGE_DIRECTION
EDGE_ID
, EDGE_WKTLINE
, EDGE_DIRECTION
,
EDGE_WEIGHT_VALUESPECIFIED
EDGE_NODE1_ID
, EDGE_NODE2_ID
EDGE_NODE1_NAME
, EDGE_NODE2_NAME
EDGE_NODE1_NAME
, EDGE_NODE2_NAME
, EDGE_LABEL
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_EDGE_ID
, WEIGHTS_VALUESPECIFIED
WEIGHTS_EDGE_ID
, WEIGHTS_FACTORSPECIFIED
WEIGHTS_EDGE_WKTLINE
, WEIGHTS_EDGE_DIRECTION
,
WEIGHTS_VALUESPECIFIED
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
WEIGHTS_WKTPOINT
, WEIGHTS_FACTORSPECIFIED
If utilizing turn penalties, the following combination becomes applicable:
WEIGHTS_FROM_EDGE_ID
, WEIGHTS_TO_EDGE_ID
, WEIGHTS_VALUESPECIFIED
RESTRICTIONS_EDGE_ID
, RESTRICTIONS_ONOFFCOMPARED
RESTRICTIONS_EDGE_ID
, RESTRICTIONS_VALUECOMPARED
RESTRICTIONS_EDGE_LABEL
, RESTRICTIONS_ONOFFCOMPARED
RESTRICTIONS_EDGE_NODE1_ID
, RESTRICTIONS_EDGE_NODE2_ID
,
RESTRICTIONS_ONOFFCOMPARED
RESTRICTIONS_EDGE_NODE1_NAME
, RESTRICTIONS_EDGE_NODE2_NAME
,
RESTRICTIONS_ONOFFCOMPARED
RESTRICTIONS_EDGE_WKTLINE
, RESTRICTIONS_EDGE_DIRECTION
,
RESTRICTIONS_ONOFFCOMPARED
RESTRICTIONS_EDGE_WKTLINE
, RESTRICTIONS_EDGE_DIRECTION
,
RESTRICTIONS_VALUECOMPARED
RESTRICTIONS_EDGE_WKTLINE
, RESTRICTIONS_ONOFFCOMPARED
RESTRICTIONS_EDGE_WKTLINE
, RESTRICTIONS_VALUECOMPARED
RESTRICTIONS_NODE_ID
, RESTRICTIONS_ONOFFCOMPARED
RESTRICTIONS_NODE_ID
, RESTRICTIONS_VALUECOMPARED
RESTRICTIONS_NODE_LABEL
, RESTRICTIONS_ONOFFCOMPARED
RESTRICTIONS_NODE_NAME
, RESTRICTIONS_VALUECOMPARED
RESTRICTIONS_NODE_NAME
, RESTRICTIONS_ONOFFCOMPARED
RESTRICTIONS_NODE_WKTPOINT
, RESTRICTIONS_ONOFFCOMPARED
RESTRICTIONS_NODE_WKTPOINT
, RESTRICTIONS_VALUECOMPARED
If utilizing turn restrictions, the following combination becomes applicable:
RESTRICTIONS_FROM_EDGE_ID
, RESTRICTIONS_TO_EDGE_ID
,
RESTRICTIONS_ONOFFCOMPARED
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:
nodes = [
TABLE_P + ".name AS NODE_NAME",
TABLE_P + ".interest AS NODE_LABEL",
"",
TABLE_P + ".name AS NODE_NAME",
TABLE_P + ".gender AS NODE_LABEL"
],
But this example is invalid:
nodes = [
TABLE_P + ".name AS NODE_NAME",
TABLE_P + ".interest AS NODE_LABEL",
TABLE_P + ".gender AS NODE_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.
The NODE_LABEL
and EDGE_LABEL
identifiers are are used to provide additional string-based
information about a node or edge respectively, similarly to the NODE_NAME
(and other related) identifiers.
The RESTRICTIONS_NODE_LABEL
and RESTRICTIONS_EDGE_LABEL
identifiers
are used to restrict the value set defined as NODE_LABEL
and EDGE_LABEL
respectively. These restrictive identifiers must follow an already-defined
NODE_LABEL
or EDGE_LABEL
, i.e. they cannot be used on their own
at graph creation time. They are used in
restriction combinations just like other restriction
identifiers.
For example, if the relation
between two people is used as the
EDGE_LABEL
when creating a graph:
edges = [
TABLE_K + ".name1 AS EDGE_NODE1_NAME",
TABLE_K + ".name2 AS EDGE_NODE2_NAME",
TABLE_K + ".relation AS EDGE_LABEL"
],
Then the family
relation label can be restricted during the subsequent
query using the RESTRICTIONS_EDGE_LABEL
identifier:
restrictions = [
"{'family'} AS RESTRICTIONS_EDGE_LABEL",
"{0} AS RESTRICTIONS_ONOFFCOMPARED"
],
There are several *_LABEL
identifiers that are unique to the
/query/graph endpoint.
The QUERY_NODE_LABEL
and QUERY_EDGE_LABEL
query identifiers are not paired with other
query combinations; they are used to retrieve only
the nodes and/or edges associated with a given label. For example:
queries=[
"{'male'} AS QUERY_NODE_LABEL"
],
The QUERY_TARGET_NODE_LABEL
query identifier is
always paired with another query combination to define a source-destination
relationship and pathing for a query. This identifier also must follow an
already-defined NODE_LABEL
. Note that an adjacency output table will have
two additional columns if the QUERY_TARGET_NODE_LABEL
identifier is used:
PATH_ID
- an ID that helps identify the different paths taken to arrive
at the query target if there is more than one adjacency for a given query.RING_ID
- an ID that helps identify the steps taken to arrive at a
query target. The RING_ID
can also be referred to as the hop ID or number
of hops it took to arrive at the query targetFor example, a social graph can be created, representing a set of people, their
primary interests, and their relationship to each other. Each node represents a
person with their first name as the NODE_NAME
and the primary interest as
the NODE_LABEL
, while each edge represents the relationship between each
pair of people. The nodes would be defined as follows, using the name &
interest columns from a table containing a given set of people as the
NODE_NAME
& NODE_LABEL
of each node, respectively:
nodes = [
TABLE_P + ".name AS NODE_NAME",
TABLE_P + ".interest AS NODE_LABEL",
],
This graph can be used to query for people with an interest in chess who are
related either directly, or indirectly via one or more other people, to the
person named Jane. This can be accomplished by querying the graph, using Jane
as the QUERY_NODE_NAME
(which instructs the graph engine to begin the search
at the node with a NODE_NAME
of Jane) and using chess as the
QUERY_TARGET_NODE_LABEL
(which directs the graph engine to only return
directly or indirectly connected nodes with a NODE_LABEL
of chess):
queries = [
"{'Jane'} AS QUERY_NODE_NAME",
"",
"{'chess'} AS QUERY_TARGET_NODE_LABEL"
],
The query results in two targets for the output adjacency table (Alex and Tom):
+-----------+--------------------------+--------------------------+
| RING_ID | QUERY_NODE_NAME_SOURCE | QUERY_NODE_NAME_TARGET |
+===========+==========================+==========================+
| 3 | Jane | Alex |
+-----------+--------------------------+--------------------------+
| 4 | Jane | Tom |
+-----------+--------------------------+--------------------------+
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.
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:
Important
Nodes and restrictions are not required to create a graph. If nodes are included, however, they should be kept in a separate table 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.
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 travelled 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:
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 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:
Solving a graph is serviced by the /solve/graph endpoint; this involves using given source node(s), 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; 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:
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).
Consult Components and Identifiers for formatting and specifications.
There are several solution types to choose from:
Solver | Description | CPU Parallel | GPU Parallel |
---|---|---|---|
SHORTEST_PATH |
Determines the shortest path upstream between given source(s) and destination(s). | X | X |
PAGE_RANK |
Calculates how connected the nodes are and determines which nodes are the most important. Weights are not required. | X | |
PROBABILITY_RANK |
Calculates the probability of a node being connected to another node using hidden Markov chains. | 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 |
ALLPATHS |
Determines all reasonable paths between a source and destination pair. | X | X |
If using the SHORTEST_PATH
solver, each source in the source list is paired
with the corresponding destination in the destination list, matched using their
respective orders in the list. A batch will be defined by each unique source
node; if there is more than one unique source node for a given list of
destination nodes, the number of nodes in the source_nodes
list must match
the number of nodes in the destination_nodes
list.
For example, if you wish to batch solve two unique sources (node_1
,
node_2
) each routing to the same three unique destinations (dest_1
,
dest_2
, dest_3
), you'd list each source paired with each destination,
resulting in each list having six total elements:
...
source_nodes = ["node_1", "node_1", "node_1", "node_2", "node_2", "node_2"]
destination_nodes = ["dest_1", "dest_2", "dest_3", "dest_1", "dest_2", "dest_3"]
...
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).
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 integer IDs, names, or WKT information. Additional adjacent rings around the specified nodes can also be queried. Results can be exported to a table in Kinetica.
Requirements for querying a graph include:
Important
Additional restrictions beyond those defined in the graph
creation stage can also be provided. Query restrictions can utilize any of
the restriction identifiers, including the unique LABEL
identifiers.
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 |
---|---|---|
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. |
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. |
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. |
QUERY_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. |
QUERY_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. |
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. |
QUERY_EDGE_WKTLINE |
wkt |
Defines the EDGE_WKTLINE value that will be matched against in
the source graph to determine the source for the query. |
QUERY_NODE1_ID |
int , long |
Defines the NODE_ID value that will be matched against in the
source graph (in conjunction with QUERY_NODE2_ID ) to determine
the source for the query. |
QUERY_NODE2_ID |
int , long |
Defines the NODE_ID value that will be matched against in the
source graph (in conjunction with QUERY_NODE1_ID ) to determine
the source for the query. |
QUERY_NODE1_WKTPOINT |
wkt |
Defines the NODE_WKTPOINT value that will be matched against in
the source graph (in conjunction with QUERY_NODE2_WKTPOINT ) to
determine the source for the query. |
QUERY_NODE2_WKTPOINT |
wkt |
Defines the NODE_WKTPOINT value that will be matched against in
the source graph (in conjunction with QUERY_NODE1_WKTPOINT ) to
determine the source for the query. |
QUERY_NODE1_NAME |
string |
Defines the NODE_NAME value that will be matched against in the
source graph (in conjunction with QUERY_NODE2_NAME ) to determine
the source for the query. |
QUERY_NODE2_NAME |
string |
Defines the NODE_NAME value that will be matched against in the
source graph (in conjunction with QUERY_NODE1_NAME ) to determine
the source for the query. |
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. |
Pair one value with an appropriate identifier to query for features connected to the given value within the provided number of rings:
queries=[
"{'male'} AS QUERY_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:
queries=[
"{'female', 'chess'} AS QUERY_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 QUERY_TARGET_NODE_LABEL
combination
(separated by an empty string) will effectively produce a source-destination
query where the first combination is the source and the
QUERY_TARGET_NODE_LABEL
is the destination (assuming the destination is
within the provided number of rings):
queries = [
"{'Jane'} AS QUERY_NODE_NAME",
"",
"{'chess'} AS QUERY_TARGET_NODE_LABEL"
],
Important
Implicitly defined nodes, e.g., from graphs defined with just edges and/or weights, cannot be queried.
To properly query a graph using identifiers, there's a minimum set of
identifiers that must be used. Each identifier combination must
reference columns from the same table, e.g., the combination QUERY_NODE1_ID
and QUERY_NODE2_ID
must both use columns from the same table. The columns
must also not be nullable.
The following combinations will query for edges adjacent to the node associated with the given information:
QUERY_NODE_ID
QUERY_NODE_LABEL
QUERY_NODE_WKTPOINT
QUERY_NODE_NAME
QUERY_TARGET_NODE_LABEL
The following combinations will query for nodes adjacent to the edge associated with the given information:
QUERY_EDGE_ID
QUERY_EDGE_LABEL
QUERY_EDGE_WKTLINE
QUERY_NODE1_ID
, QUERY_NODE2_ID
QUERY_NODE1_WKTPOINT
, QUERY_NODE2_WKTPOINT
QUERY_NODE1_NAME
, QUERY_NODE2_NAME
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):
Requirements for matching a graph include:
Solution types available:
Solver | Description |
---|---|
MARKOV_CHAIN |
Matches sample points to the graph using the Hidden Markov Model (HMM)-based method, which conducts a range-tree closest-edge search to find the best combinations of possible road segments for each sample point to create the best route. The route is secured one point at a time, so the prediction is corrected after each point. This solution type is the most accurate but also the most computationally intensive. |
MATCH_OD_PAIRS |
Matches sample points to find the most probable path between origin and destination (OD) pairs with given cost constraints. |
MATCH_SUPPLY_DEMAND |
Matches sample generic supply depots to generic demand points using abstract transportation (referred to as trucks). Each route is determined by a truck's ability (size) to service demand at each demand point. |
MATCH_BATCH_SOLVES |
Matches each provided sample source and destination pair using the shortest path between the points |
Mapping a graph to a table requires a set of sample points. Sample points must be provided to the /match/graph endpoint using the unique 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 /match/graph identifiers
Identifier | Supported Types | Description |
---|---|---|
SAMPLE_X |
float , double |
A number representing a sample's X or longitude value. |
SAMPLE_Y |
float , double |
A number representing a sample's Y or latitude value. |
SAMPLE_WKTPOINT |
float , double |
A WKT string representing a sample's geospatial point, e.g., "POINT(X Y [Z])". See Geospatial Objects for more information on WKTs. |
SAMPLE_TIME |
long , double |
A number representing a sample's time value. Note
|
SAMPLE_TRIPID |
int , long |
A number representing a unique trip identifier. |
SAMPLE_ORIGIN_WKTPOINT |
wkt |
A WKT string representing a sample's geospatial origin point, e.g., "POINT(X Y [Z])". See Geospatial Objects for more information on WKTs. |
SAMPLE_DESTINATION_WKTPOINT |
wkt |
A WKT string representing a sample's geospatial destination point, e.g., "POINT(X Y [Z])". See Geospatial Objects for more information on WKTs. |
SAMPLE_OD_TIME |
float , double |
A number representing an origin-destination (OD) pair-related sample's cost. Note
|
SAMPLE_OD_ID |
int , long |
A number representing an OD-pair-related sample's unique identifier. |
SAMPLE_DEMAND_ID |
int , long |
A number representing a demand's unique identifier. |
SAMPLE_DEMAND_WKTPOINT |
wkt |
A WKT string representing a demand's geospatial source point. |
SAMPLE_DEMAND_SIZE |
int , long |
A number representing the size of the demand. |
SAMPLE_DEMAND_DEPOT_ID |
int , long |
A number representing a demand source's unique identifier. |
SAMPLE_SUPPLY_DEPOT_ID |
int , long |
A number representing a supplier source's unique identifier. |
SAMPLE_SUPPLY_WKTPOINT |
wkt |
A WKT string representing a supplier's geospatial source point. |
SAMPLE_SUPPLY_TRUCK_ID |
int , long |
A number representing a transport's unique identifier. |
SAMPLE_SUPPLY_TRUCK_SIZE |
int , long |
A number representing a transport's capacity. |
SAMPLE_PRIORITY |
int |
A number representing a sample's priority in match processing. |
Note
Records with a timestamp of 0
for the SAMPLE_TIME
column will be
ignored when calculating the solution.
To properly match a graph using identifiers, there's a minimum set of
identifiers that must be used. Each identifier combination must
reference columns from the same table, e.g., the combination SAMPLE_WKTPOINT
and SAMPLE_TIME
must both use columns from the same table. The columns
must also not be nullable. The valid match identifier combinations per
match graph solver are as follows:
Note
If using the SAMPLE_TRIPID
identifier to match the graph, all trip IDs
will be used in the solution.
SAMPLE_X
, SAMPLE_Y
, SAMPLE_TIME
SAMPLE_WKTPOINT
, SAMPLE_TIME
SAMPLE_X
, SAMPLE_Y
, SAMPLE_TIME
, SAMPLE_TRIPID
SAMPLE_WKTPOINT
, SAMPLE_TIME
, SAMPLE_TRIPID
SAMPLE_ORIGIN_WKTPOINT
, SAMPLE_DESTINATION_WKTPOINT
,
SAMPLE_OD_TIME
SAMPLE_ORIGIN_WKTPOINT
, SAMPLE_DESTINATION_WKTPOINT
,
SAMPLE_OD_TIME
, SAMPLE_OD_ID
Important
A supply and demand combination are used in conjunction with each other to match suppliers to demand. Reference Identifier Combinations for using multiple combinations syntax.
SAMPLE_DEMAND_ID
, SAMPLE_DEMAND_WKTPOINT
, SAMPLE_DEMAND_SIZE
,
SAMPLE_DEMAND_DEPOT_ID
SAMPLE_DEMAND_ID
, SAMPLE_DEMAND_WKTPOINT
, SAMPLE_DEMAND_SIZE
,
SAMPLE_DEMAND_DEPOT_ID
, SAMPLE_PRIORITY
SAMPLE_SUPPLY_DEPOT_ID
, SUPPLY_WKTPOINT
, SAMPLE_SUPPLY_TRUCK_ID
,
SAMPLE_SUPPLY_TRUCK_SIZE
SAMPLE_ORIGIN_WKTPOINT
, SAMPLE_DESTINATION_WKTPOINT
, SAMPLE_OD_ID
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. This endpoint is used by GAdmin to populate the Graphs page.
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
.
Consult Network Graphs & Solvers Examples for detailed usage of the graph server, including creating, querying, and solving graphs.
NODE_ID
and NODE_NAME
must reference columns from the same tableNODE_ID
--> EDGE_NODE1_ID
and
EDGE_NODE2_ID
/ EDGE_ID
--> WEIGHTS_EDGE_ID
, etc.)EDGE_ID
is identified from an int
column, both EDGE_NODE1_ID
and EDGE_NODE2_ID
must also be int
nullable
propertyWEIGHTS_VALUESPECIFIED
identifier) or
multiplied (if one or both are using the WEIGHTS_FACTORSPECIFIED
identifier) together.