Path Finding Algorithms

Path finding algorithms identify the shortest path or evaluate the availability and quality of paths:

All Paths: Lists all of the paths that exist between two nodes in a graph.
Shortest Path: Finds the shortest path (the path with the least cost) from a source node to the other nodes in a graph.

All Paths

The All Paths algorithm finds all of the paths that exist between a source node and destination node in a graph.

Syntax

To incorporate the All Paths algorithm in a query, include the following SERVICE call in the WHERE clause.

SERVICE <csi:all_paths>
  {
    [] <csi:binding-vertex>        ?vertex_variable ;
       <csi:binding-edge>          ?edge_variable ;
       <csi:binding-successor>     ?successor_variable ;
       <csi:source>                <source_node_uri> ;
       <csi:destination>           <destination_node_uri> ;
     [ <csi:graph>                 <graph_uri> ; ]
     [ <csi:edge-label>            "<edge_uri>" ; ]
     [ <csi:binding-path-index>    ?path_index_variable ; ]
     [ <csi:binding-path>          ?path_variable ; ]
     [ <csi:min-length>            min_length ; ]
     [ <csi:max-length>            max_length ; ]
     [ <csi:undirected>            undirected ; ]
     [ <csi:binding-orientation>   ?orientation_variable ] .
}

Argument	Range	Description
binding-vertex	variable	Required argument that defines the name to use for the result column that lists the nodes that are reachable by the source node.
binding-edge	variable	Required argument that defines the name to use for the result column that lists the edges that exist between the nodes.
binding-successor	variable	Required argument that defines the name to use for the result column that lists the destination nodes.
source	URI	Required argument that specifies the URI of the source node.
destination	URI	Required argument that specifies the URI for the destination node.
graph	URI	Optional argument that specifies the graph to query.
edge-label	string	Optional argument that further defines the path to operate on. This property accepts complex path specifications such as W3C Property Paths. When specifying edge URIs, prefix notation is not supported. Include the full URI.
binding-path-index	variable	Optional argument that defines the name to use for the result column that lists the unique identifiers for the edges found in the path. The identifier represents the order for edges.
binding-path	variable	Optional argument that defines the name to use for the result column that lists the unique identifiers for the paths that are found.
min-length	int	Optional argument that specifies the minimum number of paths to evaluate.
max-length	int	Optional argument that specifies the maximum number of paths to evaluate. The default value is unlimited.
undirected	boolean	Optional argument that specifies whether to treat edges as undirected. When `true`, the algorithm assumes that paths can be traversed in both directions. The default value is `false`.
binding-orientation	variable	Optional argument to be used in conjunction with undirected. If `csi:undirected` is `true`, you can include this property to add a result column that lists the orientation of each path. In the results, `csi:binding-orientation` returns `t` (true) when the direction of the edge goes from the source node to the successor. `csi:binding-orientation` returns `f` (false) when the direction of the edge goes from the successor to the source node.

Shortest Path

The Shortest Path algorithm finds the shortest path from a source node to the other reachable nodes in a graph.

Syntax

To incorporate the Shortest Path algorithm in a query, include the following SERVICE call in the WHERE clause.

SERVICE <csi:shortest_path>
 {
    [] <csi:binding-vertex>          ?binding_vertex_variable ;
       <csi:binding-predecessor>     ?predecessor_variable ;
       <csi:graph>                   <graph_uri> ;
       <csi:source-vertex>           <source_node_uri> ;
       <csi:edge-label>              <edge_uri> ;
     [ <csi:binding-distance>        ?binding_distance_variable ; ]
     [ <csi:weight>                  <property_uri> ; ]
     [ <csi:destination-vertex>      <destination_node_uri>  ] .
}

Argument	Range	Description
binding-vertex	variable	Required argument that defines the name to use for the result column that lists the nodes that are reachable by the source-vertex.
binding-predecessor	variable	Required argument that defines the name to use for the result column that lists the nodes that are on the path between the source and destination vertices.
graph	URI	Required argument that specifies the graph to query.
source-vertex	URI	Required argument that specifies the URI of the source node.
edge-label	URI	Required argument that lists the edge URI that defines the graph to operate on. The graph is the set of vertices that are connected by this URI.
binding-distance	variable	Optional argument that adds a result column that lists the number of hops in the path between the source node and destination nodes. If `csi:weight` is specified, the binding-distance column displays the weight value.
weight	URI	Optional argument that specifies an edge property URI whose value can be used to determine the shortest path. When you do not specify a weight, the algorithm calculates the shortest path according the number of hops required to reach the destination vertex (or all nodes identified by the edge-label if destination-vertex is not specified). When weight is specified, the weight value is used as the shortest path measurement instead of the number of hops. For more information about properties, see Create a Labeled Property Graph (RDF-star).
destination-vertex	URI	Optional argument that specifies the URI of the destination node. Include the destination-vertex URI when you want to find the shortest path between two specific vertices. When destination-vertex is excluded, Graph Lakehouse returns the shortest path between all vertices that are accessible by the edge-label. The value for this property is only applied when weight is included in the query. It is ignored when `<csi:weight>` is excluded.

Example

The following example finds the shortest path for flights from Boston (BOS) to Honolulu (HNL). In the query, the starting point or source node (csi:source-vertex) is the URI for BOS. To find the shortest path between BOS and HNL instead of the shortest path between BOS and all other airports that are reachable by the edge-label, the query includes the csi:destination-vertex property, which specifies the URI for HNL. The csi:weight property is also included and specifies the URI for the distanceMiles edge property. That tells the algorithm to calculate the shortest path by distance rather than number of hops.

prefix : <http://anzograph.com/data#>
prefix fl: <http://anzograph.com/flights/>
prefix owl: <http://www.w3.org/2002/07/owl#>
prefix skos: <http://www.w3.org/2004/02/skos/core#>

SELECT ?destination ?distance
FROM <http://anzograph.com/airline_flight_network>
WHERE 
{
    SERVICE <csi:shortest_path> 
  { 
      [] <csi:binding-vertex> ?airport ;
         <csi:binding-predecessor> ?predecessor ;
         <csi:binding-distance> ?distance ;
         <csi:graph> <http://anzograph.com/airline_flight_network> ;
         <csi:source-vertex> <http://anzograph.com/flights/Airport/BOS> ;
         <csi:destination-vertex> <http://anzograph.com/flights/Airport/HNL> ;
         <csi:edge-label> <http://anzograph.com/flights/hasRouteTo> ;
         <csi:weight> <http://anzograph.com/flights/distanceMiles> .
  }
  ?airport fl:terminalCode ?destination .
}
ORDER BY ?distance

The results (shown below) determine that the shortest path from BOS to HNL is through Salt Lake City (SLC). The binding-vertex column (?distance) shows the distance for each leg of the flight.

destination | distance
------------+----------
BOS         |       0
SLC         |    2105
HNL         |    5099
3 rows