eg_dgraph.ex.c

Go to the documentation of this file.

/* 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 
 * */
/*****************************************************************************
 *                                                                           *
 * This program reads a weighted graph from a file and displays it on        * 
 * screen.                                                                   * 
 *                                                                           * 
 * The input file format is:                                                 * 
 *                                                                           * 
 * nnodes nedges                                                             * 
 * head0 tail0 weight0                                                       * 
 * head1 tail1 weight1                                                       * 
 * head2 tail2 weight2                                                       * 
 *   ...                                                                     * 
 * headn tailn weightn                                                       * 
 *                                                                           * 
 *****************************************************************************/

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

#ifdef LINUX
#include <getopt.h>
#endif

#include "eg_mempool.h"
#include "eg_dgraph.h"

void usage (char *program)
{
  fprintf (stdout, "Usage: %s [options]\n", program);
  fprintf (stdout, "Options:\n");
  fprintf (stdout, "     -f n   file name.\n");
}

int parseargs (int argc,
               char **argv,
               char **file_name)
{

  int c;

  while ((c = getopt (argc, argv, "f:")) != EOF)
  {
    switch (c)
    {
    case 'f':
      *file_name = optarg;
      break;
    default:
      usage (argv[0]);
      return 1;
    }
  }

  /* reporting the options */
  fprintf (stdout, "Parsed Options:\n");
  fprintf (stdout, "input         : %s\n", *file_name);

  return 0;

}

int main (int argc,
          char **argv)
{

  int rval;
  unsigned int i;
  char *file_name = 0;
  FILE *file;

  unsigned int nedges,
    nnodes;
  unsigned int *edges = 0;

  double *weight = 0;

  EGmemPool_t *mem = 0;
  EGdGraph_t *G = 0;
  EGdGraphNode_t **nodes = 0;

  /* Parse command line input to get 'file name' and 'd'. */
  rval = parseargs (argc, argv, &file_name);
  CHECKRVAL (rval);

  /* Read the objects to sort from the file */
  file = fopen (file_name, "r");
  TEST (!file, "unable to open file %s", file_name);

  fscanf (file, "%u %u", &nnodes, &nedges);

  edges = (unsigned int *) malloc (sizeof (unsigned int) * 2 * nedges);
  weight = (double *) malloc (sizeof (double) * nedges);

  for (i = 0; i < nedges; i++)
  {
    fscanf (file, "%u %u %lf", &edges[2 * i], &edges[2 * i + 1], &weight[i]);
    TEST (edges[2 * i] > (nnodes - 1), "Edge %u (head) out of bounds", i);
    TEST (edges[2 * i + 1] > (nnodes - 1), "Edge %u (tail) out of bounds", i);
  }

  fclose (file);

  /* Create a new memory pool and heap */
  mem = EGnewMemPool (100, EGmemPoolNewSize, EGmemPoolNewSize (1));

  /* Create a new di-graph */
  G = EGnewDGraph (mem);

  /* Allocate space for the node objects */
  nodes =
    (EGdGraphNode_t **) EGmemPoolMalloc (mem,
                                         sizeof (EGdGraphNode_t *) * nnodes);

  /* Add the nodes into the graph */
  fprintf (stderr, "\nAdding Nodes... ");
  for (i = 0; i < nnodes; i++)
    nodes[i] = EGdGraphAddNode (G, 0);

  /* Add the edges into the graph */
  fprintf (stderr, "done.\n\nAdding Edges... ");
  for (i = 0; i < nedges; i++)
    EGdGraphAddEdge (G, &weight[i], nodes[edges[2 * i]],
                     nodes[edges[2 * i + 1]]);

  fprintf (stderr, "done.\n\n");

  /* Liberating allocated memory */

  free (edges);
  free (weight);
  EGmemPoolFree (nodes, sizeof (EGdGraphNode_t *) * nnodes, mem);
  EGdGraphClear (G, 0, 0, 0);
  EGfreeDGraph (G);
  EGfreeMemPool (mem);

  return 0;

}

---