parser_r.c

17个最短路径源代码。代码效率高

/********************************************************************/
/*                                                                  */
/*  parse (...) :                                                   */
/*       1. Reads shortest path problem in extended DIMACS format.  */
/*       2. Prepares internal data representation #2.               */
/*                                                                  */
/********************************************************************/
       
/* files to be included: */


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


/*
  #include "types_bf_r.h"

   types: 'arc' and 'node' must be predefined

   type    arc    must contain fields 'len' and 'head': 

   typedef 
     struct arc_st
       {
         long            len;      .. length of the arc 
         struct node_st *tail;     .. tail node of the arc
         struct node_st *head;     .. head node of the arc
         struct arc_st  *next_t;   .. next arc with the same head 

         ....................
       } 
   arc;

   type    arc    must contain the field 'first': 

   typedef
     struct node_st
       {
          arc_st        *first;    ..  first outgoing arc 
          arc_st        *first_in; ..  first incoming arc
          ....................
       }
    node;
*/

/* ----------------------------------------------------------------- */

int parse( n_ad, m_ad, nodes_ad, arcs_ad, 
           source_ad, node_min_ad, problem_name )

/* all parameters are output */
long    *n_ad;                 /* address of the number of nodes */
long    *m_ad;                 /* address of the number of arcs */
node    **nodes_ad;            /* address of the array of nodes */
arc     **arcs_ad;             /* address of the array of arcs */
node    **source_ad;           /* address of the pointer to the source */
long    *node_min_ad;          /* address of the minimal node */
char    *problem_name;         /* pointer to the string with problem name */

{

#define MAXLINE       100	/* max line length in the input file */
#define ARC_FIELDS      3	/* no of fields in arc input  */
#define P_FIELDS        3       /* no of fields in problem line */
#define PROBLEM_TYPE "sp"       /* name of problem type*/
#define DEFAULT_NAME "unknown"  /* default name of the problem */


long    n,                      /* internal number of nodes */
        node_min,               /* minimal no of node  */
        node_max,               /* maximal no of nodes */
       *arc_first,              /* internal array for holding
                                     - node degree
                                     - position of the first outgoing arc */
        source,                 /* no of source */
        /* temporary variables carrying no of nodes */
        head, tail, i, source2;

long    m;                      /* internal number of arcs */
      
node    *nodes,                 /* pointer to the node structure */
        *node_i,
        *head_p,
        *tail_p;

arc     *arcs,                  /* pointer to the arc structure */
        *arc_current,
        *arc_new,
        *last,
        *arc_last;

long    length;                 /* length of the current arc */

long    no_lines=0,             /* no of current input line */
        no_plines=0,            /* no of problem-lines */
        no_tlines=0,            /* no of title(problem name)-lines */
        no_nlines=0,            /* no of node(source)-lines */
        no_alines=0;            /* no of arc-lines */

char    in_line[MAXLINE],       /* for reading input line */
        pr_type[3];             /* for reading type of the problem */

int     k,                      /* temporary */
        err_no;                 /* no of detected error */

/* -------------- error numbers & error messages ---------------- */
#define EN1   0
#define EN2   1
#define EN3   2
#define EN4   3
#define EN6   4
#define EN10  5
#define EN7   6
#define EN8   7
#define EN9   8
#define EN11  9
#define EN12 10
#define EN13 11
#define EN14 12
#define EN16 13
#define EN15 14
#define EN17 15
#define EN18 16
#define EN21 17
#define EN19 18
#define EN20 19
#define EN22 20

static char *err_message[] = 
  { 
/* 0*/    "more than one problem line.",
/* 1*/    "wrong number of parameters in the problem line.",
/* 2*/    "it is not a Shortest Path problem line.",
/* 3*/    "bad value of a parameter in the problem line.",
/* 4*/    "can't obtain enough memory to solve this problem.",
/* 5*/    "more than one line with the problem name.",
/* 6*/    "can't read problem name.",
/* 7*/    "problem description must be before source description.",
/* 8*/    "this parser doesn't support multiply sources.",
/* 9*/    "wrong number of parameters in the source line.",
/*10*/    "wrong value of parameters in the source line.",
/*11*/    "this parser doesn't support destination description.",
/*12*/    "source description must be before arc descriptions.",
/*13*/    "too many arcs in the input.",
/*14*/    "wrong number of parameters in the arc line.",
/*15*/    "wrong value of parameters in the arc line.",
/*16*/    "unknown line type in the input.",
/*17*/    "reading error.",
/*18*/    "not enough arcs in the input.",
/*19*/    "source doesn't have output arcs.",
/*20*/    "can't read anything from the input file."
  };
/* --------------------------------------------------------------- */

/* The main loop:
        -  reads the line of the input,
        -  analises its type,
        -  checks correctness of parameters,
        -  puts data to the arrays,
        -  does service functions
*/

while ( gets ( in_line ) != NULL )
  {
  no_lines ++;


  switch (in_line[0])
    {
      case 'c':                  /* skip lines with comments */
      case '\n':                 /* skip empty lines   */
      case '\0':                 /* skip empty lines at the end of file */
                break;

      case 'p':                  /* problem description      */
                if ( no_plines > 0 )
                   /* more than one problem line */
                   { err_no = EN1 ; goto error; }

                no_plines = 1;
   
                if (
        /* reading problem line: type of problem, no of nodes, no of arcs */
                    sscanf ( in_line, "%*c %2s %ld %ld", pr_type, &n, &m )
                != P_FIELDS
                   )
		    /*wrong number of parameters in the problem line*/
		    { err_no = EN2; goto error; }

                if ( strcmp ( pr_type, PROBLEM_TYPE ) )
		    /*wrong problem type*/
		    { err_no = EN3; goto error; }

                if ( n <= 0  || m <= 0 )
		    /*wrong value of no of arcs or nodes*/
		    { err_no = EN4; goto error; }

        /* allocating memory for  'nodes', 'arcs'  and internal arrays */
                nodes    = (node*) calloc ( n+2, sizeof(node) );
		arcs     = (arc*)  calloc ( m+1, sizeof(arc) );
		arc_first= (long*) calloc ( n+2, sizeof(long) );
                /* arc_first [ 0 .. n+1 ] = 0 - initialized by calloc */

                if ( nodes == NULL || arcs == NULL || 
                     arc_first == NULL )
                    /* memory is not allocated */
		    { err_no = EN6; goto error; }
		     
		/* setting pointer to the current arc */
		arc_current = arcs;
                break;

      case 't':                  /* name of the problem  */
                if ( no_tlines )
                   /* more than one name of the problem */
                   { err_no = EN10 ; goto error; }

                no_tlines = 1;
   
                if (
                /* reading problem name */
	        sscanf ( in_line, "%*c %30s", problem_name )
                != 1
                   )
                /* t-line doesn't contain problem name */
		    { err_no = EN7; goto error; }

                break;

      case 'n':		         /* source(s) description */
		if ( no_plines == 0 )
                  /* there was not problem line above */
                  { err_no = EN8; goto error; }

		if ( no_nlines != 0)
                  /* more than one node (source) line */
                  { err_no = EN9; goto error; }

		no_nlines = 1;   
		
                /* reading source */