/solve/graph

URL: http://GPUDB_IP_ADDRESS:GPUDB_PORT/solve/graph

Solves an existing graph for a type of problem (e.g., shortest path, page rank, travelling salesman, etc.) using source nodes, destination nodes, and additional, optional weights and restrictions.

IMPORTANT: It's highly recommended that you review the Network Graphs & Solvers concepts documentation, the Graph REST Tutorial, and/or some /solve/graph examples before using this endpoint.

Input Parameter Description

NameTypeDescription
graph_namestringName of the graph resource to solve.
weights_on_edgesarray of stringsAdditional weights to apply to the edges of an existing graph. Weights must be specified using identifiers; identifiers are grouped as combinations. Identifiers can be used with existing column names, e.g., 'table.column AS WEIGHTS_EDGE_ID', expressions, e.g., 'ST_LENGTH(wkt) AS WEIGHTS_VALUESPECIFIED', or constant values, e.g., '{4, 15, 2} AS WEIGHTS_VALUESPECIFIED'. 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). If using constant values in an identifier combination, the number of values specified must match across the combination. The default value is an empty array ( [] ).
restrictionsarray of stringsAdditional restrictions to apply to the nodes/edges of an existing graph. Restrictions must be specified using identifiers; identifiers are grouped as combinations. Identifiers can be used with existing column names, e.g., 'table.column AS RESTRICTIONS_EDGE_ID', expressions, e.g., 'column/2 AS RESTRICTIONS_VALUECOMPARED', or constant values, e.g., '{0, 0, 0, 1} AS RESTRICTIONS_ONOFFCOMPARED'. If using constant values in an identifier combination, the number of values specified must match across the combination. If remove_previous_restrictions is set to true, any provided restrictions will replace the existing restrictions. If remove_previous_restrictions is set to false, any provided restrictions will be added (in the case of 'RESTRICTIONS_VALUECOMPARED') to or replaced (in the case of 'RESTRICTIONS_ONOFFCOMPARED'). The default value is an empty array ( [] ).
solver_typestring

The type of solver to use for the graph. The default value is SHORTEST_PATH.

Supported ValuesDescription
SHORTEST_PATHSolves for the optimal (shortest) path based on weights and restrictions from one source to destinations nodes. Also known as the Dijkstra solver.
PAGE_RANKSolves for the probability of each destination node being visited based on the links of the graph topology. Weights are not required to use this solver.
PROBABILITY_RANKSolves for the transitional probability (Hidden Markov) for each node based on the weights (probability assigned over given edges).
CENTRALITYSolves for the degree of a node to depict how many pairs of individuals that would have to go through the node to reach one another in the minimum number of hops. Also known as betweenness.
MULTIPLE_ROUTINGSolves for finding the minimum cost cumulative path for a round-trip starting from the given source and visiting each given destination node once then returning to the source. Also known as the travelling salesman problem.
INVERSE_SHORTEST_PATHSolves for finding the optimal path cost for each destination node to route to the source node. Also known as inverse Dijkstra or the service man routing problem.
BACKHAUL_ROUTINGSolves for optimal routes that connect remote asset nodes to the fixed (backbone) asset nodes.
ALLPATHSSolves for paths that would give costs between max and min solution radia - Make sure to limit by the 'max_solution_targets' option. Min cost shoudl be >= shortest_path cost.
STATS_ALLSolves for graph statistics such as graph diameter, longest pairs, vertex valences, topology numbers, average and max cluster sizes, etc.
CLOSENESSSolves for the centrality closeness score per node as the sum of the inverse shortest path costs to all nodes in the graph.
source_nodesarray of stringsIt can be one of the nodal identifiers - e.g: 'NODE_WKTPOINT' for source nodes. For BACKHAUL_ROUTING, this list depicts the fixed assets. The default value is an empty array ( [] ).
destination_nodesarray of stringsIt can be one of the nodal identifiers - e.g: 'NODE_WKTPOINT' for destination (target) nodes. For BACKHAUL_ROUTING, this list depicts the remote assets. The default value is an empty array ( [] ).
solution_tablestringName of the table to store the solution, in [schema_name.]table_name format, using standard name resolution rules. The default value is 'graph_solutions'.
optionsmap of string to strings

Additional parameters. The default value is an empty map ( {} ).

Supported Parameters (keys)Parameter Description
max_solution_radiusFor ALLPATHS, SHORTEST_PATH and INVERSE_SHORTEST_PATH solvers only. Sets the maximum solution cost radius, which ignores the input parameter destination_nodes list and instead outputs the nodes within the radius sorted by ascending cost. If set to '0.0', the setting is ignored. The default value is '0.0'.
min_solution_radiusFor ALLPATHS, SHORTEST_PATH and INVERSE_SHORTEST_PATH solvers only. Applicable only when max_solution_radius is set. Sets the minimum solution cost radius, which ignores the input parameter destination_nodes list and instead outputs the nodes within the radius sorted by ascending cost. If set to '0.0', the setting is ignored. The default value is '0.0'.
max_solution_targetsFor ALLPATHS, SHORTEST_PATH and INVERSE_SHORTEST_PATH solvers only. Sets the maximum number of solution targets, which ignores the input parameter destination_nodes list and instead outputs no more than n number of nodes sorted by ascending cost where n is equal to the setting value. If set to 0, the setting is ignored. The default value is '1000'.
export_solve_results

Returns solution results inside the output parameter result_per_destination_node array in the response if set to true. The default value is false. The supported values are:

  • true
  • false
remove_previous_restrictions

Ignore the restrictions applied to the graph during the creation stage and only use the restrictions specified in this request if set to true. The default value is false. The supported values are:

  • true
  • false
restriction_threshold_valueValue-based restriction comparison. Any node or edge with a RESTRICTIONS_VALUECOMPARED value greater than the restriction_threshold_value will not be included in the solution.
uniform_weightsWhen specified, assigns the given value to all the edges in the graph. Note that weights provided in input parameter weights_on_edges will override this value.
left_turn_penaltyThis will add an additonal weight over the edges labelled as 'left turn' if the 'add_turn' option parameter of the /create/graph was invoked at graph creation. The default value is '0.0'.
right_turn_penaltyThis will add an additonal weight over the edges labelled as' right turn' if the 'add_turn' option parameter of the /create/graph was invoked at graph creation. The default value is '0.0'.
intersection_penaltyThis will add an additonal weight over the edges labelled as 'intersection' if the 'add_turn' option parameter of the /create/graph was invoked at graph creation. The default value is '0.0'.
sharp_turn_penaltyThis will add an additonal weight over the edges labelled as 'sharp turn' or 'u-turn' if the 'add_turn' option parameter of the /create/graph was invoked at graph creation. The default value is '0.0'.
num_best_pathsFor MULTIPLE_ROUTING solvers only; sets the number of shortest paths computed from each node. This is the heuristic criterion. Default value of zero allows the number to be computed automatically by the solver. The user may want to override this parameter to speed-up the solver. The default value is '0'.
max_num_combinationsFor MULTIPLE_ROUTING solvers only; sets the cap on the combinatorial sequences generated. If the default value of two millions is overridden to a lesser value, it can potentially speed up the solver. The default value is '2000000'.
accurate_snaps

Valid for single source destination pair solves if points are described in NODE_WKTPOINT identifier types: When true (default), it snaps to the nearest node of the graph; otherwise, it searches for the closest entity that could be an edge. For the latter case (false), the solver modifies the resulting cost with the weights proportional to the ratio of the snap location within the edge. This may be an over-kill when the performance is considered and the difference is well less than 1 percent. In batch runs, since the performance is of utmost importance, the option is always considered 'false'. The default value is true. The supported values are:

  • true
  • false
output_edge_path

If true then concatenated edge ids will be added as the EDGE path column of the solution table for each source and target pair in shortest path solves. The default value is false. The supported values are:

  • true
  • false
output_wkt_path

If true then concatenated wkt line segments will be added as the Wktroute column of the solution table for each source and target pair in shortest path solves. The default value is true. The supported values are:

  • true
  • false
server_idIndicates which graph server(s) to send the request to. Default is to send to the server, amongst those containing the corresponding graph, that has the most computational bandwidth. For SHORTEST_PATH solver type, the input is split amongst the server containing the corresponding graph.
convergence_limitFor PAGE_RANK solvers only; Maximum percent relative threshold on the pagerank scores of each node between consecutive iterations to satisfy convergence. Default value is 1 (one) percent. The default value is '1.0'.
max_iterationsFor PAGE_RANK solvers only; Maximum number of pagerank iterations for satisfying convergence. Default value is 100. The default value is '100'.
max_runsFor all CENTRALITY solvers only; Sets the maximum number of shortest path runs; maximum possible value is the number of nodes in the graph. Default value of 0 enables this value to be auto computed by the solver. The default value is '0'.
output_clusters

For STATS_ALL solvers only; the cluster index for each node will be inserted as an additional column in the output. The default value is false.

Supported ValuesDescription
trueAn additional column 'CLUSTER' will be added for each node
falseNo extra cluster info per node will be available in the output

Output Parameter Description

The GPUdb server embeds the endpoint response inside a standard response structure which contains status information and the actual response to the query. Here is a description of the various fields of the wrapper:

NameTypeDescription
statusString'OK' or 'ERROR'
messageStringEmpty if success or an error message
data_typeString'solve_graph_request' or 'none' in case of an error
dataStringEmpty string
data_strJSON or String

This embedded JSON represents the result of the /solve/graph endpoint:

NameTypeDescription
resultbooleanIndicates a successful solution on all servers.
result_per_destination_nodearray of floatsCost or Pagerank (based on solver type) for each destination node requested. Only populated if export_solve_results is set to true.
infomap of string to stringsAdditional information.

Empty string in case of an error.