00001 /* 00002 00003 Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. 00004 00005 This program is free software; you can redistribute it and/or modify it 00006 under the terms of version 2 of the GNU General Public License as 00007 published by the Free Software Foundation. 00008 00009 This program is distributed in the hope that it would be useful, but 00010 WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00012 00013 Further, this software is distributed without any warranty that it is 00014 free of the rightful claim of any third person regarding infringement 00015 or the like. Any license provided herein, whether implied or 00016 otherwise, applies only to this software file. Patent licenses, if 00017 any, provided herein do not apply to combinations of this program with 00018 other software, or any other product whatsoever. 00019 00020 You should have received a copy of the GNU General Public License along 00021 with this program; if not, write the Free Software Foundation, Inc., 59 00022 Temple Place - Suite 330, Boston MA 02111-1307, USA. 00023 00024 Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, 00025 Mountain View, CA 94043, or: 00026 00027 http://www.sgi.com 00028 00029 For further information regarding this notice, see: 00030 00031 http://oss.sgi.com/projects/GenInfo/NoticeExplan 00032 00033 */ 00034 00035 00036 #ifndef MFMC_H_INCLUDED 00037 #define MFMC_H_INCLUDED "mfmc.h" 00038 /* ====================================================================== 00039 * 00040 * Module: mfmc.h 00041 * $Revision: 1.2 $ 00042 * $Date: 02/11/07 23:41:37-00:00 $ 00043 * $Author: fchow@keyresearch.com $ 00044 * $Source: /scratch/mee/2.4-65/kpro64-pending/be/com/SCCS/s.mfmc.h $ 00045 * 00046 * Revision history: 00047 * 17-Jul-96 - Original version 00048 * 00049 * Description: 00050 * 00051 * This package provides a functional interface to a fast 00052 * implementation of one of the best practical algorithms to solve 00053 * maximum flow and minimum s-t cut problems. 00054 * 00055 * The algorithm works in the push-relabel framework of Goldberg, and 00056 * uses the maximum distance (i.e., highest level) node selection 00057 * strategy, along with global relabeling and gap relabeling 00058 * heuristics. This combination of techniques is the best known in 00059 * practice for a wide variety of classes of maximum flow problem 00060 * instances. 00061 * 00062 * The interface functions visible to users are divided into three 00063 * classes: setup, query, and other. 00064 * 00065 * Setup functions (mfmc_setup.c) 00066 * =============== 00067 * Setup functions are called by the user to describe the particular 00068 * flow/cut problem instance. 00069 * 00070 * MFMC_HANDLE MFMC_Init_problem(MEM_POOL *mem_pool, 00071 * BOOL trace, 00072 * INT32 n, 00073 * INT32 m, 00074 * INT32 n_sources, 00075 * INT32 n_sinks) 00076 * 00077 * Perform initialization to begin setting up a particular 00078 * problem instance, and return a handle that will refer to 00079 * the problem instance in subsequent MFMC interface function 00080 * calls. 00081 * 00082 * mem_pool - a pointer to a MEM_POOL from which the 00083 * MFMC package should allocate memory 00084 * required to solve the problem. 00085 * trace - (for future use) whether or not to print 00086 * tracing information during problem setup 00087 * and solution. Currently no tracing output 00088 * is implemented. 00089 * n - the number of nodes in the problem 00090 * instance. The nodes of the problem 00091 * instance will be referred to by integers 00092 * in the range [0 .. n-1]. 00093 * m - the number of arcs (directed edges) in the 00094 * problem instance. 00095 * n_sources - the number of source nodes in the problem 00096 * instance. This value must fall between 1 00097 * and n-1, inclusive. 00098 * n_sinks - the number of sink nodes in the problem 00099 * instance. This value must fall between 1 00100 * and n-1, inclusive. 00101 * 00102 * This routine returns NULL if and only if it is unable to 00103 * allocate some of the resources required to solve the 00104 * problem. At present, no MEM_POOL resources are allocated 00105 * by the MFMC package outside this function, but please 00106 * don't assume this will always be the case. 00107 * 00108 * MFMC_EC MFMC_Set_source(MFMC_HANDLE handle, 00109 * INT32 s) 00110 * 00111 * handle - the handle for a particular flow/cut problem 00112 * s - a source node in the problem referred to by 00113 * handle 00114 * 00115 * This routine tells the MFMC package that node s is a 00116 * source in the problem referred to by handle. 00117 * 00118 * Possible error returns: 00119 * MFMC_NO_ERROR - all is well 00120 * MFMC_S_T_OVERLAP - node s has already been mentioned 00121 * along with handle in a call to 00122 * MFMC_Set_source or MFMC_Set_sink. 00123 * 00124 * MFMC_EC MFMC_Set_sink(MFMC_HANDLE handle, 00125 * INT32 t) 00126 * 00127 * handle - the handle for a particular flow/cut problem 00128 * t - a sink node in the problem referred to by 00129 * handle 00130 * 00131 * This routine tells the MFMC package that node t is a sink 00132 * in the problem referred to by handle. 00133 * 00134 * Possible error returns: 00135 * same as for MFMC_Set_source 00136 * 00137 * MFMC_EC MFMC_Place_arc(MFMC_HANDLE handle, 00138 * INT32 tail, 00139 * INT32 head, 00140 * INT64 lower_cap, 00141 * INT64 upper_cap, 00142 * MFMC_ARC_HANDLE *arc_handle) 00143 * 00144 * Place an arc from node tail to node head; the arc has 00145 * forward capacity equal to upper_cap, and backward capacity 00146 * equal to -lower_cap. In a future refinement of the 00147 * implementation, if arc_handle is non-null MFMC_Place_arc 00148 * will store a unique identifier for the arc in *arc_handle 00149 * so it can be referred to later in query functions. 00150 * 00151 * handle - the handle for a particular flow/cut 00152 * problem 00153 * tail - the origin of the arc being placed 00154 * head - the destination of the arc being placed 00155 * lower_cap - lower bound on the flow through the arc; 00156 * in the present implementation this value 00157 * must be nonpositive 00158 * upper_cap - upper bound on the flow through the arc; 00159 * in the present implementation this value 00160 * must be nonnegative 00161 * arc_handle - if non-NULL, a pointer to where a future 00162 * implementation will store a unique 00163 * identifier for the placed arc; must be 00164 * NULL in the present implementation 00165 * 00166 * Possible error returns: 00167 * MFMC_NO_ERROR - all is well 00168 * MFMC_INFEASIBLE - upper_cap < lower_cap 00169 * MFMC_ZERO_INFEASIBLE - zero flow is infeasible; this 00170 * will not be an error in a 00171 * future version 00172 * MFMC_BAD_ARC_COUNT - more arcs have been placed than 00173 * were promised in the call to 00174 * MFMC_Init_problem 00175 * MFMC_NOT_IMPLEMENTED - arc_handle is non-NULL; arc 00176 * handles are not currently 00177 * implemented 00178 * 00179 * MFMC_EC MFMC_Solve_problem(MFMC_HANDLE handle) 00180 * 00181 * handle - the handle for a particular flow/cut problem 00182 * 00183 * This routine tells the MFMC package that the problem setup 00184 * phase is finished for handle, and that the package should 00185 * proceed with finding a max flow/min cut pair. 00186 * 00187 * Possible error returns: 00188 * MFMC_NO_ERROR - all is well 00189 * MFMC_UNSEEN_S_T - the number of sources or sinks 00190 * set via calls to MFMC_Set_source 00191 * and/or MFMC_Set_sink does not 00192 * match the number promised in the 00193 * call to MFMC_Init_problem 00194 * MFMC_BAD_ARC_COUNT - the number of arcs placed via 00195 * calls to MFMC_Place_arc does not 00196 * match the number promised in the 00197 * call to MFMC_Init_problem 00198 * 00199 * Query functions (mfmc_query.c) 00200 * =============== 00201 * Query functions are called by the user when a problem has been 00202 * solved and the user wants to learn details of the solution and/or 00203 * of the solution process. 00204 * 00205 * INT64 MFMC_Objective_value(MFMC_HANDLE handle) 00206 * 00207 * Returns the value of the minimum cut (equal to the value 00208 * of the maximum flow) in the problem referred to by handle. 00209 * 00210 * BOOL MFMC_Min_cut_lhs(MFMC_HANDLE handle, 00211 * INT32 i) 00212 * 00213 * Returns TRUE iff node i is on the left-hand (i.e., source) 00214 * side of the minimum cut found by the algorithm. 00215 * 00216 * INT64 MFMC_Max_flow_arc_flow(MFMC_HANDLE handle, 00217 * MFMC_ARC_HANDLE arc_handle) 00218 * 00219 * Returns the value of the flow on the arc specified by 00220 * arc_handle in the maximum flow found by the 00221 * algorithm. This function is not implemented yet, and 00222 * always asserts FALSE in the present version. 00223 * 00224 * MFMC_STATS *MFMC_Stats(MFMC_HANDLE handle) 00225 * 00226 * Returns a pointer to a structure describing statistics 00227 * collected during the process of solving the problem 00228 * referred to by handle. Typically these statistics count 00229 * either process time or the number of times particular 00230 * operations were executed. 00231 * 00232 * ====================================================================== 00233 */ 00234 #include "defs.h" 00235 #include "mempool.h" 00236 #include "errors.h" 00237 00238 typedef struct mfmc_handle *MFMC_HANDLE; 00239 typedef struct mfmc_arc *MFMC_ARC_HANDLE; 00240 00241 typedef struct mfmc_stats { 00242 INT32 n_push; 00243 INT32 n_rel; 00244 INT32 n_up; 00245 INT32 n_gap; 00246 INT32 n_gnode; 00247 float time; 00248 } MFMC_STATS; 00249 00250 typedef enum { 00251 MFMC_NO_ERROR, /* Everything OK so far. */ 00252 MFMC_S_T_OVERLAP, /* Source and sink sets intersect, or 00253 * some source/sink set twice. 00254 */ 00255 MFMC_INFEASIBLE, /* Upper capacity < lower capacity. */ 00256 MFMC_ZERO_INFEASIBLE, /* (Lower capacity > 0 or 00257 * upper capacity < 0). 00258 * Relax this restriction later? 00259 */ 00260 MFMC_UNSEEN_S_T, /* Promised number of sources/sinks 00261 * doesn't match the number actually 00262 * set. 00263 */ 00264 MFMC_BAD_ARC_COUNT, /* Promised number of arcs doesn't 00265 * match the number actually placed. 00266 */ 00267 MFMC_NOT_IMPLEMENTED /* User asked for something legitimate 00268 * that we're too stupid or lazy to do. 00269 */ 00270 } MFMC_EC; 00271 00272 #ifdef __cplusplus 00273 extern "C" { 00274 #endif 00275 00276 /* Setup interface functions */ 00277 00278 MFMC_HANDLE MFMC_Init_problem(MEM_POOL *, BOOL, INT32, INT32, 00279 INT32, INT32); 00280 MFMC_EC MFMC_Place_arc(MFMC_HANDLE, INT32, INT32, 00281 INT64, INT64, MFMC_ARC_HANDLE *); 00282 MFMC_EC MFMC_Set_source(MFMC_HANDLE, INT32); 00283 MFMC_EC MFMC_Set_sink(MFMC_HANDLE, INT32); 00284 MFMC_EC MFMC_Solve_problem(MFMC_HANDLE); 00285 00286 /* Query interface functions */ 00287 00288 extern BOOL MFMC_Min_cut_lhs(MFMC_HANDLE, INT32); 00289 #if 0 00290 /* --- NOT IMPLEMENTED YET --- */ 00291 extern INT64 MFMC_Max_flow_arc_flow(MFMC_HANDLE, MFMC_ARC_HANDLE); 00292 #else 00293 inline INT64 MFMC_Max_flow_arc_flow(MFMC_HANDLE h, MFMC_ARC_HANDLE ah) 00294 { 00295 FmtAssert(FALSE, ("MFMC_Max_flow_arc_flow: arc handles not implemented")); 00296 /*NOTREACHED*/ 00297 } 00298 #endif 00299 00300 INT64 00301 MFMC_Objective_value(MFMC_HANDLE); 00302 00303 /* Other interface functions */ 00304 extern char *MFMC_msgs[]; 00305 00306 inline void 00307 MFMC_Print_error(FILE *f, MFMC_EC err) 00308 { 00309 (void) fprintf(f, "%s\n", MFMC_msgs[err]); 00310 } 00311 00312 MFMC_STATS * 00313 MFMC_Stats(MFMC_HANDLE); 00314 00315 #ifdef __cplusplus 00316 } 00317 #endif 00318 #endif
1.5.6