Satsuma.Preflow Class Reference

Finds a maximum flow using the Goldberg-Tarjan preflow algorithm. More...

Inheritance diagram for Satsuma.Preflow:

Public Member Functions
double	Flow (Arc arc)
	The amount flowing through an arc. More...
	Preflow (IGraph graph, Func< Arc, double > capacity, Node source, Node target)

Properties
Func< Arc, double >	Capacity [get, set]
double	Error [get, set]
	A (usually very small) approximate upper bound for the difference between FlowSize and the actual maximum flow value. More...
double	FlowSize [get, set]
IGraph	Graph [get, set]
IEnumerable< KeyValuePair< Arc, double > >	NonzeroArcs [get]
Node	Source [get, set]
Node	Target [get, set]

Detailed Description

Finds a maximum flow using the Goldberg-Tarjan preflow algorithm.

Let D denote the sum of capacities for all arcs exiting Source.

• If all capacities are integers, and D < 2⁵³, then the returned flow is exact and optimal.
• Otherwise, small round-off errors may occur and the returned flow is "almost-optimal" (see Error).

  See Also

  IntegerPreflow, NetworkSimplex

Definition at line 61 of file Preflow.cs.

Constructor & Destructor Documentation

Satsuma.Preflow.Preflow	(	IGraph	graph,
		Func< Arc, double >	capacity,
		Node	source,
		Node	target
	)

Definition at line 76 of file Preflow.cs.

Member Function Documentation

double Satsuma.Preflow.Flow

(

Arc

arc

)

The amount flowing through an arc.

Returns

A number between 0 and Capacity(arc) if the arc is NOT an edge, or between -Capacity(arc) and Capacity(arc) if the arc is an edge.

Implements Satsuma.IFlow< TCapacity >.

Definition at line 157 of file Preflow.cs.

Property Documentation

Func<Arc, double> Satsuma.Preflow.Capacity

getset

Definition at line 64 of file Preflow.cs.

double Satsuma.Preflow.Error

getset

A (usually very small) approximate upper bound for the difference between FlowSize and the actual maximum flow value.

Note

Due to floating-point roundoff errors, the maximum flow cannot be calculated exactly.

Definition at line 74 of file Preflow.cs.

double Satsuma.Preflow.FlowSize

getset

Definition at line 68 of file Preflow.cs.

IGraph Satsuma.Preflow.Graph

getset

Definition at line 63 of file Preflow.cs.

IEnumerable<KeyValuePair<Arc, double> > Satsuma.Preflow.NonzeroArcs

get

Definition at line 150 of file Preflow.cs.

Node Satsuma.Preflow.Source

getset

Definition at line 65 of file Preflow.cs.

Node Satsuma.Preflow.Target

getset

Definition at line 66 of file Preflow.cs.

---

The documentation for this class was generated from the following file:

• src/Preflow.cs