Data Structures | Files | Defines | Typedefs | Functions | Variables

EGalgPushRelabel

Data Structures

struct  EGalgAPRedge_t
 Edge Structure needed to run Push-Relabel algorithm on a network. More...
struct  EGalgAPRG_t
 Graph structure needed to run Push-Relabel algorithm (with highest label node selection rule). More...
struct  EGalgAPRN_t
 Node structure neede to run Push-Relabel algorithm on a network. More...
struct  EGalgAPRse_t
 capacitated edge structure with forward/backward information. More...
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...

Files

file  eg_apr.c
file  eg_apr.h
file  eg_push_relabel.c
file  eg_push_relabel.ex.c
file  eg_push_relabel.h

Defines

#define __APR_DEBUGL__   100
 Level of debugging in the code.
#define __APR_PROFILE__   100
 Level of profiling in the code.
#define __APR_TEST_VERBOSE__   100
 Level of debugging in the code.
#define __APR_VERBOSE__   100
 Level of debugging in the code.
#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_APR_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 EGalgAPRminSTcut function call.
#define EG_APR_RELABEL_FREC   1U
 If EG_APR_RELABEL is set to one, then this integer controls how often we perform the global relabeling heuristic (in multiples of number of nodes), the default value is 1.
#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 EGalgAPRedgeClear(edge_pt)
 clear a pointer to an EGalgAPRedge_t structure, and let it ready to be freed if necesary.
#define EGalgAPRedgeInit(edge_pt)
 Initialize a pointer to an EGalgAPRedge_t structure.
#define EGalgAPRedgeReset(edge_pt)
 Reset the given edge pointer (as if it were new).
#define EGalgAPRgraphClear(graph_pt)   EGeDgraphClear(&((graph_pt)->G))
 clear a pointer to an EGalgAPRG_t structure, and let it ready to be freed if necesary.
#define EGalgAPRgraphInit(graph_pt)   EGeDgraphInit(&((graph_pt)->G))
 Initialize a pointer to an EGalgAPRG_t structure.
#define EGalgAPRgraphReset(graph_pt)   EGeDgraphReset(&((graph_pt)->G))
 Reset the given graph pointer (as if it were new).
#define EGalgAPRNInit(node_pt)
 Initialize a pointer to an EGalgAPRN_t structure.
#define EGalgAPRnodeClear(node_pt)
 clear a pointer to an EGalgAPRN_t structure, and let it ready to be freed if necesary.
#define EGalgAPRnodeReset(node_pt)   EGeDgraphNodeReset(&((node_pt)->v))
 Reset the given node pointer (as if it were new).
#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)
#define UPDATE(counter)

Typedefs

typedef struct EGalgAPRedge_t EGalgAPRedge_t
 Edge Structure needed to run Push-Relabel algorithm on a network.
typedef struct EGalgAPRG_t EGalgAPRG_t
 Graph structure needed to run Push-Relabel algorithm (with highest label node selection rule).
typedef struct EGalgAPRse_t EGalgAPRse_t
 capacitated edge structure with forward/backward information.
typedef struct EGalgPRedge_t EGalgPRedge_t
 Edge Structure needed to run Push-Relabel algorithm on a network.
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.
typedef struct EGalgPRse_t EGalgPRse_t
 capacitated edge structure with forward/backward information.

Functions

int EGalgAPRmaxSTflow (EGalgAPRG_t *const G, EGalgAPRN_t *const s, EGalgAPRN_t *const t)
 Compute a maximum $s-t$ flow from the ouput produced by EGalgAPRminCur.
int EGalgAPRminSTcut (EGalgAPRG_t *const G, EGalgAPRN_t *const s, EGalgAPRN_t *const t)
 Compute a minimum $s-t$ cut.
int EGalgAPRoptimalityTest (EGalgAPRG_t *const G, EGalgAPRN_t *const s, EGalgAPRN_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 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
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
static unsigned long long __PR_profile_lvel = 0
static unsigned long long __PR_profile_lvel = 0
static unsigned long long __PR_profile_move = 0
static unsigned long long __PR_profile_move = 0
static unsigned long long __PR_profile_numb = 0
static unsigned long long __PR_profile_numb = 0
static unsigned long long __PR_profile_push = 0
 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.
static unsigned long long __PR_profile_push = 0
 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.
static unsigned long long __PR_profile_rela = 0
static unsigned long long __PR_profile_rela = 0



void EGalgAPRprofile (void)
 If profiling is enable (i.e. __APR_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.



void EGalgPRprofile (void)
 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.

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:
  • 2010-05-07
  • 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.

Define Documentation

#define __APR_DEBUGL__   100

Level of debugging in the code.

Definition at line 39 of file eg_apr.h.

#define __APR_PROFILE__   100

Level of profiling in the code.

Definition at line 51 of file eg_apr.h.

#define __APR_TEST_VERBOSE__   100

Level of debugging in the code.

Definition at line 43 of file eg_apr.h.

#define __APR_VERBOSE__   100

Level of debugging in the code.

Definition at line 47 of file eg_apr.h.

#define __PR_DEBUGL__   100

Level of debugging in the code.

Definition at line 86 of file eg_push_relabel.h.

Referenced by EGalgPRpush(), and EGalgPRpushRelabel().

#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.

Referenced by EGalgPRoptimalityTest().

#define __PR_VERBOSE__   100

Level of debugging in the code.

Definition at line 94 of file eg_push_relabel.h.

Referenced by EGalgPRcomputeLabels(), EGalgPRglobalRelabel(), EGalgPRmaxSTflow(), EGalgPRminSTcut(), EGalgPRnumb(), EGalgPRpreprocess(), EGalgPRpush(), and EGalgPRpushRelabel().

#define EG_APR_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 EGalgAPRminSTcut function call.

Definition at line 67 of file eg_apr.h.

#define EG_APR_RELABEL_FREC   1U

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

Definition at line 73 of file eg_apr.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 114 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 120 of file eg_push_relabel.h.

Referenced by EGalgPRmaxSTflow(), and EGalgPRminSTcut().

#define EGalgAPRedgeClear (   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 EGalgAPRedge_t structure, and let it ready to be freed if necesary.

Definition at line 190 of file eg_apr.h.

#define EGalgAPRedgeInit (   edge_pt  ) 
Value:
({\
  EGalgAPRedge_t*const __EGalgAPR_ie = (edge_pt);\
  EGlpNumInitVar(__EGalgAPR_ie->fw.r);\
  EGlpNumInitVar(__EGalgAPR_ie->fw.u);\
  EGlpNumInitVar(__EGalgAPR_ie->bw.r);\
  EGlpNumInitVar(__EGalgAPR_ie->bw.u);\
  EGeDgraphEdgeInit(&(__EGalgAPR_ie->fw.e));\
  EGeDgraphEdgeInit(&(__EGalgAPR_ie->bw.e));\
  __EGalgAPR_ie->bw.type = 1;\
  __EGalgAPR_ie->fw.type = 0;})

Initialize a pointer to an EGalgAPRedge_t structure.

Definition at line 162 of file eg_apr.h.

#define EGalgAPRedgeReset (   edge_pt  ) 
Value:
({\
  EGalgAPRedge_t*const __EGalgAPR_ie = (edge_pt);\
  EGeDgraphEdgeReset(&(__EGalgAPR_ie->fw.e));\
  EGeDgraphEdgeReset(&(__EGalgAPR_ie->bw.e));\
  __EGalgAPR_ie->bw.type = 1;\
  __EGalgAPR_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 179 of file eg_apr.h.

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

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

Definition at line 223 of file eg_apr.h.

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

Initialize a pointer to an EGalgAPRG_t structure.

Definition at line 210 of file eg_apr.h.

#define EGalgAPRgraphReset (   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 218 of file eg_apr.h.

#define EGalgAPRNInit (   node_pt  ) 
Value:
({\
  EGalgAPRN_t*const __EGalgAPR_in = (node_pt);\
  EGlpNumInitVar(__EGalgAPR_in->e);\
  EGeDgraphNodeInit(&(__EGalgAPR_in->v));})

Initialize a pointer to an EGalgAPRN_t structure.

Definition at line 107 of file eg_apr.h.

#define EGalgAPRnodeClear (   node_pt  ) 
Value:
({\
  EGlpNumClearVar((node_pt)->e);\
  EGeDgraphNodeClear(&((node_pt)->v));})

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

Definition at line 123 of file eg_apr.h.

#define EGalgAPRnodeReset (   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 118 of file eg_apr.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 236 of file eg_push_relabel.h.

Referenced by main().

#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 208 of file eg_push_relabel.h.

Referenced by main().

#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 225 of file eg_push_relabel.h.

Referenced by EGalgMCbuildPRgraph().

#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 269 of file eg_push_relabel.h.

Referenced by main().

#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 256 of file eg_push_relabel.h.

Referenced by main().

#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 264 of file eg_push_relabel.h.

Referenced by EGalgMCbuildPRgraph().

#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 169 of file eg_push_relabel.h.

Referenced by main().

#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 153 of file eg_push_relabel.h.

Referenced by main().

#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 164 of file eg_push_relabel.h.

Referenced by EGalgMCbuildPRgraph().

#define UPDATE (   counter  ) 

Definition at line 53 of file eg_push_relabel.c.

Referenced by EGalgPRmaxSTflow(), EGalgPRminSTcut(), EGalgPRnumb(), EGalgPRpush(), and EGalgPRpushRelabel().

#define UPDATE (   counter  ) 

Definition at line 52 of file eg_apr.c.

Typedef Documentation

typedef struct EGalgAPRedge_t EGalgAPRedge_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 EGalgAPRG_t EGalgAPRG_t

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

typedef struct EGalgAPRse_t EGalgAPRse_t

capacitated edge structure with forward/backward information.

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

int EGalgAPRmaxSTflow ( EGalgAPRG_t *const   G,
EGalgAPRN_t *const   s,
EGalgAPRN_t *const   t 
)

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

Parameters:
s pointer to the EGalgAPRN_t* source node in the network.
t pointer to the EGalgAPRN_t* sink node in the network.
G pointer to the EGalgAPRG_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 EGalgAPRminSTcut. 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 EGalgAPRN_t::d don't correspond any more to the cut as defined in EGalgAPRminSTcut.
int EGalgAPRminSTcut ( EGalgAPRG_t *const   G,
EGalgAPRN_t *const   s,
EGalgAPRN_t *const   t 
)

Compute a minimum $s-t$ cut.

Parameters:
s pointer to the source node.
t pointer to the EGalgAPRN_t* sink node in the network.
G pointer to the EGalgAPRG_t* in wich we will work.
Returns:
zero on success, non-zero otherwise.
Description:
When this funcion finish (successfully) all nodes with field EGalgAPRN_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 EGalgAPRmaxSTflow 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.
int EGalgAPRoptimalityTest ( EGalgAPRG_t *const   G,
EGalgAPRN_t *const   s,
EGalgAPRN_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 EGalgAPRN_t* source node in the network.
t pointer to the EGalgAPRN_t* sink node in the network.
G pointer to the EGalgAPRG_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 EGalgAPRmaxSTflow .
void EGalgAPRprofile ( void   ) 

If profiling is enable (i.e. __APR_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.

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.
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, DIST[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 79 of file eg_push_relabel.c.

References __PR_VERBOSE__, EGalgPRnode_t::d, EGalgPRse_t::e, EGcontainerOf, EGeListAddAfter, EGeListDel, EGeListInit, EGeListIsEmpty, EGalgPRgraph_t::G, EGeDgraphNode_t::in_edge, EGalgPRnode_t::LVL_list, MESSAGE, EGeDgraph_t::n_nodes, EGeList_t::next, EGeDgraph_t::nodes, EGeList_t::prev, EGalgPRse_t::r, EGalgPRnode_t::T_cut, EGeDgraphEdge_t::tail, and EGalgPRnode_t::v.

Referenced by EGalgPRglobalRelabel(), EGalgPRoptimalityTest(), and EGalgPRpreprocess().

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 498 of file eg_push_relabel.c.

References __PR_VERBOSE__, CHECKRVAL, EGalgPRnode_t::d, EGalgPRnode_t::e, EGalgPRcomputeLabels(), EGcontainerOf, EGeListAddAfter, EGeListInit, EGalgPRgraph_t::G, EGalgPRnode_t::LVL_list, MESSAGE, EGeList_t::next, EGeDgraph_t::nodes, and EGalgPRnode_t::T_cut.

Referenced by EGalgPRmaxSTflow(), and EGalgPRminSTcut().

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 you 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 664 of file eg_push_relabel.c.

References __last_global, __PR_profile_lvel, __PR_VERBOSE__, CHECKRVALG, EGalgPRnode_t::d, EG_PR_RELABEL_FREC, EGalgPRglobalRelabel(), EGalgPRpushRelabel(), EGcontainerOf, EGeListIsEmpty, EGfree, EGsMalloc, EGalgPRgraph_t::G, MESSAGE, EGeDgraph_t::n_nodes, and UPDATE.

Referenced by main().

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 562 of file eg_push_relabel.c.

References __last_global, __PR_profile_lvel, __PR_VERBOSE__, CHECKRVALG, EGalgPRnode_t::d, EG_PR_RELABEL_FREC, EGalgPRglobalRelabel(), EGalgPRnumb(), EGalgPRpreprocess(), EGalgPRpushRelabel(), EGcontainerOf, EGeListInit, EGeListIsEmpty, EGfree, EGsMalloc, EGalgPRgraph_t::G, MESSAGE, EGeDgraph_t::n_nodes, and UPDATE.

Referenced by main().

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 442 of file eg_push_relabel.c.

References __PR_profile_numb, __PR_VERBOSE__, EGalgPRnode_t::d, EGcontainerOf, EGeListDel, EGalgPRnode_t::LVL_list, MESSAGE, EGeList_t::next, EGalgPRnode_t::T_cut, and UPDATE.

Referenced by EGalgPRminSTcut().

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 733 of file eg_push_relabel.c.

References __PR_TEST_VERBOSE__, CHECKRVALG, EGalgPRnode_t::d, EGalgPRse_t::e, EGalgPRnode_t::e, EGalgPRcomputeLabels(), EGcontainerOf, EGeListInit, EGfree, EGsMalloc, EGalgPRgraph_t::G, EGeDgraphEdge_t::head, EGeDgraphNode_t::in_edge, EGalgPRnode_t::LVL_list, MESSAGE, EGeDgraph_t::n_nodes, EGeList_t::next, EGeDgraph_t::nodes, EGeDgraphNode_t::out_edge, EGalgPRse_t::r, EGeDgraphEdge_t::tail, EGalgPRse_t::u, and EGalgPRnode_t::v.

Referenced by main().

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.
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, 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 implement the procedure preprocess as defined in page 225 in the "Network Flows" book of Magnanti et. all.

Definition at line 237 of file eg_push_relabel.c.

References __PR_VERBOSE__, CHECKRVAL, EGalgPRnode_t::d, EGalgPRnode_t::e, EGalgPRcomputeLabels(), EGalgPRpush(), EGcontainerOf, EGeListDel, EGalgPRgraph_t::G, EGeDgraphNode_t::in_edge, EGalgPRnode_t::LVL_list, MESSAGE, EGeDgraph_t::n_nodes, EGeList_t::next, EGeDgraph_t::nodes, EGeDgraphNode_t::out_edge, EGalgPRse_t::r, EGalgPRnode_t::T_cut, EGalgPRse_t::u, and EGalgPRnode_t::v.

Referenced by EGalgPRminSTcut().

Here is the call graph for this function:

void EGalgPRprofile ( void   ) 

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.

Referenced by main().

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 182 of file eg_push_relabel.c.

References __PR_DEBUGL__, __PR_profile_push, __PR_VERBOSE__, EGalgPRnode_t::d, EGalgPRnode_t::e, EGalgPRse_t::e, EGcontainerOf, EGeListAddAfter, EXITL, EGeDgraphEdge_t::head, EGalgPRnode_t::LVL_list, MESSAGE, EGeList_t::next, EGalgPRse_t::r, EGeDgraphEdge_t::tail, EGalgPRse_t::type, EGalgPRse_t::u, and UPDATE.

Referenced by EGalgPRpreprocess(), and EGalgPRpushRelabel().

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 315 of file eg_push_relabel.c.

References __last_global, __PR_DEBUGL__, __PR_profile_move, __PR_profile_rela, __PR_VERBOSE__, EGalgPRnode_t::d, EGalgPRse_t::e, EGalgPRnode_t::e, EGalgPRpush(), EGcontainerOf, EGeListAddAfter, EGeListDel, EGeListMoveAfter, EXITL, EGeDgraphEdge_t::head, EGalgPRnode_t::LVL_list, MESSAGE, EGeList_t::next, EGeDgraphNode_t::out_edge, EGalgPRse_t::r, EGalgPRnode_t::T_cut, UPDATE, and EGalgPRnode_t::v.

Referenced by EGalgPRmaxSTflow(), and EGalgPRminSTcut().

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 40 of file eg_push_relabel.ex.c.

References EGalgPRedge_t::bw, CHECKRVALG, EGalgPRse_t::e, EGalgPRedgeClear, EGalgPRedgeInit, EGalgPRgraphClear, EGalgPRgraphInit, EGalgPRmaxSTflow(), EGalgPRminSTcut(), EGalgPRnodeClear, EGalgPRnodeInit, EGalgPRoptimalityTest(), EGalgPRprofile(), EGcontainerOf, EGeDgraphAddEdge, EGeDgraphAddNode, EGfree, EGioClose(), EGioGets(), EGioNParse(), EGioOpen(), EGlib_info(), EGlib_version(), EGlpNumClear(), EGlpNumStart(), EGsetLimits(), EGsigSet, EGsMalloc, EGtimerReset, EGtimerStart, EGtimerStop, EGalgPRedge_t::fw, EGalgPRgraph_t::G, EGeDgraph_t::n_nodes, EGeList_t::next, EGeDgraph_t::nodes, pr_usage(), TESTG, EGtimer_t::time, and EGalgPRnode_t::v.

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 27 of file eg_push_relabel.ex.c.

Referenced by main().

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 59 of file eg_apr.c.

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 60 of file eg_push_relabel.c.

Referenced by EGalgPRmaxSTflow(), EGalgPRminSTcut(), and EGalgPRpushRelabel().

unsigned long long __PR_profile_lvel = 0 [static]

Definition at line 35 of file eg_push_relabel.c.

Referenced by EGalgPRmaxSTflow(), and EGalgPRminSTcut().

unsigned long long __PR_profile_lvel = 0 [static]

Definition at line 34 of file eg_apr.c.

unsigned long long __PR_profile_move = 0 [static]

Definition at line 35 of file eg_apr.c.

unsigned long long __PR_profile_move = 0 [static]

Definition at line 36 of file eg_push_relabel.c.

Referenced by EGalgPRpushRelabel().

unsigned long long __PR_profile_numb = 0 [static]

Definition at line 34 of file eg_push_relabel.c.

Referenced by EGalgPRnumb().

unsigned long long __PR_profile_numb = 0 [static]

Definition at line 33 of file eg_apr.c.

unsigned long long __PR_profile_push = 0 [static]

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 33 of file eg_push_relabel.c.

Referenced by EGalgPRpush().

unsigned long long __PR_profile_push = 0 [static]

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 32 of file eg_apr.c.

unsigned long long __PR_profile_rela = 0 [static]

Definition at line 36 of file eg_apr.c.

unsigned long long __PR_profile_rela = 0 [static]

Definition at line 37 of file eg_push_relabel.c.

Referenced by EGalgPRpushRelabel().

Generated on Thu Mar 29 2012 10:10:32 for EGlib by  doxygen 1.7.1