PGX 20.2.2
Documentation

Compute High-Degree Vertices

Category path finding

Algorithm ID pgx_builtin_o6_compute_supernodes

Time Complexity O(N log N) with N = number of vertices

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

Javadoc


Computes the k vertices with the highest degrees in the graph. The resulting map will contain a mapping with the sorted index to the high-degree vertex with the index.

Signature

Input Argument Type Comment
G graph
k int number of high-degree vertices to be computed.
Output Argument Type Comment
superNodes nodeSet the high-degree vertices.
superNodeMapping map the high-degree vertices.

Code

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

import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxMap;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexSet;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

@GraphAlgorithm
public class HopDistPathComputeSupernodes {
  public void computeSuperNodes(PgxGraph g, int k, @Out PgxMap<Integer, PgxVertex> superNodeMapping,
      VertexSet superNodes) {
    PgxMap<PgxVertex, Long> vertexDegrees = PgxMap.create();
    g.getVertices().forSequential(n -> {
      long deg = n.getInDegree() + n.getOutDegree();
      if (vertexDegrees.size() < k) {
        vertexDegrees.set(n, deg);
      } else {
        PgxVertex other = vertexDegrees.getKeyForMinValue();
        if (deg > vertexDegrees.get(other)) {
          vertexDegrees.remove(other);
          vertexDegrees.set(n, deg);
        }
      }
    });

    // assert vertexDegrees.size() <= k
    Scalar<Integer> counter = Scalar.create(0);
    vertexDegrees.keys().forSequential(superNode -> {
      long deg = vertexDegrees.get(superNode);
      superNodes.add(superNode);
      superNodeMapping.set(counter.get(), superNode);
      counter.increment();
    });
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
proc computeSuperNodes(graph g, int k; map<int, node> superNodeMapping, nodeSet superNodes) {

  map<node, int> vertexDegrees;
  for(n: g.nodes) {
    int deg = n.inDegree() + n.outDegree();
    if (vertexDegrees.size() < k) {
      vertexDegrees[n] = deg;
    } else {
      node other = vertexDegrees.getMinKey();
      if (deg > vertexDegrees[other]) {
        vertexDegrees.remove(other);
        vertexDegrees[n] = deg;
      }
    }
  }

  // assert vertexDegrees.size() <= k
  int counter = 0;
  for(superNode : vertexDegrees.keys) {
    superNodes.add(superNode);
    superNodeMapping[counter] = superNode;
    counter++;
  }

}