Distributed Implementation for ppr

GoldBerg and Tarjan's Distributed suggestion. Synchronous pre-flow push relabel.

Pulse

• All active vertices push their vertices until :

  • excess ducks to 0
  • one successful relabel operation

• At the end of the pulse, synchronize all the labels.

Excess :

• Function that represents the total incoming flow into a vertex.
• if there is excess on a vertex, it is active.
• all excesses other than source and sink must be pushed to 0 at the end of the algorithm.
• At the end of the algorithm, the excess at the sink is the max-flow
• excess at source is theoretically infinite.

Relabel :

• Function that represents the shortest arc distance from vertex v to sink t.
• Usually called the most number of times. Heuristics applied to lessen the number of calls to relabel.
• Prevents the preflow to flow into the wrong vertices.
• The labels, when updated at the end of a pulse, ensures that even in a distributed setup, pre-flow does not flow to a vertex it shouldn't.
• If labels change and that change is not reflected to another node, pre-flow might be pushed to a vertex that is labeled higher.
• Therefore, it is best to end the pulse at one relabel operation.

Implementation :

• Not using StarPlat constructs for the time being.

Distributed_Network.hpp :

• Class for maintaining a network that can be maintained in a distributed way.
• has functions for discharging across pulses and discharging within one pulse.