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
• LABEL_KEY
• 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
• LABEL_KEY
• 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. Multiple labels can be applied to the same node or edge.

The LABEL_KEY node identifiers & edge identifiers are used to create groupings of corresponding LABEL identifier values. Any node or edge with a label that is part of a label key group will also have that label key applied to it as an additional LABEL value.

LABEL_KEY values can be used in graph queries, matches, & solves.

• Node Label Key Configuration
• Edge Label Key Configuration

1
2
3
4
5
6
7
8
9

nodes = [
    TABLE_M + ".title AS NAME",
    TABLE_M + ".genre AS LABEL",
    "",
    # Apply the label key "movie" to any node that also has been labeled
    # with a value from the genre column of TABLE_M (movie nodes, above)
    "{'movie'} AS LABEL_KEY",
    TABLE_M + ".genre AS LABEL"
],

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

edges = [
    TABLE_I + ".person AS NODE1_NAME",
    TABLE_I + ".film AS NODE2_NAME",
    TABLE_I + ".participation AS LABEL",
    "",
    # Apply the label key "participation" to any edge that also has been labeled
    # with a value from the participation column of TABLE_I (person-to-film edges, above)
    "{'participation'} AS LABEL_KEY",
    TABLE_I + ".participation AS LABEL"
],

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 = [
    knows_table + ".name1 AS NODE1_NAME",
    knows_table + ".name2 AS NODE2_NAME",
    knows_table + ".relation AS LABEL"
],

Then the family relation label can be restricted during the subsequent query using the EDGE_LABEL restriction identifier, meaning that the query will not traverse any family relationship edges when moving from person node to person node:

1
2
3

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

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

×

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.

Using Query Identifiers

Social Graphs

Creating Social Graphs

Social Graphs

×

1
2
3

queries = [
    "{'Al Pacino'} AS NODE_NAME"
],

Multiple node identifiers can be used to start the search from multiple sources:

1
2
3

queries = [
    "{'Al Pacino', 'The Godfather'} AS NODE_NAME"
],

A set of edge identifiers can be used to determine whether there is a direct connection between two entities:

1
2
3
4

queries = [
    "{'Al Pacino'} AS NODE1_NAME",
    "{'The Godfather'} AS NODE2_NAME"
],

1
2
3

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

1
2
3

queries = [
    "{'directed'} AS EDGE_LABEL"
],

1
2
3
4
5

queries = [
    "{'Jean Reno'} AS NODE_NAME",
    "",
    "{'drama'} AS TARGET_NODE_LABEL"
],

1
2
3
4
5

+--------------------------+
| QUERY_NODE_NAME_TARGET   |
+==========================+
| The Godfather            |
+--------------------------+

1
2
3
4
5
6
7
8
9

+--------------------+--------------------+
| QUERY_NODE1_NAME   | QUERY_NODE2_NAME   |
+====================+====================+
| Jean Reno          | Ronin              |
+--------------------+--------------------+
| Robert De Niro     | Ronin              |
+--------------------+--------------------+
| Robert De Niro     | The Godfather      |
+--------------------+--------------------+

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

query_response = kinetica.query_graph(
    graph_name = GRAPH_NAME,
    queries = [
        "{'James Spader'} AS NODE_NAME",
        "",
        "{1} AS HOP_ID",
        "{'acted'} AS EDGE_LABEL",
        "",
        "{1} AS HOP_ID",
        "{'MOVIE'} AS NODE_LABEL",
        "",
        "{-2} AS HOP_ID",
        "{'directed'} AS EDGE_LABEL"
    ],
    adjacency_table = GRAPH_ADJ_TABLE,
    rings = 2
)

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: