EGalgPushRelabel

Detailed Description

Here we implement the push-relabel algorithm as defined in the book "Network Flows" by Magnanti et. all, in chapter 6,7 and 8. Using the variant "Highest-label preflow-push algorithm" (described on page 230) wich choose the active node from wich to push from as the one with highest distance label. This variant has running time $\mathcal{O}(n^2\sqrt{m})$ where n is the number of nodes in the graph, and m the number of edges in it. Note that the call to EGalgPRminSTcut produces a maximum pre_flow, to obtain a flow you should call the EGalgPRmaxSTflow that takes the graph produced by EGalgPRminSTcut and convert the preflow into a real flow. We also choose to use to register the number of nodes with distance labels $k,\quad\forall k=1,\ldots,n$ where n is the number of nodes in the network. This is done because whenever the number of nodes with distance labels k is zero, then all nodes with distance labels above k can be set to n (and thus be added to the partially computed cut-set). This is an (inportant) empirical speed-up, but does not affect the worst case complexity analysis.

Version:: 1.0.0

History:

2005-06-01
- Add globla relabeling heuristic.
2005-05-30
- Final test results on the TSP x-files, all should be right now.
2005-05-26
- First Implementation.

Note:

This algorithm is implemented the embedded structures approach. I will give further details on what this implies.

It is important to note that this algorithm (as implemented here) WILL FAIL if an edge has infinite capacities. To handle that case either we must re-program it, or you can put capacities suficiently large on them (for example 2 times the sum of all bounded capacities) for this algorithm to work.

This implementation does use global relabeling, namelly, the strategy when once in a while (for example every n or m relabeling operations) we recompute the exact distance labels. The use of this heuristic (together with the gap heuristic) have been reported to be the most successfull in practice (see "On Implementing Push-Relabel Method For The Maximum FLow Problem" from Boris V. Cherkassy and Andrew V. Goldberg.) and also in the test that we have performed on the fractional solutions of TSP's instances from the TSPLIB set of problems using CONCORDE.

Files

file eg_push_relabel.c

file eg_push_relabel.ex.c

file eg_push_relabel.h

Data Structures

struct EGalgPRedge_t

Edge Structure needed to run Push-Relabel algorithm on a network. More...

struct EGalgPRgraph_t

Graph structure needed to run Push-Relabel algorithm (with highest label node selection rule). More...

struct EGalgPRnode_t

Node structure neede to run Push-Relabel algorithm on a network. More...

struct EGalgPRse_t

capacitated edge structure with forward/backward information. More...

#define EGalgPRprofile

If profiling is enable (i.e. __PR_PROFILE__ <= DEBUG), print some profiling information of the min s-t cut used up to now, and reset all internal counters to zero, if profiling is not enabled, nothing happen.

Defines

#define __PR_DEBUGL__   100

Level of debugging in the code.

#define __PR_PROFILE__   100

Level of profiling in the code.

#define __PR_TEST_VERBOSE__   100

Level of debugging in the code.

#define __PR_VERBOSE__   100

Level of debugging in the code.

#define EG_PR_RELABEL   1

If set to non-zero, use the global relabeling heuristic (to be called every n number of relabel operations performed. if set to zero, it won't use this heuristic. Note thought that it has been shown that this is a very efficient heuristic to reduce the total running time, specially in the EGalgPRminSTcut function call.

#define EG_PR_RELABEL_FREC   1U

If EG_PR_RELABEL is set to one, then this initeger controls how often we perform the global relabeling heuristic (in multiples of number of nodes), the default value is 1.

#define EGalgPRedgeClear(edge_pt)

clear a pointer to an EGalgPRedge_t structure, and let it ready to be freed if necesary.

#define EGalgPRedgeInit(edge_pt)

Initialize a pointer to an EGalgPRedge_t structure.

#define EGalgPRedgeReset(edge_pt)

Reset the given edge pointer (as if it were new).

#define EGalgPRgraphClear(graph_pt)   EGeDgraphClear(&((graph_pt)->G))

clear a pointer to an EGalgPRgraph_t structure, and let it ready to be freed if necesary.

#define EGalgPRgraphInit(graph_pt)   EGeDgraphInit(&((graph_pt)->G))

Initialize a pointer to an EGalgPRgraph_t structure.

#define EGalgPRgraphReset(graph_pt)   EGeDgraphReset(&((graph_pt)->G))

Reset the given graph pointer (as if it were new).

#define EGalgPRnodeClear(node_pt)

clear a pointer to an EGalgPRnode_t structure, and let it ready to be freed if necesary.

#define EGalgPRnodeInit(node_pt)

Initialize a pointer to an EGalgPRnode_t structure.

#define EGalgPRnodeReset(node_pt)   EGeDgraphNodeReset(&((node_pt)->v))

Reset the given node pointer (as if it were new).

#define UPDATE(counter)

If using profiling, we count the number of push, relabels, nodes moved to S because we have a hole in the numb array, the number of levels that we we looked at, and the number of nodes that we move to the S cut because their label become bigger than number of nodes.

Typedefs

typedef EGalgPRedge_t EGalgPRedge_t

Edge Structure needed to run Push-Relabel algorithm on a network.

typedef EGalgPRgraph_t EGalgPRgraph_t

Graph structure needed to run Push-Relabel algorithm (with highest label node selection rule).

typedef EGalgPRnode_t EGalgPRnode_t

Node structure neede to run Push-Relabel algorithm on a network.

typedef EGalgPRse_t EGalgPRse_t

capacitated edge structure with forward/backward information.

Functions

static int EGalgPRcomputeLabels (EGalgPRgraph_t *const G, EGalgPRnode_t *const t, unsigned int *const numb, EGeList_t *DIST)

Compute the exact label distance in the graph to the given node.

static int EGalgPRglobalRelabel (EGalgPRgraph_t *const G, EGalgPRnode_t *const s, EGalgPRnode_t *const t, unsigned int const n_nodes, unsigned int *const numb, EGeList_t *const LEVEL, EGeList_t *const DIST)

Re-compute the global distance labels.

int EGalgPRmaxSTflow (EGalgPRgraph_t *const G, EGalgPRnode_t *const s, EGalgPRnode_t *const t)

Compute a maximum $s-t$ flow from the ouput produced by EGalgPRminCur.

int EGalgPRminSTcut (EGalgPRgraph_t *const G, EGalgPRnode_t *const s, EGalgPRnode_t *const t)

Compute a minimum $s-t$ cut.

static int EGalgPRnumb (const unsigned int hole, const unsigned int max_numb, const unsigned int n_nodes, unsigned int *const numb, EGeList_t *const DIST)

Once we have found a 'hole' in the numb arrray, all nodes with distance labels above the given value, can be set to the number of nodes in the network (and thus be assumed to be in the S cut).

int EGalgPRoptimalityTest (EGalgPRgraph_t *const G, EGalgPRnode_t *const s, EGalgPRnode_t *const t, EGlpNum_t *error)

Check if the given input graph (with it's residual capacities) represent an optimal solution to the maximum $ s-t $ flow / minimum capacity $ s-t $ cut.

static int EGalgPRpreprocess (EGalgPRgraph_t *const G, EGalgPRnode_t *const s, EGalgPRnode_t *const t, unsigned int *const numb, EGeList_t *const LEVEL, EGeList_t *const DIST)

Initialize flow to zero, and saturate forward edges in the source.

static int EGalgPRpush (EGalgPRse_t *const edge_pt, EGlpNum_t flow, EGeList_t *const LEVEL, const unsigned int n_nodes)

Perform a push operation in an edge.

static int EGalgPRpushRelabel (EGalgPRnode_t *const node_pt, unsigned int *const numb, const unsigned int n_nodes, EGeList_t *const LEVEL, EGeList_t *const DIST)

Push/Relabel the given node.

int main (int argc, char **argv)

example of usage of the Preflow-Push algorithm as implemented in (EGalgPushRelabel).

static void pr_usage (char **argv)

display usage of this program

Variables

static unsigned long long __last_global = 0

counter to keep track of the relabel operations performed, this is needed to implement the global relabeling heuristic

Define Documentation

#define __PR_DEBUGL__ 100

Level of debugging in the code.

Definition at line 86 of file eg_push_relabel.h.

#define __PR_PROFILE__ 100

Level of profiling in the code.

Definition at line 98 of file eg_push_relabel.h.

#define __PR_TEST_VERBOSE__ 100

Level of debugging in the code.

Definition at line 90 of file eg_push_relabel.h.

#define __PR_VERBOSE__ 100

Level of debugging in the code.

Definition at line 94 of file eg_push_relabel.h.

#define EG_PR_RELABEL 1

If set to non-zero, use the global relabeling heuristic (to be called every n number of relabel operations performed. if set to zero, it won't use this heuristic. Note thought that it has been shown that this is a very efficient heuristic to reduce the total running time, specially in the EGalgPRminSTcut function call.

Definition at line 129 of file eg_push_relabel.h.

#define EG_PR_RELABEL_FREC 1U

If EG_PR_RELABEL is set to one, then this initeger controls how often we perform the global relabeling heuristic (in multiples of number of nodes), the default value is 1.

Definition at line 135 of file eg_push_relabel.h.

#define EGalgPRedgeClear ( edge_pt )

Value:
({\ EGlpNumClearVar((edge_pt)->fw.r);\ EGlpNumClearVar((edge_pt)->fw.u);\ EGlpNumClearVar((edge_pt)->bw.r);\ EGlpNumClearVar((edge_pt)->bw.u);\ EGeDgraphEdgeClear(&((edge_pt)->fw.e));\ EGeDgraphEdgeClear(&((edge_pt)->bw.e));})
clear a pointer to an EGalgPRedge_t structure, and let it ready to be freed if necesary.

Examples:
eg_push_relabel.ex.c.

Definition at line 251 of file eg_push_relabel.h.

#define EGalgPRedgeInit ( edge_pt )

Value:
({\ EGalgPRedge_t*const __EGalgPR_ie = (edge_pt);\ EGlpNumInitVar(__EGalgPR_ie->fw.r);\ EGlpNumInitVar(__EGalgPR_ie->fw.u);\ EGlpNumInitVar(__EGalgPR_ie->bw.r);\ EGlpNumInitVar(__EGalgPR_ie->bw.u);\ EGeDgraphEdgeInit(&(__EGalgPR_ie->fw.e));\ EGeDgraphEdgeInit(&(__EGalgPR_ie->bw.e));\ __EGalgPR_ie->bw.type = 1;\ __EGalgPR_ie->fw.type = 0;})
Initialize a pointer to an EGalgPRedge_t structure.

Examples:
eg_push_relabel.ex.c.

Definition at line 223 of file eg_push_relabel.h.

#define EGalgPRedgeReset ( edge_pt )

Value:
({\ EGalgPRedge_t*const __EGalgPR_ie = (edge_pt);\ EGeDgraphEdgeReset(&(__EGalgPR_ie->fw.e));\ EGeDgraphEdgeReset(&(__EGalgPR_ie->bw.e));\ __EGalgPR_ie->bw.type = 1;\ __EGalgPR_ie->fw.type = 0;})
Reset the given edge pointer (as if it were new).

Parameters:

edge_pt pointer to the node to reset.

This function set the edge as an empty edge not linked with any graph.
Definition at line 240 of file eg_push_relabel.h.

#define EGalgPRgraphClear ( graph_pt ) EGeDgraphClear(&((graph_pt)->G))

clear a pointer to an EGalgPRgraph_t structure, and let it ready to be freed if necesary.

Examples:
eg_push_relabel.ex.c.

Definition at line 284 of file eg_push_relabel.h.

#define EGalgPRgraphInit ( graph_pt ) EGeDgraphInit(&((graph_pt)->G))

Initialize a pointer to an EGalgPRgraph_t structure.

Examples:
eg_push_relabel.ex.c.

Definition at line 271 of file eg_push_relabel.h.

#define EGalgPRgraphReset ( graph_pt ) EGeDgraphReset(&((graph_pt)->G))

Reset the given graph pointer (as if it were new).

Parameters:

graph_pt pointer to the node to reset.

This function set the graph as an empty graph.
Definition at line 279 of file eg_push_relabel.h.

#define EGalgPRnodeClear ( node_pt )

Value:
({\ EGlpNumClearVar((node_pt)->e);\ EGeDgraphNodeClear(&((node_pt)->v));})
clear a pointer to an EGalgPRnode_t structure, and let it ready to be freed if necesary.

Examples:
eg_push_relabel.ex.c.

Definition at line 184 of file eg_push_relabel.h.

#define EGalgPRnodeInit ( node_pt )

Value:
({\ EGalgPRnode_t*const __EGalgPR_in = (node_pt);\ EGlpNumInitVar(__EGalgPR_in->e);\ EGeDgraphNodeInit(&(__EGalgPR_in->v));})
Initialize a pointer to an EGalgPRnode_t structure.

Examples:
eg_push_relabel.ex.c.

Definition at line 168 of file eg_push_relabel.h.

#define EGalgPRnodeReset ( node_pt ) EGeDgraphNodeReset(&((node_pt)->v))

Reset the given node pointer (as if it were new).

Parameters:

node_pt pointer to the node to reset.

This function set the node as an empty node not linked with any graph.
Definition at line 179 of file eg_push_relabel.h.

#define EGalgPRprofile

If profiling is enable (i.e. __PR_PROFILE__ <= DEBUG), print some profiling information of the min s-t cut used up to now, and reset all internal counters to zero, if profiling is not enabled, nothing happen.

Examples:
eg_min_cut.ex.c, and eg_push_relabel.ex.c.

Definition at line 120 of file eg_push_relabel.h.

#define UPDATE ( counter )

If using profiling, we count the number of push, relabels, nodes moved to S because we have a hole in the numb array, the number of levels that we we looked at, and the number of nodes that we move to the S cut because their label become bigger than number of nodes.

Definition at line 41 of file eg_push_relabel.c.

Typedef Documentation

typedef struct EGalgPRedge_t EGalgPRedge_t

Edge Structure needed to run Push-Relabel algorithm on a network.

Note:
Notice that the this edge actually has actually two capacited edge substructures, one for forward edges and one for backward edge, it is assumed that fw.type == 0 and bw.type == 1. This is needed because the algorithm asumes that both edges exists (althought one may have zero capacity). Moreover, while computing the residual capacities we need to access both edges e_ij and e_ji at the same time, thus our choice to represent both edges in just one structure. We also assume that the lower bound on the flow of all edges is zero. Note that we don't need to keep explicitly the flow on the edges, because given the residual capacity and the capacity on the edge we have that $x_{ij} - x_{ji} = u_{ij} - r_{ij}$ and thus we can set $x_{ij} = (u_{ij}-r_{ij})_+$ and $x_{ji} = (r_{ij}-u_{ij})_+$ . if we have computed the maximal flow.

typedef struct EGalgPRgraph_t EGalgPRgraph_t

Graph structure needed to run Push-Relabel algorithm (with highest label node selection rule).

typedef struct EGalgPRnode_t EGalgPRnode_t

Node structure neede to run Push-Relabel algorithm on a network.

Note:
Notice that the directed graph part is embeded in this structure as well. Note that we could define internally space for LVL_list, but for the sake of speed we include them in the node structure.

typedef struct EGalgPRse_t EGalgPRse_t

capacitated edge structure with forward/backward information.

Function Documentation

static int EGalgPRcomputeLabels ( EGalgPRgraph_t *const G,

EGalgPRnode_t *const t,

unsigned int *const numb,

EGeList_t * DIST

) [inline, static]

Compute the exact label distance in the graph to the given node.

Parameters:

t pointer to the EGalgPRnode_t node to wich we are computing the exact label distances.

G pointer to the EGalgPRgraph_t graph where we are working.

DIST array of EGeList_t lists, LEVEL[i] is a list of all nodes with distance label i.

numb array of integers where numb[k] contain the number of nodes with distance labels equal to k. This array should be of size at least n_nodes.

Returns:
zero on success, non-zero otherwise.

Description:
We use a BFS implementation to solve this problem. We assume that the field EGalgPRnode_t::LVL_list is set to {0,0}. We also assume that the field EGalgPRnode_t::d is set to a suficiently large value that denotes that they are disconnected from t, this value should be at least the number of nodes in the graph that we are working on.

Definition at line 67 of file eg_push_relabel.c.

static int EGalgPRglobalRelabel ( EGalgPRgraph_t *const G,

EGalgPRnode_t *const s,

EGalgPRnode_t *const t,

unsigned int const n_nodes,

unsigned int *const numb,

EGeList_t *const LEVEL,

EGeList_t *const DIST

) [inline, static]

Re-compute the global distance labels.

Parameters:

s pointer to the EGalgPRnode_t* source node in the network.

t pointer to the EGalgPRnode_t* sink node in the network.

G pointer to the EGalgPRgraph_t* in wich we will work.

numb array of integers where numb[k] contain the number of nodes with distance labels equal to k. This array should be of size at least n_nodes.

n_nodes number of nodes in the graph.

DIST array of EGeList_t lists, DIST[i] is a list of all nodes with distance label i.

LEVEL array of EGeList_t lists, LEVEL[i] is a list of all ACTIVE nodes with distance label i.

Returns:
zero on success, non-zero otherwise.

Description:
This function will recompute the values stored in numb, in LEVEL and all distance labels exactly, without changing the current pre-flow in the network.

Definition at line 486 of file eg_push_relabel.c.
Here is the call graph for this function:

int EGalgPRmaxSTflow ( EGalgPRgraph_t *const G,

EGalgPRnode_t *const s,

EGalgPRnode_t *const t

)

Compute a maximum $s-t$ flow from the ouput produced by EGalgPRminCur.

Parameters:

s pointer to the EGalgPRnode_t* source node in the network.

t pointer to the EGalgPRnode_t* sink node in the network.

G pointer to the EGalgPRgraph_t* in wich we will work.

Returns:
zero on success, non-zero otherwise.

Description:
We assume that our input graph is the (unaltered) result of a call to EGalgPRminSTcut. Also, note that while computing the actual max s-t flow, we don't need to look for gap in the array of distances. Also note that once yoou call this function, the information in EGalgPRnode_t::d don't correspond any more to the cut as defined in EGalgPRminSTcut.

Examples:
eg_push_relabel.ex.c.

Definition at line 652 of file eg_push_relabel.c.
Here is the call graph for this function:

int EGalgPRminSTcut ( EGalgPRgraph_t *const G,

EGalgPRnode_t *const s,

EGalgPRnode_t *const t

)

Compute a minimum $s-t$ cut.

Parameters:

s pointer to the source node.

t pointer to the EGalgPRnode_t* sink node in the network.

G pointer to the EGalgPRgraph_t* in wich we will work.

Returns:
zero on success, non-zero otherwise.

Description:
When this funcion finish (successfully) all nodes with field EGalgPRnode_t::d bigger than or equal to n (the number of nodes in the graph) bellong to the s cut, while nodes with value strictly less than n will bellong to the t cut. The residual capacities imply a maximum pre-flow in the network, to get an acutal maximum flow you should run EGalgPRmaxSTflow function with imput the output graph of this function (for an example look at the file eg_push_relabel.ex.c ).

Note:
This implementation uses the gap and global relabeling heuristics to speed-up the computations.

Examples:
eg_push_relabel.ex.c.

Definition at line 550 of file eg_push_relabel.c.
Here is the call graph for this function:

static int EGalgPRnumb ( const unsigned int hole,

const unsigned int max_numb,

const unsigned int n_nodes,

unsigned int *const numb,

EGeList_t *const DIST

) [inline, static]

Once we have found a 'hole' in the numb arrray, all nodes with distance labels above the given value, can be set to the number of nodes in the network (and thus be assumed to be in the S cut).

Parameters:

hole first zero value in the numb array.

max_numb highest non-zero index value in the array numb

n_nodes number of total nodes in the working graph.

DIST pointer at the array of lists containing all nodes within each distance level.

numb array of integers where numb[k] contain the number of nodes with distance labels equal to k. This array should be of size at least n_nodes.

Returns:
zero on success, non-zero otherwise.

Definition at line 430 of file eg_push_relabel.c.

int EGalgPRoptimalityTest ( EGalgPRgraph_t *const G,

EGalgPRnode_t *const s,

EGalgPRnode_t *const t,

EGlpNum_t * error

)

Check if the given input graph (with it's residual capacities) represent an optimal solution to the maximum $ s-t $ flow / minimum capacity $ s-t $ cut.

Parameters:

s pointer to the EGalgPRnode_t* source node in the network.

t pointer to the EGalgPRnode_t* sink node in the network.

G pointer to the EGalgPRgraph_t* in wich we will work.

error worst error while checking for optimality conditions.

Returns:
zero if all discrepancies are under the epsLpNum threshold, otherwise, return the number of conditions that don't hold within that threshold, and report in error the worst error found in any condition.

Note:
The input for this function should be the graph as returned by EGalgPRmaxSTflow .

Examples:
eg_push_relabel.ex.c.

Definition at line 721 of file eg_push_relabel.c.
Here is the call graph for this function:

static int EGalgPRpreprocess ( EGalgPRgraph_t *const G,

EGalgPRnode_t *const s,

EGalgPRnode_t *const t,

unsigned int *const numb,

EGeList_t *const LEVEL,

EGeList_t *const DIST

) [inline, static]

Initialize flow to zero, and saturate forward edges in the source.

Parameters:

s pointer to the EGalgPRnode_t node source for the flow.

t pointer to the EGalgPRnode_t node sink for the flow

G pointer to the EGalgPRgraph_t graph where we are working.

numb array of integers where numb[k] contain the number of nodes with distance labels equal to k. This array should be of size at least n_nodes.

DIST array of EGeList_t lists, LEVEL[i] is a list of all nodes with distance label i.

LEVEL array of EGeList_t lists, LEVEL[i] is a list of all ACTIVE nodes with distance label i.

Returns:
zero on success, non-zero otherwise.

Description:
This function implement the procedure preprocess as defined in page 225 in the "Network Flows" book of Magnanti et. all.

Definition at line 225 of file eg_push_relabel.c.
Here is the call graph for this function:

static int EGalgPRpush ( EGalgPRse_t *const edge_pt,

EGlpNum_t flow,

EGeList_t *const LEVEL,

const unsigned int n_nodes

) [inline, static]

Perform a push operation in an edge.

Parameters:

edge_pt pointer to EGalgPRse_t edge where we will perform the push.

flow amount of (extra) flow to send in this edge.

LEVEL array of EGeList_t lists, LEVEL[i] is a list of all ACTIVE nodes with distance label i.

n_nodes number of nodes in the graph.

Returns:
zero on success, non-zero otherwise.

Description:
This function will perform a push operation on an edge, update the exess of its endpoints, and update the residual capacities in this edge and it's reverse edge. Furthermore, if debugging is enabled, this function will test that the push is feasible (i.e. the residual capacity (before the push) is larger than or equal the amount of pushed flow.

Definition at line 170 of file eg_push_relabel.c.

static int EGalgPRpushRelabel ( EGalgPRnode_t *const node_pt,

unsigned int *const numb,

const unsigned int n_nodes,

EGeList_t *const LEVEL,

EGeList_t *const DIST

) [static]

Push/Relabel the given node.

Parameters:

node_pt pointer to the EGalgPRnode_t node structure that we will relabel.

numb array of integers where numb[k] contain the number of nodes with distance labels equal to k. This array should be of size at least n_nodes.

n_nodes number of nodes in the graph.

DIST array of EGeList_t lists, LEVEL[i] is a list of all nodes with distance label i.

LEVEL array of EGeList_t lists, LEVEL[i] is a list of all ACTIVE nodes with distance label i.

Returns:
zero on success, non-zero otherwise.

Description:
This function implement the procedure push_relabel as defined in page 225 in the "Network Flows" book of Magnanti et. all.

Definition at line 303 of file eg_push_relabel.c.
Here is the call graph for this function:

int main ( int argc,

char ** argv

)

example of usage of the Preflow-Push algorithm as implemented in (EGalgPushRelabel).
We read a file from the input whose two first numbers are the number of nodes and edges (we assume that the graph is undirected ), and then a 3-tupla with head tail capacity. we use the last field (capacity) as the capacity of the algorithm, and compute the shortest path from node 0 to node 1.
Definition at line 42 of file eg_push_relabel.ex.c.
Here is the call graph for this function:

static void pr_usage ( char ** argv ) [inline, static]

display usage of this program

Examples:
eg_push_relabel.ex.c.

Definition at line 29 of file eg_push_relabel.ex.c.

Variable Documentation

unsigned long long __last_global = 0 [static]

counter to keep track of the relabel operations performed, this is needed to implement the global relabeling heuristic

Definition at line 48 of file eg_push_relabel.c.

Generated on Mon Jan 30 08:55:45 2006 for EGlib by

1.4.5


Files
file	eg_push_relabel.c
file	eg_push_relabel.ex.c
file	eg_push_relabel.h
Data Structures
struct	EGalgPRedge_t
	Edge Structure needed to run Push-Relabel algorithm on a network. More...
struct	EGalgPRgraph_t
	Graph structure needed to run Push-Relabel algorithm (with highest label node selection rule). More...
struct	EGalgPRnode_t
	Node structure neede to run Push-Relabel algorithm on a network. More...
struct	EGalgPRse_t
	capacitated edge structure with forward/backward information. More...
#define	EGalgPRprofile
	If profiling is enable (i.e. __PR_PROFILE__ <= DEBUG), print some profiling information of the min s-t cut used up to now, and reset all internal counters to zero, if profiling is not enabled, nothing happen.
Defines
#define	__PR_DEBUGL__ 100
	Level of debugging in the code.
#define	__PR_PROFILE__ 100
	Level of profiling in the code.
#define	__PR_TEST_VERBOSE__ 100
	Level of debugging in the code.
#define	__PR_VERBOSE__ 100
	Level of debugging in the code.
#define	EG_PR_RELABEL 1
	If set to non-zero, use the global relabeling heuristic (to be called every n number of relabel operations performed. if set to zero, it won't use this heuristic. Note thought that it has been shown that this is a very efficient heuristic to reduce the total running time, specially in the EGalgPRminSTcut function call.
#define	EG_PR_RELABEL_FREC 1U
	If EG_PR_RELABEL is set to one, then this initeger controls how often we perform the global relabeling heuristic (in multiples of number of nodes), the default value is 1.
#define	EGalgPRedgeClear(edge_pt)
	clear a pointer to an EGalgPRedge_t structure, and let it ready to be freed if necesary.
#define	EGalgPRedgeInit(edge_pt)
	Initialize a pointer to an EGalgPRedge_t structure.
#define	EGalgPRedgeReset(edge_pt)
	Reset the given edge pointer (as if it were new).
#define	EGalgPRgraphClear(graph_pt) EGeDgraphClear(&((graph_pt)->G))
	clear a pointer to an EGalgPRgraph_t structure, and let it ready to be freed if necesary.
#define	EGalgPRgraphInit(graph_pt) EGeDgraphInit(&((graph_pt)->G))
	Initialize a pointer to an EGalgPRgraph_t structure.
#define	EGalgPRgraphReset(graph_pt) EGeDgraphReset(&((graph_pt)->G))
	Reset the given graph pointer (as if it were new).
#define	EGalgPRnodeClear(node_pt)
	clear a pointer to an EGalgPRnode_t structure, and let it ready to be freed if necesary.
#define	EGalgPRnodeInit(node_pt)
	Initialize a pointer to an EGalgPRnode_t structure.
#define	EGalgPRnodeReset(node_pt) EGeDgraphNodeReset(&((node_pt)->v))
	Reset the given node pointer (as if it were new).
#define	UPDATE(counter)
	If using profiling, we count the number of push, relabels, nodes moved to S because we have a hole in the numb array, the number of levels that we we looked at, and the number of nodes that we move to the S cut because their label become bigger than number of nodes.
Typedefs
typedef EGalgPRedge_t	EGalgPRedge_t
	Edge Structure needed to run Push-Relabel algorithm on a network.
typedef EGalgPRgraph_t	EGalgPRgraph_t
	Graph structure needed to run Push-Relabel algorithm (with highest label node selection rule).
typedef EGalgPRnode_t	EGalgPRnode_t
	Node structure neede to run Push-Relabel algorithm on a network.
typedef EGalgPRse_t	EGalgPRse_t
	capacitated edge structure with forward/backward information.
Functions
static int	EGalgPRcomputeLabels (EGalgPRgraph_t const G, EGalgPRnode_t const t, unsigned int const numb, EGeList_t DIST)
	Compute the exact label distance in the graph to the given node.
static int	EGalgPRglobalRelabel (EGalgPRgraph_t const G, EGalgPRnode_t const s, EGalgPRnode_t const t, unsigned int const n_nodes, unsigned int const numb, EGeList_t const LEVEL, EGeList_t const DIST)
	Re-compute the global distance labels.
int	EGalgPRmaxSTflow (EGalgPRgraph_t const G, EGalgPRnode_t const s, EGalgPRnode_t *const t)
	Compute a maximum flow from the ouput produced by EGalgPRminCur.
int	EGalgPRminSTcut (EGalgPRgraph_t const G, EGalgPRnode_t const s, EGalgPRnode_t *const t)
	Compute a minimum cut.
static int	EGalgPRnumb (const unsigned int hole, const unsigned int max_numb, const unsigned int n_nodes, unsigned int const numb, EGeList_t const DIST)
	Once we have found a 'hole' in the numb arrray, all nodes with distance labels above the given value, can be set to the number of nodes in the network (and thus be assumed to be in the S cut).
int	EGalgPRoptimalityTest (EGalgPRgraph_t const G, EGalgPRnode_t const s, EGalgPRnode_t const t, EGlpNum_t error)
	Check if the given input graph (with it's residual capacities) represent an optimal solution to the maximum flow / minimum capacity cut.
static int	EGalgPRpreprocess (EGalgPRgraph_t const G, EGalgPRnode_t const s, EGalgPRnode_t const t, unsigned int const numb, EGeList_t const LEVEL, EGeList_t const DIST)
	Initialize flow to zero, and saturate forward edges in the source.
static int	EGalgPRpush (EGalgPRse_t const edge_pt, EGlpNum_t flow, EGeList_t const LEVEL, const unsigned int n_nodes)
	Perform a push operation in an edge.
static int	EGalgPRpushRelabel (EGalgPRnode_t const node_pt, unsigned int const numb, const unsigned int n_nodes, EGeList_t const LEVEL, EGeList_t const DIST)
	Push/Relabel the given node.
int	main (int argc, char **argv)
	example of usage of the Preflow-Push algorithm as implemented in (EGalgPushRelabel).
static void	pr_usage (char **argv)
	display usage of this program
Variables
static unsigned long long	__last_global = 0
	counter to keep track of the relabel operations performed, this is needed to implement the global relabeling heuristic