search

tf_graph_shortest_paths_distances

Given a distance-weighted directed graph, consisting of a queryCURSOR input consisting of the starting and ending node for each edge and a distance, and a specified origin node, tf_graph_shortest_paths_distances computes the shortest distance-weighted path distance between the origin_node and every other node in the graph. It returns a row for each node in the graph, with output columns consisting of the input origin_node, the given destination_node, the distance for the shortest path between the two nodes, and the number of edges or graph "hops" between the two nodes. If origin_node does not exist in the node1 column of the edge_list CURSOR, an error is returned.

SELECT * FROM TABLE(
    tf_graph_shortest_paths_distances(
        edge_list => CURSOR(
            SELECT node1, node2, distance FROM table
        ),
        origin_node => <origin node>
    )

Input Arguments

Parameter
Description
Data Types

node1

Origin node column in directed edge list CURSOR

Column<INT | BIGINT | TEXT ENCODED DICT>

node2

Destination node column in directed edge list CURSOR

Column<INT | BIGINT | TEXT ENCODED DICT> (must be the same type as node1)

distance

Distance between origin and destination node in directed edge list CURSOR

Column INT | BIGINT | FLOAT | DOUBLE>

origin_node

The origin node to start graph traversal from. If not a value present in edge_list.node1, will cause empty result set to be returned.

BIGINT | TEXT ENCODED DICT

Output Columns

Name
Description
Data Types

origin_node

Starting node in graph traversal. Always equal to input origin_node.

Column <INT | BIGINT | TEXT ENCODED DICT> (same type as the node1 and node2 input columns)

destination_node

Final node in graph traversal. Will be equal to one of values of node2 input column.

Column <INT | BIGINT | TEXT ENCODED DICT> (same type as the node1 and node2 input columns)

distance

Cumulative distance between origin and destination node for shortest path graph traversal.

Column<INT | BIGINT | FLOAT | DOUBLE> (same type as the distance input column)

num_edges_traversed

Number of edges (or "hops") traversed in the graph to arrive at destination_node from origin_node for the shortest path graph traversal between these two nodes.

Column <INT>

Example A

/* Compute the 10 furthest destination airports as measured by average travel-time
when departing origin airport 'RDU' (Raleigh-Durham, NC) on United Airlines for the
year 2008, adding 60 minutes for each leg to account forboarding/plane change time 
costs. */

SELECT
  *
FROM
  TABLE(
    tf_graph_shortest_paths_distances(
      edge_list => CURSOR(
        SELECT
          origin,
          dest,
          /* Add 60 minutes to each leg to account for boarding/plane change costs */
          AVG(airtime) + 60 as avg_airtime
        FROM
          flights_2008
        WHERE
          carrier_name = 'United Air Lines'
        GROUP by
          origin,
          dest
      ),
      origin_node => 'RDU'
    )
  )
ORDER BY
  distance DESC
LIMIT
  10;
  
origin_node|destination_node|distance|num_edges_traversed
RDU|JFK|803|3
RDU|LIH|757|2
RDU|KOA|746|2
RDU|HNL|735|2
RDU|OGG|728|2
RDU|EUG|595|3
RDU|ANC|586|2
RDU|SJC|468|2
RDU|SFO|468|2
RDU|OAK|468|2

Example B

Rendered chart of the output of tf_graph_shortest_paths_distances along an Eastern US time-traversal weighted edge graph. The shortest travel destinations are rendered in blue, and the furthest travel destinations in yellow.
Previoustf_graph_shortest_pathNexttf_load_point_cloud

Last updated

Was this helpful?