Version:

Network Graphs Solver Concepts

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.

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 NODE_WKTPOINT
  • Using expressions, e.g., ST_LENGTH(wkt) AS WEIGHTS_VALUESPECIFIED
  • Using raw values, e.g., {0} AS RESTRICTIONS_ONOFFCOMPARED

Note

There are separate identifiers and combinations for /query/graph and /match/graph. See the associated Querying a Graph and Matching a Graph sections for more information.

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 as a supported type can be any 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.
NODE_LABEL string

A string value representing a node's label. Exclusively used with /query/graph restrictions.

Important

Even though this identifier can only be used when querying a graph, this identifier must be specified during the /create/graph stage.

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)"), 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).
EDGE_LABEL string

A string value representing an edge's label. Exclusively used with /query/graph restrictions.

Important

Even though this identifier can only be used when querying a graph, this identifier must be specified during the /create/graph stage.

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_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, 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 representing 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.
RESTRICTIONS_NODE_LABEL string

A string value referring to a node label for restrictive purposes. Exclusively used with /query/graph restrictions.

Important

Even though this identifier can only be used when querying a graph, this identifier must be specified during the /create/graph stage.

RESTRICTIONS_EDGE_LABEL string

A string value referring an edge label for restrictive purposes. Exclusively used with /query/graph restrictions.

Important

Even though this identifier can only be used when querying a graph, this identifier must be specified during the /create/graph stage.

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 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, or querying a graph, the combinations must be separated by empty quotes ("") in the respective array, e.g.:

    queries = [
      "{'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"

Nodes

  • 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

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

  • 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

Restrictions

  • RESTRICTIONS_EDGE_ID, RESTRICTIONS_ONOFFCOMPARED
  • RESTRICTIONS_EDGE_ID, RESTRICTIONS_VALUECOMPARED
  • RESTRICTIONS_EDGE_LABEL, RESTRICTIONS_ONOFFCOMPARED
  • RESTRICTIONS_EDGE_WKTLINE, RESTRICTIONS_VALUECOMPARED
  • RESTRICTIONS_EDGE_WKTLINE, RESTRICTIONS_ONOFFCOMPARED
  • 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_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.

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

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). 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 using single-source routing. 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

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 integer 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 to query

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.

Query 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 A number representing the node to be queried.
QUERY_NODE_WKTPOINT wkt A WKT string representing the node to be queried.
QUERY_NODE_NAME string A string value representing the node to be queried.
QUERY_EDGE_ID int, long A number representing the edge to be queried.
QUERY_EDGE_WKTLINE wkt A WKT string representing the edge to be queried.
QUERY_NODE1_ID int, long A number representing the first node of the edge to be queried.
QUERY_NODE2_ID int, long A number representing the second node of the edge to be queried.
QUERY_NODE1_WKTPOINT wkt A WKT string representing the first node of the edge to be queried.
QUERY_NODE2_WKTPOINT wkt A WKT string representing the second node of the edge to be queried.
QUERY_NODE1_NAME string A string value representing the first node of the edge to be queried.
QUERY_NODE2_NAME string A string value representing the second node of the edge to be queried.
QUERY_TARGET_NODE_LABEL string A string value representing the target of the query. See Using Labels for an example.

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

Nodes

  • QUERY_NODE_ID
  • QUERY_NODE_WKTPOINT
  • QUERY_NODE_NAME
  • QUERY_TARGET_NODE_LABEL

Edges

  • QUERY_EDGE_ID
  • QUERY_EDGE_WKTLINE
  • QUERY_NODE1_ID, QUERY_NODE2_ID
  • QUERY_NODE1_WKTPOINT, QUERY_NODE2_WKTPOINT
  • QUERY_NODE1_NAME, QUERY_NODE2_NAME

Using Labels

Labels are a type of identifer that provide additional context to a node or edge and can act as a target for a query. Labels can only be referenced in the context of queries using the /query/graph endpoint. There are two types of labels: restriction labels and query labels.

Restriction Labels

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 when querying a graph just like other restriction identifiers.

For example, if the relation between two people is used as the EDGE_LABEL when creating the 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 identifer:

    restrictions = [
      "{'family'} AS RESTRICTIONS_EDGE_LABEL",
      "{0} AS RESTRICTIONS_ONOFFCOMPARED"
    ],

Query Labels

The QUERY_TARGET_NODE_LABEL query identifier is unique to /query/graph. It's typically paired with another query combination to define a source-destination relationship for a query. This identifer 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 target

Example: if the interest of a person is used as the NODE_LABEL when creating the graph:

    nodes = [
      TABLE_P + ".name AS NODE_NAME",
      TABLE_P + ".interest AS NODE_LABEL"
    ],

Then the Jane node can be mapped to any node with chess as NODE_LABEL (interest):

    queries = [
      "{'Jane'} AS QUERY_NODE_NAME",
      "",
      "{'chess'} AS QUERY_TARGET_NODE_LABEL"
    ],

The query results in two targets for the output adjacency table:

 ID Name 1   Name 2    Path ID Ring ID
=== ======== ========= ======= =======
    Jane     Bill      0       1
    Bill     Susan     0       2
    Susan    Alex      0       3
    Jane     Bill      1       1
    Bill     Susan     1       2
    Susan    Alex      1       3
    Alex     Tom       1       4

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 tracks 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 solving a graph include:

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

Solution types available:

Solver Description
INCREMENTAL_WEIGHTED Matches sample points to the graph using time and/or distance between points to influence one or more shortest paths across the sample points.
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 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.

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)". See Geospatial Objects for more information on WKTs.
SAMPLE_TIME long, double A number representing a sample's timestamp.
SAMPLE_TRIPID int, long A number representing a unique trip identifier.

Note

Records with a timestamp of 0 for the SAMPLE_TIME column will be ignored when calculating the solution.

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 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 are as follows:

  • SAMPLE_X, SAMPLE_Y, SAMPLE_TIME
  • SAMPLE_WKTPOINT, SAMPLE_TIME
  • SAMPLE_X, SAMPLE_Y, SAMPLE_TIME, SAMPLE_TRIPID
  • SAMPLE_WKTPOINT, SAMPLE_TIME, SAMPLE_TRIPID

Note

If using the SAMPLE_TRIPID identifier to match the graph, all trip IDs will be used in the solution.

Listing a Graph

Listing a graph is serviced by the /list/graph endpoint; this involves providing a graph name to view information about the provided graph on the graph server. Providing no graph name will return information on all 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).

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

Consult Network Graph Solver Examples for detailed usage of the graph server, including creating, querying, and solving graphs.

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.