PGX 20.1.1
Documentation

Triangle Counting Algorithms

Counts the number of triangles inside a graph.


Triangle Counting

Category structure evaluation

Algorithm ID pgx_builtin_s1_triangle_counting

Time Complexity O(E ^ 1.5) with E = number of edges

Space Requirement O(V) with V = number of vertices

Javadoc


This algorithm is intended for directed graphs and will count all the existing triangles on it. To run the algorithm on undirected graphs, use the undirected version.

Signature

Input Argument Type Comment
G graph
Return Value Type Comment
long returns the total number of triangles found.

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.Scalar;

@GraphAlgorithm
public class TriangleCounting {
  public long triangleCounting(PgxGraph g) {
    Scalar<Long> t = Scalar.create(0L);

    g.getVertices().forEach(u -> u.getInOutNeighbors().filter(v -> v.greaterThan(u)).forEach(v -> {
      u.getInOutNeighbors().filter(w -> w.greaterThan(v)).forEach(w -> {
        if (v.hasEdgeTo(w)) {
          t.increment();
        }
        if (v.hasEdgeFrom(w)) {
          t.increment();
        }
      });
    }));

    return t.get();
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure triangle_counting(graph G) : long {
  long t = 0;

  foreach (u: G.nodes) {
    foreach (v: u.inOutNbrs) (v > u) {
      foreach (w: u.inOutNbrs) (w > v) {
        if (v.hasEdgeTo(w)) {
          t++;
        }
      }
      foreach (w: u.inOutNbrs) (w > v) {
        if (v.hasEdgeFrom(w)) {
          t++;
        }
      }
    }
  }
  return t;
}

Triangle Counting (undirected)

Category structure evaluation

Algorithm ID pgx_builtin_s1b_triangle_counting_undirected

Time Complexity O(E ^ 1.5) with E = number of edges

Space Requirement O(V) with V = number of vertices

Javadoc


This algorithm is intended for undirected graphs and will count all the existing triangles on it. If the graph is a directed one, the algorithm will not count correctly the triangles in it.

Signature

Input Argument Type Comment
G graph
Return Value Type Comment
long returns the total number of triangles found.

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.Scalar;

@GraphAlgorithm
public class TriangleCountingUndirected {
  public long triangleCounting(PgxGraph g) {
    Scalar<Long> t = Scalar.create(0L);

    g.getVertices().forEach(u -> u.getNeighbors().filter(v -> v.greaterThan(u)).forEach(v -> {
      u.getNeighbors().filter(w -> w.greaterThan(v)).forEach(w -> {
        if (v.hasEdgeTo(w)) {
          t.increment();
        }
      });
    }));

    return t.get();
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure triangle_counting_undirected(graph G) : long {
  long t = 0;

  foreach (u: G.nodes) {
    foreach (v: u.nbrs) (v > u) {
      foreach (w: u.nbrs) (w > v) {
        if (v.hasEdgeTo(w)) {
          t++;
        }
      }
    }
  }
  return t;
}