ghc_tree_main.c

#include <stdlib.h>
#include <stdio.h>
#include "graph.h"


#define NO_MEM  fprintf(stderr,"Unable to allocate memory\n")
#define LEPS 1e-8

      /* protoype definitions */

float user_time (); 
BOOL ghc_tree (graph *);                  


void print_time (float t)
{
  long t_sec, t_hun; 
  float t1;

  if (t < 1.0)
    printf ("0'%d [s'10ms]\n", (long) (t * 100.0));
  else
   { t1 = t * 100.0;
     t_sec = (long) t;
     t_hun = (long) t1 - (long) 100 * t_sec;
     printf ("%d'%d [s'10ms]\n", t_sec, t_hun);
   }
}


BOOL alloc_graph (long n, long m, graph **gr)
{
  if ((*gr = (graph *) malloc (sizeof (graph))) == (graph *) 0)
    return (FALSE);
  if (((*gr)->nodes = (node *) malloc (n * sizeof (node))) 
      == (node *) 0)
   { free (*gr);
     return (FALSE);
   }
  if (((*gr)->edges = (edge *) malloc (2L * m * sizeof (edge)))
      == (edge *) 0)
   { free (*gr);
     free ((*gr)->nodes);
     return (FALSE);
   }
  return (TRUE);
}


void dealloc_graph (graph *gr)
{
  free (gr->nodes);
  free (gr->edges);
  free (gr);
}


char skip_comment (FILE *fd)
{ 
  char any;
  char *c;
  static char buf[256];

  do { c = fgets (buf, 256, fd);
       fscanf (fd, "%c", &any);
     } 
  while (any == 'c');
  return (any);
}


graph *get_graph (FILE *fd) 
{
  long n, m, m0, i, j, nod1, nod2;
  double cap;
  node *nptr, *nptr1, *nptr2;
  edge *eptr1, *eptr2;
  graph *gr;
  char inp[4], any;

  /* Scans input file and constructs internal representation
     of graph.

     Undirected edges are represented by pairs of edge desrip-
     tors associated to incident nodes, the incidence list of 
     a node is represented as a one way linked list of edge de-
     scriptors each of which contains a pointer to an adjacent
     node and a "back" pointer to the descriptor of the other
     edge in the pair contained in the incidence list of the
     adjacent node. 
  */

  fscanf (fd, "%c", &any);
  if (any == 'c')
    any = skip_comment (fd);
  if (any != 'p')
   { fprintf (stderr, "Problem line missing in input file\n");
     exit (1);
   }
  fscanf (fd, "%s", inp);  
  if (inp[0] != 'g' || inp[1] != 'h' ||
      inp[2] != 'c' || inp[3] != 't' )
   { fprintf (stderr,
              "problem in input file is not Gomory/Gu cut tree\n");
     return ((graph *) 0);
   }

  fscanf (fd, "%ld", &n);
  fscanf (fd, "%ld", &m);

  if (! alloc_graph (n, m, &gr))
   { NO_MEM;
     return ((graph *) 0);
   }

  gr->n_nodes = n;
  gr->n_edges0 = m;
  m0 = 0;

  //printf ("Number of nodes and edges: %d, %d\n", n, m);

  for (i = n, nptr = &(gr->nodes[n-1]); i > 0L; --nptr, --i)
    { nptr->id = i;
      nptr->first_edge = NILE;
    }

  eptr1 = &(gr->edges[0L]);
  eptr2 = &(gr->edges[m]);
  for (j = 0L; j < m; j++)
    { if (fscanf (fd, "%s %ld %ld %lg", inp, &nod1, &nod2, &cap)
          == EOF)
       { fprintf (stderr,
                  "EOF reached in input file, %d edges read\n", j);
         dealloc_graph (gr);
         return ((graph *) 0);
       }
      if (inp[0] != 'e')
       { printf ("syntax error - edge descriptor line expected\n");
         dealloc_graph (gr);
         return ((graph *) 0);
       }
      if (nod1 < 1 || nod1 > n)
       { fprintf (stderr,
                  "invalid node id %d in input graph\n", nod1);
         dealloc_graph (gr);
         return ((graph *) 0);
       }
      if (nod2 < 1 || nod2 > n)
       { fprintf (stderr, 
                  "invalid node id %d in input graph\n", nod2);
         dealloc_graph (gr);
         return ((graph *) 0);
       }
      if (nod1 == nod2)
       { fprintf (stderr,
                  "loop on node %d in input graph\n", nod1);
         dealloc_graph (gr);
         return ((graph *) 0);
       }
      if (cap > EPS)
       { /* put edge into internal graph representation */
         --nod1;
         --nod2;
         nptr1 = &(gr->nodes[nod1]);
         nptr2 = &(gr->nodes[nod2]);
         eptr1->adjac = nptr2;
         eptr2->adjac = nptr1;
         eptr1->cap = cap;
         eptr2->cap = cap;
         eptr1->back = eptr2;
         eptr2->back = eptr1;
         if (nptr1->first_edge == NILE)
          { nptr1->first_edge = eptr1;
            eptr1->next = NILE;
          }
         else
          { eptr1->next = nptr1->first_edge;
            nptr1->first_edge = eptr1;
          }
         if (nptr2->first_edge == NILE)
          { nptr2->first_edge = eptr2;
            eptr2->next = NILE;
          }
         else
          { eptr2->next = nptr2->first_edge;
            nptr2->first_edge = eptr2;
          }
         ++eptr1;
         ++eptr2;
       }
      else
       { /* zero capacity edge not put into edge lists 
            of its incident nodes, just counted        */
         m0++; 
       }
      gr->n_edges = m - m0;
    }
  return (gr);
}

/*
void updateCapacities(graph* gr; double* cap)
{
   edge *eptr1, *eptr2;
   eptr1 = &(gr->edges[0L]);
   eptr2 = &(gr->edges[m]);

   for (int j = 0; j < G.number_of_edges(); j++) {
      eptr1->cap = cap[j];
      eptr2->cap = cap[j];
      ++eptr1;
      ++eptr2;
   }

   return;
}  
*/

void print_tree (graph *gr)
{
  node *nptr; 

  printf ("Gomory/Hu cut tree:\n");
  printf ("root  1\n");
  for (nptr = &(gr->nodes[gr->n_nodes-1L]);
                  nptr >= &(gr->nodes[1L]); nptr--)
     printf ("e  %d  %d    %e\n",
             nptr->id, nptr->parent->id, nptr->mincap);
}  

void compute_tree (int n, int m, int* os, int* ot, double* oc, int* cts, int* ctt, double* ctc)
{
  long m0, i, j, nod1, nod2;
  double cap;
  node *nptr, *nptr1, *nptr2;
  edge *eptr1, *eptr2;
  graph *gr;

  /* Scans input data and constructs internal representation
     of graph.

     Undirected edges are represented by pairs of edge desrip-
     tors associated to incident nodes, the incidence list of 
     a node is represented as a one way linked list of edge de-
     scriptors each of which contains a pointer to an adjacent
     node and a "back" pointer to the descriptor of the other
     edge in the pair contained in the incidence list of the
     adjacent node. 
  */

  if (! alloc_graph (n, m, &gr))
   { NO_MEM;
     exit(1);
   }

  gr->n_nodes = n;
  gr->n_edges0 = m;
  m0 = 0;

  //printf ("CUT_TREE:\nNumber of nodes and edges: %d, %d\n", n, m);

  for (i = n, nptr = &(gr->nodes[n-1]); i > 0; --nptr, --i)
    { nptr->id = i;
      nptr->first_edge = NILE;
    }

  eptr1 = &(gr->edges[0L]);
  eptr2 = &(gr->edges[m]);
  /* insert the edges into the graph 
   * node numbering is expected to start with 1! */
  for (j = 0; j < m; j++)
    { 
       nod1 = os[j];
       nod2 = ot[j];
       cap = oc[j];
      if (nod1 == nod2)
       { fprintf (stderr,
                  "loop on node %d in input graph\n", nod1);
         dealloc_graph (gr);
         exit(1);
       }
      if (cap > EPS)
       { /* put edge into internal graph representation */
         --nod1;
         --nod2;
         nptr1 = &(gr->nodes[nod1]);
         nptr2 = &(gr->nodes[nod2]);
         eptr1->adjac = nptr2;
         eptr2->adjac = nptr1;
         eptr1->cap = cap;
         eptr2->cap = cap;
         eptr1->back = eptr2;
         eptr2->back = eptr1;
         if (nptr1->first_edge == NILE)
          { nptr1->first_edge = eptr1;
            eptr1->next = NILE;
          }
         else
          { eptr1->next = nptr1->first_edge;
            nptr1->first_edge = eptr1;
          }
         if (nptr2->first_edge == NILE)
          { nptr2->first_edge = eptr2;
            eptr2->next = NILE;
          }
         else
          { eptr2->next = nptr2->first_edge;
            nptr2->first_edge = eptr2;
          }
         ++eptr1;
         ++eptr2;
       }
      else
       { /* zero capacity edge not put into edge lists 
            of its incident nodes, just counted        */
         m0++; 
       }
      gr->n_edges = m - m0;
    }

  /* compute the cut tree */
  ghc_tree (gr);

  /* initialize the return data */
  int oi = 0;

  for (nptr = &(gr->nodes[gr->n_nodes-1L]);
                  nptr >= &(gr->nodes[1L]); nptr--) {
             cts[oi] = nptr->id;
             ctt[oi] = nptr->parent->id;
             ctc[oi] =  nptr->mincap;
             oi++;
  }
  dealloc_graph(gr);

  if( oi != n-1 ) {
     printf("Wrong number of edges in cut tree!\n");
     exit(1);
  }

  return;
}  


#ifdef GCT_MAIN
void main (argc, argv)
  int argc;
  char **argv;
{
  FILE *fd;
  graph *gr;
  long n1, n2;
  float t0, t1, t2;

  /* Main programm for Gomory/Hu cut tree function   
     
     Input format is compatible to DIMACS, nodes and arcs
     are asssumed to be numbered 1 to n and m respectively. 
  */
                    
  if  (argc != 2)
   { fprintf (stderr, "ghc_tree: call parameter missing\n");
     fprintf (stderr,
              "usage:  ghc_tree <input filename>\n");
     exit (1);
   }
  t0 = user_time (); 
  if ((fd = fopen (argv[1], "r")) == NULL)
   { fprintf(stderr, "Unable to open %s\n", argv[1]);
     exit (1);
   }

  gr = get_graph (fd);
  if (gr == (graph *) 0)
   { close (fd); 
     exit (1);
   }
  close (fd);  

  t1 = user_time ();

  if (ghc_tree (gr))
   { t2 = user_time (); 
     print_tree (gr);
     printf ("File input and initialization time: ");
     print_time (t1 - t0);
     printf ("Total execution time: ");
     print_time (t2 - t0);
   }
  dealloc_graph (gr);
}
#endif 

---