Network Graphs & Solvers Concepts

Solve Graph Solvers

Match Graph Solvers

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 [Z])) or XY pair. Nodes are optional, as the start and end points of an edge can implicitly be used as nodes.

Edges

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.

Weights

Graph Weights

Modeling Weighted Graphs

Graph Weights

×

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.

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

Nodes

• ID
• ID, NAME
• ID, WKTPOINT
• ID, X, Y
• NAME
• NAME, WKTPOINT
• NAME, X, Y
• WKTPOINT
• X, Y

The following identifiers can be added to any valid node combination:

• LABEL
• PARTITION_BOUNDARY

Edges

• ID, NODE1_ID, NODE2_ID
• ID, NODE1_ID, NODE2_ID, DIRECTION
• ID, NODE1_NAME, NODE2_NAME
• ID, NODE1_WKTPOINT, NODE2_WKTPOINT
• ID, NODE1_X, NODE1_Y, NODE2_X, NODE2_Y
• ID, WKTLINE
• ID, WKTLINE, DIRECTION
• NODE1_ID, NODE2_ID
• NODE1_NAME, NODE2_NAME
• NODE1_WKTPOINT, NODE2_WKTPOINT
• NODE1_X, NODE1_Y, NODE2_X, NODE2_Y
• WKTLINE
• WKTLINE, DIRECTION

Any or all of the following identifiers can be added to any valid edge combination:

• LABEL
• PARTITION
• WEIGHT_VALUESPECIFIED

Weights

• EDGE_ID, VALUESPECIFIED
• EDGE_ID, FACTORSPECIFIED
• EDGE_WKTLINE, EDGE_DIRECTION, VALUESPECIFIED
• EDGE_WKTLINE, VALUESPECIFIED
• EDGE_WKTLINE, FACTORSPECIFIED
• EDGE_NODE1_NAME, EDGE_NODE2_NAME, VALUESPECIFIED
• EDGE_NODE1_NAME, EDGE_NODE2_NAME, FACTORSPECIFIED
• EDGE_NODE1_ID, EDGE_NODE2_ID, VALUESPECIFIED
• EDGE_NODE1_ID, EDGE_NODE2_ID, FACTORSPECIFIED
• WKTPOINT, FACTORSPECIFIED

If utilizing turn penalties, the following combination becomes applicable:

• FROM_EDGE_ID, TO_EDGE_ID, VALUESPECIFIED

Restrictions

• EDGE_ID, ONOFFCOMPARED
• EDGE_ID, VALUECOMPARED
• EDGE_LABEL, ONOFFCOMPARED
• EDGE_NODE1_ID, EDGE_NODE2_ID, ONOFFCOMPARED
• EDGE_NODE1_NAME, EDGE_NODE2_NAME, ONOFFCOMPARED
• EDGE_WKTLINE, EDGE_DIRECTION, ONOFFCOMPARED
• EDGE_WKTLINE, EDGE_DIRECTION, VALUECOMPARED
• EDGE_WKTLINE, ONOFFCOMPARED
• EDGE_WKTLINE, VALUECOMPARED
• NODE_ID, ONOFFCOMPARED
• NODE_ID, VALUECOMPARED
• NODE_LABEL, ONOFFCOMPARED
• NODE_NAME, VALUECOMPARED
• NODE_NAME, ONOFFCOMPARED
• NODE_WKTPOINT, ONOFFCOMPARED
• NODE_WKTPOINT, VALUECOMPARED

If utilizing turn restrictions, the following combination becomes applicable:

• FROM_EDGE_ID, TO_EDGE_ID, ONOFFCOMPARED

Node / Edge Labels

The LABEL node identifiers & edge identifiers are used to provide additional string-based information about a node or edge respectively, similarly to the node NAME (and other related) identifiers.

Restriction Labels

The NODE_LABEL and EDGE_LABEL restriction identifiers are used to restrict the value set defined as node & edge LABEL respectively. These restrictive identifiers must follow an already-defined node 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:

1
2
3
4
5

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

Then the family relation label can be restricted during the subsequent query using the EDGE_LABEL restriction identifier:

1
2
3
4

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

Unique Query Labels

There are several *_LABEL query identifiers that are unique to the /query/graph endpoint.

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 |
+------------------------+------------------------+--------------------------+--------------------------+-----------+

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

×

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.

Non-Batch Solving

Non-batch solving is utilized exclusively with every solver except for SHORTEST_PATH, in which case the length of the source and destination node lists will determine if non-batch or Batch Solving is utilized. If the source and destination lists do not match and the SHORTEST_PATH solver is specified, batch solving will be used. If the source and destination node lists match in length (and SHORTEST_PATH is the specified solver), non-batch solving will be used. This means that the first source index would only be matched with the first destination index, the second source index to the second destination index, etc.

For example, if you attempt to solve three unique sources (node_1, node_2, and node_3) to three unique destinations (dest_1, dest_2, dest_3) by only listing each source and destination once (calling /solve/graph with source_nodes set to ["node_1", "node_2", "node_3"] and destination_nodes set to ["dest_1", "dest_2", "dest_3"]), it would yield a result set like this:

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

Batch Solving

If using the SHORTEST_PATH solver, multiple sources can be routed to multiple destinations using batch solving. A batch will be defined by each unique source node visiting each destination node provided which will yield a Cartesian product.

For example, if you wish to batch solve two unique sources (node_1, node_2) each routing to three unique destinations (dest_1, dest_2, dest_3), you'd list each source and each destination, noting that the solution will automatically map node_1 and node_2 to dest_1, dest_2, and dest_3 individually. A call to /solve/graph with source_nodes set to ["node_1", "node_2"] and destination_nodes set to ["dest_1", "dest_2", "dest_3"] would yield a result set like this:

+--------+--------+
| 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 |
+--------+--------+

However, if you wish to batch solve three unique sources (node_1, node_2, node_3) to three unique destinations (dest_1, dest_2, dest_3) (or n sources to n destinations for that matter), you'll need to list out all 9 combinations manually, e.g.,:

 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"
],

The above setup would yield a similar result set as the first example:

+--------+--------+
| 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 |
+--------+--------+

Query Identifiers

Querying Graphs

Advanced Example

Querying Graphs

×

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.

Query Identifier Combinations

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 NODE1_ID and NODE2_ID must both use columns from the same table. The columns must also not be nullable.

Match Identifiers

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.

Match Identifier Combinations

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 WKTPOINT and 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: