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 flow from the ouput produced by EGalgAPRminCur. | |
int | EGalgAPRminSTcut (EGalgAPRG_t *const G, EGalgAPRN_t *const s, EGalgAPRN_t *const t) |
Compute a minimum 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 flow / minimum capacity 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 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 | |
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. |
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 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 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.
#define __APR_TEST_VERBOSE__ 100 |
#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.
#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.
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 | ) |
({\ 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.
#define EGalgAPRedgeInit | ( | edge_pt | ) |
({\ 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.
#define EGalgAPRedgeReset | ( | edge_pt | ) |
({\ 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).
edge_pt | pointer to the node to reset. |
This function set the edge as an empty edge not linked with any graph.
#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)) |
#define EGalgAPRNInit | ( | node_pt | ) |
({\ EGalgAPRN_t*const __EGalgAPR_in = (node_pt);\ EGlpNumInitVar(__EGalgAPR_in->e);\ EGeDgraphNodeInit(&(__EGalgAPR_in->v));})
Initialize a pointer to an EGalgAPRN_t structure.
#define EGalgAPRnodeClear | ( | node_pt | ) |
({\ 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.
#define EGalgAPRnodeReset | ( | node_pt | ) | EGeDgraphNodeReset(&((node_pt)->v)) |
#define EGalgPRedgeClear | ( | edge_pt | ) |
({\ 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.
Definition at line 236 of file eg_push_relabel.h.
Referenced by main().
#define EGalgPRedgeInit | ( | edge_pt | ) |
({\ 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.
Definition at line 208 of file eg_push_relabel.h.
Referenced by main().
#define EGalgPRedgeReset | ( | edge_pt | ) |
({\ 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).
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.
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.
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).
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 | ) |
({\ 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.
Definition at line 169 of file eg_push_relabel.h.
Referenced by main().
#define EGalgPRnodeInit | ( | node_pt | ) |
({\ EGalgPRnode_t*const __EGalgPR_in = (node_pt);\ EGlpNumInitVar(__EGalgPR_in->e);\ EGeDgraphNodeInit(&(__EGalgPR_in->v));})
Initialize a pointer to an EGalgPRnode_t structure.
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).
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().
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.
int EGalgAPRmaxSTflow | ( | EGalgAPRG_t *const | G, | |
EGalgAPRN_t *const | s, | |||
EGalgAPRN_t *const | t | |||
) |
Compute a maximum flow from the ouput produced by EGalgAPRminCur.
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. |
int EGalgAPRminSTcut | ( | EGalgAPRG_t *const | G, | |
EGalgAPRN_t *const | s, | |||
EGalgAPRN_t *const | t | |||
) |
Compute a minimum cut.
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. |
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 flow / minimum capacity cut.
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. |
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.
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. |
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. |
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.
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. |
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().
int EGalgPRmaxSTflow | ( | EGalgPRgraph_t *const | G, | |
EGalgPRnode_t *const | s, | |||
EGalgPRnode_t *const | t | |||
) |
Compute a maximum flow from the ouput produced by EGalgPRminCur.
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. |
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().
int EGalgPRminSTcut | ( | EGalgPRgraph_t *const | G, | |
EGalgPRnode_t *const | s, | |||
EGalgPRnode_t *const | t | |||
) |
Compute a minimum cut.
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. |
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().
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).
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. |
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 flow / minimum capacity cut.
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. |
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().
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.
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. |
preprocess
as defined in page 225 in the "Network Flows" book of Magnanti et. all.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. |
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().
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.
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.
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. |
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.
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. |
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().
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.
static void pr_usage | ( | char ** | argv | ) | [inline, static] |
display usage of this program
Definition at line 27 of file eg_push_relabel.ex.c.
Referenced by main().
unsigned long long __last_global = 0 [static] |
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] |
unsigned long long __PR_profile_move = 0 [static] |
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] |
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.
unsigned long long __PR_profile_rela = 0 [static] |
unsigned long long __PR_profile_rela = 0 [static] |
Definition at line 37 of file eg_push_relabel.c.
Referenced by EGalgPRpushRelabel().