Triangle Finding

Description, inputs and outputs of the Triangle finding algorithm

URI 

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

Description

The Triangle Finding algorithm is used to find all the triangles in the graph. The output can be customized to return either all triangles, or only the cyclic or non-cyclic triangles. The number of triangles in a given region of a graph is a good indicator of the density of that part of the graph.

Inputs and Default Values

  • Vector inputs- None.
  • Scalar inputs - This algorithm accepts a single integer scalar argument. The value of this integer ranges from 0 to 4 and specifies which types of triangles are to be output..
    • 0 - Return all the triangles in the graph, both cyclic (including rotations) and non-cyclic triangles
    • 1: Return all the unique triangles in the graph, both cyclic and non-cyclic triangles
    • 2: Return only the non-cyclic triangles
    • 3: Return only the cyclic triangles (including rotations)
    • 4: Return only the unique cyclic triangles

Outputs

The code returns a four-column IRA . Each row in the IRA represents the three URIs of the vertices of a triangle followed by a cyclic flag (set to 1 for cyclic, 0 for non-cyclic). The non-cyclic triangles are written out in the order of through_vertex, in_vertex, out_vertex. The cyclic flag is considered optional in the PRODUCING clause in the case where only the URIs of the vertices are needed.

Example: Triangle Finding

PREFIX cray: <http://cray.com/>

  SELECT ?vertexID1 ?vertexID2 ?vertexID3 ?cyc
  WHERE {
    CONSTRUCT{
      ?sub ?pred ?obj .
    }
    WHERE{
      ?sub ?pred ?obj .
    }
    INVOKE cray:graphAlgorithm.triangle_finding(1) 
    PRODUCING ?vertexID1 ?vertexID2 ?vertexID3 ?cyc