PGX 20.1.1
Documentation

Eccentricity Algorithms

These algorithms compute distances between vertices.


Diameter / Radius

Category structure evaluation

Algorithm ID pgx_builtin_s11_diameter

Time Complexity O(V * E) with V = number of vertices, E = number of edges

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

Javadoc


The diameter of a graph is the maximal value of eccentricity of all the vertices in the graph, while the radius is the minimum graph eccentricity. The eccentricity of a vertex is the maximum distance via shortest paths to any other vertex in the graph. This algorithm will compute the eccentricity of all the vertices and will also return the diameter or radius value depending on the request. The algorithm will return an INF eccentricity and diameter/radius, for graphs with more than one strongly connected component.

Signature

Input Argument Type Comment
G graph
diameterOn boolean boolean flag to determine whether the algorithm will return the diameter or radius of the graph.
Output Argument Type Comment
eccentricity nodeProp vertex property holding the eccentricity value for each vertex.
Return Value Type Comment
int value of the diameter or radius, depending the chosen option.

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.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.Traversal.currentLevel;
import static oracle.pgx.algorithm.Traversal.inBFS;
import static java.lang.Integer.MAX_VALUE;

@GraphAlgorithm
public class Diameter {
  public int diameter(PgxGraph g, boolean diameterOn, @Out VertexProperty<Integer> eccentricity) {
    eccentricity.setAll(0);
    long n = g.getNumVertices();
    Scalar<Integer> diameter = Scalar.create(0);
    Scalar<Integer> radius = Scalar.create(MAX_VALUE);
    Scalar<Boolean> disconnected = Scalar.create(false);

    g.getVertices().filter(s -> !disconnected.get()).forEach(s -> {
      Scalar<Integer> visited = Scalar.create(1);
      Scalar<Integer> maxLevel = Scalar.create(0);

      inBFS(g, s).filter(v -> v != s).forward(v -> {
        maxLevel.reduceMax(currentLevel());
        visited.increment();
      });

      disconnected.set(visited.get() < n);
      diameter.reduceMax(maxLevel.get());
      radius.reduceMin(maxLevel.get());
      eccentricity.set(s, maxLevel.get());
    });

    if (disconnected.get()) {
      eccentricity.setAll(MAX_VALUE);
      return MAX_VALUE;
    }

    if (diameterOn) {
      return diameter.get();
    } else {
      return radius.get();
    }
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure diameter(graph G, bool diameterOn; nodeProp<int> eccentricity) : int {

  G.eccentricity = 0;
  int diameter = 0;
  int radius = INF;
  long N = G.numNodes();
  bool disconnected = false;

  foreach (s: G.nodes) (!disconnected) {
    int visited = 1;
    int max_level = 0;
    inBFS (v: G.nodes from s) (v != s) {
      max_level max= currentBFSLevel();
      visited++;
    }
    disconnected = visited < N ? true : false;
    diameter max= max_level;
    radius min= max_level;
    s.eccentricity = max_level;
  }

  if (disconnected) {
    G.eccentricity = INF;
    return INF;
  }

  if (diameterOn) {
    return diameter;
  } else {
    return radius;
  }
}

Periphery / Center

Category structure evaluation

Algorithm ID pgx_builtin_s12_periphery

Time Complexity O(V * E) with V = number of vertices, E = number of edges

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

Javadoc


The periphery of a graph is the set of vertices that have an eccentricity value equal to the diameter of the graph. Similarly, the center is comprised by the set of vertices with eccentricity equal to the radius of the graph. The diameter of a graph is the maximal value of eccentricity of all the vertices in the graph, while the radius is the minimum graph eccentricity. The eccentricity of a vertex is the maximum distance via shortests paths to any other vertex in the graph. This algorithm will return the set of vertices from the periphery or the center of the graph, depending on the request. The algorithm will return a set with all the vertices for graphs with more than one strongly connected component.

Signature

Input Argument Type Comment
G graph
peripheryOn boolean boolean flag to determine whether the algorithm will return the periphery or center of the graph.
Output Argument Type Comment
periphery nodeSet vertex set holding the vertices from the periphery or center of the graph.

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.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSet;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static oracle.pgx.algorithm.Traversal.currentLevel;
import static oracle.pgx.algorithm.Traversal.inBFS;
import static java.lang.Integer.MAX_VALUE;

@GraphAlgorithm
public class Periphery {
  public void periphery(PgxGraph g, boolean peripheryOn, @Out VertexSet periphery) {
    VertexProperty<Integer> eccentricity = VertexProperty.create();

    eccentricity.setAll(0);
    Scalar<Integer> diameter = Scalar.create(0);
    Scalar<Integer> radius = Scalar.create(MAX_VALUE);
    long n = g.getNumVertices();
    Scalar<Boolean> disconnected = Scalar.create(false);

    g.getVertices().filter(s -> !disconnected.get()).forEach(s -> {
      Scalar<Integer> visited = Scalar.create(1);
      Scalar<Integer> maxLevel = Scalar.create(0);

      inBFS(g, s).filter(v -> v != s).forward(v -> {
        maxLevel.reduceMax(currentLevel());
        visited.increment();
      });

      disconnected.set(visited.get() < n);
      diameter.reduceMax(maxLevel.get());
      radius.reduceMin(maxLevel.get());
      eccentricity.set(s, maxLevel.get());
    });

    if (disconnected.get()) {
      g.getVertices().forEach(periphery::add);
    } else {
      int chosen = peripheryOn ? diameter.get() : radius.get();
      g.getVertices().forEach(w -> {
        if (eccentricity.get(w) == chosen) {
          periphery.add(w);
        }
      });
    }
  }
}
/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure periphery(graph G, bool peripheryOn; nodeSet periphery) {

  nodeProp<int> eccentricity;

  G.eccentricity = 0;
  int diameter = 0;
  int radius = INF;
  long N = G.numNodes();
  bool disconnected = false;

  foreach (s: G.nodes) (!disconnected) {
    int visited = 1;
    int max_level = 0;
    inBFS (v: G.nodes from s) (v != s) {
      max_level max= currentBFSLevel();
      visited++;
    }
    disconnected = visited < N ? true : false;
    diameter max= max_level;
    radius min= max_level;
    s.eccentricity = max_level;
  }

  if (disconnected) {
    foreach (s: G.nodes) {
      periphery.add(s);
    }
  } else {
    int chosen = peripheryOn ? diameter : radius;
    foreach (s: G.nodes) {
      if (s.eccentricity == chosen) {
        periphery.add(s);
      }
    }
  }
}