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.
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 | vertexProp |
vertex property holding the parent vertex of the each vertex in the fattest path. |
parent_edge | vertexProp |
vertex property holding the edge ID linking the current vertex in the path with the previous vertex in the path. |
fat | vertexProp |
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. |
/* * 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; vertexProp<node> parent_node, vertexProp<edge> parent_edge, vertexProp<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; } } } }