PGX 20.1.1
Documentation

Fattest Path

Category path finding

Algorithm ID pgx_builtin_p5_fattest_path

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

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

Javadoc

The Fattest path algorithm can be regarded as a variant of Dijkstra's algorithm, it tries to find the fattest path between the given source and all the reachable vertices in the graph. The fatness of a path is equal to the minimum value of the capacity from the edges that take part in the path, thus a fattest path is conformed by the edges with the largest possible capacity.

Signature

Input Argument Type Comment
G graph
capacity edgeProp edge property holding the capacity of each edge in the graph.
root node the source vertex from the graph for the path.
Output Argument Type Comment
parent_node nodeProp vertex property holding the parent vertex of the each vertex in the fattest path.
parent_edge nodeProp vertex property holding the edge ID linking the current vertex in the path with the previous vertex in the path.
fat nodeProp vertex property holding the capacity value of the fattest path up to the current vertex. The fatness value for the source vertex will be INF, while it will be 0 for all the vertices that are not reachable from the source.

Code

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

import oracle.pgx.algorithm.EdgeProperty;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxMap;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

import static java.lang.Double.POSITIVE_INFINITY;

@GraphAlgorithm
public class FattestPath {
  public void fattestPath(PgxGraph g, EdgeProperty<Double> capacity, PgxVertex root,
      @Out VertexProperty<PgxVertex> parentNode, @Out VertexProperty<PgxEdge> parentEdge,
      @Out VertexProperty<Double> fat) {
    if (g.getNumVertices() == 0) {
      return;
    }

    // sequentially initialize, otherwise compiler flags this algorithm as parallel in nature
    g.getVertices().forSequential(n -> {
      parentNode.set(n, PgxVertex.NONE);
      parentEdge.set(n, PgxEdge.NONE);
      fat.set(n, (double) 0);
    });

    fat.set(root, POSITIVE_INFINITY);

    // create 'queue'
    PgxMap<PgxVertex, Double> q = PgxMap.create();
    q.set(root, POSITIVE_INFINITY);

    while (q.size() > 0) {
      PgxVertex u = q.getKeyForMaxValue();
      q.remove(u);

      u.getOutEdges().forEach(e -> {
        PgxVertex v = e.destinationVertex();
        double minCap = (fat.get(u) < capacity.get(e)) ? fat.get(u) : capacity.get(e);
        if (fat.get(v) < minCap) {
          fat.set(v, minCap);
          q.set(v, fat.get(v));
          parentNode.set(v, u);
          parentEdge.set(v, e);
        }
      });
    }
  }
}

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure fattest_path(graph G, edgeProp<double> capacity, node root; nodeProp<node> parent_node,
    nodeProp<edge> parent_edge, nodeProperty<double> fat) {

  if (G.numNodes() == 0) {
    return;
  }

  // sequentially initialize, otherwise compiler flags this algorithm as
  // parallel in nature
  for (n: G.nodes) {
    n.parent_node = NIL;
    n.parent_edge = NIL;
    n.fat = 0;
  }
  root.fat = +INF;

  // create 'queue'
  map<node, double> Q;
  Q[root] = +INF;

  while (Q.size() > 0) {
    node u = Q.getMaxKey();
    Q.remove(u);

    for (e : u.outEdges) {
      node v = e.toNode();
      double minCap = (u.fat < e.capacity) ? u.fat : e.capacity;
      if(v.fat < minCap) {
        v.fat = minCap;
        Q[v] = v.fat;
        v.parent_node = u;
        v.parent_edge = e;
      }
    }
  }
}