eg_push_relabel.ex.c

This is a complete example for the min-cut max-flow problem using the push/relabel implementation offered in EGalgPR.

/* EGlib "Efficient General Library" provides some basic structures and
 * algorithms commons in many optimization algorithms.
 *
 * Copyright (C) 2005 Daniel Espinoza and Marcos Goycoolea.
 * 
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
 * */
/** @file
 * @ingroup EGalgPushRelabel */
/** @addtogroup EGalgPushRelabel */
/** @{ */
#include "eg_push_relabel.h"
#include "eg_timer.h"
#include <stdio.h>
/* ========================================================================= */
/** @brief display usage of this program */
static inline void pr_usage (char **argv)
{
  fprintf (stderr, "Usage: %s input_file\n", argv[0]);
}

/* ========================================================================= */
/** @brief 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. */
int main (int argc,
          char **argv)
{
  int rval = 0;
  FILE *in_file = 0;
  unsigned int n_nodes = 0;
  unsigned int n_edges = 0;
  unsigned int register i;
  unsigned int head,
    tail;
  EGlpNum_t cap;
  EGtimer_t cut_timer;
  EGalgPRgraph_t G;
  EGalgPRnode_t *nodes = 0,
   *node_pt;
  EGalgPRedge_t *edges = 0;
  EGeList_t *n_it;
  char l_str[1024];
  EGtimerReset (&cut_timer);
  EGlpNumStart ();
  EGalgPRgraphInit (&G);
  EGlpNumInitVar (cap);
  /* test we have an input file */
  if (argc < 2)
  {
    pr_usage (argv);
    rval = 1;
    goto CLEANUP;
  }
  in_file = fopen (argv[1], "r");
  if (!in_file)
  {
    fprintf (stderr, "Can't open file %s\n", argv[1]);
    pr_usage (argv);
    rval = 1;
    goto CLEANUP;
  }
  /* now we start reading the file */
  fscanf (in_file, "%u %u", &n_nodes, &n_edges);
  if (!n_nodes || !n_edges)
  {
    fprintf (stderr, "Problem is trivial with %u nodes and %u edges\n",
             n_nodes, n_edges);
    goto CLEANUP;
  }
  fprintf (stderr, "Reading graph on %u nodes and %u edges...", n_nodes,
           n_edges);
  nodes = EGsMalloc (EGalgPRnode_t, n_nodes);
  edges = EGsMalloc (EGalgPRedge_t, n_edges);
  for (i = n_nodes; i--;)
  {
    EGalgPRnodeInit (nodes + i);
    EGeDgraphAddNode (&(G.G), &(nodes[i].v));
  }
  for (i = n_edges; i--;)
  {
    EGalgPRedgeInit (edges + i);
    fscanf (in_file, "%u %u %s", &head, &tail, l_str);
    EGlpNumReadStr (cap, l_str);
    EGeDgraphAddEdge (&(G.G),
                      &(nodes[head].v), &(nodes[tail].v), &(edges[i].fw.e));
    EGeDgraphAddEdge (&(G.G),
                      &(nodes[tail].v), &(nodes[head].v), &(edges[i].bw.e));
    EGlpNumCopy (edges[i].fw.u, cap);
    EGlpNumCopy (edges[i].bw.u, cap);
  }
  fclose (in_file);
  in_file = 0;
  fprintf (stderr, "...done\nComputing Min Cut 0 %u:", n_nodes >> 1);

  /* now we call the min cut algorithm */
  EGtimerStart (&cut_timer);
  rval = EGalgPRminSTcut (&G, nodes, nodes + (n_nodes >> 1));
  EGtimerStop (&cut_timer);
  fprintf (stderr, "...done in %lf seconds\n", cut_timer.time);
  /* now display all nodes in the cut */
#if 1
  fprintf (stderr, "Minimum Cut: ");
  for (n_it = G.G.nodes.next; n_it != &(G.G.nodes); n_it = n_it->next)
  {
    node_pt = EGcontainerOf (n_it, EGalgPRnode_t, v.node_cn);
    if (node_pt->d < G.G.n_nodes)
      fprintf (stderr, "%u ", (unsigned) (node_pt - nodes));
  }
  fprintf (stderr, "\n");
#endif
  fprintf (stderr, "Computing max flow...");
  EGtimerReset (&cut_timer);
  EGtimerStart (&cut_timer);
  rval = EGalgPRmaxSTflow (&G, nodes, nodes + (n_nodes >> 1));
  EGtimerStop (&cut_timer);
  fprintf (stderr, "...done in %lf seconds\n", cut_timer.time);
  /* now we print the value of the cut */
  fprintf (stderr, "Minimum Cut Capacity %lf\n",
           EGlpNumToLf (nodes[n_nodes >> 1].e));
  /* check the solution */
  rval = EGalgPRoptimalityTest (&G, nodes, nodes + (n_nodes >> 1), &cap);
  TESTG (rval, CLEANUP, "Worst error %lg, standard expected error %lg,"
         " number of errors %d", EGlpNumToLf (cap), EGlpNumToLf (epsLpNum),
         rval);
  CHECKRVALG (rval, CLEANUP);

  /* ending */
CLEANUP:
  if (in_file)
    fclose (in_file);
  EGlpNumClearVar (cap);
  EGalgPRgraphClear (&G);
  for (i = n_nodes; i--;)
    EGalgPRnodeClear (nodes + i);
  for (i = n_edges; i--;)
    EGalgPRedgeClear (edges + i);
  EGfree (nodes);
  EGfree (edges);
  EGlpNumExit ();
  EGalgPRprofile;
  return rval;
}

/* ========================================================================= */
/** @} */

---