eg_push_relabel.ex.c

Go to the documentation of this file.
00001 /* EGlib "Efficient General Library" provides some basic structures and
00002  * algorithms commons in many optimization algorithms.
00003  *
00004  * Copyright (C) 2005 Daniel Espinoza and Marcos Goycoolea.
00005  * 
00006  * This library is free software; you can redistribute it and/or modify it
00007  * under the terms of the GNU Lesser General Public License as published by the
00008  * Free Software Foundation; either version 2.1 of the License, or (at your
00009  * option) any later version.
00010  *
00011  * This library is distributed in the hope that it will be useful, but 
00012  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
00013  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
00014  * License for more details.
00015  *
00016  * You should have received a copy of the GNU Lesser General Public License
00017  * along with this library; if not, write to the Free Software Foundation,
00018  * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
00019  * */
00020 /** @file
00021  * @ingroup EGalgPushRelabel */
00022 /** @addtogroup EGalgPushRelabel */
00023 /** @{ */
00024 #include "EGlib.h"
00025 /* ========================================================================= */
00026 /** @brief display usage of this program */
00027 static inline void pr_usage (char **argv)
00028 {
00029   fprintf (stderr, "Usage: %s input_file\n", argv[0]);
00030 }
00031 
00032 /* ========================================================================= */
00033 /** @brief example of usage of the Preflow-Push algorithm as implemented in
00034  * (EGalgPushRelabel).
00035  * 
00036  * We read a file from the input whose two first numbers are the number of nodes
00037  * and edges (we assume that the graph is undirected ), and then a 3-tupla with
00038  * head tail capacity. we use the last field (capacity) as the capacity of the
00039  * algorithm, and compute the shortest path from node 0 to node 1. */
00040 int main (int argc,
00041           char **argv)
00042 {
00043   int rval = 0;
00044   EGioFile_t *in_file = 0;
00045   unsigned int n_nodes = 0;
00046   unsigned int n_edges = 0;
00047   register unsigned int i;
00048   unsigned int head,
00049     tail;
00050   EGlpNum_t cap;
00051   EGtimer_t cut_timer;
00052   EGalgPRgraph_t G;
00053   EGalgPRnode_t *nodes = 0/*,
00054    *node_pt*/;
00055   EGalgPRedge_t *edges = 0;
00056   /*EGeList_t *n_it;*/
00057   char l_str[1024];
00058   char*l_argv[128];
00059   int l_argc;
00060   EGlib_info();
00061   EGlib_version();
00062   EGlpNumStart();
00063   /* set signal and limits */
00064   EGsigSet(rval,CLEANUP);
00065   EGsetLimits(3600.0,4294967295UL);
00066   EGtimerReset (&cut_timer);
00067   EGalgPRgraphInit (&G);
00068   EGlpNumInitVar (cap);
00069   /* test we have an input file */
00070   if (argc < 2)
00071   {
00072     pr_usage (argv);
00073     rval = 1;
00074     goto CLEANUP;
00075   }
00076   in_file = EGioOpen (argv[1], "r");
00077   if (!in_file)
00078   {
00079     fprintf (stderr, "Can't open file %s\n", argv[1]);
00080     pr_usage (argv);
00081     rval = 1;
00082     goto CLEANUP;
00083   }
00084   /* now we start reading the file */
00085   EGioGets(l_str,1024,in_file);
00086   EGioNParse(l_str,128," ","%#",&l_argc,l_argv);
00087   TESTG((rval=(l_argc!=2)),CLEANUP,"Expected two tokens, but found %d",l_argc);
00088   n_nodes = (unsigned) atoi(l_argv[0]);
00089   n_edges = (unsigned) atoi(l_argv[1]);
00090   if (!n_nodes || !n_edges)
00091   {
00092     fprintf (stderr, "Problem is trivial with %u nodes and %u edges\n",
00093              n_nodes, n_edges);
00094     goto CLEANUP;
00095   }
00096   fprintf (stderr, "Reading graph on %u nodes and %u edges...", n_nodes,
00097            n_edges);
00098   nodes = EGsMalloc (EGalgPRnode_t, n_nodes);
00099   edges = EGsMalloc (EGalgPRedge_t, n_edges);
00100   for (i = n_nodes; i--;)
00101   {
00102     EGalgPRnodeInit (nodes + i);
00103     EGeDgraphAddNode (&(G.G), &(nodes[i].v));
00104   }
00105   for (i = n_edges; i--;)
00106   {
00107     EGalgPRedgeInit (edges + i);
00108     EGioGets(l_str,1024,in_file);
00109     EGioNParse(l_str,128," ","%#",&l_argc,l_argv);
00110     TESTG((rval=(l_argc!=3)),CLEANUP,"Expected three tokens, but found %d",l_argc);
00111     head = atoi(l_argv[0]);
00112     tail = atoi(l_argv[1]);
00113     EGlpNumReadStr (cap, l_argv[2]);
00114     EGeDgraphAddEdge (&(G.G),
00115                       &(nodes[head].v), &(nodes[tail].v), &(edges[i].fw.e));
00116     EGeDgraphAddEdge (&(G.G),
00117                       &(nodes[tail].v), &(nodes[head].v), &(edges[i].bw.e));
00118     EGlpNumCopy (edges[i].fw.u, cap);
00119     EGlpNumCopy (edges[i].bw.u, cap);
00120   }
00121   EGioClose(in_file);
00122   in_file = 0;
00123   fprintf (stderr, "...done\nComputing Min Cut 0 %u:", n_nodes >> 1);
00124 
00125   /* now we call the min cut algorithm */
00126   EGtimerStart (&cut_timer);
00127   rval = EGalgPRminSTcut (&G, nodes, nodes + (n_nodes >> 1));
00128   EGtimerStop (&cut_timer);
00129   fprintf (stderr, "...done in %lf seconds\n", cut_timer.time);
00130   /* now display all nodes in the cut */
00131 #if 0
00132   fprintf (stderr, "Minimum Cut: ");
00133   for (n_it = G.G.nodes.next; n_it != &(G.G.nodes); n_it = n_it->next)
00134   {
00135     node_pt = EGcontainerOf (n_it, EGalgPRnode_t, v.node_cn);
00136     if (node_pt->d < G.G.n_nodes)
00137       fprintf (stderr, "%u ", (unsigned) (node_pt - nodes));
00138   }
00139   fprintf (stderr, "\n");
00140 #endif
00141   fprintf (stderr, "Computing max flow...");
00142   EGtimerReset (&cut_timer);
00143   EGtimerStart (&cut_timer);
00144   rval = EGalgPRmaxSTflow (&G, nodes, nodes + (n_nodes >> 1));
00145   EGtimerStop (&cut_timer);
00146   fprintf (stderr, "...done in %lf seconds\n", cut_timer.time);
00147   /* now we print the value of the cut */
00148   fprintf (stderr, "Minimum Cut Capacity %lf\n",
00149            EGlpNumToLf (nodes[n_nodes >> 1].e));
00150   /* check the solution */
00151   rval = EGalgPRoptimalityTest (&G, nodes, nodes + (n_nodes >> 1), &cap);
00152   TESTG (rval, CLEANUP, "Worst error %lg, standard expected error %lg,"
00153          " number of errors %d", EGlpNumToLf (cap), EGlpNumToLf (epsLpNum),
00154          rval);
00155   CHECKRVALG (rval, CLEANUP);
00156 
00157   /* ending */
00158 CLEANUP:
00159   if (in_file) EGioClose (in_file);
00160   EGlpNumClearVar (cap);
00161   EGalgPRgraphClear (&G);
00162   for (i = n_nodes; i--;)
00163     EGalgPRnodeClear (nodes + i);
00164   for (i = n_edges; i--;)
00165     EGalgPRedgeClear (edges + i);
00166   EGfree (nodes);
00167   EGfree (edges);
00168   EGalgPRprofile();
00169   EGlpNumClear();
00170   return rval;
00171 }
00172 
00173 /* ========================================================================= */
00174 /** @} */