S-T Set Connectivity

Description, inputs and outputs of the S-T Set connectivity algorithm

URI

<http://cray.com/graphAlgorithm.st_set_connectivity>

Inputs and Default Values

Scalar inputs - None.

Vector inputs - The S-T Set Connectivity function accepts input of a set of vertices designated as sources and a set of vertices designated as targets. These are added to the constructed graph using the <http:∕∕cray.com∕sourceVertex> and <http:∕∕cray.com∕targetVertex> URIs, as well as the standard RDFS predicate <http:∕∕www.w3.org∕1999∕02∕22-rdf-syntax-ns#type>, which may be abbreviated as “a” in a SPARQL query.


Subject	Predicate	Object
Source vertex identifier	`a`	`<http:∕∕cray.com∕sourceVertex>`
Target vertex identifier	`a`	`<http:∕∕cray.com∕targetVertex>`

Outputs

A call to the S-T Set Connectivity function returns an intermediate result set containing a single integer. The values and meaning of this integer are described below:

If the integer’s value is 0, there is no path between any pair of vertices with the source vertex taken from the source set and the target vertex taken from the target set.
If the value is greater than 0, it represents the number of hops in the shortest path between any such pair of vertices.

Important: The S-T Set Connectivity function will return an error in the following cases:

Nonexistence of input source and/or target vertex
Invalid input source and/or target vertex
Nonexistence of input source and/or target vertex in the input edge list

Example: S-T Set Connectivity

The following example selects all of the edges from the default graph and calls S-T Set Connectivity on the resulting graph.

PREFIX cray: <http://cray.com/>
SELECT ?distance
WHERE {
  CONSTRUCT{
     ?sub ?pred ?obj .
     ?srcNode a cray:sourceVertex .
     ?trgNode a cray:targetVertex .
    }
  WHERE{
     {
        ?sub ?pred ?obj .
     }
     UNION {
        VALUES ?srcNode
        {
          <http://bgf.org/c/03/i/000000>
          <http://bgf.org/c/05/i/000000>
          <http://bgf.org/c/08/i/000003>
        }
     }
     UNION {
        VALUES ?trgNode
        {
          <http://bgf.org/c/05/i/000001>
          <http://bgf.org/c/08/i/000007>
        }
     }
  }
  INVOKE cray:graphAlgorithm.st_set_connectivity()
  PRODUCING ?distance
}